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 | */ |
76 | struct _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 | |
87 | static inline gsize |
88 | nearest_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 | */ |
117 | GStringChunk * |
118 | g_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 | */ |
142 | void |
143 | g_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 | */ |
166 | void |
167 | g_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 | */ |
204 | gchar* |
205 | g_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 | */ |
235 | gchar* |
236 | g_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 | */ |
278 | gchar* |
279 | g_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 | |