/* 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;
}