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