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  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  20  */
  21
  22 /*
  23  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  24  * file for a list of people on the GLib Team.  See the ChangeLog
  25  * files for a list of changes.  These files are distributed with
  26  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  27  */
  28
  29 /*
  30  * MT safe ; except for g_data*_foreach()
  31  */
  32
  33 #include "config.h"
  34
  35 #include <string.h>
  36
  37 #include "gdataset.h"
  38 #include "gbitlock.h"
  39
  40 #include "gslice.h"
  41 #include "gdatasetprivate.h"
  42 #include "ghash.h"
  43 #include "gquark.h"
  44 #include "gstrfuncs.h"
  45 #include "gtestutils.h"
  46 #include "gthread.h"
  47 #include "glib_trace.h"
  48
  49 /**
  50  * SECTION:datasets
  51  * @title: Datasets
  52  * @short_description: associate groups of data elements with
  53  *                     particular memory locations
  54  *
  55  * Datasets associate groups of data elements with particular memory
  56  * locations. These are useful if you need to associate data with a
  57  * structure returned from an external library. Since you cannot modify
  58  * the structure, you use its location in memory as the key into a
  59  * dataset, where you can associate any number of data elements with it.
  60  *
  61  * There are two forms of most of the dataset functions. The first form
  62  * uses strings to identify the data elements associated with a
  63  * location. The second form uses #GQuark identifiers, which are
  64  * created with a call to g_quark_from_string() or
  65  * g_quark_from_static_string(). The second form is quicker, since it
  66  * does not require looking up the string in the hash table of #GQuark
  67  * identifiers.
  68  *
  69  * There is no function to create a dataset. It is automatically
  70  * created as soon as you add elements to it.
  71  *
  72  * To add data elements to a dataset use g_dataset_id_set_data(),
  73  * g_dataset_id_set_data_full(), g_dataset_set_data() and
  74  * g_dataset_set_data_full().
  75  *
  76  * To get data elements from a dataset use g_dataset_id_get_data() and
  77  * g_dataset_get_data().
  78  *
  79  * To iterate over all data elements in a dataset use
  80  * g_dataset_foreach() (not thread-safe).
  81  *
  82  * To remove data elements from a dataset use
  83  * g_dataset_id_remove_data() and g_dataset_remove_data().
  84  *
  85  * To destroy a dataset, use g_dataset_destroy().
  86  **/
  87
  88 /**
  89  * SECTION:datalist
  90  * @title: Keyed Data Lists
  91  * @short_description: lists of data elements which are accessible by a
  92  *                     string or GQuark identifier
  93  *
  94  * Keyed data lists provide lists of arbitrary data elements which can
  95  * be accessed either with a string or with a #GQuark corresponding to
  96  * the string.
  97  *
  98  * The #GQuark methods are quicker, since the strings have to be
  99  * converted to #GQuarks anyway.
 100  *
 101  * Data lists are used for associating arbitrary data with #GObjects,
 102  * using g_object_set_data() and related functions.
 103  *
 104  * To create a datalist, use g_datalist_init().
 105  *
 106  * To add data elements to a datalist use g_datalist_id_set_data(),
 107  * g_datalist_id_set_data_full(), g_datalist_set_data() and
 108  * g_datalist_set_data_full().
 109  *
 110  * To get data elements from a datalist use g_datalist_id_get_data()
 111  * and g_datalist_get_data().
 112  *
 113  * To iterate over all data elements in a datalist use
 114  * g_datalist_foreach() (not thread-safe).
 115  *
 116  * To remove data elements from a datalist use
 117  * g_datalist_id_remove_data() and g_datalist_remove_data().
 118  *
 119  * To remove all data elements from a datalist, use g_datalist_clear().
 120  **/
 121
 122 /**
 123  * GData:
 124  *
 125  * The #GData struct is an opaque data structure to represent a <link
 126  * linkend="glib-Keyed-Data-Lists">Keyed Data List</link>. It should
 127  * only be accessed via the following functions.
 128  **/
 129
 130 /**
 131  * GDestroyNotify:
 132  * @data: the data element.
 133  *
 134  * Specifies the type of function which is called when a data element
 135  * is destroyed. It is passed the pointer to the data element and
 136  * should free any memory and resources allocated for it.
 137  **/
 138
 139 /* --- defines --- */
 140 #define G_QUARK_BLOCK_SIZE                      (2048)
 141
 142 #define G_DATALIST_FLAGS_MASK_INTERNAL 0x7
 143
 144 /* datalist pointer accesses have to be carried out atomically */
 145 #define G_DATALIST_GET_POINTER(datalist)                                                \
 146   ((GData*) ((gsize) g_atomic_pointer_get (datalist) & ~(gsize) G_DATALIST_FLAGS_MASK_INTERNAL))
 147
 148 #define G_DATALIST_SET_POINTER(datalist, pointer)       G_STMT_START {                  \
 149   gpointer _oldv, _newv;                                                                \
 150   do {                                                                                  \
 151     _oldv = g_atomic_pointer_get (datalist);                                            \
 152     _newv = (gpointer) (((gsize) _oldv & G_DATALIST_FLAGS_MASK_INTERNAL) | (gsize) pointer);     \
 153   } while (!g_atomic_pointer_compare_and_exchange ((void**) datalist, _oldv, _newv));   \
 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   gint 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:
 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   gint 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   register 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   register 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: 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       register 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 /**
 493  * g_dataset_id_set_data_full:
 494  * @dataset_location: the location identifying the dataset.
 495  * @key_id: the #GQuark id to identify the data element.
 496  * @data: the data element.
 497  * @destroy_func: the function to call when the data element is
 498  *                removed. This function will be called with the data
 499  *                element and can be used to free any memory allocated
 500  *                for it.
 501  *
 502  * Sets the data element associated with the given #GQuark id, and also
 503  * the function to call when the data element is destroyed. Any
 504  * previous data with the same key is removed, and its destroy function
 505  * is called.
 506  **/
 507 /**
 508  * g_dataset_set_data_full:
 509  * @l: the location identifying the dataset.
 510  * @k: the string to identify the data element.
 511  * @d: the data element.
 512  * @f: the function to call when the data element is removed. This
 513  *     function will be called with the data element and can be used to
 514  *     free any memory allocated for it.
 515  *
 516  * Sets the data corresponding to the given string identifier, and the
 517  * function to call when the data element is destroyed.
 518  **/
 519 /**
 520  * g_dataset_id_set_data:
 521  * @l: the location identifying the dataset.
 522  * @k: the #GQuark id to identify the data element.
 523  * @d: the data element.
 524  *
 525  * Sets the data element associated with the given #GQuark id. Any
 526  * previous data with the same key is removed, and its destroy function
 527  * is called.
 528  **/
 529 /**
 530  * g_dataset_set_data:
 531  * @l: the location identifying the dataset.
 532  * @k: the string to identify the data element.
 533  * @d: the data element.
 534  *
 535  * Sets the data corresponding to the given string identifier.
 536  **/
 537 /**
 538  * g_dataset_id_remove_data:
 539  * @l: the location identifying the dataset.
 540  * @k: the #GQuark id identifying the data element.
 541  *
 542  * Removes a data element from a dataset. The data element's destroy
 543  * function is called if it has been set.
 544  **/
 545 /**
 546  * g_dataset_remove_data:
 547  * @l: the location identifying the dataset.
 548  * @k: the string identifying the data element.
 549  *
 550  * Removes a data element corresponding to a string. Its destroy
 551  * function is called if it has been set.
 552  **/
 553 void
 554 g_dataset_id_set_data_full (gconstpointer  dataset_location,
 555                             GQuark         key_id,
 556                             gpointer       data,
 557                             GDestroyNotify destroy_func)
 558 {
 559   register GDataset *dataset;
 560
 561   g_return_if_fail (dataset_location != NULL);
 562   if (!data)
 563     g_return_if_fail (destroy_func == NULL);
 564   if (!key_id)
 565     {
 566       if (data)
 567         g_return_if_fail (key_id > 0);
 568       else
 569         return;
 570     }
 571
 572   G_LOCK (g_dataset_global);
 573   if (!g_dataset_location_ht)
 574     g_data_initialize ();
 575
 576   dataset = g_dataset_lookup (dataset_location);
 577   if (!dataset)
 578     {
 579       dataset = g_slice_new (GDataset);
 580       dataset->location = dataset_location;
 581       g_datalist_init (&dataset->datalist);
 582       g_hash_table_insert (g_dataset_location_ht,
 583                            (gpointer) dataset->location,
 584                            dataset);
 585     }
 586
 587   g_data_set_internal (&dataset->datalist, key_id, data, destroy_func, dataset);
 588   G_UNLOCK (g_dataset_global);
 589 }
 590
 591 /**
 592  * g_datalist_id_set_data_full:
 593  * @datalist: a datalist.
 594  * @key_id: the #GQuark to identify the data element.
 595  * @data: (allow-none): the data element or %NULL to remove any previous element
 596  *        corresponding to @key_id.
 597  * @destroy_func: the function to call when the data element is
 598  *                removed. This function will be called with the data
 599  *                element and can be used to free any memory allocated
 600  *                for it. If @data is %NULL, then @destroy_func must
 601  *                also be %NULL.
 602  *
 603  * Sets the data corresponding to the given #GQuark id, and the
 604  * function to be called when the element is removed from the datalist.
 605  * Any previous data with the same key is removed, and its destroy
 606  * function is called.
 607  **/
 608 /**
 609  * g_datalist_set_data_full:
 610  * @dl: a datalist.
 611  * @k: the string to identify the data element.
 612  * @d: (allow-none): the data element, or %NULL to remove any previous element
 613  *     corresponding to @k.
 614  * @f: the function to call when the data element is removed. This
 615  *     function will be called with the data element and can be used to
 616  *     free any memory allocated for it. If @d is %NULL, then @f must
 617  *     also be %NULL.
 618  *
 619  * Sets the data element corresponding to the given string identifier,
 620  * and the function to be called when the data element is removed.
 621  **/
 622 /**
 623  * g_datalist_id_set_data:
 624  * @dl: a datalist.
 625  * @q: the #GQuark to identify the data element.
 626  * @d: (allow-none): the data element, or %NULL to remove any previous element
 627  *     corresponding to @q.
 628  *
 629  * Sets the data corresponding to the given #GQuark id. Any previous
 630  * data with the same key is removed, and its destroy function is
 631  * called.
 632  **/
 633 /**
 634  * g_datalist_set_data:
 635  * @dl: a datalist.
 636  * @k: the string to identify the data element.
 637  * @d: (allow-none): the data element, or %NULL to remove any previous element
 638  *     corresponding to @k.
 639  *
 640  * Sets the data element corresponding to the given string identifier.
 641  **/
 642 /**
 643  * g_datalist_id_remove_data:
 644  * @dl: a datalist.
 645  * @q: the #GQuark identifying the data element.
 646  *
 647  * Removes an element, using its #GQuark identifier.
 648  **/
 649 /**
 650  * g_datalist_remove_data:
 651  * @dl: a datalist.
 652  * @k: the string identifying the data element.
 653  *
 654  * Removes an element using its string identifier. The data element's
 655  * destroy function is called if it has been set.
 656  **/
 657 void
 658 g_datalist_id_set_data_full (GData        **datalist,
 659                              GQuark         key_id,
 660                              gpointer       data,
 661                              GDestroyNotify destroy_func)
 662 {
 663   g_return_if_fail (datalist != NULL);
 664   if (!data)
 665     g_return_if_fail (destroy_func == NULL);
 666   if (!key_id)
 667     {
 668       if (data)
 669         g_return_if_fail (key_id > 0);
 670       else
 671         return;
 672     }
 673
 674   g_data_set_internal (datalist, key_id, data, destroy_func, NULL);
 675 }
 676
 677 /**
 678  * g_dataset_id_remove_no_notify:
 679  * @dataset_location: the location identifying the dataset.
 680  * @key_id: the #GQuark ID identifying the data element.
 681  * @Returns: the data previously stored at @key_id, or %NULL if none.
 682  *
 683  * Removes an element, without calling its destroy notification
 684  * function.
 685  **/
 686 /**
 687  * g_dataset_remove_no_notify:
 688  * @l: the location identifying the dataset.
 689  * @k: the string identifying the data element.
 690  *
 691  * Removes an element, without calling its destroy notifier.
 692  **/
 693 gpointer
 694 g_dataset_id_remove_no_notify (gconstpointer  dataset_location,
 695                                GQuark         key_id)
 696 {
 697   gpointer ret_data = NULL;
 698
 699   g_return_val_if_fail (dataset_location != NULL, NULL);
 700
 701   G_LOCK (g_dataset_global);
 702   if (key_id && g_dataset_location_ht)
 703     {
 704       GDataset *dataset;
 705
 706       dataset = g_dataset_lookup (dataset_location);
 707       if (dataset)
 708         ret_data = g_data_set_internal (&dataset->datalist, key_id, NULL, (GDestroyNotify) 42, dataset);
 709     }
 710   G_UNLOCK (g_dataset_global);
 711
 712   return ret_data;
 713 }
 714
 715 /**
 716  * g_datalist_id_remove_no_notify:
 717  * @datalist: a datalist.
 718  * @key_id: the #GQuark identifying a data element.
 719  * @Returns: the data previously stored at @key_id, or %NULL if none.
 720  *
 721  * Removes an element, without calling its destroy notification
 722  * function.
 723  **/
 724 /**
 725  * g_datalist_remove_no_notify:
 726  * @dl: a datalist.
 727  * @k: the string identifying the data element.
 728  *
 729  * Removes an element, without calling its destroy notifier.
 730  **/
 731 gpointer
 732 g_datalist_id_remove_no_notify (GData   **datalist,
 733                                 GQuark    key_id)
 734 {
 735   gpointer ret_data = NULL;
 736
 737   g_return_val_if_fail (datalist != NULL, NULL);
 738
 739   if (key_id)
 740     ret_data = g_data_set_internal (datalist, key_id, NULL, (GDestroyNotify) 42, NULL);
 741
 742   return ret_data;
 743 }
 744
 745 /**
 746  * g_dataset_id_get_data:
 747  * @dataset_location: the location identifying the dataset.
 748  * @key_id: the #GQuark id to identify the data element.
 749  * @Returns: the data element corresponding to the #GQuark, or %NULL if
 750  *           it is not found.
 751  *
 752  * Gets the data element corresponding to a #GQuark.
 753  **/
 754 /**
 755  * g_dataset_get_data:
 756  * @l: the location identifying the dataset.
 757  * @k: the string identifying the data element.
 758  * @Returns: the data element corresponding to the string, or %NULL if
 759  *           it is not found.
 760  *
 761  * Gets the data element corresponding to a string.
 762  **/
 763 gpointer
 764 g_dataset_id_get_data (gconstpointer  dataset_location,
 765                        GQuark         key_id)
 766 {
 767   gpointer retval = NULL;
 768
 769   g_return_val_if_fail (dataset_location != NULL, NULL);
 770
 771   G_LOCK (g_dataset_global);
 772   if (key_id && g_dataset_location_ht)
 773     {
 774       GDataset *dataset;
 775
 776       dataset = g_dataset_lookup (dataset_location);
 777       if (dataset)
 778         retval = g_datalist_id_get_data (&dataset->datalist, key_id);
 779     }
 780   G_UNLOCK (g_dataset_global);
 781
 782   return retval;
 783 }
 784
 785 /**
 786  * g_datalist_id_get_data:
 787  * @datalist: a datalist.
 788  * @key_id: the #GQuark identifying a data element.
 789  *
 790  * Retrieves the data element corresponding to @key_id.
 791  *
 792  * Returns: the data element, or %NULL if it is not found.
 793  */
 794 gpointer
 795 g_datalist_id_get_data (GData  **datalist,
 796                         GQuark   key_id)
 797 {
 798   return g_datalist_id_dup_data (datalist, key_id, NULL, NULL);
 799 }
 800
 801 /**
 802  * GDuplicateFunc:
 803  * @data: the data to duplicate
 804  *
 805  * The type of functions that are used to 'duplicate' an object.
 806  * What this means depends on the context, it could just be
 807  * incrementing the reference count, if @data is a ref-counted
 808  * object.
 809  *
 810  * Returns: a duplicate of data
 811  */
 812
 813 /**
 814  * g_datalist_id_dup_data:
 815  * @datalist: location of a datalist
 816  * @key_id: the #GQuark identifying a data element
 817  * @dup_func: (allow-none): function to duplicate the old value
 818  * @user_data: (allow-none): passed as user_data to @dup_func
 819  *
 820  * This is a variant of g_datalist_id_get_data() which
 821  * returns a 'duplicate' of the value. @dup_func defines the
 822  * meaning of 'duplicate' in this context, it could e.g.
 823  * take a reference on a ref-counted object.
 824  *
 825  * If the @key_id is not set in the datalist then @dup_func
 826  * will be called with a %NULL argument.
 827  *
 828  * Note that @dup_func is called while the datalist is locked, so it
 829  * is not allowed to read or modify the datalist.
 830  *
 831  * This function can be useful to avoid races when multiple
 832  * threads are using the same datalist and the same key.
 833  *
 834  * Returns: the result of calling @dup_func on the value
 835  *     associated with @key_id in @datalist, or %NULL if not set.
 836  *     If @dup_func is %NULL, the value is returned unmodified.
 837  *
 838  * Since: 2.34
 839  */
 840 gpointer
 841 g_datalist_id_dup_data (GData          **datalist,
 842                         GQuark           key_id,
 843                         GDuplicateFunc   dup_func,
 844                         gpointer         user_data)
 845 {
 846   gpointer val = NULL;
 847   gpointer retval = NULL;
 848   GData *d;
 849   GDataElt *data, *data_end;
 850
 851   g_return_val_if_fail (datalist != NULL, NULL);
 852   g_return_val_if_fail (key_id != 0, NULL);
 853
 854   g_datalist_lock (datalist);
 855
 856   d = G_DATALIST_GET_POINTER (datalist);
 857   if (d)
 858     {
 859       data = d->data;
 860       data_end = data + d->len - 1;
 861       while (data <= data_end)
 862         {
 863           if (data->key == key_id)
 864             {
 865               val = data->data;
 866               break;
 867             }
 868           data++;
 869         }
 870     }
 871
 872   if (dup_func)
 873     retval = dup_func (val, user_data);
 874   else
 875     retval = val;
 876
 877   g_datalist_unlock (datalist);
 878
 879   return retval;
 880 }
 881
 882 /**
 883  * g_datalist_id_replace_data:
 884  * @datalist: location of a datalist
 885  * @key_id: the #GQuark identifying a data element
 886  * @oldval: (allow-none): the old value to compare against
 887  * @newval: (allow-none): the new value to replace it with
 888  * @destroy: (allow-none): destroy notify for the new value
 889  * @old_destroy: (allow-none): destroy notify for the existing value
 890  *
 891  * Compares the member that is associated with @key_id in
 892  * @datalist to @oldval, and if they are the same, replace
 893  * @oldval with @newval.
 894  *
 895  * This is like a typical atomic compare-and-exchange
 896  * operation, for a member of @datalist.
 897  *
 898  * If the previous value was replaced then ownership of the
 899  * old value (@oldval) is passed to the caller, including
 900  * the registred destroy notify for it (passed out in @old_destroy).
 901  * Its up to the caller to free this as he wishes, which may
 902  * or may not include using @old_destroy as sometimes replacement
 903  * should not destroy the object in the normal way.
 904  *
 905  * Return: %TRUE if the existing value for @key_id was replaced
 906  *  by @newval, %FALSE otherwise.
 907  *
 908  * Since: 2.34
 909  */
 910 gboolean
 911 g_datalist_id_replace_data (GData          **datalist,
 912                             GQuark           key_id,
 913                             gpointer         oldval,
 914                             gpointer         newval,
 915                             GDestroyNotify   destroy,
 916                             GDestroyNotify  *old_destroy)
 917 {
 918   gpointer val = NULL;
 919   GData *d;
 920   GDataElt *data, *data_end;
 921
 922   g_return_val_if_fail (datalist != NULL, FALSE);
 923   g_return_val_if_fail (key_id != 0, FALSE);
 924
 925   if (old_destroy)
 926     *old_destroy = NULL;
 927
 928   g_datalist_lock (datalist);
 929
 930   d = G_DATALIST_GET_POINTER (datalist);
 931   if (d)
 932     {
 933       data = d->data;
 934       data_end = data + d->len - 1;
 935       while (data <= data_end)
 936         {
 937           if (data->key == key_id)
 938             {
 939               val = data->data;
 940               if (val == oldval)
 941                 {
 942                   if (old_destroy)
 943                     *old_destroy = data->destroy;
 944                   if (newval != NULL)
 945                     {
 946                       data->data = newval;
 947                       data->destroy = destroy;
 948                     }
 949                   else
 950                    {
 951                      if (data != data_end)
 952                        *data = *data_end;
 953                      d->len--;
 954
 955                      /* We don't bother to shrink, but if all data are now gone
 956                       * we at least free the memory
 957                       */
 958                      if (d->len == 0)
 959                        {
 960                          G_DATALIST_SET_POINTER (datalist, NULL);
 961                          g_free (d);
 962                        }
 963                    }
 964                 }
 965               break;
 966             }
 967           data++;
 968         }
 969     }
 970
 971   if (val == NULL && oldval == NULL && newval != NULL)
 972     {
 973       GData *old_d;
 974
 975       /* insert newval */
 976       old_d = d;
 977       if (d == NULL)
 978         {
 979           d = g_malloc (sizeof (GData));
 980           d->len = 0;
 981           d->alloc = 1;
 982         }
 983       else if (d->len == d->alloc)
 984         {
 985           d->alloc = d->alloc * 2;
 986           d = g_realloc (d, sizeof (GData) + (d->alloc - 1) * sizeof (GDataElt));
 987         }
 988       if (old_d != d)
 989         G_DATALIST_SET_POINTER (datalist, d);
 990
 991       d->data[d->len].key = key_id;
 992       d->data[d->len].data = newval;
 993       d->data[d->len].destroy = destroy;
 994       d->len++;
 995     }
 996
 997   g_datalist_unlock (datalist);
 998
 999   return val == oldval;
1000 }
1001
1002 /**
1003  * g_datalist_get_data:
1004  * @datalist: a datalist.
1005  * @key: the string identifying a data element.
1006  * @Returns: the data element, or %NULL if it is not found.
1007  *
1008  * Gets a data element, using its string identifier. This is slower than
1009  * g_datalist_id_get_data() because it compares strings.
1010  **/
1011 gpointer
1012 g_datalist_get_data (GData       **datalist,
1013                      const gchar *key)
1014 {
1015   gpointer res = NULL;
1016   GData *d;
1017   GDataElt *data, *data_end;
1018
1019   g_return_val_if_fail (datalist != NULL, NULL);
1020
1021   g_datalist_lock (datalist);
1022
1023   d = G_DATALIST_GET_POINTER (datalist);
1024   if (d)
1025     {
1026       data = d->data;
1027       data_end = data + d->len;
1028       while (data < data_end)
1029         {
1030           if (strcmp (g_quark_to_string (data->key), key) == 0)
1031             {
1032               res = data->data;
1033               break;
1034             }
1035           data++;
1036         }
1037     }
1038
1039   g_datalist_unlock (datalist);
1040
1041   return res;
1042 }
1043
1044 /**
1045  * GDataForeachFunc:
1046  * @key_id: the #GQuark id to identifying the data element.
1047  * @data: the data element.
1048  * @user_data: user data passed to g_dataset_foreach().
1049  *
1050  * Specifies the type of function passed to g_dataset_foreach(). It is
1051  * called with each #GQuark id and associated data element, together
1052  * with the @user_data parameter supplied to g_dataset_foreach().
1053  **/
1054
1055 /**
1056  * g_dataset_foreach:
1057  * @dataset_location: the location identifying the dataset.
1058  * @func: the function to call for each data element.
1059  * @user_data: user data to pass to the function.
1060  *
1061  * Calls the given function for each data element which is associated
1062  * with the given location. Note that this function is NOT thread-safe.
1063  * So unless @datalist can be protected from any modifications during
1064  * invocation of this function, it should not be called.
1065  **/
1066 void
1067 g_dataset_foreach (gconstpointer    dataset_location,
1068                    GDataForeachFunc func,
1069                    gpointer         user_data)
1070 {
1071   register GDataset *dataset;
1072
1073   g_return_if_fail (dataset_location != NULL);
1074   g_return_if_fail (func != NULL);
1075
1076   G_LOCK (g_dataset_global);
1077   if (g_dataset_location_ht)
1078     {
1079       dataset = g_dataset_lookup (dataset_location);
1080       G_UNLOCK (g_dataset_global);
1081       if (dataset)
1082         g_datalist_foreach (&dataset->datalist, func, user_data);
1083     }
1084   else
1085     {
1086       G_UNLOCK (g_dataset_global);
1087     }
1088 }
1089
1090 /**
1091  * g_datalist_foreach:
1092  * @datalist: a datalist.
1093  * @func: the function to call for each data element.
1094  * @user_data: user data to pass to the function.
1095  *
1096  * Calls the given function for each data element of the datalist. The
1097  * function is called with each data element's #GQuark id and data,
1098  * together with the given @user_data parameter. Note that this
1099  * function is NOT thread-safe. So unless @datalist can be protected
1100  * from any modifications during invocation of this function, it should
1101  * not be called.
1102  **/
1103 void
1104 g_datalist_foreach (GData          **datalist,
1105                     GDataForeachFunc func,
1106                     gpointer         user_data)
1107 {
1108   GData *d;
1109   int i, j, len;
1110   GQuark *keys;
1111
1112   g_return_if_fail (datalist != NULL);
1113   g_return_if_fail (func != NULL);
1114
1115   d = G_DATALIST_GET_POINTER (datalist);
1116   if (d == NULL)
1117     return;
1118
1119   /* We make a copy of the keys so that we can handle it changing
1120      in the callback */
1121   len = d->len;
1122   keys = g_new (GQuark, len);
1123   for (i = 0; i < len; i++)
1124     keys[i] = d->data[i].key;
1125
1126   for (i = 0; i < len; i++)
1127     {
1128       /* A previous callback might have removed a later item, so always check that
1129          it still exists before calling */
1130       d = G_DATALIST_GET_POINTER (datalist);
1131
1132       if (d == NULL)
1133         break;
1134       for (j = 0; j < d->len; j++)
1135         {
1136           if (d->data[j].key == keys[i]) {
1137             func (d->data[i].key, d->data[i].data, user_data);
1138             break;
1139           }
1140         }
1141     }
1142   g_free (keys);
1143 }
1144
1145 /**
1146  * g_datalist_init:
1147  * @datalist: a pointer to a pointer to a datalist.
1148  *
1149  * Resets the datalist to %NULL. It does not free any memory or call
1150  * any destroy functions.
1151  **/
1152 void
1153 g_datalist_init (GData **datalist)
1154 {
1155   g_return_if_fail (datalist != NULL);
1156
1157   g_atomic_pointer_set (datalist, NULL);
1158 }
1159
1160 /**
1161  * g_datalist_set_flags:
1162  * @datalist: pointer to the location that holds a list
1163  * @flags: the flags to turn on. The values of the flags are
1164  *   restricted by %G_DATALIST_FLAGS_MASK (currently
1165  *   3; giving two possible boolean flags).
1166  *   A value for @flags that doesn't fit within the mask is
1167  *   an error.
1168  *
1169  * Turns on flag values for a data list. This function is used
1170  * to keep a small number of boolean flags in an object with
1171  * a data list without using any additional space. It is
1172  * not generally useful except in circumstances where space
1173  * is very tight. (It is used in the base #GObject type, for
1174  * example.)
1175  *
1176  * Since: 2.8
1177  **/
1178 void
1179 g_datalist_set_flags (GData **datalist,
1180                       guint   flags)
1181 {
1182   g_return_if_fail (datalist != NULL);
1183   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
1184
1185   g_atomic_pointer_or (datalist, (gsize)flags);
1186 }
1187
1188 /**
1189  * g_datalist_unset_flags:
1190  * @datalist: pointer to the location that holds a list
1191  * @flags: the flags to turn off. The values of the flags are
1192  *   restricted by %G_DATALIST_FLAGS_MASK (currently
1193  *   3: giving two possible boolean flags).
1194  *   A value for @flags that doesn't fit within the mask is
1195  *   an error.
1196  *
1197  * Turns off flag values for a data list. See g_datalist_unset_flags()
1198  *
1199  * Since: 2.8
1200  **/
1201 void
1202 g_datalist_unset_flags (GData **datalist,
1203                         guint   flags)
1204 {
1205   g_return_if_fail (datalist != NULL);
1206   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
1207
1208   g_atomic_pointer_and (datalist, ~(gsize)flags);
1209 }
1210
1211 /**
1212  * g_datalist_get_flags:
1213  * @datalist: pointer to the location that holds a list
1214  *
1215  * Gets flags values packed in together with the datalist.
1216  * See g_datalist_set_flags().
1217  *
1218  * Return value: the flags of the datalist
1219  *
1220  * Since: 2.8
1221  **/
1222 guint
1223 g_datalist_get_flags (GData **datalist)
1224 {
1225   g_return_val_if_fail (datalist != NULL, 0);
1226
1227   return G_DATALIST_GET_FLAGS (datalist); /* atomic macro */
1228 }
1229
1230 /* HOLDS: g_dataset_global_lock */
1231 static void
1232 g_data_initialize (void)
1233 {
1234   g_return_if_fail (g_dataset_location_ht == NULL);
1235
1236   g_dataset_location_ht = g_hash_table_new (g_direct_hash, NULL);
1237   g_dataset_cached = NULL;
1238 }