1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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 of the License, or (at your option) any later version.
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.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
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/.
35 #include "gstringchunk.h"
39 #include "gmessages.h"
42 * SECTION:string_chunks
43 * @title: String Chunks
44 * @short_description: efficient storage of groups of strings
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.
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.
55 * By adding strings with g_string_chunk_insert_const() it is also
56 * possible to remove duplicates.
58 * To create a new #GStringChunk use g_string_chunk_new().
60 * To add strings to a #GStringChunk use g_string_chunk_insert().
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().
66 * To free the entire #GStringChunk use g_string_chunk_free(). It is
67 * not possible to free individual strings.
73 * An opaque data structure representing String Chunks.
74 * It should only be accessed by using the following functions.
78 GHashTable *const_table;
85 #define MY_MAXSIZE ((gsize)-1)
88 nearest_power (gsize base,
91 if (num > MY_MAXSIZE / 2)
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.
113 * Creates a new #GStringChunk.
115 * Returns: a new #GStringChunk
118 g_string_chunk_new (gsize size)
120 GStringChunk *new_chunk = g_new (GStringChunk, 1);
121 gsize actual_size = 1;
123 actual_size = nearest_power (1, size);
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;
135 * g_string_chunk_free:
136 * @chunk: a #GStringChunk
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.
143 g_string_chunk_free (GStringChunk *chunk)
147 g_return_if_fail (chunk != NULL);
149 if (chunk->storage_list)
151 for (tmp_list = chunk->storage_list; tmp_list; tmp_list = tmp_list->next)
152 g_free (tmp_list->data);
154 g_slist_free (chunk->storage_list);
157 if (chunk->const_table)
158 g_hash_table_destroy (chunk->const_table);
164 * g_string_chunk_clear:
165 * @chunk: a #GStringChunk
167 * Frees all strings contained within the #GStringChunk.
168 * After calling g_string_chunk_clear() it is not safe to
169 * access any of the strings which were contained within it.
174 g_string_chunk_clear (GStringChunk *chunk)
178 g_return_if_fail (chunk != NULL);
180 if (chunk->storage_list)
182 for (tmp_list = chunk->storage_list; tmp_list; tmp_list = tmp_list->next)
183 g_free (tmp_list->data);
185 g_slist_free (chunk->storage_list);
187 chunk->storage_list = NULL;
188 chunk->storage_next = chunk->default_size;
189 chunk->this_size = chunk->default_size;
192 if (chunk->const_table)
193 g_hash_table_remove_all (chunk->const_table);
197 * g_string_chunk_insert:
198 * @chunk: a #GStringChunk
199 * @string: the string to add
201 * Adds a copy of @string to the #GStringChunk.
202 * It returns a pointer to the new copy of the string
203 * in the #GStringChunk. The characters in the string
204 * can be changed, if necessary, though you should not
205 * change anything after the end of the string.
207 * Unlike g_string_chunk_insert_const(), this function
208 * does not check for duplicates. Also strings added
209 * with g_string_chunk_insert() will not be searched
210 * by g_string_chunk_insert_const() when looking for
213 * Returns: a pointer to the copy of @string within
217 g_string_chunk_insert (GStringChunk *chunk,
220 g_return_val_if_fail (chunk != NULL, NULL);
222 return g_string_chunk_insert_len (chunk, string, -1);
226 * g_string_chunk_insert_const:
227 * @chunk: a #GStringChunk
228 * @string: the string to add
230 * Adds a copy of @string to the #GStringChunk, unless the same
231 * string has already been added to the #GStringChunk with
232 * g_string_chunk_insert_const().
234 * This function is useful if you need to copy a large number
235 * of strings but do not want to waste space storing duplicates.
236 * But you must remember that there may be several pointers to
237 * the same string, and so any changes made to the strings
238 * should be done very carefully.
240 * Note that g_string_chunk_insert_const() will not return a
241 * pointer to a string added with g_string_chunk_insert(), even
244 * Returns: a pointer to the new or existing copy of @string
245 * within the #GStringChunk
248 g_string_chunk_insert_const (GStringChunk *chunk,
253 g_return_val_if_fail (chunk != NULL, NULL);
255 if (!chunk->const_table)
256 chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
258 lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
262 lookup = g_string_chunk_insert (chunk, string);
263 g_hash_table_insert (chunk->const_table, lookup, lookup);
270 * g_string_chunk_insert_len:
271 * @chunk: a #GStringChunk
272 * @string: bytes to insert
273 * @len: number of bytes of @string to insert, or -1 to insert a
274 * nul-terminated string
276 * Adds a copy of the first @len bytes of @string to the #GStringChunk.
277 * The copy is nul-terminated.
279 * Since this function does not stop at nul bytes, it is the caller's
280 * responsibility to ensure that @string has at least @len addressable
283 * The characters in the returned string can be changed, if necessary,
284 * though you should not change anything after the end of the string.
286 * Return value: a pointer to the copy of @string within the #GStringChunk
291 g_string_chunk_insert_len (GStringChunk *chunk,
298 g_return_val_if_fail (chunk != NULL, NULL);
301 size = strlen (string);
305 if ((chunk->storage_next + size + 1) > chunk->this_size)
307 gsize new_size = nearest_power (chunk->default_size, size + 1);
309 chunk->storage_list = g_slist_prepend (chunk->storage_list,
310 g_new (gchar, new_size));
312 chunk->this_size = new_size;
313 chunk->storage_next = 0;
316 pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
318 *(pos + size) = '\0';
320 memcpy (pos, string, size);
322 chunk->storage_next += size + 1;