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                      (2048)
 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 int           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 gpointer
 780 g_datalist_id_get_data (GData    **datalist,
 781                         GQuark     key_id)
 782 {
 783   gpointer res = NULL;
 784
 785   g_return_val_if_fail (datalist != NULL, NULL);
 786   if (key_id)
 787     {
 788       GData *d;
 789       GDataElt *data, *data_end;
 790
 791       g_datalist_lock (datalist);
 792
 793       d = G_DATALIST_GET_POINTER (datalist);
 794       if (d)
 795         {
 796           data = d->data;
 797           data_end = data + d->len;
 798           while (data < data_end)
 799             {
 800               if (data->key == key_id)
 801                 {
 802                   res = data->data;
 803                   break;
 804                 }
 805               data++;
 806             }
 807         }
 808
 809       g_datalist_unlock (datalist);
 810     }
 811
 812   return res;
 813 }
 814
 815 /**
 816  * g_datalist_get_data:
 817  * @dl: a datalist.
 818  * @k: the string identifying a data element.
 819  * @Returns: the data element, or %NULL if it is not found.
 820  *
 821  * Gets a data element, using its string identifer. This is slower than
 822  * g_datalist_id_get_data() because it compares strings.
 823  **/
 824 gpointer
 825 g_datalist_get_data (GData       **datalist,
 826                      const gchar *key)
 827 {
 828   gpointer res = NULL;
 829   GData *d;
 830   GDataElt *data, *data_end;
 831
 832   g_return_val_if_fail (datalist != NULL, NULL);
 833
 834   g_datalist_lock (datalist);
 835
 836   d = G_DATALIST_GET_POINTER (datalist);
 837   if (d)
 838     {
 839       data = d->data;
 840       data_end = data + d->len;
 841       while (data < data_end)
 842         {
 843           if (strcmp (g_quark_to_string (data->key), key) == 0)
 844             {
 845               res = data->data;
 846               break;
 847             }
 848           data++;
 849         }
 850     }
 851
 852   g_datalist_unlock (datalist);
 853
 854   return res;
 855 }
 856
 857 /**
 858  * GDataForeachFunc:
 859  * @key_id: the #GQuark id to identifying the data element.
 860  * @data: the data element.
 861  * @user_data: user data passed to g_dataset_foreach().
 862  *
 863  * Specifies the type of function passed to g_dataset_foreach(). It is
 864  * called with each #GQuark id and associated data element, together
 865  * with the @user_data parameter supplied to g_dataset_foreach().
 866  **/
 867
 868 /**
 869  * g_dataset_foreach:
 870  * @dataset_location: the location identifying the dataset.
 871  * @func: the function to call for each data element.
 872  * @user_data: user data to pass to the function.
 873  *
 874  * Calls the given function for each data element which is associated
 875  * with the given location. Note that this function is NOT thread-safe.
 876  * So unless @datalist can be protected from any modifications during
 877  * invocation of this function, it should not be called.
 878  **/
 879 void
 880 g_dataset_foreach (gconstpointer    dataset_location,
 881                    GDataForeachFunc func,
 882                    gpointer         user_data)
 883 {
 884   register GDataset *dataset;
 885
 886   g_return_if_fail (dataset_location != NULL);
 887   g_return_if_fail (func != NULL);
 888
 889   G_LOCK (g_dataset_global);
 890   if (g_dataset_location_ht)
 891     {
 892       dataset = g_dataset_lookup (dataset_location);
 893       G_UNLOCK (g_dataset_global);
 894       if (dataset)
 895         g_datalist_foreach (&dataset->datalist, func, user_data);
 896     }
 897   else
 898     {
 899       G_UNLOCK (g_dataset_global);
 900     }
 901 }
 902
 903 /**
 904  * g_datalist_foreach:
 905  * @datalist: a datalist.
 906  * @func: the function to call for each data element.
 907  * @user_data: user data to pass to the function.
 908  *
 909  * Calls the given function for each data element of the datalist. The
 910  * function is called with each data element's #GQuark id and data,
 911  * together with the given @user_data parameter. Note that this
 912  * function is NOT thread-safe. So unless @datalist can be protected
 913  * from any modifications during invocation of this function, it should
 914  * not be called.
 915  **/
 916 void
 917 g_datalist_foreach (GData          **datalist,
 918                     GDataForeachFunc func,
 919                     gpointer         user_data)
 920 {
 921   GData *d;
 922   int i, j, len;
 923   GQuark *keys;
 924
 925   g_return_if_fail (datalist != NULL);
 926   g_return_if_fail (func != NULL);
 927
 928   d = G_DATALIST_GET_POINTER (datalist);
 929   if (d == NULL)
 930     return;
 931
 932   /* We make a copy of the keys so that we can handle it changing
 933      in the callback */
 934   len = d->len;
 935   keys = g_new (GQuark, len);
 936   for (i = 0; i < len; i++)
 937     keys[i] = d->data[i].key;
 938
 939   for (i = 0; i < len; i++)
 940     {
 941       /* A previous callback might have removed a later item, so always check that
 942          it still exists before calling */
 943       d = G_DATALIST_GET_POINTER (datalist);
 944
 945       if (d == NULL)
 946         break;
 947       for (j = 0; j < d->len; j++)
 948         {
 949           if (d->data[j].key == keys[i]) {
 950             func (d->data[i].key, d->data[i].data, user_data);
 951             break;
 952           }
 953         }
 954     }
 955   g_free (keys);
 956 }
 957
 958 /**
 959  * g_datalist_init:
 960  * @datalist: a pointer to a pointer to a datalist.
 961  *
 962  * Resets the datalist to %NULL. It does not free any memory or call
 963  * any destroy functions.
 964  **/
 965 void
 966 g_datalist_init (GData **datalist)
 967 {
 968   g_return_if_fail (datalist != NULL);
 969
 970   g_atomic_pointer_set (datalist, NULL);
 971 }
 972
 973 /**
 974  * g_datalist_set_flags:
 975  * @datalist: pointer to the location that holds a list
 976  * @flags: the flags to turn on. The values of the flags are
 977  *   restricted by %G_DATALIST_FLAGS_MASK (currently
 978  *   3; giving two possible boolean flags).
 979  *   A value for @flags that doesn't fit within the mask is
 980  *   an error.
 981  *
 982  * Turns on flag values for a data list. This function is used
 983  * to keep a small number of boolean flags in an object with
 984  * a data list without using any additional space. It is
 985  * not generally useful except in circumstances where space
 986  * is very tight. (It is used in the base #GObject type, for
 987  * example.)
 988  *
 989  * Since: 2.8
 990  **/
 991 void
 992 g_datalist_set_flags (GData **datalist,
 993                       guint   flags)
 994 {
 995   gpointer oldvalue;
 996   g_return_if_fail (datalist != NULL);
 997   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
 998
 999   do
1000     {
1001       oldvalue = g_atomic_pointer_get (datalist);
1002     }
1003   while (!g_atomic_pointer_compare_and_exchange ((void**) datalist, oldvalue,
1004                                                  (gpointer) ((gsize) oldvalue | flags)));
1005 }
1006
1007 /**
1008  * g_datalist_unset_flags:
1009  * @datalist: pointer to the location that holds a list
1010  * @flags: the flags to turn off. The values of the flags are
1011  *   restricted by %G_DATALIST_FLAGS_MASK (currently
1012  *   3: giving two possible boolean flags).
1013  *   A value for @flags that doesn't fit within the mask is
1014  *   an error.
1015  *
1016  * Turns off flag values for a data list. See g_datalist_unset_flags()
1017  *
1018  * Since: 2.8
1019  **/
1020 void
1021 g_datalist_unset_flags (GData **datalist,
1022                         guint   flags)
1023 {
1024   gpointer oldvalue;
1025   g_return_if_fail (datalist != NULL);
1026   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
1027
1028   do
1029     {
1030       oldvalue = g_atomic_pointer_get (datalist);
1031     }
1032   while (!g_atomic_pointer_compare_and_exchange ((void**) datalist, oldvalue,
1033                                                  (gpointer) ((gsize) oldvalue & ~(gsize) flags)));
1034 }
1035
1036 /**
1037  * g_datalist_get_flags:
1038  * @datalist: pointer to the location that holds a list
1039  *
1040  * Gets flags values packed in together with the datalist.
1041  * See g_datalist_set_flags().
1042  *
1043  * Return value: the flags of the datalist
1044  *
1045  * Since: 2.8
1046  **/
1047 guint
1048 g_datalist_get_flags (GData **datalist)
1049 {
1050   g_return_val_if_fail (datalist != NULL, 0);
1051
1052   return G_DATALIST_GET_FLAGS (datalist); /* atomic macro */
1053 }
1054
1055 /* HOLDS: g_dataset_global_lock */
1056 static void
1057 g_data_initialize (void)
1058 {
1059   g_return_if_fail (g_dataset_location_ht == NULL);
1060
1061   g_dataset_location_ht = g_hash_table_new (g_direct_hash, NULL);
1062   g_dataset_cached = NULL;
1063 }
1064
1065 /**
1066  * SECTION:quarks
1067  * @title: Quarks
1068  * @short_description: a 2-way association between a string and a
1069  *                     unique integer identifier
1070  *
1071  * Quarks are associations between strings and integer identifiers.
1072  * Given either the string or the #GQuark identifier it is possible to
1073  * retrieve the other.
1074  *
1075  * Quarks are used for both <link
1076  * linkend="glib-datasets">Datasets</link> and <link
1077  * linkend="glib-keyed-data-lists">Keyed Data Lists</link>.
1078  *
1079  * To create a new quark from a string, use g_quark_from_string() or
1080  * g_quark_from_static_string().
1081  *
1082  * To find the string corresponding to a given #GQuark, use
1083  * g_quark_to_string().
1084  *
1085  * To find the #GQuark corresponding to a given string, use
1086  * g_quark_try_string().
1087  *
1088  * Another use for the string pool maintained for the quark functions
1089  * is string interning, using g_intern_string() or
1090  * g_intern_static_string(). An interned string is a canonical
1091  * representation for a string. One important advantage of interned
1092  * strings is that they can be compared for equality by a simple
1093  * pointer comparision, rather than using strcmp().
1094  **/
1095
1096 /**
1097  * GQuark:
1098  *
1099  * A GQuark is a non-zero integer which uniquely identifies a
1100  * particular string. A GQuark value of zero is associated to %NULL.
1101  **/
1102
1103 /**
1104  * g_quark_try_string:
1105  * @string: a string.
1106  * @Returns: the #GQuark associated with the string, or 0 if @string is
1107  *           %NULL or there is no #GQuark associated with it.
1108  *
1109  * Gets the #GQuark associated with the given string, or 0 if string is
1110  * %NULL or it has no associated #GQuark.
1111  *
1112  * If you want the GQuark to be created if it doesn't already exist,
1113  * use g_quark_from_string() or g_quark_from_static_string().
1114  **/
1115 GQuark
1116 g_quark_try_string (const gchar *string)
1117 {
1118   GQuark quark = 0;
1119
1120   if (string == NULL)
1121     return 0;
1122
1123   G_LOCK (g_quark_global);
1124   if (g_quark_ht)
1125     quark = GPOINTER_TO_UINT (g_hash_table_lookup (g_quark_ht, string));
1126   G_UNLOCK (g_quark_global);
1127
1128   return quark;
1129 }
1130
1131 #define QUARK_STRING_BLOCK_SIZE (4096 - sizeof (gsize))
1132 static char *quark_block = NULL;
1133 static int quark_block_offset = 0;
1134
1135 /* HOLDS: g_quark_global_lock */
1136 static char *
1137 quark_strdup(const gchar *string)
1138 {
1139   gchar *copy;
1140   gsize len;
1141
1142   len = strlen (string) + 1;
1143
1144   /* For strings longer than half the block size, fall back
1145      to strdup so that we fill our blocks at least 50%. */
1146   if (len > QUARK_STRING_BLOCK_SIZE / 2)
1147     return g_strdup (string);
1148
1149   if (quark_block == NULL ||
1150       QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
1151     {
1152       quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
1153       quark_block_offset = 0;
1154     }
1155
1156   copy = quark_block + quark_block_offset;
1157   memcpy (copy, string, len);
1158   quark_block_offset += len;
1159
1160   return copy;
1161 }
1162
1163 /* HOLDS: g_quark_global_lock */
1164 static inline GQuark
1165 g_quark_from_string_internal (const gchar *string,
1166                               gboolean     duplicate)
1167 {
1168   GQuark quark = 0;
1169
1170   if (g_quark_ht)
1171     quark = GPOINTER_TO_UINT (g_hash_table_lookup (g_quark_ht, string));
1172
1173   if (!quark)
1174     {
1175       quark = g_quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
1176       TRACE(GLIB_QUARK_NEW(string, quark));
1177     }
1178
1179   return quark;
1180 }
1181
1182 /**
1183  * g_quark_from_string:
1184  * @string: a string.
1185  * @Returns: the #GQuark identifying the string, or 0 if @string is
1186  *           %NULL.
1187  *
1188  * Gets the #GQuark identifying the given string. If the string does
1189  * not currently have an associated #GQuark, a new #GQuark is created,
1190  * using a copy of the string.
1191  **/
1192 GQuark
1193 g_quark_from_string (const gchar *string)
1194 {
1195   GQuark quark;
1196
1197   if (!string)
1198     return 0;
1199
1200   G_LOCK (g_quark_global);
1201   quark = g_quark_from_string_internal (string, TRUE);
1202   G_UNLOCK (g_quark_global);
1203
1204   return quark;
1205 }
1206
1207 /**
1208  * g_quark_from_static_string:
1209  * @string: a string.
1210  * @Returns: the #GQuark identifying the string, or 0 if @string is
1211  *           %NULL.
1212  *
1213  * Gets the #GQuark identifying the given (static) string. If the
1214  * string does not currently have an associated #GQuark, a new #GQuark
1215  * is created, linked to the given string.
1216  *
1217  * Note that this function is identical to g_quark_from_string() except
1218  * that if a new #GQuark is created the string itself is used rather
1219  * than a copy. This saves memory, but can only be used if the string
1220  * will <emphasis>always</emphasis> exist. It can be used with
1221  * statically allocated strings in the main program, but not with
1222  * statically allocated memory in dynamically loaded modules, if you
1223  * expect to ever unload the module again (e.g. do not use this
1224  * function in GTK+ theme engines).
1225  **/
1226 GQuark
1227 g_quark_from_static_string (const gchar *string)
1228 {
1229   GQuark quark;
1230
1231   if (!string)
1232     return 0;
1233
1234   G_LOCK (g_quark_global);
1235   quark = g_quark_from_string_internal (string, FALSE);
1236   G_UNLOCK (g_quark_global);
1237
1238   return quark;
1239 }
1240
1241 /**
1242  * g_quark_to_string:
1243  * @quark: a #GQuark.
1244  * @Returns: the string associated with the #GQuark.
1245  *
1246  * Gets the string associated with the given #GQuark.
1247  **/
1248 G_CONST_RETURN gchar*
1249 g_quark_to_string (GQuark quark)
1250 {
1251   gchar* result = NULL;
1252   gchar **quarks;
1253   gint quark_seq_id;
1254
1255   quark_seq_id = g_atomic_int_get (&g_quark_seq_id);
1256   quarks = g_atomic_pointer_get (&g_quarks);
1257
1258   if (quark < quark_seq_id)
1259     result = quarks[quark];
1260
1261   return result;
1262 }
1263
1264 /* HOLDS: g_quark_global_lock */
1265 static inline GQuark
1266 g_quark_new (gchar *string)
1267 {
1268   GQuark quark;
1269   gchar **g_quarks_new;
1270
1271   if (g_quark_seq_id % G_QUARK_BLOCK_SIZE == 0)
1272     {
1273       g_quarks_new = g_new (gchar*, g_quark_seq_id + G_QUARK_BLOCK_SIZE);
1274       if (g_quark_seq_id != 0)
1275         memcpy (g_quarks_new, g_quarks, sizeof (char *) * g_quark_seq_id);
1276       memset (g_quarks_new + g_quark_seq_id, 0, sizeof (char *) * G_QUARK_BLOCK_SIZE);
1277       /* This leaks the old quarks array. Its unfortunate, but it allows
1278          us to do lockless lookup of the arrays, and there shouldn't be that
1279          many quarks in an app */
1280       g_atomic_pointer_set (&g_quarks, g_quarks_new);
1281     }
1282   if (!g_quark_ht)
1283     {
1284       g_assert (g_quark_seq_id == 0);
1285       g_quark_ht = g_hash_table_new (g_str_hash, g_str_equal);
1286       g_quarks[g_quark_seq_id] = NULL;
1287       g_atomic_int_inc (&g_quark_seq_id);
1288     }
1289
1290   quark = g_quark_seq_id;
1291   g_atomic_pointer_set (&g_quarks[quark], string);
1292   g_hash_table_insert (g_quark_ht, string, GUINT_TO_POINTER (quark));
1293   g_atomic_int_inc (&g_quark_seq_id);
1294
1295   return quark;
1296 }
1297
1298 /**
1299  * g_intern_string:
1300  * @string: a string
1301  *
1302  * Returns a canonical representation for @string. Interned strings can
1303  * be compared for equality by comparing the pointers, instead of using strcmp().
1304  *
1305  * Returns: a canonical representation for the string
1306  *
1307  * Since: 2.10
1308  */
1309 G_CONST_RETURN gchar*
1310 g_intern_string (const gchar *string)
1311 {
1312   const gchar *result;
1313   GQuark quark;
1314
1315   if (!string)
1316     return NULL;
1317
1318   G_LOCK (g_quark_global);
1319   quark = g_quark_from_string_internal (string, TRUE);
1320   result = g_quarks[quark];
1321   G_UNLOCK (g_quark_global);
1322
1323   return result;
1324 }
1325
1326 /**
1327  * g_intern_static_string:
1328  * @string: a static string
1329  *
1330  * Returns a canonical representation for @string. Interned strings can
1331  * be compared for equality by comparing the pointers, instead of using strcmp().
1332  * g_intern_static_string() does not copy the string, therefore @string must
1333  * not be freed or modified.
1334  *
1335  * Returns: a canonical representation for the string
1336  *
1337  * Since: 2.10
1338  */
1339 G_CONST_RETURN gchar*
1340 g_intern_static_string (const gchar *string)
1341 {
1342   GQuark quark;
1343   const gchar *result;
1344
1345   if (!string)
1346     return NULL;
1347
1348   G_LOCK (g_quark_global);
1349   quark = g_quark_from_string_internal (string, FALSE);
1350   result = g_quarks[quark];
1351   G_UNLOCK (g_quark_global);
1352
1353   return result;
1354 }