glib/gquark.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  * Copyright (C) 1998 Tim Janik
   4  *
   5  * gquark.c: Functions for dealing with quarks and interned strings
   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, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21 /*
  22  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  23  * file for a list of people on the GLib Team.  See the ChangeLog
  24  * files for a list of changes.  These files are distributed with
  25  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  26  */
  27
  28 /*
  29  * MT safe
  30  */
  31
  32 #include "config.h"
  33
  34 #include <string.h>
  35
  36 #include "gslice.h"
  37 #include "ghash.h"
  38 #include "gquark.h"
  39 #include "gstrfuncs.h"
  40 #include "gthread.h"
  41 #include "gtestutils.h"
  42 #include "glib_trace.h"
  43
  44 #define QUARK_BLOCK_SIZE         2048
  45 #define QUARK_STRING_BLOCK_SIZE (4096 - sizeof (gsize))
  46
  47 static inline GQuark  quark_new (gchar *string);
  48
  49 G_LOCK_DEFINE_STATIC (quark_global);
  50 static GHashTable    *quark_ht = NULL;
  51 static gchar        **quarks = NULL;
  52 static gint           quark_seq_id = 0;
  53 static gchar         *quark_block = NULL;
  54 static gint           quark_block_offset = 0;
  55
  56 /**
  57  * SECTION:quarks
  58  * @title: Quarks
  59  * @short_description: a 2-way association between a string and a
  60  *     unique integer identifier
  61  *
  62  * Quarks are associations between strings and integer identifiers.
  63  * Given either the string or the #GQuark identifier it is possible to
  64  * retrieve the other.
  65  *
  66  * Quarks are used for both [datasets][glib-Datasets] and
  67  * [keyed data lists][glib-Keyed-Data-Lists].
  68  *
  69  * To create a new quark from a string, use g_quark_from_string() or
  70  * g_quark_from_static_string().
  71  *
  72  * To find the string corresponding to a given #GQuark, use
  73  * g_quark_to_string().
  74  *
  75  * To find the #GQuark corresponding to a given string, use
  76  * g_quark_try_string().
  77  *
  78  * Another use for the string pool maintained for the quark functions
  79  * is string interning, using g_intern_string() or
  80  * g_intern_static_string(). An interned string is a canonical
  81  * representation for a string. One important advantage of interned
  82  * strings is that they can be compared for equality by a simple
  83  * pointer comparison, rather than using strcmp().
  84  */
  85
  86 /**
  87  * GQuark:
  88  *
  89  * A GQuark is a non-zero integer which uniquely identifies a
  90  * particular string. A GQuark value of zero is associated to %NULL.
  91  */
  92
  93 /**
  94  * G_DEFINE_QUARK:
  95  * @QN: the name to return a #GQuark for
  96  * @q_n: prefix for the function name
  97  *
  98  * A convenience macro which defines a function returning the
  99  * #GQuark for the name @QN. The function will be named
 100  * @q_n_quark().
 101  *
 102  * Note that the quark name will be stringified automatically
 103  * in the macro, so you shouldn't use double quotes.
 104  *
 105  * Since: 2.34
 106  */
 107
 108 /**
 109  * g_quark_try_string:
 110  * @string: (allow-none): a string
 111  *
 112  * Gets the #GQuark associated with the given string, or 0 if string is
 113  * %NULL or it has no associated #GQuark.
 114  *
 115  * If you want the GQuark to be created if it doesn't already exist,
 116  * use g_quark_from_string() or g_quark_from_static_string().
 117  *
 118  * Returns: the #GQuark associated with the string, or 0 if @string is
 119  *     %NULL or there is no #GQuark associated with it
 120  */
 121 GQuark
 122 g_quark_try_string (const gchar *string)
 123 {
 124   GQuark quark = 0;
 125
 126   if (string == NULL)
 127     return 0;
 128
 129   G_LOCK (quark_global);
 130   if (quark_ht)
 131     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 132   G_UNLOCK (quark_global);
 133
 134   return quark;
 135 }
 136
 137 /* HOLDS: quark_global_lock */
 138 static char *
 139 quark_strdup (const gchar *string)
 140 {
 141   gchar *copy;
 142   gsize len;
 143
 144   len = strlen (string) + 1;
 145
 146   /* For strings longer than half the block size, fall back
 147      to strdup so that we fill our blocks at least 50%. */
 148   if (len > QUARK_STRING_BLOCK_SIZE / 2)
 149     return g_strdup (string);
 150
 151   if (quark_block == NULL ||
 152       QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
 153     {
 154       quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
 155       quark_block_offset = 0;
 156     }
 157
 158   copy = quark_block + quark_block_offset;
 159   memcpy (copy, string, len);
 160   quark_block_offset += len;
 161
 162   return copy;
 163 }
 164
 165 /* HOLDS: quark_global_lock */
 166 static inline GQuark
 167 quark_from_string (const gchar *string,
 168                    gboolean     duplicate)
 169 {
 170   GQuark quark = 0;
 171
 172   if (quark_ht)
 173     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 174
 175   if (!quark)
 176     {
 177       quark = quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
 178       TRACE(GLIB_QUARK_NEW(string, quark));
 179     }
 180
 181   return quark;
 182 }
 183
 184 /**
 185  * g_quark_from_string:
 186  * @string: (allow-none): a string
 187  *
 188  * Gets the #GQuark identifying the given string. If the string does
 189  * not currently have an associated #GQuark, a new #GQuark is created,
 190  * using a copy of the string.
 191  *
 192  * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
 193  */
 194 GQuark
 195 g_quark_from_string (const gchar *string)
 196 {
 197   GQuark quark;
 198
 199   if (!string)
 200     return 0;
 201
 202   G_LOCK (quark_global);
 203   quark = quark_from_string (string, TRUE);
 204   G_UNLOCK (quark_global);
 205
 206   return quark;
 207 }
 208
 209 /**
 210  * g_quark_from_static_string:
 211  * @string: (allow-none): a string
 212  *
 213  * Gets the #GQuark identifying the given (static) string. If the
 214  * string does not currently have an associated #GQuark, a new #GQuark
 215  * is created, linked to the given string.
 216  *
 217  * Note that this function is identical to g_quark_from_string() except
 218  * that if a new #GQuark is created the string itself is used rather
 219  * than a copy. This saves memory, but can only be used if the string
 220  * will continue to exist until the program terminates. It can be used
 221  * with statically allocated strings in the main program, but not with
 222  * statically allocated memory in dynamically loaded modules, if you
 223  * expect to ever unload the module again (e.g. do not use this
 224  * function in GTK+ theme engines).
 225  *
 226  * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
 227  */
 228 GQuark
 229 g_quark_from_static_string (const gchar *string)
 230 {
 231   GQuark quark;
 232
 233   if (!string)
 234     return 0;
 235
 236   G_LOCK (quark_global);
 237   quark = quark_from_string (string, FALSE);
 238   G_UNLOCK (quark_global);
 239
 240   return quark;
 241 }
 242
 243 /**
 244  * g_quark_to_string:
 245  * @quark: a #GQuark.
 246  *
 247  * Gets the string associated with the given #GQuark.
 248  *
 249  * Returns: the string associated with the #GQuark
 250  */
 251 const gchar *
 252 g_quark_to_string (GQuark quark)
 253 {
 254   gchar* result = NULL;
 255   gchar **strings;
 256   gint seq_id;
 257
 258   seq_id = g_atomic_int_get (&quark_seq_id);
 259   strings = g_atomic_pointer_get (&quarks);
 260
 261   if (quark < seq_id)
 262     result = strings[quark];
 263
 264   return result;
 265 }
 266
 267 /* HOLDS: g_quark_global_lock */
 268 static inline GQuark
 269 quark_new (gchar *string)
 270 {
 271   GQuark quark;
 272   gchar **quarks_new;
 273
 274   if (quark_seq_id % QUARK_BLOCK_SIZE == 0)
 275     {
 276       quarks_new = g_new (gchar*, quark_seq_id + QUARK_BLOCK_SIZE);
 277       if (quark_seq_id != 0)
 278         memcpy (quarks_new, quarks, sizeof (char *) * quark_seq_id);
 279       memset (quarks_new + quark_seq_id, 0, sizeof (char *) * QUARK_BLOCK_SIZE);
 280       /* This leaks the old quarks array. Its unfortunate, but it allows
 281        * us to do lockless lookup of the arrays, and there shouldn't be that
 282        * many quarks in an app
 283        */
 284       g_atomic_pointer_set (&quarks, quarks_new);
 285     }
 286   if (!quark_ht)
 287     {
 288       g_assert (quark_seq_id == 0);
 289       quark_ht = g_hash_table_new (g_str_hash, g_str_equal);
 290       quarks[quark_seq_id] = NULL;
 291       g_atomic_int_inc (&quark_seq_id);
 292     }
 293
 294   quark = quark_seq_id;
 295   g_atomic_pointer_set (&quarks[quark], string);
 296   g_hash_table_insert (quark_ht, string, GUINT_TO_POINTER (quark));
 297   g_atomic_int_inc (&quark_seq_id);
 298
 299   return quark;
 300 }
 301
 302 /**
 303  * g_intern_string:
 304  * @string: (allow-none): a string
 305  *
 306  * Returns a canonical representation for @string. Interned strings
 307  * can be compared for equality by comparing the pointers, instead of
 308  * using strcmp().
 309  *
 310  * Returns: a canonical representation for the string
 311  *
 312  * Since: 2.10
 313  */
 314 const gchar *
 315 g_intern_string (const gchar *string)
 316 {
 317   const gchar *result;
 318   GQuark quark;
 319
 320   if (!string)
 321     return NULL;
 322
 323   G_LOCK (quark_global);
 324   quark = quark_from_string (string, TRUE);
 325   result = quarks[quark];
 326   G_UNLOCK (quark_global);
 327
 328   return result;
 329 }
 330
 331 /**
 332  * g_intern_static_string:
 333  * @string: (allow-none): a static string
 334  *
 335  * Returns a canonical representation for @string. Interned strings
 336  * can be compared for equality by comparing the pointers, instead of
 337  * using strcmp(). g_intern_static_string() does not copy the string,
 338  * therefore @string must not be freed or modified.
 339  *
 340  * Returns: a canonical representation for the string
 341  *
 342  * Since: 2.10
 343  */
 344 const gchar *
 345 g_intern_static_string (const gchar *string)
 346 {
 347   GQuark quark;
 348   const gchar *result;
 349
 350   if (!string)
 351     return NULL;
 352
 353   G_LOCK (quark_global);
 354   quark = quark_from_string (string, FALSE);
 355   result = quarks[quark];
 356   G_UNLOCK (quark_global);
 357
 358   return result;
 359 }