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 #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 /**
 194  * g_quark_from_string:
 195  * @string: (nullable): a string
 196  *
 197  * Gets the #GQuark identifying the given string. If the string does
 198  * not currently have an associated #GQuark, a new #GQuark is created,
 199  * using a copy of the string.
 200  *
 201  * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
 202  */
 203 GQuark
 204 g_quark_from_string (const gchar *string)
 205 {
 206   GQuark quark;
 207
 208   if (!string)
 209     return 0;
 210
 211   G_LOCK (quark_global);
 212   quark = quark_from_string (string, TRUE);
 213   G_UNLOCK (quark_global);
 214
 215   return quark;
 216 }
 217
 218 /**
 219  * g_quark_from_static_string:
 220  * @string: (nullable): a string
 221  *
 222  * Gets the #GQuark identifying the given (static) string. If the
 223  * string does not currently have an associated #GQuark, a new #GQuark
 224  * is created, linked to the given string.
 225  *
 226  * Note that this function is identical to g_quark_from_string() except
 227  * that if a new #GQuark is created the string itself is used rather
 228  * than a copy. This saves memory, but can only be used if the string
 229  * will continue to exist until the program terminates. It can be used
 230  * with statically allocated strings in the main program, but not with
 231  * statically allocated memory in dynamically loaded modules, if you
 232  * expect to ever unload the module again (e.g. do not use this
 233  * function in GTK+ theme engines).
 234  *
 235  * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
 236  */
 237 GQuark
 238 g_quark_from_static_string (const gchar *string)
 239 {
 240   GQuark quark;
 241
 242   if (!string)
 243     return 0;
 244
 245   G_LOCK (quark_global);
 246   quark = quark_from_string (string, FALSE);
 247   G_UNLOCK (quark_global);
 248
 249   return quark;
 250 }
 251
 252 /**
 253  * g_quark_to_string:
 254  * @quark: a #GQuark.
 255  *
 256  * Gets the string associated with the given #GQuark.
 257  *
 258  * Returns: the string associated with the #GQuark
 259  */
 260 const gchar *
 261 g_quark_to_string (GQuark quark)
 262 {
 263   gchar* result = NULL;
 264   gchar **strings;
 265   gint seq_id;
 266
 267   seq_id = g_atomic_int_get (&quark_seq_id);
 268   strings = g_atomic_pointer_get (&quarks);
 269
 270   if (quark < seq_id)
 271     result = strings[quark];
 272
 273   return result;
 274 }
 275
 276 /* HOLDS: g_quark_global_lock */
 277 static inline GQuark
 278 quark_new (gchar *string)
 279 {
 280   GQuark quark;
 281   gchar **quarks_new;
 282
 283   if (quark_seq_id % QUARK_BLOCK_SIZE == 0)
 284     {
 285       quarks_new = g_new (gchar*, quark_seq_id + QUARK_BLOCK_SIZE);
 286       if (quark_seq_id != 0)
 287         memcpy (quarks_new, quarks, sizeof (char *) * quark_seq_id);
 288       memset (quarks_new + quark_seq_id, 0, sizeof (char *) * QUARK_BLOCK_SIZE);
 289       /* This leaks the old quarks array. Its unfortunate, but it allows
 290        * us to do lockless lookup of the arrays, and there shouldn't be that
 291        * many quarks in an app
 292        */
 293       g_atomic_pointer_set (&quarks, quarks_new);
 294     }
 295
 296   quark = quark_seq_id;
 297   g_atomic_pointer_set (&quarks[quark], string);
 298   g_hash_table_insert (quark_ht, string, GUINT_TO_POINTER (quark));
 299   g_atomic_int_inc (&quark_seq_id);
 300
 301   return quark;
 302 }
 303
 304 /**
 305  * g_intern_string:
 306  * @string: (nullable): a string
 307  *
 308  * Returns a canonical representation for @string. Interned strings
 309  * can be compared for equality by comparing the pointers, instead of
 310  * using strcmp().
 311  *
 312  * Returns: a canonical representation for the string
 313  *
 314  * Since: 2.10
 315  */
 316 const gchar *
 317 g_intern_string (const gchar *string)
 318 {
 319   const gchar *result;
 320   GQuark quark;
 321
 322   if (!string)
 323     return NULL;
 324
 325   G_LOCK (quark_global);
 326   quark = quark_from_string (string, TRUE);
 327   result = quarks[quark];
 328   G_UNLOCK (quark_global);
 329
 330   return result;
 331 }
 332
 333 /**
 334  * g_intern_static_string:
 335  * @string: (nullable): a static string
 336  *
 337  * Returns a canonical representation for @string. Interned strings
 338  * can be compared for equality by comparing the pointers, instead of
 339  * using strcmp(). g_intern_static_string() does not copy the string,
 340  * therefore @string must not be freed or modified.
 341  *
 342  * Returns: a canonical representation for the string
 343  *
 344  * Since: 2.10
 345  */
 346 const gchar *
 347 g_intern_static_string (const gchar *string)
 348 {
 349   GQuark quark;
 350   const gchar *result;
 351
 352   if (!string)
 353     return NULL;
 354
 355   G_LOCK (quark_global);
 356   quark = quark_from_string (string, FALSE);
 357   result = quarks[quark];
 358   G_UNLOCK (quark_global);
 359
 360   return result;
 361 }