src/nm-multi-index.c

   1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */
   2 /* NetworkManager -- Network link manager
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Copyright (C) 2015 Red Hat, Inc.
  19  */
  20
  21 #include "nm-default.h"
  22
  23 #include "nm-multi-index.h"
  24
  25 #include <string.h>
  26
  27 struct NMMultiIndex {
  28         NMMultiIndexFuncEqual equal_fcn;
  29         NMMultiIndexFuncClone clone_fcn;
  30         GHashTable *hash;
  31 };
  32
  33 typedef struct {
  34         /* when storing the first item for a multi-index id, we don't yet create
  35          * the hashtable @index. Instead we store it inplace to @value0. Note that
  36          * &values_data->value0 is a NULL terminated array with one item that is
  37          * suitable to be returned directly from nm_multi_index_lookup(). */
  38         union {
  39                 gpointer value0;
  40                 gpointer *values;
  41         };
  42         GHashTable *index;
  43 } ValuesData;
  44
  45 /******************************************************************************************/
  46
  47 static void
  48 _values_data_destroy (ValuesData *values_data)
  49 {
  50         if (values_data->index) {
  51                 g_free (values_data->values);
  52                 g_hash_table_unref (values_data->index);
  53         }
  54         g_slice_free (ValuesData, values_data);
  55 }
  56
  57 static gboolean
  58 _values_data_contains (ValuesData *values_data, gconstpointer value)
  59 {
  60         return values_data->index
  61                ? g_hash_table_contains (values_data->index, value)
  62                : value == values_data->value0;
  63 }
  64
  65 static void
  66 _values_data_get_data (ValuesData *values_data,
  67                        void *const**out_data,
  68                        guint *out_len)
  69 {
  70         guint i, len;
  71         gpointer *values;
  72         GHashTableIter iter;
  73
  74         nm_assert (values_data);
  75
  76         if (!values_data->index) {
  77                 NM_SET_OUT (out_data, &values_data->value0);
  78                 NM_SET_OUT (out_len, 1);
  79                 return;
  80         }
  81
  82         nm_assert (values_data->index && g_hash_table_size (values_data->index) > 0);
  83
  84         if (!values_data->values) {
  85                 len = g_hash_table_size (values_data->index);
  86                 values = g_new (gpointer, len + 1);
  87
  88                 g_hash_table_iter_init (&iter, values_data->index);
  89                 for (i = 0; g_hash_table_iter_next (&iter, &values[i], NULL); i++)
  90                         nm_assert (i < len);
  91                 nm_assert (i == len);
  92                 values[i] = NULL;
  93
  94                 values_data->values = values;
  95                 NM_SET_OUT (out_len, len);
  96         } else if (out_len)
  97                 NM_SET_OUT (out_len, g_hash_table_size (values_data->index));
  98
  99         NM_SET_OUT (out_data, values_data->values);
 100 }
 101
 102 /******************************************************************************************/
 103
 104 /**
 105  * nm_multi_index_lookup():
 106  * @index:
 107  * @id:
 108  * @out_len: (allow-none): output the number of values
 109  *   that are returned.
 110  *
 111  * Returns: (transfer none): %NULL if there are no values
 112  *   or a %NULL terminated array of pointers.
 113  */
 114 void *const*
 115 nm_multi_index_lookup (const NMMultiIndex *index,
 116                        const NMMultiIndexId *id,
 117                        guint *out_len)
 118 {
 119         ValuesData *values_data;
 120         void *const*values;
 121
 122         g_return_val_if_fail (index, NULL);
 123         g_return_val_if_fail (id, NULL);
 124
 125         values_data = g_hash_table_lookup (index->hash, id);
 126         if (!values_data) {
 127                 if (out_len)
 128                         *out_len = 0;
 129                 return NULL;
 130         }
 131         _values_data_get_data (values_data, &values, out_len);
 132         return values;
 133 }
 134
 135 gboolean
 136 nm_multi_index_contains (const NMMultiIndex *index,
 137                          const NMMultiIndexId *id,
 138                          gconstpointer value)
 139 {
 140         ValuesData *values_data;
 141
 142         g_return_val_if_fail (index, FALSE);
 143         g_return_val_if_fail (id, FALSE);
 144         g_return_val_if_fail (value, FALSE);
 145
 146         values_data = g_hash_table_lookup (index->hash, id);
 147         return values_data && _values_data_contains (values_data, value);
 148 }
 149
 150 const NMMultiIndexId *
 151 nm_multi_index_lookup_first_by_value (const NMMultiIndex *index,
 152                                       gconstpointer value)
 153 {
 154         GHashTableIter iter;
 155         const NMMultiIndexId *id;
 156         ValuesData *values_data;
 157
 158         g_return_val_if_fail (index, NULL);
 159         g_return_val_if_fail (value, NULL);
 160
 161         /* reverse-lookup needs to iterate over all hash tables. It should
 162          * still be fairly quick, if the number of hash tables is small.
 163          * There is no O(1) reverse lookup implemented, because this access
 164          * pattern is not what NMMultiIndex is here for.
 165          * You are supposed to use NMMultiIndex by always knowing which @id
 166          * a @value has.
 167          */
 168
 169         g_hash_table_iter_init (&iter, index->hash);
 170         while (g_hash_table_iter_next (&iter, (gpointer *) &id, (gpointer *) &values_data)) {
 171                 if (_values_data_contains (values_data, value))
 172                         return id;
 173         }
 174         return NULL;
 175 }
 176
 177 void
 178 nm_multi_index_foreach (const NMMultiIndex *index,
 179                         gconstpointer value,
 180                         NMMultiIndexFuncForeach foreach_func,
 181                         gpointer user_data)
 182 {
 183         GHashTableIter iter;
 184         const NMMultiIndexId *id;
 185         ValuesData *values_data;
 186         guint len;
 187         void *const*values;
 188
 189         g_return_if_fail (index);
 190         g_return_if_fail (foreach_func);
 191
 192         g_hash_table_iter_init (&iter, index->hash);
 193         while (g_hash_table_iter_next (&iter, (gpointer *) &id, (gpointer *) &values_data)) {
 194                 if (value && !_values_data_contains (values_data, value))
 195                         continue;
 196
 197                 _values_data_get_data (values_data, &values, &len);
 198                 if (!foreach_func (id, values, len, user_data))
 199                         return;
 200         }
 201 }
 202
 203 void
 204 nm_multi_index_iter_init (NMMultiIndexIter *iter,
 205                           const NMMultiIndex *index,
 206                           gconstpointer value)
 207 {
 208         g_return_if_fail (index);
 209         g_return_if_fail (iter);
 210
 211         g_hash_table_iter_init (&iter->_iter, index->hash);
 212         iter->_index = index;
 213         iter->_value = value;
 214 }
 215
 216 gboolean
 217 nm_multi_index_iter_next (NMMultiIndexIter *iter,
 218                           const NMMultiIndexId **out_id,
 219                           void *const**out_values,
 220                           guint *out_len)
 221 {
 222         const NMMultiIndexId *id;
 223         ValuesData *values_data;
 224
 225         g_return_val_if_fail (iter, FALSE);
 226
 227         while (g_hash_table_iter_next (&iter->_iter, (gpointer *) &id, (gpointer *) &values_data)) {
 228                 if (   !iter->_value
 229                     || _values_data_contains (values_data, iter->_value)) {
 230                         if (out_values || out_len)
 231                                 _values_data_get_data (values_data, out_values, out_len);
 232                         if (out_id)
 233                                 *out_id = id;
 234                         return TRUE;
 235                 }
 236         }
 237         return FALSE;
 238 }
 239
 240 /******************************************************************************************/
 241
 242 void
 243 nm_multi_index_id_iter_init (NMMultiIndexIdIter *iter,
 244                              const NMMultiIndex *index,
 245                              const NMMultiIndexId *id)
 246 {
 247         ValuesData *values_data;
 248
 249         g_return_if_fail (index);
 250         g_return_if_fail (iter);
 251         g_return_if_fail (id);
 252
 253         values_data = g_hash_table_lookup (index->hash, id);
 254         if (!values_data)
 255                 iter->_state = 2;
 256         else if (values_data->index) {
 257                 iter->_state = 1;
 258                 g_hash_table_iter_init (&iter->_iter, values_data->index);
 259         } else {
 260                 iter->_state = 0;
 261                 iter->_value = values_data->value0;
 262         }
 263 }
 264
 265 gboolean
 266 nm_multi_index_id_iter_next (NMMultiIndexIdIter *iter,
 267                              void **out_value)
 268 {
 269         g_return_val_if_fail (iter, FALSE);
 270
 271         switch (iter->_state) {
 272         case 0:
 273                 iter->_state = 2;
 274                 NM_SET_OUT (out_value, iter->_value);
 275                 return TRUE;
 276         case 1:
 277                 return g_hash_table_iter_next (&iter->_iter, out_value, NULL);
 278         case 2:
 279                 iter->_state = 3;
 280                 return FALSE;
 281         default:
 282                 g_return_val_if_reached (FALSE);
 283         }
 284 }
 285
 286 /******************************************************************************************/
 287
 288 static gboolean
 289 _do_add (NMMultiIndex *index,
 290          const NMMultiIndexId *id,
 291          gconstpointer value)
 292 {
 293         ValuesData *values_data;
 294
 295         values_data = g_hash_table_lookup (index->hash, id);
 296         if (!values_data) {
 297                 NMMultiIndexId *id_new;
 298
 299                 /* Contrary to GHashTable, we don't take ownership of the @id that was
 300                  * provided to nm_multi_index_add(). Instead we clone it via @clone_fcn
 301                  * when needed.
 302                  *
 303                  * The reason is, that we expect in most cases that there exists
 304                  * already a @id so that we don't need ownership of it (or clone it).
 305                  * By doing this, the caller can pass a stack allocated @id or
 306                  * reuse the @id for other insertions.
 307                  */
 308                 id_new = index->clone_fcn (id);
 309                 if (!id_new)
 310                         g_return_val_if_reached (FALSE);
 311
 312                 values_data = g_slice_new0 (ValuesData);
 313                 values_data->value0 = (gpointer) value;
 314
 315                 g_hash_table_insert (index->hash, id_new, values_data);
 316         } else {
 317                 if (!values_data->index) {
 318                         if (values_data->value0 == value)
 319                                 return FALSE;
 320                         values_data->index = g_hash_table_new (NULL, NULL);
 321                         g_hash_table_replace (values_data->index, (gpointer) value, (gpointer) value);
 322                         g_hash_table_replace (values_data->index, values_data->value0, values_data->value0);
 323                         values_data->values = NULL;
 324                 } else {
 325                         if (!nm_g_hash_table_replace (values_data->index, (gpointer) value, (gpointer) value))
 326                                 return FALSE;
 327                         g_clear_pointer (&values_data->values, g_free);
 328                 }
 329         }
 330         return TRUE;
 331 }
 332
 333 static gboolean
 334 _do_remove (NMMultiIndex *index,
 335             const NMMultiIndexId *id,
 336             gconstpointer value)
 337 {
 338         ValuesData *values_data;
 339
 340         values_data = g_hash_table_lookup (index->hash, id);
 341         if (!values_data)
 342                 return FALSE;
 343
 344         if (values_data->index) {
 345                 if (!g_hash_table_remove (values_data->index, value))
 346                         return FALSE;
 347                 if (g_hash_table_size (values_data->index) == 0)
 348                         g_hash_table_remove (index->hash, id);
 349                 else
 350                         g_clear_pointer (&values_data->values, g_free);
 351         } else {
 352                 if (values_data->value0 != value)
 353                         return FALSE;
 354                 g_hash_table_remove (index->hash, id);
 355         }
 356
 357         return TRUE;
 358 }
 359
 360 gboolean
 361 nm_multi_index_add (NMMultiIndex *index,
 362                     const NMMultiIndexId *id,
 363                     gconstpointer value)
 364 {
 365         g_return_val_if_fail (index, FALSE);
 366         g_return_val_if_fail (id, FALSE);
 367         g_return_val_if_fail (value, FALSE);
 368
 369         return _do_add (index, id, value);
 370 }
 371
 372 gboolean
 373 nm_multi_index_remove (NMMultiIndex *index,
 374                        const NMMultiIndexId *id,
 375                        gconstpointer value)
 376 {
 377         g_return_val_if_fail (index, FALSE);
 378         g_return_val_if_fail (value, FALSE);
 379
 380         if (!id)
 381                 g_return_val_if_reached (FALSE);
 382         return _do_remove (index, id, value);
 383 }
 384
 385 /**
 386  * nm_multi_index_move:
 387  * @index:
 388  * @id_old: (allow-none): remove @value at @id_old
 389  * @id_new: (allow-none): add @value under @id_new
 390  * @value: the value to add
 391  *
 392  * Similar to a remove(), followed by an add(). The difference
 393  * is, that we allow %NULL for both @id_old and @id_new.
 394  * And the return value indicates whether @value was successfully
 395  * removed *and* added.
 396  *
 397  * Returns: %TRUE, if the value was removed from @id_old and added
 398  *   as %id_new. %FALSE could mean, that @value was not added to @id_old
 399  *   before, or that that @value was already part of @id_new. */
 400 gboolean
 401 nm_multi_index_move (NMMultiIndex *index,
 402                      const NMMultiIndexId *id_old,
 403                      const NMMultiIndexId *id_new,
 404                      gconstpointer value)
 405 {
 406         g_return_val_if_fail (index, FALSE);
 407         g_return_val_if_fail (value, FALSE);
 408
 409         if (!id_old && !id_new) {
 410                 /* nothing to do, @value was and is not in @index. */
 411                 return TRUE;
 412         } if (!id_old) {
 413                 /* add @value to @index with @id_new */
 414                 return _do_add (index, id_new, value);
 415         } else if (!id_new) {
 416                 /* remove @value from @index with @id_old */
 417                 return _do_remove (index, id_old, value);
 418         } else if (index->equal_fcn (id_old, id_new)) {
 419                 if (_do_add (index, id_new, value)) {
 420                         /* we would expect, that @value is already in @index,
 421                          * Return %FALSE, if it wasn't. */
 422                         return FALSE;
 423                 }
 424                 return TRUE;
 425         } else {
 426                 gboolean did_remove;
 427
 428                 did_remove = _do_remove (index, id_old, value);
 429                 return _do_add (index, id_new, value) && did_remove;
 430         }
 431 }
 432
 433 /******************************************************************************************/
 434
 435 guint
 436 nm_multi_index_get_num_groups (const NMMultiIndex *index)
 437 {
 438         g_return_val_if_fail (index, 0);
 439         return g_hash_table_size (index->hash);
 440 }
 441
 442 NMMultiIndex *
 443 nm_multi_index_new (NMMultiIndexFuncHash hash_fcn,
 444                     NMMultiIndexFuncEqual equal_fcn,
 445                     NMMultiIndexFuncClone clone_fcn,
 446                     NMMultiIndexFuncDestroy destroy_fcn)
 447 {
 448         NMMultiIndex *index;
 449
 450         g_return_val_if_fail (hash_fcn, NULL);
 451         g_return_val_if_fail (equal_fcn, NULL);
 452         g_return_val_if_fail (clone_fcn, NULL);
 453         g_return_val_if_fail (destroy_fcn, NULL);
 454
 455         index = g_new (NMMultiIndex, 1);
 456         index->equal_fcn = equal_fcn;
 457         index->clone_fcn = clone_fcn;
 458
 459         index->hash = g_hash_table_new_full ((GHashFunc) hash_fcn,
 460                                              (GEqualFunc) equal_fcn,
 461                                              (GDestroyNotify) destroy_fcn,
 462                                              (GDestroyNotify) _values_data_destroy);
 463         return index;
 464 }
 465
 466 void
 467 nm_multi_index_free (NMMultiIndex *index)
 468 {
 469         g_return_if_fail (index);
 470         g_hash_table_unref (index->hash);
 471         g_free (index);
 472 }
 473