Branch data Line data Source code
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 : 3 : g_string_chunk_new (gsize size)
94 : : {
95 : 3 : GStringChunk *new_chunk = g_new (GStringChunk, 1);
96 : 3 : gsize actual_size = 1;
97 : :
98 : 3 : actual_size = g_nearest_pow (MAX (1, size));
99 : :
100 : 3 : new_chunk->const_table = NULL;
101 : 3 : new_chunk->storage_list = NULL;
102 : 3 : new_chunk->storage_next = actual_size;
103 : 3 : new_chunk->default_size = actual_size;
104 : 3 : new_chunk->this_size = actual_size;
105 : :
106 : 3 : 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 : 3 : g_string_chunk_free (GStringChunk *chunk)
119 : : {
120 : 3 : g_return_if_fail (chunk != NULL);
121 : :
122 : 3 : if (chunk->storage_list)
123 : 1 : g_slist_free_full (chunk->storage_list, g_free);
124 : :
125 : 3 : if (chunk->const_table)
126 : 1 : g_hash_table_destroy (chunk->const_table);
127 : :
128 : 3 : 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 : 1 : g_string_chunk_clear (GStringChunk *chunk)
143 : : {
144 : 1 : g_return_if_fail (chunk != NULL);
145 : :
146 : 1 : if (chunk->storage_list)
147 : : {
148 : 1 : g_slist_free_full (chunk->storage_list, g_free);
149 : :
150 : 1 : chunk->storage_list = NULL;
151 : 1 : chunk->storage_next = chunk->default_size;
152 : 1 : chunk->this_size = chunk->default_size;
153 : : }
154 : :
155 : 1 : if (chunk->const_table)
156 : 1 : 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 : 100003 : g_string_chunk_insert (GStringChunk *chunk,
181 : : const gchar *string)
182 : : {
183 : 100003 : g_return_val_if_fail (chunk != NULL, NULL);
184 : :
185 : 100003 : 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 : 2 : g_string_chunk_insert_const (GStringChunk *chunk,
212 : : const gchar *string)
213 : : {
214 : : char* lookup;
215 : :
216 : 2 : g_return_val_if_fail (chunk != NULL, NULL);
217 : :
218 : 2 : if (!chunk->const_table)
219 : 1 : chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
220 : :
221 : 2 : lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
222 : :
223 : 2 : if (!lookup)
224 : : {
225 : 1 : lookup = g_string_chunk_insert (chunk, string);
226 : 1 : g_hash_table_add (chunk->const_table, lookup);
227 : : }
228 : :
229 : 2 : 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 : 100004 : g_string_chunk_insert_len (GStringChunk *chunk,
255 : : const gchar *string,
256 : : gssize len)
257 : : {
258 : : gsize size;
259 : : gchar* pos;
260 : :
261 : 100004 : g_return_val_if_fail (chunk != NULL, NULL);
262 : :
263 : 100004 : if (len < 0)
264 : 100003 : size = strlen (string);
265 : : else
266 : 1 : size = (gsize) len;
267 : :
268 : 100004 : if ((G_MAXSIZE - chunk->storage_next < size + 1) || (chunk->storage_next + size + 1) > chunk->this_size)
269 : : {
270 : 783 : 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 : 783 : if (new_size == 0)
275 : 0 : new_size = size + 1;
276 : :
277 : 783 : chunk->storage_list = g_slist_prepend (chunk->storage_list,
278 : : g_new (gchar, new_size));
279 : :
280 : 783 : chunk->this_size = new_size;
281 : 783 : chunk->storage_next = 0;
282 : : }
283 : :
284 : 100004 : pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
285 : :
286 : 100004 : *(pos + size) = '\0';
287 : :
288 : 100004 : memcpy (pos, string, size);
289 : :
290 : 100004 : chunk->storage_next += size + 1;
291 : :
292 : 100004 : return pos;
293 : : }
|
