1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * SPDX-License-Identifier: LGPL-2.1-or-later
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 */
19
20 /*
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
25 */
26
27 /*
28 * MT safe
29 */
30
31 #include "config.h"
32
33 #include <string.h>
34
35 #include "gstringchunk.h"
36
37 #include "ghash.h"
38 #include "gslist.h"
39 #include "gmessages.h"
40
41 #include "gutils.h"
42 #include "gutilsprivate.h"
43
44 /**
45 * GStringChunk:
46 *
47 * `GStringChunk` provides efficient storage of groups of strings
48 *
49 * String chunks are used to store groups of strings. Memory is
50 * allocated in blocks, and as strings are added to the `GStringChunk`
51 * they are copied into the next free position in a block. When a block
52 * is full a new block is allocated.
53 *
54 * When storing a large number of strings, string chunks are more
55 * efficient than using [func@GLib.strdup] since fewer calls to `malloc()`
56 * are needed, and less memory is wasted in memory allocation overheads.
57 *
58 * By adding strings with [method@GLib.StringChunk.insert_const] it is also
59 * possible to remove duplicates.
60 *
61 * To create a new `GStringChunk` use [func@GLib.StringChunk.new].
62 *
63 * To add strings to a `GStringChunk` use [method@GLib.StringChunk.insert].
64 *
65 * To add strings to a `GStringChunk`, but without duplicating strings
66 * which are already in the `GStringChunk`, use [method@GLib.StringChunk.insert_const].
67 *
68 * To free the entire `GStringChunk` use [method@GLib.StringChunk.free].
69 * It is not possible to free individual strings.
70 */
71
72 struct _GStringChunk
73 {
74 GHashTable *const_table;
75 GSList *storage_list;
76 gsize storage_next;
77 gsize this_size;
78 gsize default_size;
79 };
80
81 /**
82 * g_string_chunk_new: (constructor)
83 * @size: the default size of the blocks of memory which are
84 * allocated to store the strings. If a particular string
85 * is larger than this default size, a larger block of
86 * memory will be allocated for it.
87 *
88 * Creates a new #GStringChunk.
89 *
90 * Returns: (transfer full): a new #GStringChunk
91 */
92 GStringChunk *
93 g_string_chunk_new (gsize size)
94 {
95 GStringChunk *new_chunk = g_new (GStringChunk, 1);
96 gsize actual_size = 1;
97
98 actual_size = g_nearest_pow (MAX (1, size));
99
100 new_chunk->const_table = NULL;
101 new_chunk->storage_list = NULL;
102 new_chunk->storage_next = actual_size;
103 new_chunk->default_size = actual_size;
104 new_chunk->this_size = actual_size;
105
106 return new_chunk;
107 }
108
109 /**
110 * g_string_chunk_free:
111 * @chunk: (transfer full): a #GStringChunk
112 *
113 * Frees all memory allocated by the #GStringChunk.
114 * After calling g_string_chunk_free() it is not safe to
115 * access any of the strings which were contained within it.
116 */
117 void
118 g_string_chunk_free (GStringChunk *chunk)
119 {
120 g_return_if_fail (chunk != NULL);
121
122 if (chunk->storage_list)
123 g_slist_free_full (chunk->storage_list, g_free);
124
125 if (chunk->const_table)
126 g_hash_table_destroy (chunk->const_table);
127
128 g_free (chunk);
129 }
130
131 /**
132 * g_string_chunk_clear:
133 * @chunk: a #GStringChunk
134 *
135 * Frees all strings contained within the #GStringChunk.
136 * After calling g_string_chunk_clear() it is not safe to
137 * access any of the strings which were contained within it.
138 *
139 * Since: 2.14
140 */
141 void
142 g_string_chunk_clear (GStringChunk *chunk)
143 {
144 g_return_if_fail (chunk != NULL);
145
146 if (chunk->storage_list)
147 {
148 g_slist_free_full (chunk->storage_list, g_free);
149
150 chunk->storage_list = NULL;
151 chunk->storage_next = chunk->default_size;
152 chunk->this_size = chunk->default_size;
153 }
154
155 if (chunk->const_table)
156 g_hash_table_remove_all (chunk->const_table);
157 }
158
159 /**
160 * g_string_chunk_insert:
161 * @chunk: a #GStringChunk
162 * @string: the string to add
163 *
164 * Adds a copy of @string to the #GStringChunk.
165 * It returns a pointer to the new copy of the string
166 * in the #GStringChunk. The characters in the string
167 * can be changed, if necessary, though you should not
168 * change anything after the end of the string.
169 *
170 * Unlike g_string_chunk_insert_const(), this function
171 * does not check for duplicates. Also strings added
172 * with g_string_chunk_insert() will not be searched
173 * by g_string_chunk_insert_const() when looking for
174 * duplicates.
175 *
176 * Returns: a pointer to the copy of @string within
177 * the #GStringChunk
178 */
179 gchar*
180 g_string_chunk_insert (GStringChunk *chunk,
181 const gchar *string)
182 {
183 g_return_val_if_fail (chunk != NULL, NULL);
184
185 return g_string_chunk_insert_len (chunk, string, -1);
186 }
187
188 /**
189 * g_string_chunk_insert_const:
190 * @chunk: a #GStringChunk
191 * @string: the string to add
192 *
193 * Adds a copy of @string to the #GStringChunk, unless the same
194 * string has already been added to the #GStringChunk with
195 * g_string_chunk_insert_const().
196 *
197 * This function is useful if you need to copy a large number
198 * of strings but do not want to waste space storing duplicates.
199 * But you must remember that there may be several pointers to
200 * the same string, and so any changes made to the strings
201 * should be done very carefully.
202 *
203 * Note that g_string_chunk_insert_const() will not return a
204 * pointer to a string added with g_string_chunk_insert(), even
205 * if they do match.
206 *
207 * Returns: a pointer to the new or existing copy of @string
208 * within the #GStringChunk
209 */
210 gchar*
211 g_string_chunk_insert_const (GStringChunk *chunk,
212 const gchar *string)
213 {
214 char* lookup;
215
216 g_return_val_if_fail (chunk != NULL, NULL);
217
218 if (!chunk->const_table)
219 chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
220
221 lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
222
223 if (!lookup)
224 {
225 lookup = g_string_chunk_insert (chunk, string);
226 g_hash_table_add (chunk->const_table, lookup);
227 }
228
229 return lookup;
230 }
231
232 /**
233 * g_string_chunk_insert_len:
234 * @chunk: a #GStringChunk
235 * @string: bytes to insert
236 * @len: number of bytes of @string to insert, or -1 to insert a
237 * nul-terminated string
238 *
239 * Adds a copy of the first @len bytes of @string to the #GStringChunk.
240 * The copy is nul-terminated.
241 *
242 * Since this function does not stop at nul bytes, it is the caller's
243 * responsibility to ensure that @string has at least @len addressable
244 * bytes.
245 *
246 * The characters in the returned string can be changed, if necessary,
247 * though you should not change anything after the end of the string.
248 *
249 * Returns: a pointer to the copy of @string within the #GStringChunk
250 *
251 * Since: 2.4
252 */
253 gchar*
254 g_string_chunk_insert_len (GStringChunk *chunk,
255 const gchar *string,
256 gssize len)
257 {
258 gsize size;
259 gchar* pos;
260
261 g_return_val_if_fail (chunk != NULL, NULL);
262
263 if (len < 0)
264 size = strlen (string);
265 else
266 size = (gsize) len;
267
268 if ((G_MAXSIZE - chunk->storage_next < size + 1) || (chunk->storage_next + size + 1) > chunk->this_size)
269 {
270 gsize new_size = g_nearest_pow (MAX (chunk->default_size, size + 1));
271
272 /* If size is bigger than G_MAXSIZE / 2 then store it in its own
273 * allocation instead of failing here */
274 if (new_size == 0)
275 new_size = size + 1;
276
277 chunk->storage_list = g_slist_prepend (chunk->storage_list,
278 g_new (gchar, new_size));
279
280 chunk->this_size = new_size;
281 chunk->storage_next = 0;
282 }
283
284 pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
285
286 *(pos + size) = '\0';
287
288 memcpy (pos, string, size);
289
290 chunk->storage_next += size + 1;
291
292 return pos;
293 }