glib/gdataset.c

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