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  * Note that the quark name will be stringified automatically in the
 103  * macro, so you shouldn't use double quotes.
 104  *
 105  * Since: 2.34
 106  */
 107
 108 /**
 109  * g_quark_try_string:
 110  * @string: (allow-none): a string.
 111  * @Returns: the #GQuark associated with the string, or 0 if @string is
 112  *           %NULL or there is no #GQuark associated with it.
 113  *
 114  * Gets the #GQuark associated with the given string, or 0 if string is
 115  * %NULL or it has no associated #GQuark.
 116  *
 117  * If you want the GQuark to be created if it doesn't already exist,
 118  * use g_quark_from_string() or g_quark_from_static_string().
 119  **/
 120 GQuark
 121 g_quark_try_string (const gchar *string)
 122 {
 123   GQuark quark = 0;
 124
 125   if (string == NULL)
 126     return 0;
 127
 128   G_LOCK (quark_global);
 129   if (quark_ht)
 130     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 131   G_UNLOCK (quark_global);
 132
 133   return quark;
 134 }
 135
 136 /* HOLDS: quark_global_lock */
 137 static char *
 138 quark_strdup (const gchar *string)
 139 {
 140   gchar *copy;
 141   gsize len;
 142
 143   len = strlen (string) + 1;
 144
 145   /* For strings longer than half the block size, fall back
 146      to strdup so that we fill our blocks at least 50%. */
 147   if (len > QUARK_STRING_BLOCK_SIZE / 2)
 148     return g_strdup (string);
 149
 150   if (quark_block == NULL ||
 151       QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
 152     {
 153       quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
 154       quark_block_offset = 0;
 155     }
 156
 157   copy = quark_block + quark_block_offset;
 158   memcpy (copy, string, len);
 159   quark_block_offset += len;
 160
 161   return copy;
 162 }
 163
 164 /* HOLDS: quark_global_lock */
 165 static inline GQuark
 166 quark_from_string (const gchar *string,
 167                    gboolean     duplicate)
 168 {
 169   GQuark quark = 0;
 170
 171   if (quark_ht)
 172     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 173
 174   if (!quark)
 175     {
 176       quark = quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
 177       TRACE(GLIB_QUARK_NEW(string, quark));
 178     }
 179
 180   return quark;
 181 }
 182
 183 /**
 184  * g_quark_from_string:
 185  * @string: (allow-none): a string.
 186  *
 187  * Gets the #GQuark identifying the given string. If the string does
 188  * not currently have an associated #GQuark, a new #GQuark is created,
 189  * using a copy of the string.
 190  *
 191  * Returns: the #GQuark identifying the string, or 0 if @string is
 192  *     %NULL.
 193  */
 194 GQuark
 195 g_quark_from_string (const gchar *string)
 196 {
 197   GQuark quark;
 198
 199   if (!string)
 200     return 0;
 201
 202   G_LOCK (quark_global);
 203   quark = quark_from_string (string, TRUE);
 204   G_UNLOCK (quark_global);
 205
 206   return quark;
 207 }
 208
 209 /**
 210  * g_quark_from_static_string:
 211  * @string: (allow-none): a string.
 212  *
 213  * Gets the #GQuark identifying the given (static) string. If the
 214  * string does not currently have an associated #GQuark, a new #GQuark
 215  * is created, linked to the given string.
 216  *
 217  * Note that this function is identical to g_quark_from_string() except
 218  * that if a new #GQuark is created the string itself is used rather
 219  * than a copy. This saves memory, but can only be used if the string
 220  * will <emphasis>always</emphasis> exist. It can be used with
 221  * statically allocated strings in the main program, but not with
 222  * statically allocated memory in dynamically loaded modules, if you
 223  * expect to ever unload the module again (e.g. do not use this
 224  * function in GTK+ theme engines).
 225  *
 226  * Returns: the #GQuark identifying the string, or 0 if @string is
 227  *     %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 }