glib/gstringchunk.c

   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 #include "gutilsprivate.h"
  41
  42 /**
  43  * SECTION:string_chunks
  44  * @title: String Chunks
  45  * @short_description: efficient storage of groups of strings
  46  *
  47  * String chunks are used to store groups of strings. Memory is
  48  * allocated in blocks, and as strings are added to the #GStringChunk
  49  * they are copied into the next free position in a block. When a block
  50  * is full a new block is allocated.
  51  *
  52  * When storing a large number of strings, string chunks are more
  53  * efficient than using g_strdup() since fewer calls to malloc() are
  54  * needed, and less memory is wasted in memory allocation overheads.
  55  *
  56  * By adding strings with g_string_chunk_insert_const() it is also
  57  * possible to remove duplicates.
  58  *
  59  * To create a new #GStringChunk use g_string_chunk_new().
  60  *
  61  * To add strings to a #GStringChunk use g_string_chunk_insert().
  62  *
  63  * To add strings to a #GStringChunk, but without duplicating strings
  64  * which are already in the #GStringChunk, use
  65  * g_string_chunk_insert_const().
  66  *
  67  * To free the entire #GStringChunk use g_string_chunk_free(). It is
  68  * not possible to free individual strings.
  69  */
  70
  71 /**
  72  * GStringChunk:
  73  *
  74  * An opaque data structure representing String Chunks.
  75  * It should only be accessed by using the following functions.
  76  */
  77 struct _GStringChunk
  78 {
  79   GHashTable *const_table;
  80   GSList     *storage_list;
  81   gsize       storage_next;
  82   gsize       this_size;
  83   gsize       default_size;
  84 };
  85
  86 /**
  87  * g_string_chunk_new:
  88  * @size: the default size of the blocks of memory which are
  89  *     allocated to store the strings. If a particular string
  90  *     is larger than this default size, a larger block of
  91  *     memory will be allocated for it.
  92  *
  93  * Creates a new #GStringChunk.
  94  *
  95  * Returns: a new #GStringChunk
  96  */
  97 GStringChunk *
  98 g_string_chunk_new (gsize size)
  99 {
 100   GStringChunk *new_chunk = g_new (GStringChunk, 1);
 101   gsize actual_size = 1;
 102
 103   actual_size = g_nearest_pow (MAX (1, size));
 104
 105   new_chunk->const_table  = NULL;
 106   new_chunk->storage_list = NULL;
 107   new_chunk->storage_next = actual_size;
 108   new_chunk->default_size = actual_size;
 109   new_chunk->this_size    = actual_size;
 110
 111   return new_chunk;
 112 }
 113
 114 /**
 115  * g_string_chunk_free:
 116  * @chunk: a #GStringChunk
 117  *
 118  * Frees all memory allocated by the #GStringChunk.
 119  * After calling g_string_chunk_free() it is not safe to
 120  * access any of the strings which were contained within it.
 121  */
 122 void
 123 g_string_chunk_free (GStringChunk *chunk)
 124 {
 125   g_return_if_fail (chunk != NULL);
 126
 127   if (chunk->storage_list)
 128     g_slist_free_full (chunk->storage_list, g_free);
 129
 130   if (chunk->const_table)
 131     g_hash_table_destroy (chunk->const_table);
 132
 133   g_free (chunk);
 134 }
 135
 136 /**
 137  * g_string_chunk_clear:
 138  * @chunk: a #GStringChunk
 139  *
 140  * Frees all strings contained within the #GStringChunk.
 141  * After calling g_string_chunk_clear() it is not safe to
 142  * access any of the strings which were contained within it.
 143  *
 144  * Since: 2.14
 145  */
 146 void
 147 g_string_chunk_clear (GStringChunk *chunk)
 148 {
 149   g_return_if_fail (chunk != NULL);
 150
 151   if (chunk->storage_list)
 152     {
 153       g_slist_free_full (chunk->storage_list, g_free);
 154
 155       chunk->storage_list = NULL;
 156       chunk->storage_next = chunk->default_size;
 157       chunk->this_size    = chunk->default_size;
 158     }
 159
 160   if (chunk->const_table)
 161       g_hash_table_remove_all (chunk->const_table);
 162 }
 163
 164 /**
 165  * g_string_chunk_insert:
 166  * @chunk: a #GStringChunk
 167  * @string: the string to add
 168  *
 169  * Adds a copy of @string to the #GStringChunk.
 170  * It returns a pointer to the new copy of the string
 171  * in the #GStringChunk. The characters in the string
 172  * can be changed, if necessary, though you should not
 173  * change anything after the end of the string.
 174  *
 175  * Unlike g_string_chunk_insert_const(), this function
 176  * does not check for duplicates. Also strings added
 177  * with g_string_chunk_insert() will not be searched
 178  * by g_string_chunk_insert_const() when looking for
 179  * duplicates.
 180  *
 181  * Returns: a pointer to the copy of @string within
 182  *     the #GStringChunk
 183  */
 184 gchar*
 185 g_string_chunk_insert (GStringChunk *chunk,
 186                        const gchar  *string)
 187 {
 188   g_return_val_if_fail (chunk != NULL, NULL);
 189
 190   return g_string_chunk_insert_len (chunk, string, -1);
 191 }
 192
 193 /**
 194  * g_string_chunk_insert_const:
 195  * @chunk: a #GStringChunk
 196  * @string: the string to add
 197  *
 198  * Adds a copy of @string to the #GStringChunk, unless the same
 199  * string has already been added to the #GStringChunk with
 200  * g_string_chunk_insert_const().
 201  *
 202  * This function is useful if you need to copy a large number
 203  * of strings but do not want to waste space storing duplicates.
 204  * But you must remember that there may be several pointers to
 205  * the same string, and so any changes made to the strings
 206  * should be done very carefully.
 207  *
 208  * Note that g_string_chunk_insert_const() will not return a
 209  * pointer to a string added with g_string_chunk_insert(), even
 210  * if they do match.
 211  *
 212  * Returns: a pointer to the new or existing copy of @string
 213  *     within the #GStringChunk
 214  */
 215 gchar*
 216 g_string_chunk_insert_const (GStringChunk *chunk,
 217                              const gchar  *string)
 218 {
 219   char* lookup;
 220
 221   g_return_val_if_fail (chunk != NULL, NULL);
 222
 223   if (!chunk->const_table)
 224     chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
 225
 226   lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
 227
 228   if (!lookup)
 229     {
 230       lookup = g_string_chunk_insert (chunk, string);
 231       g_hash_table_add (chunk->const_table, lookup);
 232     }
 233
 234   return lookup;
 235 }
 236
 237 /**
 238  * g_string_chunk_insert_len:
 239  * @chunk: a #GStringChunk
 240  * @string: bytes to insert
 241  * @len: number of bytes of @string to insert, or -1 to insert a
 242  *     nul-terminated string
 243  *
 244  * Adds a copy of the first @len bytes of @string to the #GStringChunk.
 245  * The copy is nul-terminated.
 246  *
 247  * Since this function does not stop at nul bytes, it is the caller's
 248  * responsibility to ensure that @string has at least @len addressable
 249  * bytes.
 250  *
 251  * The characters in the returned string can be changed, if necessary,
 252  * though you should not change anything after the end of the string.
 253  *
 254  * Returns: a pointer to the copy of @string within the #GStringChunk
 255  *
 256  * Since: 2.4
 257  */
 258 gchar*
 259 g_string_chunk_insert_len (GStringChunk *chunk,
 260                            const gchar  *string,
 261                            gssize        len)
 262 {
 263   gsize size;
 264   gchar* pos;
 265
 266   g_return_val_if_fail (chunk != NULL, NULL);
 267
 268   if (len < 0)
 269     size = strlen (string);
 270   else
 271     size = (gsize) len;
 272
 273   if ((G_MAXSIZE - chunk->storage_next < size + 1) || (chunk->storage_next + size + 1) > chunk->this_size)
 274     {
 275       gsize new_size = g_nearest_pow (MAX (chunk->default_size, size + 1));
 276
 277       /* If size is bigger than G_MAXSIZE / 2 then store it in its own
 278        * allocation instead of failing here */
 279       if (new_size == 0)
 280         new_size = size + 1;
 281
 282       chunk->storage_list = g_slist_prepend (chunk->storage_list,
 283                                              g_new (gchar, new_size));
 284
 285       chunk->this_size = new_size;
 286       chunk->storage_next = 0;
 287     }
 288
 289   pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
 290
 291   *(pos + size) = '\0';
 292
 293   memcpy (pos, string, size);
 294
 295   chunk->storage_next += size + 1;
 296
 297   return pos;
 298 }