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 * SPDX-License-Identifier: LGPL-2.1-or-later
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
21 */
22
23 /*
24 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
25 * file for a list of people on the GLib Team. See the ChangeLog
26 * files for a list of changes. These files are distributed with
27 * GLib at ftp://ftp.gtk.org/pub/gtk/.
28 */
29
30 /*
31 * MT safe
32 */
33
34 #include "config.h"
35
36 #include <string.h>
37
38 #include "gslice.h"
39 #include "ghash.h"
40 #include "gquark.h"
41 #include "gstrfuncs.h"
42 #include "gthread.h"
43 #include "gtestutils.h"
44 #include "glib_trace.h"
45 #include "glib-init.h"
46 #include "glib-private.h"
47
48 #define QUARK_BLOCK_SIZE 2048
49 #define QUARK_STRING_BLOCK_SIZE (4096 - sizeof (gsize))
50
51 static inline GQuark quark_new (gchar *string);
52
53 G_LOCK_DEFINE_STATIC (quark_global);
54 static GHashTable *quark_ht = NULL;
55 static gchar **quarks = NULL;
56 static gint quark_seq_id = 0;
57 static gchar *quark_block = NULL;
58 static gint quark_block_offset = 0;
59
60 void
61 g_quark_init (void)
62 {
63 g_assert (quark_seq_id == 0);
64 quark_ht = g_hash_table_new (g_str_hash, g_str_equal);
65 quarks = g_new (gchar*, QUARK_BLOCK_SIZE);
66 quarks[0] = NULL;
67 quark_seq_id = 1;
68 }
69
70 /**
71 * GQuark:
72 *
73 * A GQuark is a non-zero integer which uniquely identifies a
74 * particular string.
75 *
76 * A GQuark value of zero is associated to `NULL`.
77 *
78 * Given either the string or the `GQuark` identifier it is possible to
79 * retrieve the other.
80 *
81 * Quarks are used for both
82 * [datasets and keyed data lists](datalist-and-dataset.html).
83 *
84 * To create a new quark from a string, use [func@GLib.quark_from_string]
85 * or [func@GLib.quark_from_static_string].
86 *
87 * To find the string corresponding to a given `GQuark`, use
88 * [func@GLib.quark_to_string].
89 *
90 * To find the `GQuark` corresponding to a given string, use
91 * [func@GLib.quark_try_string].
92 *
93 * Another use for the string pool maintained for the quark functions
94 * is string interning, using [func@GLib.intern_string] or
95 * [func@GLib.intern_static_string]. An interned string is a canonical
96 * representation for a string. One important advantage of interned
97 * strings is that they can be compared for equality by a simple
98 * pointer comparison, rather than using `strcmp()`.
99 */
100
101 /**
102 * G_DEFINE_QUARK:
103 * @QN: the name to return a #GQuark for
104 * @q_n: prefix for the function name
105 *
106 * A convenience macro which defines a function returning the
107 * #GQuark for the name @QN. The function will be named
108 * @q_n_quark().
109 *
110 * Note that the quark name will be stringified automatically
111 * in the macro, so you shouldn't use double quotes.
112 *
113 * Since: 2.34
114 */
115
116 /**
117 * g_quark_try_string:
118 * @string: (nullable): a string
119 *
120 * Gets the #GQuark associated with the given string, or 0 if string is
121 * %NULL or it has no associated #GQuark.
122 *
123 * If you want the GQuark to be created if it doesn't already exist,
124 * use g_quark_from_string() or g_quark_from_static_string().
125 *
126 * This function must not be used before library constructors have finished
127 * running.
128 *
129 * Returns: the #GQuark associated with the string, or 0 if @string is
130 * %NULL or there is no #GQuark associated with it
131 */
132 GQuark
133 g_quark_try_string (const gchar *string)
134 {
135 GQuark quark = 0;
136
137 if (string == NULL)
138 return 0;
139
140 G_LOCK (quark_global);
141 quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
142 G_UNLOCK (quark_global);
143
144 return quark;
145 }
146
147 /* HOLDS: quark_global_lock */
148 static char *
149 quark_strdup (const gchar *string)
150 {
151 gchar *copy;
152 gsize len;
153
154 len = strlen (string) + 1;
155
156 /* For strings longer than half the block size, fall back
157 to strdup so that we fill our blocks at least 50%. */
158 if (len > QUARK_STRING_BLOCK_SIZE / 2)
159 return g_strdup (string);
160
161 if (quark_block == NULL ||
162 QUARK_STRING_BLOCK_SIZE - quark_block_offset < len)
163 {
164 quark_block = g_malloc (QUARK_STRING_BLOCK_SIZE);
165 quark_block_offset = 0;
166 }
167
168 copy = quark_block + quark_block_offset;
169 memcpy (copy, string, len);
170 quark_block_offset += len;
171
172 return copy;
173 }
174
175 /* HOLDS: quark_global_lock */
176 static inline GQuark
177 quark_from_string (const gchar *string,
178 gboolean duplicate)
179 {
180 GQuark quark = 0;
181
182 quark = GPOINTER_TO_UINT (g_hash_table_lookup (quark_ht, string));
183
184 if (!quark)
185 {
186 quark = quark_new (duplicate ? quark_strdup (string) : (gchar *)string);
187 TRACE(GLIB_QUARK_NEW(string, quark));
188 }
189
190 return quark;
191 }
192
193 static inline GQuark
194 quark_from_string_locked (const gchar *string,
195 gboolean duplicate)
196 {
197 GQuark quark = 0;
198
199 if (!string)
200 return 0;
201
202 G_LOCK (quark_global);
203 quark = quark_from_string (string, duplicate);
204 G_UNLOCK (quark_global);
205
206 return quark;
207 }
208
209 /**
210 * g_quark_from_string:
211 * @string: (nullable): a string
212 *
213 * Gets the #GQuark identifying the given string. If the string does
214 * not currently have an associated #GQuark, a new #GQuark is created,
215 * using a copy of the string.
216 *
217 * This function must not be used before library constructors have finished
218 * running. In particular, this means it cannot be used to initialize global
219 * variables in C++.
220 *
221 * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
222 */
223 GQuark
224 g_quark_from_string (const gchar *string)
225 {
226 return quark_from_string_locked (string, TRUE);
227 }
228
229 /**
230 * g_quark_from_static_string:
231 * @string: (nullable): a string
232 *
233 * Gets the #GQuark identifying the given (static) string. If the
234 * string does not currently have an associated #GQuark, a new #GQuark
235 * is created, linked to the given string.
236 *
237 * Note that this function is identical to g_quark_from_string() except
238 * that if a new #GQuark is created the string itself is used rather
239 * than a copy. This saves memory, but can only be used if the string
240 * will continue to exist until the program terminates. It can be used
241 * with statically allocated strings in the main program, but not with
242 * statically allocated memory in dynamically loaded modules, if you
243 * expect to ever unload the module again (e.g. do not use this
244 * function in GTK theme engines).
245 *
246 * This function must not be used before library constructors have finished
247 * running. In particular, this means it cannot be used to initialize global
248 * variables in C++.
249 *
250 * Returns: the #GQuark identifying the string, or 0 if @string is %NULL
251 */
252 GQuark
253 g_quark_from_static_string (const gchar *string)
254 {
255 return quark_from_string_locked (string, FALSE);
256 }
257
258 /**
259 * g_quark_to_string:
260 * @quark: a #GQuark.
261 *
262 * Gets the string associated with the given #GQuark.
263 *
264 * Returns: the string associated with the #GQuark
265 */
266 const gchar *
267 g_quark_to_string (GQuark quark)
268 {
269 gchar* result = NULL;
270 gchar **strings;
271 guint seq_id;
272
273 seq_id = (guint) g_atomic_int_get (&quark_seq_id);
274 strings = g_atomic_pointer_get (&quarks);
275
276 if (quark < seq_id)
277 result = strings[quark];
278
279 return result;
280 }
281
282 /* HOLDS: g_quark_global_lock */
283 static inline GQuark
284 quark_new (gchar *string)
285 {
286 GQuark quark;
287 gchar **quarks_new;
288
289 if (quark_seq_id % QUARK_BLOCK_SIZE == 0)
290 {
291 quarks_new = g_new (gchar*, quark_seq_id + QUARK_BLOCK_SIZE);
292 if (quark_seq_id != 0)
293 memcpy (quarks_new, quarks, sizeof (char *) * quark_seq_id);
294 memset (quarks_new + quark_seq_id, 0, sizeof (char *) * QUARK_BLOCK_SIZE);
295 /* This leaks the old quarks array. Its unfortunate, but it allows
296 * us to do lockless lookup of the arrays, and there shouldn't be that
297 * many quarks in an app
298 */
299 g_ignore_leak (g_atomic_pointer_get (&quarks));
300 g_atomic_pointer_set (&quarks, quarks_new);
301 }
302
303 quark = quark_seq_id;
304 g_atomic_pointer_set (&quarks[quark], string);
305 g_hash_table_insert (quark_ht, string, GUINT_TO_POINTER (quark));
306 g_atomic_int_inc (&quark_seq_id);
307
308 return quark;
309 }
310
311 static inline const gchar *
312 quark_intern_string_locked (const gchar *string,
313 gboolean duplicate)
314 {
315 const gchar *result;
316 GQuark quark;
317
318 if (!string)
319 return NULL;
320
321 G_LOCK (quark_global);
322 quark = quark_from_string (string, duplicate);
323 result = quarks[quark];
324 G_UNLOCK (quark_global);
325
326 return result;
327 }
328
329 /**
330 * g_intern_string:
331 * @string: (nullable): a string
332 *
333 * Returns a canonical representation for @string. Interned strings
334 * can be compared for equality by comparing the pointers, instead of
335 * using strcmp().
336 *
337 * This function must not be used before library constructors have finished
338 * running. In particular, this means it cannot be used to initialize global
339 * variables in C++.
340 *
341 * Returns: a canonical representation for the string
342 *
343 * Since: 2.10
344 */
345 const gchar *
346 g_intern_string (const gchar *string)
347 {
348 return quark_intern_string_locked (string, TRUE);
349 }
350
351 /**
352 * g_intern_static_string:
353 * @string: (nullable): a static string
354 *
355 * Returns a canonical representation for @string. Interned strings
356 * can be compared for equality by comparing the pointers, instead of
357 * using strcmp(). g_intern_static_string() does not copy the string,
358 * therefore @string must not be freed or modified.
359 *
360 * This function must not be used before library constructors have finished
361 * running. In particular, this means it cannot be used to initialize global
362 * variables in C++.
363 *
364 * Returns: a canonical representation for the string
365 *
366 * Since: 2.10
367 */
368 const gchar *
369 g_intern_static_string (const gchar *string)
370 {
371 return quark_intern_string_locked (string, FALSE);
372 }