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, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  20  */
  21
  22 /*
  23  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  24  * file for a list of people on the GLib Team.  See the ChangeLog
  25  * files for a list of changes.  These files are distributed with
  26  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  27  */
  28
  29 /*
  30  * MT safe
  31  */
  32
  33 #include "config.h"
  34
  35 #include <string.h>
  36
  37 #include "gslice.h"
  38 #include "ghash.h"
  39 #include "gquark.h"
  40 #include "gstrfuncs.h"
  41 #include "gthread.h"
  42 #include "gtestutils.h"
  43 #include "glib_trace.h"
  44
  45 #define QUARK_BLOCK_SIZE         2048
  46 #define QUARK_STRING_BLOCK_SIZE (4096 - sizeof (gsize))
  47
  48 static inline GQuark  quark_new (gchar *string);
  49
  50 G_LOCK_DEFINE_STATIC (quark_global);
  51 static GHashTable    *quark_ht = NULL;
  52 static gchar        **quarks = NULL;
  53 static gint           quark_seq_id = 0;
  54 static gchar         *quark_block = NULL;
  55 static gint           quark_block_offset = 0;
  56
  57 /**
  58  * SECTION:quarks
  59  * @title: Quarks
  60  * @short_description: a 2-way association between a string and a
  61  *                     unique integer identifier
  62  *
  63  * Quarks are associations between strings and integer identifiers.
  64  * Given either the string or the #GQuark identifier it is possible to
  65  * retrieve the other.
  66  *
  67  * Quarks are used for both <link
  68  * linkend="glib-Datasets">Datasets</link> and <link
  69  * linkend="glib-Keyed-Data-Lists">Keyed Data Lists</link>.
  70  *
  71  * To create a new quark from a string, use g_quark_from_string() or
  72  * g_quark_from_static_string().
  73  *
  74  * To find the string corresponding to a given #GQuark, use
  75  * g_quark_to_string().
  76  *
  77  * To find the #GQuark corresponding to a given string, use
  78  * g_quark_try_string().
  79  *
  80  * Another use for the string pool maintained for the quark functions
  81  * is string interning, using g_intern_string() or
  82  * g_intern_static_string(). An interned string is a canonical
  83  * representation for a string. One important advantage of interned
  84  * strings is that they can be compared for equality by a simple
  85  * pointer comparison, rather than using strcmp().
  86  **/
  87
  88 /**
  89  * GQuark:
  90  *
  91  * A GQuark is a non-zero integer which uniquely identifies a
  92  * particular string. A GQuark value of zero is associated to %NULL.
  93  **/
  94
  95 /**
  96  * G_DEFINE_QUARK:
  97  * @QN: the name to return a #GQuark for
  98  * @q_n: prefix for the function name
  99  *
 100  * A convenience macro which defines a function returning the
 101  * #GQuark for the name @QN. The function will be named
 102  * @q_n<!-- -->_quark().
 103  * Note that the quark name will be stringified automatically in the
 104  * 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  * @Returns: the #GQuark associated with the string, or 0 if @string is
 113  *           %NULL or there is no #GQuark associated with it.
 114  *
 115  * Gets the #GQuark associated with the given string, or 0 if string is
 116  * %NULL or it has no associated #GQuark.
 117  *
 118  * If you want the GQuark to be created if it doesn't already exist,
 119  * use g_quark_from_string() or g_quark_from_static_string().
 120  **/
 121 GQuark
 122 g_quark_try_string (const gchar *string)
 123 {
 124   GQuark quark = 0;
 125
 126   if (string == NULL)
 127     return 0;
 128
 129   G_LOCK (quark_global);
 130   if (quark_ht)
 131     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 132   G_UNLOCK (quark_global);
 133
 134   return quark;
 135 }
 136
 137 /* HOLDS: quark_global_lock */
 138 static char *
 139 quark_strdup (const gchar *string)
 140 {
 141   gchar *copy;
 142   gsize len;
 143
 144   len = strlen (string) + 1;
 145
 146   /* For strings longer than half the block size, fall back
 147      to strdup so that we fill our blocks at least 50%. */
 148   if (len > QUARK_STRING_BLOCK_SIZE / 2)
 149     return g_strdup (string);
 150
 151   if (quark_block == NULL ||
 152       QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
 153     {
 154       quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
 155       quark_block_offset = 0;
 156     }
 157
 158   copy = quark_block + quark_block_offset;
 159   memcpy (copy, string, len);
 160   quark_block_offset += len;
 161
 162   return copy;
 163 }
 164
 165 /* HOLDS: quark_global_lock */
 166 static inline GQuark
 167 quark_from_string (const gchar *string,
 168                    gboolean     duplicate)
 169 {
 170   GQuark quark = 0;
 171
 172   if (quark_ht)
 173     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 174
 175   if (!quark)
 176     {
 177       quark = quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
 178       TRACE(GLIB_QUARK_NEW(string, quark));
 179     }
 180
 181   return quark;
 182 }
 183
 184 /**
 185  * g_quark_from_string:
 186  * @string: (allow-none): a string.
 187  *
 188  * Gets the #GQuark identifying the given string. If the string does
 189  * not currently have an associated #GQuark, a new #GQuark is created,
 190  * using a copy of the string.
 191  *
 192  * Returns: the #GQuark identifying the string, or 0 if @string is
 193  *     %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 <emphasis>always</emphasis> exist. It can be used with
 222  * 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
 228  *     %NULL.
 229  */
 230 GQuark
 231 g_quark_from_static_string (const gchar *string)
 232 {
 233   GQuark quark;
 234
 235   if (!string)
 236     return 0;
 237
 238   G_LOCK (quark_global);
 239   quark = quark_from_string (string, FALSE);
 240   G_UNLOCK (quark_global);
 241
 242   return quark;
 243 }
 244
 245 /**
 246  * g_quark_to_string:
 247  * @quark: a #GQuark.
 248  *
 249  * Gets the string associated with the given #GQuark.
 250  *
 251  * Returns: the string associated with the #GQuark
 252  */
 253 const gchar *
 254 g_quark_to_string (GQuark quark)
 255 {
 256   gchar* result = NULL;
 257   gchar **strings;
 258   gint seq_id;
 259
 260   seq_id = g_atomic_int_get (&quark_seq_id);
 261   strings = g_atomic_pointer_get (&quarks);
 262
 263   if (quark < seq_id)
 264     result = strings[quark];
 265
 266   return result;
 267 }
 268
 269 /* HOLDS: g_quark_global_lock */
 270 static inline GQuark
 271 quark_new (gchar *string)
 272 {
 273   GQuark quark;
 274   gchar **quarks_new;
 275
 276   if (quark_seq_id % QUARK_BLOCK_SIZE == 0)
 277     {
 278       quarks_new = g_new (gchar*, quark_seq_id + QUARK_BLOCK_SIZE);
 279       if (quark_seq_id != 0)
 280         memcpy (quarks_new, quarks, sizeof (char *) * quark_seq_id);
 281       memset (quarks_new + quark_seq_id, 0, sizeof (char *) * QUARK_BLOCK_SIZE);
 282       /* This leaks the old quarks array. Its unfortunate, but it allows
 283        * us to do lockless lookup of the arrays, and there shouldn't be that
 284        * many quarks in an app
 285        */
 286       g_atomic_pointer_set (&quarks, quarks_new);
 287     }
 288   if (!quark_ht)
 289     {
 290       g_assert (quark_seq_id == 0);
 291       quark_ht = g_hash_table_new (g_str_hash, g_str_equal);
 292       quarks[quark_seq_id] = NULL;
 293       g_atomic_int_inc (&quark_seq_id);
 294     }
 295
 296   quark = quark_seq_id;
 297   g_atomic_pointer_set (&quarks[quark], string);
 298   g_hash_table_insert (quark_ht, string, GUINT_TO_POINTER (quark));
 299   g_atomic_int_inc (&quark_seq_id);
 300
 301   return quark;
 302 }
 303
 304 /**
 305  * g_intern_string:
 306  * @string: (allow-none): a string
 307  *
 308  * Returns a canonical representation for @string. Interned strings
 309  * can be compared for equality by comparing the pointers, instead of
 310  * using strcmp().
 311  *
 312  * Returns: a canonical representation for the string
 313  *
 314  * Since: 2.10
 315  */
 316 const gchar *
 317 g_intern_string (const gchar *string)
 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, TRUE);
 327   result = quarks[quark];
 328   G_UNLOCK (quark_global);
 329
 330   return result;
 331 }
 332
 333 /**
 334  * g_intern_static_string:
 335  * @string: (allow-none): a static 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(). g_intern_static_string() does not copy the string,
 340  * therefore @string must not be freed or modified.
 341  *
 342  * Returns: a canonical representation for the string
 343  *
 344  * Since: 2.10
 345  */
 346 const gchar *
 347 g_intern_static_string (const gchar *string)
 348 {
 349   GQuark quark;
 350   const gchar *result;
 351
 352   if (!string)
 353     return NULL;
 354
 355   G_LOCK (quark_global);
 356   quark = quark_from_string (string, FALSE);
 357   result = quarks[quark];
 358   G_UNLOCK (quark_global);
 359
 360   return result;
 361 }