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