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   g_return_if_fail (datalist != NULL);
 996   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
 997
 998   g_atomic_pointer_or (datalist, (gsize)flags);
 999 }
1000
1001 /**
1002  * g_datalist_unset_flags:
1003  * @datalist: pointer to the location that holds a list
1004  * @flags: the flags to turn off. The values of the flags are
1005  *   restricted by %G_DATALIST_FLAGS_MASK (currently
1006  *   3: giving two possible boolean flags).
1007  *   A value for @flags that doesn't fit within the mask is
1008  *   an error.
1009  *
1010  * Turns off flag values for a data list. See g_datalist_unset_flags()
1011  *
1012  * Since: 2.8
1013  **/
1014 void
1015 g_datalist_unset_flags (GData **datalist,
1016                         guint   flags)
1017 {
1018   g_return_if_fail (datalist != NULL);
1019   g_return_if_fail ((flags & ~G_DATALIST_FLAGS_MASK) == 0);
1020
1021   g_atomic_pointer_and (datalist, ~(gsize)flags);
1022 }
1023
1024 /**
1025  * g_datalist_get_flags:
1026  * @datalist: pointer to the location that holds a list
1027  *
1028  * Gets flags values packed in together with the datalist.
1029  * See g_datalist_set_flags().
1030  *
1031  * Return value: the flags of the datalist
1032  *
1033  * Since: 2.8
1034  **/
1035 guint
1036 g_datalist_get_flags (GData **datalist)
1037 {
1038   g_return_val_if_fail (datalist != NULL, 0);
1039
1040   return G_DATALIST_GET_FLAGS (datalist); /* atomic macro */
1041 }
1042
1043 /* HOLDS: g_dataset_global_lock */
1044 static void
1045 g_data_initialize (void)
1046 {
1047   g_return_if_fail (g_dataset_location_ht == NULL);
1048
1049   g_dataset_location_ht = g_hash_table_new (g_direct_hash, NULL);
1050   g_dataset_cached = NULL;
1051 }
1052
1053 /**
1054  * SECTION:quarks
1055  * @title: Quarks
1056  * @short_description: a 2-way association between a string and a
1057  *                     unique integer identifier
1058  *
1059  * Quarks are associations between strings and integer identifiers.
1060  * Given either the string or the #GQuark identifier it is possible to
1061  * retrieve the other.
1062  *
1063  * Quarks are used for both <link
1064  * linkend="glib-Datasets">Datasets</link> and <link
1065  * linkend="glib-Keyed-Data-Lists">Keyed Data Lists</link>.
1066  *
1067  * To create a new quark from a string, use g_quark_from_string() or
1068  * g_quark_from_static_string().
1069  *
1070  * To find the string corresponding to a given #GQuark, use
1071  * g_quark_to_string().
1072  *
1073  * To find the #GQuark corresponding to a given string, use
1074  * g_quark_try_string().
1075  *
1076  * Another use for the string pool maintained for the quark functions
1077  * is string interning, using g_intern_string() or
1078  * g_intern_static_string(). An interned string is a canonical
1079  * representation for a string. One important advantage of interned
1080  * strings is that they can be compared for equality by a simple
1081  * pointer comparision, rather than using strcmp().
1082  **/
1083
1084 /**
1085  * GQuark:
1086  *
1087  * A GQuark is a non-zero integer which uniquely identifies a
1088  * particular string. A GQuark value of zero is associated to %NULL.
1089  **/
1090
1091 /**
1092  * g_quark_try_string:
1093  * @string: a string.
1094  * @Returns: the #GQuark associated with the string, or 0 if @string is
1095  *           %NULL or there is no #GQuark associated with it.
1096  *
1097  * Gets the #GQuark associated with the given string, or 0 if string is
1098  * %NULL or it has no associated #GQuark.
1099  *
1100  * If you want the GQuark to be created if it doesn't already exist,
1101  * use g_quark_from_string() or g_quark_from_static_string().
1102  **/
1103 GQuark
1104 g_quark_try_string (const gchar *string)
1105 {
1106   GQuark quark = 0;
1107
1108   if (string == NULL)
1109     return 0;
1110
1111   G_LOCK (g_quark_global);
1112   if (g_quark_ht)
1113     quark = GPOINTER_TO_UINT (g_hash_table_lookup (g_quark_ht, string));
1114   G_UNLOCK (g_quark_global);
1115
1116   return quark;
1117 }
1118
1119 #define QUARK_STRING_BLOCK_SIZE (4096 - sizeof (gsize))
1120 static char *quark_block = NULL;
1121 static int quark_block_offset = 0;
1122
1123 /* HOLDS: g_quark_global_lock */
1124 static char *
1125 quark_strdup(const gchar *string)
1126 {
1127   gchar *copy;
1128   gsize len;
1129
1130   len = strlen (string) + 1;
1131
1132   /* For strings longer than half the block size, fall back
1133      to strdup so that we fill our blocks at least 50%. */
1134   if (len > QUARK_STRING_BLOCK_SIZE / 2)
1135     return g_strdup (string);
1136
1137   if (quark_block == NULL ||
1138       QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
1139     {
1140       quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
1141       quark_block_offset = 0;
1142     }
1143
1144   copy = quark_block + quark_block_offset;
1145   memcpy (copy, string, len);
1146   quark_block_offset += len;
1147
1148   return copy;
1149 }
1150
1151 /* HOLDS: g_quark_global_lock */
1152 static inline GQuark
1153 g_quark_from_string_internal (const gchar *string,
1154                               gboolean     duplicate)
1155 {
1156   GQuark quark = 0;
1157
1158   if (g_quark_ht)
1159     quark = GPOINTER_TO_UINT (g_hash_table_lookup (g_quark_ht, string));
1160
1161   if (!quark)
1162     {
1163       quark = g_quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
1164       TRACE(GLIB_QUARK_NEW(string, quark));
1165     }
1166
1167   return quark;
1168 }
1169
1170 /**
1171  * g_quark_from_string:
1172  * @string: a string.
1173  * @Returns: the #GQuark identifying the string, or 0 if @string is
1174  *           %NULL.
1175  *
1176  * Gets the #GQuark identifying the given string. If the string does
1177  * not currently have an associated #GQuark, a new #GQuark is created,
1178  * using a copy of the string.
1179  **/
1180 GQuark
1181 g_quark_from_string (const gchar *string)
1182 {
1183   GQuark quark;
1184
1185   if (!string)
1186     return 0;
1187
1188   G_LOCK (g_quark_global);
1189   quark = g_quark_from_string_internal (string, TRUE);
1190   G_UNLOCK (g_quark_global);
1191
1192   return quark;
1193 }
1194
1195 /**
1196  * g_quark_from_static_string:
1197  * @string: a string.
1198  * @Returns: the #GQuark identifying the string, or 0 if @string is
1199  *           %NULL.
1200  *
1201  * Gets the #GQuark identifying the given (static) string. If the
1202  * string does not currently have an associated #GQuark, a new #GQuark
1203  * is created, linked to the given string.
1204  *
1205  * Note that this function is identical to g_quark_from_string() except
1206  * that if a new #GQuark is created the string itself is used rather
1207  * than a copy. This saves memory, but can only be used if the string
1208  * will <emphasis>always</emphasis> exist. It can be used with
1209  * statically allocated strings in the main program, but not with
1210  * statically allocated memory in dynamically loaded modules, if you
1211  * expect to ever unload the module again (e.g. do not use this
1212  * function in GTK+ theme engines).
1213  **/
1214 GQuark
1215 g_quark_from_static_string (const gchar *string)
1216 {
1217   GQuark quark;
1218
1219   if (!string)
1220     return 0;
1221
1222   G_LOCK (g_quark_global);
1223   quark = g_quark_from_string_internal (string, FALSE);
1224   G_UNLOCK (g_quark_global);
1225
1226   return quark;
1227 }
1228
1229 /**
1230  * g_quark_to_string:
1231  * @quark: a #GQuark.
1232  * @Returns: the string associated with the #GQuark.
1233  *
1234  * Gets the string associated with the given #GQuark.
1235  **/
1236 G_CONST_RETURN gchar*
1237 g_quark_to_string (GQuark quark)
1238 {
1239   gchar* result = NULL;
1240   gchar **quarks;
1241   gint quark_seq_id;
1242
1243   quark_seq_id = g_atomic_int_get (&g_quark_seq_id);
1244   quarks = g_atomic_pointer_get (&g_quarks);
1245
1246   if (quark < quark_seq_id)
1247     result = quarks[quark];
1248
1249   return result;
1250 }
1251
1252 /* HOLDS: g_quark_global_lock */
1253 static inline GQuark
1254 g_quark_new (gchar *string)
1255 {
1256   GQuark quark;
1257   gchar **g_quarks_new;
1258
1259   if (g_quark_seq_id % G_QUARK_BLOCK_SIZE == 0)
1260     {
1261       g_quarks_new = g_new (gchar*, g_quark_seq_id + G_QUARK_BLOCK_SIZE);
1262       if (g_quark_seq_id != 0)
1263         memcpy (g_quarks_new, g_quarks, sizeof (char *) * g_quark_seq_id);
1264       memset (g_quarks_new + g_quark_seq_id, 0, sizeof (char *) * G_QUARK_BLOCK_SIZE);
1265       /* This leaks the old quarks array. Its unfortunate, but it allows
1266          us to do lockless lookup of the arrays, and there shouldn't be that
1267          many quarks in an app */
1268       g_atomic_pointer_set (&g_quarks, g_quarks_new);
1269     }
1270   if (!g_quark_ht)
1271     {
1272       g_assert (g_quark_seq_id == 0);
1273       g_quark_ht = g_hash_table_new (g_str_hash, g_str_equal);
1274       g_quarks[g_quark_seq_id] = NULL;
1275       g_atomic_int_inc (&g_quark_seq_id);
1276     }
1277
1278   quark = g_quark_seq_id;
1279   g_atomic_pointer_set (&g_quarks[quark], string);
1280   g_hash_table_insert (g_quark_ht, string, GUINT_TO_POINTER (quark));
1281   g_atomic_int_inc (&g_quark_seq_id);
1282
1283   return quark;
1284 }
1285
1286 /**
1287  * g_intern_string:
1288  * @string: a string
1289  *
1290  * Returns a canonical representation for @string. Interned strings can
1291  * be compared for equality by comparing the pointers, instead of using strcmp().
1292  *
1293  * Returns: a canonical representation for the string
1294  *
1295  * Since: 2.10
1296  */
1297 G_CONST_RETURN gchar*
1298 g_intern_string (const gchar *string)
1299 {
1300   const gchar *result;
1301   GQuark quark;
1302
1303   if (!string)
1304     return NULL;
1305
1306   G_LOCK (g_quark_global);
1307   quark = g_quark_from_string_internal (string, TRUE);
1308   result = g_quarks[quark];
1309   G_UNLOCK (g_quark_global);
1310
1311   return result;
1312 }
1313
1314 /**
1315  * g_intern_static_string:
1316  * @string: a static string
1317  *
1318  * Returns a canonical representation for @string. Interned strings can
1319  * be compared for equality by comparing the pointers, instead of using strcmp().
1320  * g_intern_static_string() does not copy the string, therefore @string must
1321  * not be freed or modified.
1322  *
1323  * Returns: a canonical representation for the string
1324  *
1325  * Since: 2.10
1326  */
1327 G_CONST_RETURN gchar*
1328 g_intern_static_string (const gchar *string)
1329 {
1330   GQuark quark;
1331   const gchar *result;
1332
1333   if (!string)
1334     return NULL;
1335
1336   G_LOCK (g_quark_global);
1337   quark = g_quark_from_string_internal (string, FALSE);
1338   result = g_quarks[quark];
1339   G_UNLOCK (g_quark_global);
1340
1341   return result;
1342 }