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