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