Branch data Line data Source code
1 : : /* grefstring.c: Reference counted strings
2 : : *
3 : : * Copyright 2018 Emmanuele Bassi
4 : : *
5 : : * SPDX-License-Identifier: LGPL-2.1-or-later
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 : : #include "config.h"
22 : :
23 : : #include "grefstring.h"
24 : :
25 : : #include "ghash.h"
26 : : #include "gmessages.h"
27 : : #include "gtestutils.h"
28 : : #include "gthread.h"
29 : :
30 : : #include <string.h>
31 : :
32 : : /* A global table of refcounted strings; the hash table does not own
33 : : * the strings, just a pointer to them. Strings are interned as long
34 : : * as they are alive; once their reference count drops to zero, they
35 : : * are removed from the table
36 : : */
37 : : G_LOCK_DEFINE_STATIC (interned_ref_strings);
38 : : static GHashTable *interned_ref_strings;
39 : :
40 : : #if G_GNUC_CHECK_VERSION(4,8) || defined(__clang__)
41 : : # define _attribute_aligned(n) __attribute__((aligned(n)))
42 : : #elif defined(_MSC_VER)
43 : : # define _attribute_aligned(n) __declspec(align(n))
44 : : #else
45 : : # define _attribute_aligned(n)
46 : : #endif
47 : :
48 : : typedef struct {
49 : : /* Length of the string without NUL-terminator */
50 : : size_t len;
51 : : /* Atomic reference count placed here to reduce struct padding */
52 : : int ref_count;
53 : : /* TRUE if interned, FALSE otherwise; immutable after construction */
54 : : guint8 interned;
55 : :
56 : : /* First character of the actual string
57 : : * Make sure it is at least 2 * sizeof (size_t) aligned to allow for SIMD
58 : : * optimizations in operations on the string.
59 : : * Because MSVC sucks we need to handle both cases explicitly. */
60 : : #if GLIB_SIZEOF_SIZE_T == 4
61 : : _attribute_aligned (8) char s[];
62 : : #elif GLIB_SIZEOF_SIZE_T == 8
63 : : _attribute_aligned (16) char s[];
64 : : #else
65 : : #error "Only 32 bit and 64 bit size_t supported currently"
66 : : #endif
67 : : } GRefStringImpl;
68 : :
69 : : /* Assert that the start of the actual string is at least 2 * alignof (size_t) aligned */
70 : : G_STATIC_ASSERT (offsetof (GRefStringImpl, s) % (2 * G_ALIGNOF (size_t)) == 0);
71 : :
72 : : /* Gets a pointer to the GRefStringImpl from its string pointer */
73 : : #define G_REF_STRING_IMPL_FROM_STR(str) ((GRefStringImpl *) ((guint8 *) str - offsetof (GRefStringImpl, s)))
74 : : /* Gets a pointer to the string pointer from the GRefStringImpl */
75 : : #define G_REF_STRING_IMPL_TO_STR(str) (str->s)
76 : :
77 : : /**
78 : : * g_ref_string_new:
79 : : * @str: (not nullable): a NUL-terminated string
80 : : *
81 : : * Creates a new reference counted string and copies the contents of @str
82 : : * into it.
83 : : *
84 : : * Returns: (transfer full) (not nullable): the newly created reference counted string
85 : : *
86 : : * Since: 2.58
87 : : */
88 : : char *
89 : 188590 : g_ref_string_new (const char *str)
90 : : {
91 : : GRefStringImpl *impl;
92 : : gsize len;
93 : :
94 : 188590 : g_return_val_if_fail (str != NULL, NULL);
95 : :
96 : 188590 : len = strlen (str);
97 : :
98 : 188590 : if (sizeof (char) * len > G_MAXSIZE - sizeof (GRefStringImpl) - 1)
99 : 0 : g_error ("GRefString allocation would overflow");
100 : :
101 : 188590 : impl = g_malloc (sizeof (GRefStringImpl) + sizeof (char) * len + 1);
102 : 188590 : impl->len = len;
103 : 188590 : impl->ref_count = 1;
104 : 188590 : impl->interned = FALSE;
105 : 188590 : memcpy (G_REF_STRING_IMPL_TO_STR (impl), str, len + 1);
106 : :
107 : 188590 : return G_REF_STRING_IMPL_TO_STR (impl);
108 : : }
109 : :
110 : : /**
111 : : * g_ref_string_new_len:
112 : : * @str: (not nullable): a string
113 : : * @len: length of @str to use, or -1 if @str is nul-terminated
114 : : *
115 : : * Creates a new reference counted string and copies the contents of @str
116 : : * into it, up to @len bytes.
117 : : *
118 : : * Since this function does not stop at nul bytes, it is the caller's
119 : : * responsibility to ensure that @str has at least @len addressable bytes.
120 : : *
121 : : * Returns: (transfer full) (not nullable): the newly created reference counted string
122 : : *
123 : : * Since: 2.58
124 : : */
125 : : char *
126 : 3 : g_ref_string_new_len (const char *str, gssize len)
127 : : {
128 : : GRefStringImpl *impl;
129 : :
130 : 3 : g_return_val_if_fail (str != NULL, NULL);
131 : :
132 : 3 : if (len < 0)
133 : 1 : return g_ref_string_new (str);
134 : :
135 : : /* allocate then copy as str[len] may not be readable */
136 : 2 : if (sizeof (char) * len > G_MAXSIZE - sizeof (GRefStringImpl) - 1)
137 : 0 : g_error ("GRefString allocation would overflow");
138 : :
139 : 2 : impl = g_malloc (sizeof (GRefStringImpl) + sizeof (char) * len + 1);
140 : 2 : impl->len = len;
141 : 2 : impl->ref_count = 1;
142 : 2 : impl->interned = FALSE;
143 : 2 : memcpy (G_REF_STRING_IMPL_TO_STR (impl), str, len);
144 : 2 : G_REF_STRING_IMPL_TO_STR (impl)[len] = '\0';
145 : :
146 : 2 : return G_REF_STRING_IMPL_TO_STR (impl);
147 : : }
148 : :
149 : : /* interned_str_equal: variant of g_str_equal() that compares
150 : : * pointers as well as contents; this avoids running strcmp()
151 : : * on arbitrarily long strings, as it's more likely to have
152 : : * g_ref_string_new_intern() being called on the same refcounted
153 : : * string instance, than on a different string with the same
154 : : * contents
155 : : */
156 : : static gboolean
157 : 2000003 : interned_str_equal (gconstpointer v1,
158 : : gconstpointer v2)
159 : : {
160 : 2000003 : const char *str1 = v1;
161 : 2000003 : const char *str2 = v2;
162 : :
163 : 2000003 : if (v1 == v2)
164 : 188580 : return TRUE;
165 : :
166 : 1811423 : return strcmp (str1, str2) == 0;
167 : : }
168 : :
169 : : /**
170 : : * g_ref_string_new_intern:
171 : : * @str: (not nullable): a NUL-terminated string
172 : : *
173 : : * Creates a new reference counted string and copies the content of @str
174 : : * into it.
175 : : *
176 : : * If you call this function multiple times with the same @str, or with
177 : : * the same contents of @str, it will return a new reference, instead of
178 : : * creating a new string.
179 : : *
180 : : * Returns: (transfer full) (not nullable): the newly created reference
181 : : * counted string, or a new reference to an existing string
182 : : *
183 : : * Since: 2.58
184 : : */
185 : : char *
186 : 2000003 : g_ref_string_new_intern (const char *str)
187 : : {
188 : : char *res;
189 : :
190 : 2000003 : g_return_val_if_fail (str != NULL, NULL);
191 : :
192 : 2000003 : G_LOCK (interned_ref_strings);
193 : :
194 : 2000003 : if (G_UNLIKELY (interned_ref_strings == NULL))
195 : 188579 : interned_ref_strings = g_hash_table_new (g_str_hash, interned_str_equal);
196 : :
197 : 2000003 : res = g_hash_table_lookup (interned_ref_strings, str);
198 : 2000003 : if (res != NULL)
199 : : {
200 : 1811423 : GRefStringImpl *impl = G_REF_STRING_IMPL_FROM_STR (res);
201 : 1811423 : g_atomic_int_inc (&impl->ref_count);
202 : 1811423 : G_UNLOCK (interned_ref_strings);
203 : 1811423 : return res;
204 : : }
205 : :
206 : 188580 : res = g_ref_string_new (str);
207 : 188580 : G_REF_STRING_IMPL_FROM_STR (res)->interned = TRUE;
208 : 188580 : g_hash_table_add (interned_ref_strings, res);
209 : 188580 : G_UNLOCK (interned_ref_strings);
210 : :
211 : 188580 : return res;
212 : : }
213 : :
214 : : /**
215 : : * g_ref_string_acquire:
216 : : * @str: a reference counted string
217 : : *
218 : : * Acquires a reference on a string.
219 : : *
220 : : * Returns: the given string, with its reference count increased
221 : : *
222 : : * Since: 2.58
223 : : */
224 : : char *
225 : 1 : g_ref_string_acquire (char *str)
226 : : {
227 : 1 : g_return_val_if_fail (str != NULL, NULL);
228 : :
229 : 1 : g_atomic_int_inc (&G_REF_STRING_IMPL_FROM_STR (str)->ref_count);
230 : :
231 : 1 : return str;
232 : : }
233 : :
234 : : /**
235 : : * g_ref_string_release:
236 : : * @str: a reference counted string
237 : : *
238 : : * Releases a reference on a string; if it was the last reference, the
239 : : * resources allocated by the string are freed as well.
240 : : *
241 : : * Since: 2.58
242 : : */
243 : : void
244 : 2000016 : g_ref_string_release (char *str)
245 : : {
246 : : GRefStringImpl *impl;
247 : : int old_ref_count;
248 : :
249 : 3810708 : g_return_if_fail (str != NULL);
250 : :
251 : 2000016 : impl = G_REF_STRING_IMPL_FROM_STR (str);
252 : :
253 : : /* Non-interned strings are easy so let's get that out of the way here first */
254 : 2000016 : if (!impl->interned)
255 : : {
256 : 13 : if (g_atomic_int_dec_and_test (&impl->ref_count))
257 : 12 : g_free (impl);
258 : 13 : return;
259 : : }
260 : :
261 : 2000003 : old_ref_count = g_atomic_int_get (&impl->ref_count);
262 : 2000003 : g_assert (old_ref_count >= 1);
263 : 2000040 : retry:
264 : : /* Fast path: multiple references, we can just try decrementing and be done with it */
265 : 2000040 : if (old_ref_count > 1)
266 : : {
267 : : /* If the reference count stayed the same we're done, otherwise retry */
268 : 1810716 : if (!g_atomic_int_compare_and_exchange_full (&impl->ref_count, old_ref_count, old_ref_count - 1, &old_ref_count))
269 : 37 : goto retry;
270 : :
271 : 1810679 : return;
272 : : }
273 : :
274 : : /* This is the last reference *currently* and would potentially free the string.
275 : : * To avoid races between freeing it and returning it from g_ref_string_new_intern()
276 : : * we must take the lock here before decrementing the reference count!
277 : : */
278 : 189324 : G_LOCK (interned_ref_strings);
279 : : /* If the string was not given out again in the meantime we're done */
280 : 189324 : if (g_atomic_int_dec_and_test (&impl->ref_count))
281 : : {
282 : : gboolean removed G_GNUC_UNUSED /* when compiling with G_DISABLE_ASSERT */;
283 : :
284 : 188580 : removed = g_hash_table_remove (interned_ref_strings, str);
285 : 188580 : g_assert (removed);
286 : :
287 : 188580 : if (g_hash_table_size (interned_ref_strings) == 0)
288 : 188579 : g_clear_pointer (&interned_ref_strings, g_hash_table_destroy);
289 : :
290 : 188580 : g_free (impl);
291 : : }
292 : 189324 : G_UNLOCK (interned_ref_strings);
293 : : }
294 : :
295 : : /**
296 : : * g_ref_string_length:
297 : : * @str: a reference counted string
298 : : *
299 : : * Retrieves the length of @str.
300 : : *
301 : : * Returns: the length of the given string, in bytes
302 : : *
303 : : * Since: 2.58
304 : : */
305 : : gsize
306 : 4 : g_ref_string_length (char *str)
307 : : {
308 : 4 : g_return_val_if_fail (str != NULL, 0);
309 : :
310 : 4 : return G_REF_STRING_IMPL_FROM_STR (str)->len;
311 : : }
312 : :
313 : : /**
314 : : * g_ref_string_equal:
315 : : * @str1: a reference counted string
316 : : * @str2: a reference counted string
317 : : *
318 : : * Compares two ref-counted strings for byte-by-byte equality.
319 : : *
320 : : * It can be passed to [func@GLib.HashTable.new] as the key equality function,
321 : : * and behaves exactly the same as [func@GLib.str_equal] (or `strcmp()`), but
322 : : * can return slightly faster as it can check the string lengths before checking
323 : : * all the bytes.
324 : : *
325 : : * Returns: `TRUE` if the strings are equal, otherwise `FALSE`
326 : : *
327 : : * Since: 2.84
328 : : */
329 : : gboolean
330 : 5 : g_ref_string_equal (const char *str1,
331 : : const char *str2)
332 : : {
333 : 5 : if (G_REF_STRING_IMPL_FROM_STR ((char *) str1)->len != G_REF_STRING_IMPL_FROM_STR ((char *) str2)->len)
334 : 1 : return FALSE;
335 : :
336 : 4 : return strcmp (str1, str2) == 0;
337 : : }
|