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