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_quark_try_string:
  97  * @string: (allow-none): a string.
  98  * @Returns: the #GQuark associated with the string, or 0 if @string is
  99  *           %NULL or there is no #GQuark associated with it.
 100  *
 101  * Gets the #GQuark associated with the given string, or 0 if string is
 102  * %NULL or it has no associated #GQuark.
 103  *
 104  * If you want the GQuark to be created if it doesn't already exist,
 105  * use g_quark_from_string() or g_quark_from_static_string().
 106  **/
 107 GQuark
 108 g_quark_try_string (const gchar *string)
 109 {
 110   GQuark quark = 0;
 111
 112   if (string == NULL)
 113     return 0;
 114
 115   G_LOCK (quark_global);
 116   if (quark_ht)
 117     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 118   G_UNLOCK (quark_global);
 119
 120   return quark;
 121 }
 122
 123 /* HOLDS: quark_global_lock */
 124 static char *
 125 quark_strdup (const gchar *string)
 126 {
 127   gchar *copy;
 128   gsize len;
 129
 130   len = strlen (string) + 1;
 131
 132   /* For strings longer than half the block size, fall back
 133      to strdup so that we fill our blocks at least 50%. */
 134   if (len > QUARK_STRING_BLOCK_SIZE / 2)
 135     return g_strdup (string);
 136
 137   if (quark_block == NULL ||
 138       QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
 139     {
 140       quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
 141       quark_block_offset = 0;
 142     }
 143
 144   copy = quark_block + quark_block_offset;
 145   memcpy (copy, string, len);
 146   quark_block_offset += len;
 147
 148   return copy;
 149 }
 150
 151 /* HOLDS: quark_global_lock */
 152 static inline GQuark
 153 quark_from_string (const gchar *string,
 154                    gboolean     duplicate)
 155 {
 156   GQuark quark = 0;
 157
 158   if (quark_ht)
 159     quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
 160
 161   if (!quark)
 162     {
 163       quark = quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
 164       TRACE(GLIB_QUARK_NEW(string, quark));
 165     }
 166
 167   return quark;
 168 }
 169
 170 /**
 171  * g_quark_from_string:
 172  * @string: (allow-none): a string.
 173  *
 174  * Gets the #GQuark identifying the given string. If the string does
 175  * not currently have an associated #GQuark, a new #GQuark is created,
 176  * using a copy of the string.
 177  *
 178  * Returns: the #GQuark identifying the string, or 0 if @string is
 179  *     %NULL.
 180  */
 181 GQuark
 182 g_quark_from_string (const gchar *string)
 183 {
 184   GQuark quark;
 185
 186   if (!string)
 187     return 0;
 188
 189   G_LOCK (quark_global);
 190   quark = quark_from_string (string, TRUE);
 191   G_UNLOCK (quark_global);
 192
 193   return quark;
 194 }
 195
 196 /**
 197  * g_quark_from_static_string:
 198  * @string: (allow-none): a string.
 199  *
 200  * Gets the #GQuark identifying the given (static) string. If the
 201  * string does not currently have an associated #GQuark, a new #GQuark
 202  * is created, linked to the given string.
 203  *
 204  * Note that this function is identical to g_quark_from_string() except
 205  * that if a new #GQuark is created the string itself is used rather
 206  * than a copy. This saves memory, but can only be used if the string
 207  * will <emphasis>always</emphasis> exist. It can be used with
 208  * statically allocated strings in the main program, but not with
 209  * statically allocated memory in dynamically loaded modules, if you
 210  * expect to ever unload the module again (e.g. do not use this
 211  * function in GTK+ theme engines).
 212  *
 213  * Returns: the #GQuark identifying the string, or 0 if @string is
 214  *     %NULL.
 215  */
 216 GQuark
 217 g_quark_from_static_string (const gchar *string)
 218 {
 219   GQuark quark;
 220
 221   if (!string)
 222     return 0;
 223
 224   G_LOCK (quark_global);
 225   quark = quark_from_string (string, FALSE);
 226   G_UNLOCK (quark_global);
 227
 228   return quark;
 229 }
 230
 231 /**
 232  * g_quark_to_string:
 233  * @quark: a #GQuark.
 234  *
 235  * Gets the string associated with the given #GQuark.
 236  *
 237  * Returns: the string associated with the #GQuark
 238  */
 239 const gchar *
 240 g_quark_to_string (GQuark quark)
 241 {
 242   gchar* result = NULL;
 243   gchar **strings;
 244   gint seq_id;
 245
 246   seq_id = g_atomic_int_get (&quark_seq_id);
 247   strings = g_atomic_pointer_get (&quarks);
 248
 249   if (quark < seq_id)
 250     result = strings[quark];
 251
 252   return result;
 253 }
 254
 255 /* HOLDS: g_quark_global_lock */
 256 static inline GQuark
 257 quark_new (gchar *string)
 258 {
 259   GQuark quark;
 260   gchar **quarks_new;
 261
 262   if (quark_seq_id % QUARK_BLOCK_SIZE == 0)
 263     {
 264       quarks_new = g_new (gchar*, quark_seq_id + QUARK_BLOCK_SIZE);
 265       if (quark_seq_id != 0)
 266         memcpy (quarks_new, quarks, sizeof (char *) * quark_seq_id);
 267       memset (quarks_new + quark_seq_id, 0, sizeof (char *) * QUARK_BLOCK_SIZE);
 268       /* This leaks the old quarks array. Its unfortunate, but it allows
 269        * us to do lockless lookup of the arrays, and there shouldn't be that
 270        * many quarks in an app
 271        */
 272       g_atomic_pointer_set (&quarks, quarks_new);
 273     }
 274   if (!quark_ht)
 275     {
 276       g_assert (quark_seq_id == 0);
 277       quark_ht = g_hash_table_new (g_str_hash, g_str_equal);
 278       quarks[quark_seq_id] = NULL;
 279       g_atomic_int_inc (&quark_seq_id);
 280     }
 281
 282   quark = quark_seq_id;
 283   g_atomic_pointer_set (&quarks[quark], string);
 284   g_hash_table_insert (quark_ht, string, GUINT_TO_POINTER (quark));
 285   g_atomic_int_inc (&quark_seq_id);
 286
 287   return quark;
 288 }
 289
 290 /**
 291  * g_intern_string:
 292  * @string: (allow-none): a string
 293  *
 294  * Returns a canonical representation for @string. Interned strings
 295  * can be compared for equality by comparing the pointers, instead of
 296  * using strcmp().
 297  *
 298  * Returns: a canonical representation for the string
 299  *
 300  * Since: 2.10
 301  */
 302 const gchar *
 303 g_intern_string (const gchar *string)
 304 {
 305   const gchar *result;
 306   GQuark quark;
 307
 308   if (!string)
 309     return NULL;
 310
 311   G_LOCK (quark_global);
 312   quark = quark_from_string (string, TRUE);
 313   result = quarks[quark];
 314   G_UNLOCK (quark_global);
 315
 316   return result;
 317 }
 318
 319 /**
 320  * g_intern_static_string:
 321  * @string: (allow-none): a static string
 322  *
 323  * Returns a canonical representation for @string. Interned strings
 324  * can be compared for equality by comparing the pointers, instead of
 325  * using strcmp(). g_intern_static_string() does not copy the string,
 326  * therefore @string must not be freed or modified.
 327  *
 328  * Returns: a canonical representation for the string
 329  *
 330  * Since: 2.10
 331  */
 332 const gchar *
 333 g_intern_static_string (const gchar *string)
 334 {
 335   GQuark quark;
 336   const gchar *result;
 337
 338   if (!string)
 339     return NULL;
 340
 341   G_LOCK (quark_global);
 342   quark = quark_from_string (string, FALSE);
 343   result = quarks[quark];
 344   G_UNLOCK (quark_global);
 345
 346   return result;
 347 }