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