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  * GQuark:
  72  *
  73  * A GQuark is a non-zero integer which uniquely identifies a
  74  * particular string.
  75  *
  76  * A GQuark value of zero is associated to `NULL`.
  77  *
  78  * Given either the string or the `GQuark` identifier it is possible to
  79  * retrieve the other.
  80  *
  81  * Quarks are used for both
  82  * [datasets and keyed data lists](datalist-and-dataset.html).
  83  *
  84  * To create a new quark from a string, use [func@GLib.quark_from_string]
  85  * or [func@GLib.quark_from_static_string].
  86  *
  87  * To find the string corresponding to a given `GQuark`, use
  88  * [func@GLib.quark_to_string].
  89  *
  90  * To find the `GQuark` corresponding to a given string, use
  91  * [func@GLib.quark_try_string].
  92  *
  93  * Another use for the string pool maintained for the quark functions
  94  * is string interning, using [func@GLib.intern_string] or
  95  * [func@GLib.intern_static_string]. An interned string is a canonical
  96  * representation for a string. One important advantage of interned
  97  * strings is that they can be compared for equality by a simple
  98  * pointer comparison, rather than using `strcmp()`.
  99  */
 100
 101 /**
 102  * G_DEFINE_QUARK:
 103  * @QN: the name to return a #GQuark for
 104  * @q_n: prefix for the function name
 105  *
 106  * A convenience macro which defines a function returning the
 107  * #GQuark for the name @QN. The function will be named
 108  * @q_n_quark().
 109  *
 110  * Note that the quark name will be stringified automatically
 111  * in the macro, so you shouldn't use double quotes.
 112  *
 113  * Since: 2.34
 114  */
 115
 116 /**
 117  * g_quark_try_string:
 118  * @string: (nullable): a string
 119  *
 120  * Gets the #GQuark associated with the given string, or 0 if string is
 121  * %NULL or it has no associated #GQuark.
 122  *
 123  * If you want the GQuark to be created if it doesn't already exist,
 124  * use g_quark_from_string() or g_quark_from_static_string().
 125  *
 126  * This function must not be used before library constructors have finished
 127  * running.
 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  * This function must not be used before library constructors have finished
 218  * running. In particular, this means it cannot be used to initialize global
 219  * variables in C++.
 220  *
 221  * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
 222  */
 223 GQuark
 224 g_quark_from_string (const gchar *string)
 225 {
 226   return quark_from_string_locked (string, TRUE);
 227 }
 228
 229 /**
 230  * g_quark_from_static_string:
 231  * @string: (nullable): a string
 232  *
 233  * Gets the #GQuark identifying the given (static) string. If the
 234  * string does not currently have an associated #GQuark, a new #GQuark
 235  * is created, linked to the given string.
 236  *
 237  * Note that this function is identical to g_quark_from_string() except
 238  * that if a new #GQuark is created the string itself is used rather
 239  * than a copy. This saves memory, but can only be used if the string
 240  * will continue to exist until the program terminates. It can be used
 241  * with statically allocated strings in the main program, but not with
 242  * statically allocated memory in dynamically loaded modules, if you
 243  * expect to ever unload the module again (e.g. do not use this
 244  * function in GTK theme engines).
 245  *
 246  * This function must not be used before library constructors have finished
 247  * running. In particular, this means it cannot be used to initialize global
 248  * variables in C++.
 249  *
 250  * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
 251  */
 252 GQuark
 253 g_quark_from_static_string (const gchar *string)
 254 {
 255   return quark_from_string_locked (string, FALSE);
 256 }
 257
 258 /**
 259  * g_quark_to_string:
 260  * @quark: a #GQuark.
 261  *
 262  * Gets the string associated with the given #GQuark.
 263  *
 264  * Returns: the string associated with the #GQuark
 265  */
 266 const gchar *
 267 g_quark_to_string (GQuark quark)
 268 {
 269   gchar* result = NULL;
 270   gchar **strings;
 271   guint seq_id;
 272
 273   seq_id = (guint) g_atomic_int_get (&quark_seq_id);
 274   strings = g_atomic_pointer_get (&quarks);
 275
 276   if (quark < seq_id)
 277     result = strings[quark];
 278
 279   return result;
 280 }
 281
 282 /* HOLDS: g_quark_global_lock */
 283 static inline GQuark
 284 quark_new (gchar *string)
 285 {
 286   GQuark quark;
 287   gchar **quarks_new;
 288
 289   if (quark_seq_id % QUARK_BLOCK_SIZE == 0)
 290     {
 291       quarks_new = g_new (gchar*, quark_seq_id + QUARK_BLOCK_SIZE);
 292       if (quark_seq_id != 0)
 293         memcpy (quarks_new, quarks, sizeof (char *) * quark_seq_id);
 294       memset (quarks_new + quark_seq_id, 0, sizeof (char *) * QUARK_BLOCK_SIZE);
 295       /* This leaks the old quarks array. Its unfortunate, but it allows
 296        * us to do lockless lookup of the arrays, and there shouldn't be that
 297        * many quarks in an app
 298        */
 299       g_ignore_leak (g_atomic_pointer_get (&quarks));
 300       g_atomic_pointer_set (&quarks, quarks_new);
 301     }
 302
 303   quark = quark_seq_id;
 304   g_atomic_pointer_set (&quarks[quark], string);
 305   g_hash_table_insert (quark_ht, string, GUINT_TO_POINTER (quark));
 306   g_atomic_int_inc (&quark_seq_id);
 307
 308   return quark;
 309 }
 310
 311 static inline const gchar *
 312 quark_intern_string_locked (const gchar   *string,
 313                             gboolean       duplicate)
 314 {
 315   const gchar *result;
 316   GQuark quark;
 317
 318   if (!string)
 319     return NULL;
 320
 321   G_LOCK (quark_global);
 322   quark = quark_from_string (string, duplicate);
 323   result = quarks[quark];
 324   G_UNLOCK (quark_global);
 325
 326   return result;
 327 }
 328
 329 /**
 330  * g_intern_string:
 331  * @string: (nullable): a string
 332  *
 333  * Returns a canonical representation for @string. Interned strings
 334  * can be compared for equality by comparing the pointers, instead of
 335  * using strcmp().
 336  *
 337  * This function must not be used before library constructors have finished
 338  * running. In particular, this means it cannot be used to initialize global
 339  * variables in C++.
 340  *
 341  * Returns: a canonical representation for the string
 342  *
 343  * Since: 2.10
 344  */
 345 const gchar *
 346 g_intern_string (const gchar *string)
 347 {
 348   return quark_intern_string_locked (string, TRUE);
 349 }
 350
 351 /**
 352  * g_intern_static_string:
 353  * @string: (nullable): a static string
 354  *
 355  * Returns a canonical representation for @string. Interned strings
 356  * can be compared for equality by comparing the pointers, instead of
 357  * using strcmp(). g_intern_static_string() does not copy the string,
 358  * therefore @string must not be freed or modified.
 359  *
 360  * This function must not be used before library constructors have finished
 361  * running. In particular, this means it cannot be used to initialize global
 362  * variables in C++.
 363  *
 364  * Returns: a canonical representation for the string
 365  *
 366  * Since: 2.10
 367  */
 368 const gchar *
 369 g_intern_static_string (const gchar *string)
 370 {
 371   return quark_intern_string_locked (string, FALSE);
 372 }