/* GLIB - Library of useful routines for C programming
* Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
/*
* Modified by the GLib Team and others 1997-2000. See the AUTHORS
* file for a list of people on the GLib Team. See the ChangeLog
* files for a list of changes. These files are distributed with
* GLib at ftp://ftp.gtk.org/pub/gtk/.
*/
/*
* MT safe
*/
#include "config.h"
#include <string.h>
#include "gstringchunk.h"
#include "ghash.h"
#include "gslist.h"
#include "gmessages.h"
#include "gutils.h"
/**
* SECTION:string_chunks
* @title: String Chunks
* @short_description: efficient storage of groups of strings
*
* String chunks are used to store groups of strings. Memory is
* allocated in blocks, and as strings are added to the #GStringChunk
* they are copied into the next free position in a block. When a block
* is full a new block is allocated.
*
* When storing a large number of strings, string chunks are more
* efficient than using g_strdup() since fewer calls to malloc() are
* needed, and less memory is wasted in memory allocation overheads.
*
* By adding strings with g_string_chunk_insert_const() it is also
* possible to remove duplicates.
*
* To create a new #GStringChunk use g_string_chunk_new().
*
* To add strings to a #GStringChunk use g_string_chunk_insert().
*
* To add strings to a #GStringChunk, but without duplicating strings
* which are already in the #GStringChunk, use
* g_string_chunk_insert_const().
*
* To free the entire #GStringChunk use g_string_chunk_free(). It is
* not possible to free individual strings.
*/
/**
* GStringChunk:
*
* An opaque data structure representing String Chunks.
* It should only be accessed by using the following functions.
*/
struct _GStringChunk
{
GHashTable *const_table;
GSList *storage_list;
gsize storage_next;
gsize this_size;
gsize default_size;
};
#define MY_MAXSIZE ((gsize)-1)
static inline gsize
nearest_power (gsize base,
gsize num)
{
if (num > MY_MAXSIZE / 2)
{
return MY_MAXSIZE;
}
else
{
gsize n = base;
while (n < num)
n <<= 1;
return n;
}
}
/**
* g_string_chunk_new:
* @size: the default size of the blocks of memory which are
* allocated to store the strings. If a particular string
* is larger than this default size, a larger block of
* memory will be allocated for it.
*
* Creates a new #GStringChunk.
*
* Returns: a new #GStringChunk
*/
GStringChunk *
g_string_chunk_new (gsize size)
{
GStringChunk *new_chunk = g_new (GStringChunk, 1);
gsize actual_size = 1;
actual_size = nearest_power (1, size);
new_chunk->const_table = NULL;
new_chunk->storage_list = NULL;
new_chunk->storage_next = actual_size;
new_chunk->default_size = actual_size;
new_chunk->this_size = actual_size;
return new_chunk;
}
/**
* g_string_chunk_free:
* @chunk: a #GStringChunk
*
* Frees all memory allocated by the #GStringChunk.
* After calling g_string_chunk_free() it is not safe to
* access any of the strings which were contained within it.
*/
void
g_string_chunk_free (GStringChunk *chunk)
{
GSList *tmp_list;
g_return_if_fail (chunk != NULL);
if (chunk->storage_list)
{
for (tmp_list = chunk->storage_list; tmp_list; tmp_list = tmp_list->next)
g_free (tmp_list->data);
g_slist_free (chunk->storage_list);
}
if (chunk->const_table)
g_hash_table_destroy (chunk->const_table);
g_free (chunk);
}
/**
* g_string_chunk_clear:
* @chunk: a #GStringChunk
*
* Frees all strings contained within the #GStringChunk.
* After calling g_string_chunk_clear() it is not safe to
* access any of the strings which were contained within it.
*
* Since: 2.14
*/
void
g_string_chunk_clear (GStringChunk *chunk)
{
GSList *tmp_list;
g_return_if_fail (chunk != NULL);
if (chunk->storage_list)
{
for (tmp_list = chunk->storage_list; tmp_list; tmp_list = tmp_list->next)
g_free (tmp_list->data);
g_slist_free (chunk->storage_list);
chunk->storage_list = NULL;
chunk->storage_next = chunk->default_size;
chunk->this_size = chunk->default_size;
}
if (chunk->const_table)
g_hash_table_remove_all (chunk->const_table);
}
/**
* g_string_chunk_insert:
* @chunk: a #GStringChunk
* @string: the string to add
*
* Adds a copy of @string to the #GStringChunk.
* It returns a pointer to the new copy of the string
* in the #GStringChunk. The characters in the string
* can be changed, if necessary, though you should not
* change anything after the end of the string.
*
* Unlike g_string_chunk_insert_const(), this function
* does not check for duplicates. Also strings added
* with g_string_chunk_insert() will not be searched
* by g_string_chunk_insert_const() when looking for
* duplicates.
*
* Returns: a pointer to the copy of @string within
* the #GStringChunk
*/
gchar*
g_string_chunk_insert (GStringChunk *chunk,
const gchar *string)
{
g_return_val_if_fail (chunk != NULL, NULL);
return g_string_chunk_insert_len (chunk, string, -1);
}
/**
* g_string_chunk_insert_const:
* @chunk: a #GStringChunk
* @string: the string to add
*
* Adds a copy of @string to the #GStringChunk, unless the same
* string has already been added to the #GStringChunk with
* g_string_chunk_insert_const().
*
* This function is useful if you need to copy a large number
* of strings but do not want to waste space storing duplicates.
* But you must remember that there may be several pointers to
* the same string, and so any changes made to the strings
* should be done very carefully.
*
* Note that g_string_chunk_insert_const() will not return a
* pointer to a string added with g_string_chunk_insert(), even
* if they do match.
*
* Returns: a pointer to the new or existing copy of @string
* within the #GStringChunk
*/
gchar*
g_string_chunk_insert_const (GStringChunk *chunk,
const gchar *string)
{
char* lookup;
g_return_val_if_fail (chunk != NULL, NULL);
if (!chunk->const_table)
chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
if (!lookup)
{
lookup = g_string_chunk_insert (chunk, string);
g_hash_table_insert (chunk->const_table, lookup, lookup);
}
return lookup;
}
/**
* g_string_chunk_insert_len:
* @chunk: a #GStringChunk
* @string: bytes to insert
* @len: number of bytes of @string to insert, or -1 to insert a
* nul-terminated string
*
* Adds a copy of the first @len bytes of @string to the #GStringChunk.
* The copy is nul-terminated.
*
* Since this function does not stop at nul bytes, it is the caller's
* responsibility to ensure that @string has at least @len addressable
* bytes.
*
* The characters in the returned string can be changed, if necessary,
* though you should not change anything after the end of the string.
*
* Return value: a pointer to the copy of @string within the #GStringChunk
*
* Since: 2.4
*/
gchar*
g_string_chunk_insert_len (GStringChunk *chunk,
const gchar *string,
gssize len)
{
gssize size;
gchar* pos;
g_return_val_if_fail (chunk != NULL, NULL);
if (len < 0)
size = strlen (string);
else
size = len;
if ((chunk->storage_next + size + 1) > chunk->this_size)
{
gsize new_size = nearest_power (chunk->default_size, size + 1);
chunk->storage_list = g_slist_prepend (chunk->storage_list,
g_new (gchar, new_size));
chunk->this_size = new_size;
chunk->storage_next = 0;
}
pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
*(pos + size) = '\0';
memcpy (pos, string, size);
chunk->storage_next += size + 1;
return pos;
}