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
  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 (1, 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 (chunk->storage_list, g_free);
 149
 150   if (chunk->const_table)
 151     g_hash_table_destroy (chunk->const_table);
 152
 153   g_free (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 (chunk->storage_list, 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 (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, -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 (g_str_hash, g_str_equal);
 245
 246   lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
 247
 248   if (!lookup)
 249     {
 250       lookup = g_string_chunk_insert (chunk, string);
 251       g_hash_table_add (chunk->const_table, 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 (string);
 290   else
 291     size = len;
 292
 293   if ((chunk->storage_next + size + 1) > chunk->this_size)
 294     {
 295       gsize new_size = nearest_power (chunk->default_size, size + 1);
 296
 297       chunk->storage_list = g_slist_prepend (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 (pos, string, size);
 309
 310   chunk->storage_next += size + 1;
 311
 312   return pos;
 313 }