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