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

source code of gtk/subprojects/glib/glib/gstringchunk.c