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