glib/gdataset.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * gdataset.c: Generic dataset mechanism, similar to GtkObject data.
   5  * Copyright (C) 1998 Tim Janik
   6  *
   7  * SPDX-License-Identifier: LGPL-2.1-or-later
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2.1 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  21  */
  22
  23 /*
  24  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  25  * file for a list of people on the GLib Team.  See the ChangeLog
  26  * files for a list of changes.  These files are distributed with
  27  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  28  */
  29
  30 /*
  31  * MT safe ; except for g_data*_foreach()
  32  */
  33
  34 #include "config.h"
  35
  36 #include <string.h>
  37
  38 #include "gdataset.h"
  39 #include "gbitlock.h"
  40
  41 #include "gslice.h"
  42 #include "gdatasetprivate.h"
  43 #include "gutilsprivate.h"
  44 #include "ghash.h"
  45 #include "gquark.h"
  46 #include "gstrfuncs.h"
  47 #include "gtestutils.h"
  48 #include "gthread.h"
  49 #include "glib_trace.h"
  50 #include "galloca.h"
  51
  52 /**
  53  * GData:
  54  *
  55  * An opaque data structure that represents a keyed data list.
  56  *
  57  * See also: [Keyed data lists](datalist-and-dataset.html).
  58  **/
  59
  60 /**
  61  * GDestroyNotify:
  62  * @data: the data element.
  63  *
  64  * Specifies the type of function which is called when a data element
  65  * is destroyed. It is passed the pointer to the data element and
  66  * should free any memory and resources allocated for it.
  67  **/
  68
  69 #define G_DATALIST_FLAGS_MASK_INTERNAL 0x7
  70
  71 #define G_DATALIST_CLEAN_POINTER(ptr) \
  72   ((GData *) ((gpointer) (((guintptr) (ptr)) & ~((guintptr) G_DATALIST_FLAGS_MASK_INTERNAL))))
  73
  74 /* datalist pointer accesses have to be carried out atomically */
  75 #define G_DATALIST_GET_POINTER(datalist) \
  76   G_DATALIST_CLEAN_POINTER (g_atomic_pointer_get (datalist))
  77
  78 #define G_DATALIST_SET_POINTER(datalist, pointer)       G_STMT_START {                           \
  79   gpointer _oldv = g_atomic_pointer_get (datalist);                                              \
  80   gpointer _newv;                                                                                \
  81   do {                                                                                           \
  82     _newv = (gpointer) (((guintptr) _oldv & ((guintptr) G_DATALIST_FLAGS_MASK_INTERNAL)) | (guintptr) pointer); \
  83   } while (!g_atomic_pointer_compare_and_exchange_full ((void**) datalist, _oldv,                \
  84                                                         _newv, &_oldv));                         \
  85 } G_STMT_END
  86
  87 /* --- structures --- */
  88 typedef struct {
  89   GQuark          key;
  90   gpointer        data;
  91   GDestroyNotify  destroy;
  92 } GDataElt;
  93
  94 typedef struct _GDataset GDataset;
  95 struct _GData
  96 {
  97   guint32  len;     /* Number of elements */
  98   guint32  alloc;   /* Number of allocated elements */
  99   GDataElt data[1]; /* Flexible array */
 100 };
 101
 102 struct _GDataset
 103 {
 104   gconstpointer location;
 105   GData        *datalist;
 106 };
 107
 108
 109 /* --- prototypes --- */
 110 static inline GDataset* g_dataset_lookup                (gconstpointer    dataset_location);
 111 static void             g_dataset_destroy_internal      (GDataset        *dataset);
 112 static inline gpointer  g_data_set_internal             (GData          **datalist,
 113                                                          GQuark           key_id,
 114                                                          gpointer         data,
 115                                                          GDestroyNotify   destroy_func,
 116                                                          GDataset        *dataset);
 117 static void             g_data_initialize               (void);
 118
 119 /* Locking model:
 120  * Each standalone GDataList is protected by a bitlock in the datalist pointer,
 121  * which protects that modification of the non-flags part of the datalist pointer
 122  * and the contents of the datalist.
 123  *
 124  * For GDataSet we have a global lock g_dataset_global that protects
 125  * the global dataset hash and cache, and additionally it protects the
 126  * datalist such that we can avoid to use the bit lock in a few places
 127  * where it is easy.
 128  */
 129
 130 /* --- variables --- */
 131 G_LOCK_DEFINE_STATIC (g_dataset_global);
 132 static GHashTable   *g_dataset_location_ht = NULL;
 133 static GDataset     *g_dataset_cached = NULL; /* should this be
 134                                                  thread specific? */
 135
 136 /* --- functions --- */
 137
 138 #define DATALIST_LOCK_BIT 2
 139
 140 G_ALWAYS_INLINE static inline GData *
 141 g_datalist_lock_and_get (GData **datalist)
 142 {
 143   guintptr ptr;
 144
 145   g_pointer_bit_lock_and_get ((void **) datalist, DATALIST_LOCK_BIT, &ptr);
 146   return G_DATALIST_CLEAN_POINTER (ptr);
 147 }
 148
 149 static void
 150 g_datalist_unlock (GData **datalist)
 151 {
 152   g_pointer_bit_unlock ((void **)datalist, DATALIST_LOCK_BIT);
 153 }
 154
 155 static void
 156 g_datalist_unlock_and_set (GData **datalist, gpointer ptr)
 157 {
 158   g_pointer_bit_unlock_and_set ((void **) datalist, DATALIST_LOCK_BIT, ptr, G_DATALIST_FLAGS_MASK_INTERNAL);
 159 }
 160
 161 static gboolean
 162 datalist_append (GData **data, GQuark key_id, gpointer new_data, GDestroyNotify destroy_func)
 163 {
 164   gboolean reallocated;
 165   GData *d;
 166
 167   d = *data;
 168   if (!d)
 169     {
 170       d = g_malloc (G_STRUCT_OFFSET (GData, data) + 2u * sizeof (GDataElt));
 171       d->len = 0;
 172       d->alloc = 2u;
 173       *data = d;
 174       reallocated = TRUE;
 175     }
 176   else if (d->len == d->alloc)
 177     {
 178       d->alloc = d->alloc * 2u;
 179 #if G_ENABLE_DEBUG
 180       /* d->alloc is always a power of two. It thus overflows the first time
 181        * when going to (G_MAXUINT32+1), or when requesting 2^31+1 elements.
 182        *
 183        * This is not handled, and we just crash. That's because we track the GData
 184        * in a linear list, which horribly degrades long before we add 2 billion entries.
 185        * Don't ever try to do that. */
 186       g_assert (d->alloc > d->len);
 187 #endif
 188       d = g_realloc (d, G_STRUCT_OFFSET (GData, data) + d->alloc * sizeof (GDataElt));
 189       *data = d;
 190       reallocated = TRUE;
 191     }
 192   else
 193     reallocated = FALSE;
 194
 195   d->data[d->len] = (GDataElt){
 196     .key = key_id,
 197     .data = new_data,
 198     .destroy = destroy_func,
 199   };
 200   d->len++;
 201
 202   return reallocated;
 203 }
 204
 205 static void
 206 datalist_remove (GData *data, guint32 idx)
 207 {
 208 #if G_ENABLE_DEBUG
 209   g_assert (idx < data->len);
 210 #endif
 211
 212   /* g_data_remove_internal() relies on the fact, that this function removes
 213    * the entry similar to g_array_remove_index_fast(). That is, the entries up
 214    * to @idx are left unchanged, and the last entry is moved to position @idx.
 215    * */
 216
 217   data->len--;
 218
 219   if (idx != data->len)
 220     data->data[idx] = data->data[data->len];
 221 }
 222
 223 static gboolean
 224 datalist_shrink (GData **data, GData **d_to_free)
 225 {
 226   guint32 alloc_by_4;
 227   guint32 v;
 228   GData *d;
 229
 230   d = *data;
 231
 232   alloc_by_4 = d->alloc / 4u;
 233
 234   if (G_LIKELY (d->len > alloc_by_4))
 235     {
 236       /* No shrinking */
 237       return FALSE;
 238     }
 239
 240   if (d->len == 0)
 241     {
 242       /* The list became empty. We drop the allocated memory altogether. */
 243
 244       /* The caller will free the buffer after releasing the lock, to minimize
 245        * the time we hold the lock. Transfer it out. */
 246       *d_to_free = d;
 247       *data = NULL;
 248       return TRUE;
 249     }
 250
 251   /* If the buffer is filled not more than 25%. Shrink to double the current length. */
 252
 253   v = d->len;
 254   if (v != alloc_by_4)
 255     {
 256       /* d->alloc is a power of two. Usually, we remove one element at a
 257        * time, then we will just reach reach a quarter of that.
 258        *
 259        * However, with g_datalist_id_remove_multiple(), len can be smaller
 260        * at once. In that case, find first the next power of two. */
 261       v = g_nearest_pow (v);
 262     }
 263   v *= 2u;
 264
 265 #if G_ENABLE_DEBUG
 266   g_assert (v > d->len);
 267   g_assert (v <= d->alloc / 2u);
 268 #endif
 269
 270   d->alloc = v;
 271   d = g_realloc (d, G_STRUCT_OFFSET (GData, data) + (v * sizeof (GDataElt)));
 272   *d_to_free = NULL;
 273   *data = d;
 274   return TRUE;
 275 }
 276
 277 static GDataElt *
 278 datalist_find (GData *data, GQuark key_id, guint32 *out_idx)
 279 {
 280   guint32 i;
 281
 282   if (data)
 283     {
 284       for (i = 0; i < data->len; i++)
 285         {
 286           GDataElt *data_elt = &data->data[i];
 287
 288           if (data_elt->key == key_id)
 289             {
 290               if (out_idx)
 291                 *out_idx = i;
 292               return data_elt;
 293             }
 294         }
 295     }
 296   if (out_idx)
 297     *out_idx = G_MAXUINT32;
 298   return NULL;
 299 }
 300
 301 /**
 302  * g_datalist_clear: (skip)
 303  * @datalist: a datalist.
 304  *
 305  * Frees all the data elements of the datalist.
 306  * The data elements' destroy functions are called
 307  * if they have been set.
 308  **/
 309 void
 310 g_datalist_clear (GData **datalist)
 311 {
 312   GData *data;
 313   guint i;
 314
 315   g_return_if_fail (datalist != NULL);
 316
 317   data = g_datalist_lock_and_get (datalist);
 318
 319   if (!data)
 320     {
 321       g_datalist_unlock (datalist);
 322       return;
 323     }
 324
 325   g_datalist_unlock_and_set (datalist, NULL);
 326
 327   for (i = 0; i < data->len; i++)
 328     {
 329       if (data->data[i].data && data->data[i].destroy)
 330         data->data[i].destroy (data->data[i].data);
 331     }
 332
 333   g_free (data);
 334 }
 335
 336 /* HOLDS: g_dataset_global_lock */
 337 static inline GDataset*
 338 g_dataset_lookup (gconstpointer dataset_location)
 339 {
 340   GDataset *dataset;
 341
 342   if (g_dataset_cached && g_dataset_cached->location == dataset_location)
 343     return g_dataset_cached;
 344
 345   dataset = g_hash_table_lookup (g_dataset_location_ht, dataset_location);
 346   if (dataset)
 347     g_dataset_cached = dataset;
 348
 349   return dataset;
 350 }
 351
 352 /* HOLDS: g_dataset_global_lock */
 353 static void
 354 g_dataset_destroy_internal (GDataset *dataset)
 355 {
 356   gconstpointer dataset_location;
 357
 358   dataset_location = dataset->location;
 359   while (dataset)
 360     {
 361       GData *data;
 362       guint i;
 363
 364       data = G_DATALIST_GET_POINTER (&dataset->datalist);
 365
 366       if (!data)
 367         {
 368           if (dataset == g_dataset_cached)
 369             g_dataset_cached = NULL;
 370           g_hash_table_remove (g_dataset_location_ht, dataset_location);
 371           g_slice_free (GDataset, dataset);
 372           break;
 373         }
 374
 375       G_DATALIST_SET_POINTER (&dataset->datalist, NULL);
 376
 377       G_UNLOCK (g_dataset_global);
 378
 379       for (i = 0; i < data->len; i++)
 380         {
 381           if (data->data[i].data && data->data[i].destroy)
 382             data->data[i].destroy (data->data[i].data);
 383         }
 384       g_free (data);
 385
 386       G_LOCK (g_dataset_global);
 387       dataset = g_dataset_lookup (dataset_location);
 388     }
 389 }
 390
 391 /**
 392  * g_dataset_destroy:
 393  * @dataset_location: (not nullable): the location identifying the dataset.
 394  *
 395  * Destroys the dataset, freeing all memory allocated, and calling any
 396  * destroy functions set for data elements.
 397  */
 398 void
 399 g_dataset_destroy (gconstpointer  dataset_location)
 400 {
 401   g_return_if_fail (dataset_location != NULL);
 402
 403   G_LOCK (g_dataset_global);
 404   if (g_dataset_location_ht)
 405     {
 406       GDataset *dataset;
 407
 408       dataset = g_dataset_lookup (dataset_location);
 409       if (dataset)
 410         g_dataset_destroy_internal (dataset);
 411     }
 412   G_UNLOCK (g_dataset_global);
 413 }
 414
 415 /* HOLDS: g_dataset_global_lock if dataset != null */
 416 static inline gpointer
 417 g_data_set_internal (GData        **datalist,
 418                      GQuark         key_id,
 419                      gpointer       new_data,
 420                      GDestroyNotify new_destroy_func,
 421                      GDataset      *dataset)
 422 {
 423   GData *d;
 424   GData *new_d = NULL;
 425   GDataElt old, *data;
 426   guint32 idx;
 427
 428   d = g_datalist_lock_and_get (datalist);
 429
 430   data = datalist_find (d, key_id, &idx);
 431
 432   if (new_data == NULL) /* remove */
 433     {
 434       if (data)
 435         {
 436           GData *d_to_free;
 437
 438           old = *data;
 439
 440           datalist_remove (d, idx);
 441           if (datalist_shrink (&d, &d_to_free))
 442             {
 443               g_datalist_unlock_and_set (datalist, d);
 444
 445               /* the dataset destruction *must* be done
 446                * prior to invocation of the data destroy function
 447                */
 448               if (dataset && !d)
 449                 g_dataset_destroy_internal (dataset);
 450
 451               if (d_to_free)
 452                 g_free (d_to_free);
 453             }
 454           else
 455             g_datalist_unlock (datalist);
 456
 457           /* We found and removed an old value
 458            * the GData struct *must* already be unlinked
 459            * when invoking the destroy function.
 460            * we use (new_data==NULL && new_destroy_func!=NULL) as
 461            * a special hint combination to "steal"
 462            * data without destroy notification
 463            */
 464           if (old.destroy && !new_destroy_func)
 465             {
 466               if (dataset)
 467                 G_UNLOCK (g_dataset_global);
 468               old.destroy (old.data);
 469               if (dataset)
 470                 G_LOCK (g_dataset_global);
 471               old.data = NULL;
 472             }
 473
 474           return old.data;
 475         }
 476     }
 477   else
 478     {
 479       if (data)
 480         {
 481           if (!data->destroy)
 482             {
 483               data->data = new_data;
 484               data->destroy = new_destroy_func;
 485               g_datalist_unlock (datalist);
 486             }
 487           else
 488             {
 489               old = *data;
 490               data->data = new_data;
 491               data->destroy = new_destroy_func;
 492
 493               g_datalist_unlock (datalist);
 494
 495               /* We found and replaced an old value
 496                * the GData struct *must* already be unlinked
 497                * when invoking the destroy function.
 498                */
 499               if (dataset)
 500                 G_UNLOCK (g_dataset_global);
 501               old.destroy (old.data);
 502               if (dataset)
 503                 G_LOCK (g_dataset_global);
 504             }
 505           return NULL;
 506         }
 507
 508       /* The key was not found, insert it */
 509       if (datalist_append (&d, key_id, new_data, new_destroy_func))
 510         new_d = d;
 511     }
 512
 513   if (new_d)
 514     g_datalist_unlock_and_set (datalist, new_d);
 515   else
 516     g_datalist_unlock (datalist);
 517
 518   return NULL;
 519
 520 }
 521
 522 static inline void
 523 g_data_remove_internal (GData  **datalist,
 524                         GQuark  *keys,
 525                         gsize    n_keys)
 526 {
 527   GData *d;
 528   GDataElt *old;
 529   GDataElt *old_to_free = NULL;
 530   GData *d_to_free;
 531   gsize found_keys;
 532   gsize i_keys;
 533   guint32 i_data;
 534
 535   d = g_datalist_lock_and_get (datalist);
 536
 537   if (!d)
 538     {
 539       g_datalist_unlock (datalist);
 540       return;
 541     }
 542
 543   /* Allocate an array of GDataElt to hold copies of the elements
 544    * that are removed from the datalist. Allow enough space for all
 545    * the keys; if a key is not found, the corresponding element of
 546    * old is not populated, so we initialize them all to NULL to
 547    * detect that case.
 548    *
 549    * At most allocate 400 bytes on the stack. Especially since we call
 550    * out to external code, we don't know how much stack we can use. */
 551   if (n_keys <= 400u / sizeof (GDataElt))
 552     old = g_newa0 (GDataElt, n_keys);
 553   else
 554     {
 555       old_to_free = g_new0 (GDataElt, n_keys);
 556       old = old_to_free;
 557     }
 558
 559   i_data = 0;
 560   found_keys = 0;
 561   while (i_data < d->len && found_keys < n_keys)
 562     {
 563       GDataElt *data = &d->data[i_data];
 564       gboolean remove = FALSE;
 565
 566       for (i_keys = 0; i_keys < n_keys; i_keys++)
 567         {
 568           if (data->key == keys[i_keys])
 569             {
 570               /* We must invoke the destroy notifications in the order of @keys.
 571                * Hence, build up the list @old at index @i_keys. */
 572               old[i_keys] = *data;
 573               found_keys++;
 574               remove = TRUE;
 575               break;
 576             }
 577         }
 578
 579       if (!remove)
 580         {
 581           i_data++;
 582           continue;
 583         }
 584
 585       datalist_remove (d, i_data);
 586     }
 587
 588   if (found_keys > 0 && datalist_shrink (&d, &d_to_free))
 589     {
 590       g_datalist_unlock_and_set (datalist, d);
 591       if (d_to_free)
 592         g_free (d_to_free);
 593     }
 594   else
 595     g_datalist_unlock (datalist);
 596
 597   if (found_keys > 0)
 598     {
 599       for (i_keys = 0; i_keys < n_keys; i_keys++)
 600         {
 601           if (old[i_keys].destroy)
 602             old[i_keys].destroy (old[i_keys].data);
 603         }
 604     }
 605
 606   if (G_UNLIKELY (old_to_free))
 607     g_free (old_to_free);
 608 }
 609
 610 /**
 611  * g_dataset_id_set_data_full: (skip)
 612  * @dataset_location: (not nullable): the location identifying the dataset.
 613  * @key_id: the #GQuark id to identify the data element.
 614  * @data: the data element.
 615  * @destroy_func: the function to call when the data element is
 616  *                removed. This function will be called with the data
 617  *                element and can be used to free any memory allocated
 618  *                for it.
 619  *
 620  * Sets the data element associated with the given #GQuark id, and also
 621  * the function to call when the data element is destroyed. Any
 622  * previous data with the same key is removed, and its destroy function
 623  * is called.
 624  **/
 625 /**
 626  * g_dataset_set_data_full: (skip)
 627  * @l: the location identifying the dataset.
 628  * @k: the string to identify the data element.
 629  * @d: the data element.
 630  * @f: the function to call when the data element is removed. This
 631  *     function will be called with the data element and can be used to
 632  *     free any memory allocated for it.
 633  *
 634  * Sets the data corresponding to the given string identifier, and the
 635  * function to call when the data element is destroyed.
 636  **/
 637 /**
 638  * g_dataset_id_set_data:
 639  * @l: the location identifying the dataset.
 640  * @k: the #GQuark id to identify the data element.
 641  * @d: the data element.
 642  *
 643  * Sets the data element associated with the given #GQuark id. Any
 644  * previous data with the same key is removed, and its destroy function
 645  * is called.
 646  **/
 647 /**
 648  * g_dataset_set_data:
 649  * @l: the location identifying the dataset.
 650  * @k: the string to identify the data element.
 651  * @d: the data element.
 652  *
 653  * Sets the data corresponding to the given string identifier.
 654  **/
 655 /**
 656  * g_dataset_id_remove_data:
 657  * @l: the location identifying the dataset.
 658  * @k: the #GQuark id identifying the data element.
 659  *
 660  * Removes a data element from a dataset. The data element's destroy
 661  * function is called if it has been set.
 662  **/
 663 /**
 664  * g_dataset_remove_data:
 665  * @l: the location identifying the dataset.
 666  * @k: the string identifying the data element.
 667  *
 668  * Removes a data element corresponding to a string. Its destroy
 669  * function is called if it has been set.
 670  **/
 671 void
 672 g_dataset_id_set_data_full (gconstpointer  dataset_location,
 673                             GQuark         key_id,
 674                             gpointer       data,
 675                             GDestroyNotify destroy_func)
 676 {
 677   GDataset *dataset;
 678
 679   g_return_if_fail (dataset_location != NULL);
 680   if (!data)
 681     g_return_if_fail (destroy_func == NULL);
 682   if (!key_id)
 683     {
 684       if (data)
 685         g_return_if_fail (key_id > 0);
 686       else
 687         return;
 688     }
 689
 690   G_LOCK (g_dataset_global);
 691   if (!g_dataset_location_ht)
 692     g_data_initialize ();
 693
 694   dataset = g_dataset_lookup (dataset_location);
 695   if (!dataset)
 696     {
 697       dataset = g_slice_new (GDataset);
 698       dataset->location = dataset_location;
 699       g_datalist_init (&dataset->datalist);
 700       g_hash_table_insert (g_dataset_location_ht,
 701                            (gpointer) dataset->location,
 702                            dataset);
 703     }
 704
 705   g_data_set_internal (&dataset->datalist, key_id, data, destroy_func, dataset);
 706   G_UNLOCK (g_dataset_global);
 707 }
 708
 709 /**
 710  * g_datalist_id_set_data_full: (skip)
 711  * @datalist: a datalist.
 712  * @key_id: the #GQuark to identify the data element.
 713  * @data: (nullable): the data element or %NULL to remove any previous element
 714  *        corresponding to @key_id.
 715  * @destroy_func: (nullable): the function to call when the data element is
 716  *                removed. This function will be called with the data
 717  *                element and can be used to free any memory allocated
 718  *                for it. If @data is %NULL, then @destroy_func must
 719  *                also be %NULL.
 720  *
 721  * Sets the data corresponding to the given #GQuark id, and the
 722  * function to be called when the element is removed from the datalist.
 723  * Any previous data with the same key is removed, and its destroy
 724  * function is called.
 725  **/
 726 /**
 727  * g_datalist_set_data_full: (skip)
 728  * @dl: a datalist.
 729  * @k: the string to identify the data element.
 730  * @d: (nullable): the data element, or %NULL to remove any previous element
 731  *     corresponding to @k.
 732  * @f: (nullable): the function to call when the data element is removed.
 733  *     This function will be called with the data element and can be used to
 734  *     free any memory allocated for it. If @d is %NULL, then @f must
 735  *     also be %NULL.
 736  *
 737  * Sets the data element corresponding to the given string identifier,
 738  * and the function to be called when the data element is removed.
 739  **/
 740 /**
 741  * g_datalist_id_set_data:
 742  * @dl: a datalist.
 743  * @q: the #GQuark to identify the data element.
 744  * @d: (nullable): the data element, or %NULL to remove any previous element
 745  *     corresponding to @q.
 746  *
 747  * Sets the data corresponding to the given #GQuark id. Any previous
 748  * data with the same key is removed, and its destroy function is
 749  * called.
 750  **/
 751 /**
 752  * g_datalist_set_data:
 753  * @dl: a datalist.
 754  * @k: the string to identify the data element.
 755  * @d: (nullable): the data element, or %NULL to remove any previous element
 756  *     corresponding to @k.
 757  *
 758  * Sets the data element corresponding to the given string identifier.
 759  **/
 760 /**
 761  * g_datalist_id_remove_data:
 762  * @dl: a datalist.
 763  * @q: the #GQuark identifying the data element.
 764  *
 765  * Removes an element, using its #GQuark identifier.
 766  **/
 767 /**
 768  * g_datalist_remove_data:
 769  * @dl: a datalist.
 770  * @k: the string identifying the data element.
 771  *
 772  * Removes an element using its string identifier. The data element's
 773  * destroy function is called if it has been set.
 774  **/
 775 void
 776 g_datalist_id_set_data_full (GData        **datalist,
 777                              GQuark         key_id,
 778                              gpointer       data,
 779                              GDestroyNotify destroy_func)
 780 {
 781   g_return_if_fail (datalist != NULL);
 782   if (!data)
 783     g_return_if_fail (destroy_func == NULL);
 784   if (!key_id)
 785     {
 786       if (data)
 787         g_return_if_fail (key_id > 0);
 788       else
 789         return;
 790     }
 791
 792   g_data_set_internal (datalist, key_id, data, destroy_func, NULL);
 793 }
 794
 795 /**
 796  * g_datalist_id_remove_multiple:
 797  * @datalist: a datalist
 798  * @keys: (array length=n_keys): keys to remove
 799  * @n_keys: length of @keys.
 800  *
 801  * Removes multiple keys from a datalist.
 802  *
 803  * This is more efficient than calling g_datalist_id_remove_data()
 804  * multiple times in a row.
 805  *
 806  * Before 2.80, @n_keys had to be not larger than 16. Now it can be larger, but
 807  * note that GData does a linear search, so an excessive number of keys will
 808  * perform badly.
 809  *
 810  * Since: 2.74
 811  */
 812 void
 813 g_datalist_id_remove_multiple (GData  **datalist,
 814                                GQuark  *keys,
 815                                gsize    n_keys)
 816 {
 817   g_data_remove_internal (datalist, keys, n_keys);
 818 }
 819
 820 /**
 821  * g_dataset_id_remove_no_notify: (skip)
 822  * @dataset_location: (not nullable): the location identifying the dataset.
 823  * @key_id: the #GQuark ID identifying the data element.
 824  *
 825  * Removes an element, without calling its destroy notification
 826  * function.
 827  *
 828  * Returns: (nullable): the data previously stored at @key_id,
 829  *          or %NULL if none.
 830  **/
 831 /**
 832  * g_dataset_remove_no_notify: (skip)
 833  * @l: the location identifying the dataset.
 834  * @k: the string identifying the data element.
 835  *
 836  * Removes an element, without calling its destroy notifier.
 837  **/
 838 gpointer
 839 g_dataset_id_remove_no_notify (gconstpointer  dataset_location,
 840                                GQuark         key_id)
 841 {
 842   gpointer ret_data = NULL;
 843
 844   g_return_val_if_fail (dataset_location != NULL, NULL);
 845
 846   G_LOCK (g_dataset_global);
 847   if (key_id && g_dataset_location_ht)
 848     {
 849       GDataset *dataset;
 850
 851       dataset = g_dataset_lookup (dataset_location);
 852       if (dataset)
 853         ret_data = g_data_set_internal (&dataset->datalist, key_id, NULL, (GDestroyNotify) 42, dataset);
 854     }
 855   G_UNLOCK (g_dataset_global);
 856
 857   return ret_data;
 858 }
 859
 860 /**
 861  * g_datalist_id_remove_no_notify: (skip)
 862  * @datalist: a datalist.
 863  * @key_id: the #GQuark identifying a data element.
 864  *
 865  * Removes an element, without calling its destroy notification
 866  * function.
 867  *
 868  * Returns: (nullable): the data previously stored at @key_id,
 869  *          or %NULL if none.
 870  **/
 871 /**
 872  * g_datalist_remove_no_notify: (skip)
 873  * @dl: a datalist.
 874  * @k: the string identifying the data element.
 875  *
 876  * Removes an element, without calling its destroy notifier.
 877  **/
 878 gpointer
 879 g_datalist_id_remove_no_notify (GData   **datalist,
 880                                 GQuark    key_id)
 881 {
 882   gpointer ret_data = NULL;
 883
 884   g_return_val_if_fail (datalist != NULL, NULL);
 885
 886   if (key_id)
 887     ret_data = g_data_set_internal (datalist, key_id, NULL, (GDestroyNotify) 42, NULL);
 888
 889   return ret_data;
 890 }
 891
 892 /*< private >
 893  * g_datalist_id_update_atomic:
 894  * @datalist: the data list
 895  * @key_id: the key to add.
 896  * @callback: (scope call): callback to update (set, remove, steal, update) the
 897  *   data.
 898  * @user_data: the user data for @callback.
 899  *
 900  * Will call @callback while holding the lock on @datalist. Be careful to not
 901  * end up calling into another data-list function, because the lock is not
 902  * reentrant and deadlock will happen.
 903  *
 904  * The callback receives the current data and destroy function. If @key_id is
 905  * currently not in @datalist, they will be %NULL. The callback can update
 906  * those pointers, and @datalist will be updated with the result. Note that if
 907  * callback modifies a received data, then it MUST steal it and take ownership
 908  * on it. Possibly by freeing it with the provided destroy function.
 909  *
 910  * The point is to atomically access the entry, while holding a lock
 911  * of @datalist. Without this, the user would have to hold their own mutex
 912  * while handling @key_id entry.
 913  *
 914  * The return value of @callback is not used, except it becomes the return
 915  * value of the function. This is an alternative to returning a result via
 916  * @user_data.
 917  *
 918  * Returns: the value returned by @callback.
 919  *
 920  * Since: 2.80
 921  */
 922 gpointer
 923 g_datalist_id_update_atomic (GData **datalist,
 924                              GQuark key_id,
 925                              GDataListUpdateAtomicFunc callback,
 926                              gpointer user_data)
 927 {
 928   GData *d;
 929   GDataElt *data;
 930   gpointer new_data;
 931   gpointer result;
 932   GDestroyNotify new_destroy;
 933   guint32 idx;
 934   gboolean to_unlock = TRUE;
 935
 936   d = g_datalist_lock_and_get (datalist);
 937
 938   data = datalist_find (d, key_id, &idx);
 939
 940   if (data)
 941     {
 942       new_data = data->data;
 943       new_destroy = data->destroy;
 944     }
 945   else
 946     {
 947       new_data = NULL;
 948       new_destroy = NULL;
 949     }
 950
 951   result = callback (key_id, &new_data, &new_destroy, user_data);
 952
 953   if (data && !new_data)
 954     {
 955       GData *d_to_free;
 956
 957       /* Remove. The callback indicates to drop the entry.
 958        *
 959        * The old data->data was stolen by callback(). */
 960       datalist_remove (d, idx);
 961       if (datalist_shrink (&d, &d_to_free))
 962         {
 963           g_datalist_unlock_and_set (datalist, d);
 964           if (d_to_free)
 965             g_free (d_to_free);
 966           to_unlock = FALSE;
 967         }
 968     }
 969   else if (data)
 970     {
 971       /* Update. The callback may have provided new pointers to an existing
 972        * entry.
 973        *
 974        * The old data was stolen by callback(). We only update the pointers and
 975        * are done. */
 976       data->data = new_data;
 977       data->destroy = new_destroy;
 978     }
 979   else if (!data && !new_data)
 980     {
 981       /* Absent. No change. The entry didn't exist and still does not. */
 982     }
 983   else
 984     {
 985       /* Add. Add a new entry that didn't exist previously. */
 986       if (datalist_append (&d, key_id, new_data, new_destroy))
 987         {
 988           g_datalist_unlock_and_set (datalist, d);
 989           to_unlock = FALSE;
 990         }
 991     }
 992
 993   if (to_unlock)
 994     g_datalist_unlock (datalist);
 995
 996   return result;
 997 }
 998
 999 /**
1000  * g_dataset_id_get_data:
1001  * @dataset_location: (not nullable): the location identifying the dataset.
1002  * @key_id: the #GQuark id to identify the data element.
1003  *
1004  * Gets the data element corresponding to a #GQuark.
1005  *
1006  * Returns: (transfer none) (nullable): the data element corresponding to
1007  *          the #GQuark, or %NULL if it is not found.
1008  **/
1009 /**
1010  * g_dataset_get_data:
1011  * @l: the location identifying the dataset.
1012  * @k: the string identifying the data element.
1013  *
1014  * Gets the data element corresponding to a string.
1015  *
1016  * Returns: (transfer none) (nullable): the data element corresponding to
1017  *          the string, or %NULL if it is not found.
1018  **/
1019 gpointer
1020 g_dataset_id_get_data (gconstpointer  dataset_location,
1021                        GQuark         key_id)
1022 {
1023   gpointer retval = NULL;
1024
1025   g_return_val_if_fail (dataset_location != NULL, NULL);
1026
1027   G_LOCK (g_dataset_global);
1028   if (key_id && g_dataset_location_ht)
1029     {
1030       GDataset *dataset;
1031
1032       dataset = g_dataset_lookup (dataset_location);
1033       if (dataset)
1034         retval = g_datalist_id_get_data (&dataset->datalist, key_id);
1035     }
1036   G_UNLOCK (g_dataset_global);
1037
1038   return retval;
1039 }
1040
1041 /**
1042  * g_datalist_id_get_data:
1043  * @datalist: a datalist.
1044  * @key_id: the #GQuark identifying a data element.
1045  *
1046  * Retrieves the data element corresponding to @key_id.
1047  *
1048  * Returns: (transfer none) (nullable): the data element, or %NULL if
1049  *          it is not found.
1050  */
1051 gpointer
1052 g_datalist_id_get_data (GData  **datalist,
1053                         GQuark   key_id)
1054 {
1055   return g_datalist_id_dup_data (datalist, key_id, NULL, NULL);
1056 }
1057
1058 /**
1059  * GDuplicateFunc:
1060  * @data: the data to duplicate
1061  * @user_data: (closure): user data that was specified in
1062  *             g_datalist_id_dup_data()
1063  *
1064  * The type of functions that are used to 'duplicate' an object.
1065  * What this means depends on the context, it could just be
1066  * incrementing the reference count, if @data is a ref-counted
1067  * object.
1068  *
1069  * Returns: a duplicate of data
1070  */
1071
1072 /**
1073  * g_datalist_id_dup_data: (skip)
1074  * @datalist: location of a datalist
1075  * @key_id: the #GQuark identifying a data element
1076  * @dup_func: (scope call) (closure user_data) (nullable): function to
1077  *   duplicate the old value
1078  * @user_data: passed as user_data to @dup_func
1079  *
1080  * This is a variant of g_datalist_id_get_data() which
1081  * returns a 'duplicate' of the value. @dup_func defines the
1082  * meaning of 'duplicate' in this context, it could e.g.
1083  * take a reference on a ref-counted object.
1084  *
1085  * If the @key_id is not set in the datalist then @dup_func
1086  * will be called with a %NULL argument.
1087  *
1088  * Note that @dup_func is called while the datalist is locked, so it
1089  * is not allowed to read or modify the datalist.
1090  *
1091  * This function can be useful to avoid races when multiple
1092  * threads are using the same datalist and the same key.
1093  *
1094  * Returns: (nullable): the result of calling @dup_func on the value
1095  *     associated with @key_id in @datalist, or %NULL if not set.
1096  *     If @dup_func is %NULL, the value is returned unmodified.
1097  *
1098  * Since: 2.34
1099  */
1100 gpointer
1101 g_datalist_id_dup_data (GData          **datalist,
1102                         GQuark           key_id,
1103                         GDuplicateFunc   dup_func,
1104                         gpointer         user_data)
1105 {
1106   gpointer val = NULL;
1107   gpointer retval = NULL;
1108   GData *d;
1109   GDataElt *data;
1110
1111   d = g_datalist_lock_and_get (datalist);
1112
1113   data = datalist_find (d, key_id, NULL);
1114   if (data)
1115     val = data->data;
1116
1117   if (dup_func)
1118     retval = dup_func (val, user_data);
1119   else
1120     retval = val;
1121
1122   g_datalist_unlock (datalist);
1123
1124   return retval;
1125 }
1126
1127 /**
1128  * g_datalist_id_replace_data: (skip)
1129  * @datalist: location of a datalist
1130  * @key_id: the #GQuark identifying a data element
1131  * @oldval: (nullable): the old value to compare against
1132  * @newval: (nullable): the new value to replace it with
1133  * @destroy: (nullable): destroy notify for the new value
1134  * @old_destroy: (out) (optional): destroy notify for the existing value
1135  *
1136  * Compares the member that is associated with @key_id in
1137  * @datalist to @oldval, and if they are the same, replace
1138  * @oldval with @newval.
1139  *
1140  * This is like a typical atomic compare-and-exchange
1141  * operation, for a member of @datalist.
1142  *
1143  * If the previous value was replaced then ownership of the
1144  * old value (@oldval) is passed to the caller, including
1145  * the registered destroy notify for it (passed out in @old_destroy).
1146  * Its up to the caller to free this as they wish, which may
1147  * or may not include using @old_destroy as sometimes replacement
1148  * should not destroy the object in the normal way.
1149  *
1150  * Returns: %TRUE if the existing value for @key_id was replaced
1151  *  by @newval, %FALSE otherwise.
1152  *
1153  * Since: 2.34
1154  */
1155 gboolean
1156 g_datalist_id_replace_data (GData          **datalist,
1157                             GQuark           key_id,
1158                             gpointer         oldval,
1159                             gpointer         newval,
1160                             GDestroyNotify   destroy,
1161                             GDestroyNotify  *old_destroy)
1162 {
1163   gpointer val = NULL;
1164   GData *d;
1165   GDataElt *data;
1166   GData *d_to_free = NULL;
1167   gboolean set_d = FALSE;
1168   guint32 idx;
1169
1170   g_return_val_if_fail (datalist != NULL, FALSE);
1171   g_return_val_if_fail (key_id != 0, FALSE);
1172
1173   if (old_destroy)
1174     *old_destroy = NULL;
1175
1176   d = g_datalist_lock_and_get (datalist);
1177
1178   data = datalist_find (d, key_id, &idx);
1179   if (data)
1180     {
1181       val = data->data;
1182       if (val == oldval)
1183         {
1184           if (old_destroy)
1185             *old_destroy = data->destroy;
1186           if (newval != NULL)
1187             {
1188               data->data = newval;
1189               data->destroy = destroy;
1190             }
1191           else
1192             {
1193               datalist_remove (d, idx);
1194               if (datalist_shrink (&d, &d_to_free))
1195                 set_d = TRUE;
1196             }
1197         }
1198     }
1199
1200   if (val == NULL && oldval == NULL && newval != NULL)
1201     {
1202       if (datalist_append (&d, key_id, newval, destroy))
1203         {
1204           set_d = TRUE;
1205         }
1206     }
1207
1208   if (set_d)
1209     g_datalist_unlock_and_set (datalist, d);
1210   else
1211     g_datalist_unlock (datalist);
1212
1213   if (d_to_free)
1214     g_free (d_to_free);
1215
1216   return val == oldval;
1217 }
1218
1219 /**
1220  * g_datalist_get_data:
1221  * @datalist: a datalist.
1222  * @key: the string identifying a data element.
1223  *
1224  * Gets a data element, using its string identifier. This is slower than
1225  * g_datalist_id_get_data() because it compares strings.
1226  *
1227  * Returns: (transfer none) (nullable): the data element, or %NULL if it
1228  *          is not found.
1229  **/
1230 gpointer
1231 g_datalist_get_data (GData       **datalist,
1232                      const gchar *key)
1233 {
1234   gpointer res = NULL;
1235   GData *d;
1236   GDataElt *data, *data_end;
1237
1238   g_return_val_if_fail (datalist != NULL, NULL);
1239
1240   d = g_datalist_lock_and_get (datalist);
1241   if (d)
1242     {
1243       data = d->data;
1244       data_end = data + d->len;
1245       while (data < data_end)
1246         {
1247           /* Here we intentionally compare by strings, instead of calling
1248            * g_quark_try_string() first.
1249            *
1250            * See commit 1cceda49b60b ('Make g_datalist_get_data not look up the
1251            * quark').
1252            */
1253           if (g_strcmp0 (g_quark_to_string (data->key), key) == 0)
1254             {
1255               res = data->data;
1256               break;
1257             }
1258           data++;
1259         }
1260     }
1261
1262   g_datalist_unlock (datalist);
1263
1264   return res;
1265 }
1266
1267 /**
1268  * GDataForeachFunc:
1269  * @key_id: the #GQuark id to identifying the data element.
1270  * @data: the data element.
1271  * @user_data: (closure): user data passed to g_dataset_foreach().
1272  *
1273  * Specifies the type of function passed to g_dataset_foreach(). It is
1274  * called with each #GQuark id and associated data element, together
1275  * with the @user_data parameter supplied to g_dataset_foreach().
1276  **/
1277
1278 /**
1279  * g_dataset_foreach:
1280  * @dataset_location: (not nullable): the location identifying the dataset.
1281  * @func: (scope call) (closure user_data): the function to call for each data element.
1282  * @user_data: user data to pass to the function.
1283  *
1284  * Calls the given function for each data element which is associated
1285  * with the given location. Note that this function is NOT thread-safe.
1286  * So unless @dataset_location can be protected from any modifications
1287  * during invocation of this function, it should not be called.
1288  *
1289  * @func can make changes to the dataset, but the iteration will not
1290  * reflect changes made during the g_dataset_foreach() call, other
1291  * than skipping over elements that are removed.
1292  **/
1293 void
1294 g_dataset_foreach (gconstpointer    dataset_location,
1295                    GDataForeachFunc func,
1296                    gpointer         user_data)
1297 {
1298   GDataset *dataset;
1299
1300   g_return_if_fail (dataset_location != NULL);
1301   g_return_if_fail (func != NULL);
1302
1303   G_LOCK (g_dataset_global);
1304   if (g_dataset_location_ht)
1305     {
1306       dataset = g_dataset_lookup (dataset_location);
1307       G_UNLOCK (g_dataset_global);
1308       if (dataset)
1309         g_datalist_foreach (&dataset->datalist, func, user_data);
1310     }
1311   else
1312     {
1313       G_UNLOCK (g_dataset_global);
1314     }
1315 }
1316
1317 /**
1318  * g_datalist_foreach:
1319  * @datalist: a datalist.
1320  * @func: (scope call) (closure user_data): the function to call for each data element.
1321  * @user_data: user data to pass to the function.
1322  *
1323  * Calls the given function for each data element of the datalist. The
1324  * function is called with each data element's #GQuark id and data,
1325  * together with the given @user_data parameter. Note that this
1326  * function is NOT thread-safe. So unless @datalist can be protected
1327  * from any modifications during invocation of this function, it should
1328  * not be called.
1329  *
1330  * @func can make changes to @datalist, but the iteration will not
1331  * reflect changes made during the g_datalist_foreach() call, other
1332  * than skipping over elements that are removed.
1333  **/
1334 void
1335 g_datalist_foreach (GData          **datalist,
1336                     GDataForeachFunc func,
1337                     gpointer         user_data)
1338 {
1339   GData *d;
1340   guint i, j, len;
1341   GQuark *keys;
1342
1343   g_return_if_fail (datalist != NULL);
1344   g_return_if_fail (func != NULL);
1345
1346   d = G_DATALIST_GET_POINTER (datalist);
1347   if (d == NULL)
1348     return;
1349
1350   /* We make a copy of the keys so that we can handle it changing
1351      in the callback */
1352   len = d->len;
1353   keys = g_new (GQuark, len);
1354   for (i = 0; i < len; i++)
1355     keys[i] = d->data[i].key;
1356
1357   for (i = 0; i < len; i++)
1358     {
1359       /* A previous callback might have removed a later item, so always check that
1360          it still exists before calling */
1361       d = G_DATALIST_GET_POINTER (datalist);
1362
1363       if (d == NULL)
1364         break;
1365       for (j = 0; j < d->len; j++)
1366         {
1367           if (d->data[j].key == keys[i]) {
1368             func (d->data[i].key, d->data[i].data, user_data);
1369             break;
1370           }
1371         }
1372     }
1373   g_free (keys);
1374 }
1375
1376 /**
1377  * g_datalist_init: (skip)
1378  * @datalist: a pointer to a pointer to a datalist.
1379  *
1380  * Resets the datalist to %NULL. It does not free any memory or call
1381  * any destroy functions.
1382  **/
1383 void
1384 g_datalist_init (GData **datalist)
1385 {
1386   g_return_if_fail (datalist != NULL);
1387
1388   g_atomic_pointer_set (datalist, NULL);
1389 }
1390
1391 /**
1392  * g_datalist_set_flags:
1393  * @datalist: pointer to the location that holds a list
1394  * @flags: the flags to turn on. The values of the flags are
1395  *   restricted by %G_DATALIST_FLAGS_MASK (currently
1396  *   3; giving two possible boolean flags).
1397  *   A value for @flags that doesn't fit within the mask is
1398  *   an error.
1399  *
1400  * Turns on flag values for a data list. This function is used
1401  * to keep a small number of boolean flags in an object with
1402  * a data list without using any additional space. It is
1403  * not generally useful except in circumstances where space
1404  * is very tight. (It is used in the base #GObject type, for
1405  * example.)
1406  *
1407  * Since: 2.8
1408  **/
1409 void
1410 g_datalist_set_flags (GData **datalist,
1411                       guint   flags)
1412 {
1413   g_return_if_fail (datalist != NULL);
1414   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
1415
1416   g_atomic_pointer_or (datalist, (gsize)flags);
1417 }
1418
1419 /**
1420  * g_datalist_unset_flags:
1421  * @datalist: pointer to the location that holds a list
1422  * @flags: the flags to turn off. The values of the flags are
1423  *   restricted by %G_DATALIST_FLAGS_MASK (currently
1424  *   3: giving two possible boolean flags).
1425  *   A value for @flags that doesn't fit within the mask is
1426  *   an error.
1427  *
1428  * Turns off flag values for a data list. See g_datalist_unset_flags()
1429  *
1430  * Since: 2.8
1431  **/
1432 void
1433 g_datalist_unset_flags (GData **datalist,
1434                         guint   flags)
1435 {
1436   g_return_if_fail (datalist != NULL);
1437   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
1438
1439   g_atomic_pointer_and (datalist, ~(gsize)flags);
1440 }
1441
1442 /**
1443  * g_datalist_get_flags:
1444  * @datalist: pointer to the location that holds a list
1445  *
1446  * Gets flags values packed in together with the datalist.
1447  * See g_datalist_set_flags().
1448  *
1449  * Returns: the flags of the datalist
1450  *
1451  * Since: 2.8
1452  **/
1453 guint
1454 g_datalist_get_flags (GData **datalist)
1455 {
1456   g_return_val_if_fail (datalist != NULL, 0);
1457
1458   return G_DATALIST_GET_FLAGS (datalist); /* atomic macro */
1459 }
1460
1461 /* HOLDS: g_dataset_global_lock */
1462 static void
1463 g_data_initialize (void)
1464 {
1465   g_return_if_fail (g_dataset_location_ht == NULL);
1466
1467   g_dataset_location_ht = g_hash_table_new (g_direct_hash, NULL);
1468   g_dataset_cached = NULL;
1469 }