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