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