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