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