/* GLIB - Library of useful routines for C programming

 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

 * Portions copyright (c) 2006-2009 Nokia Corporation.  All rights reserved.

 *

 * 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"

#ifdef HAVE_UNISTD_H

#include <unistd.h>

#endif

#include <stdarg.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include "glib.h"

#include "gprintf.h"

#include "galias.h"

struct _GStringChunk

{

  GHashTable *const_table;

  GSList     *storage_list;

  gsize       storage_next;    

  gsize       this_size;       

  gsize       default_size;    

};

/* Hash Functions.

 */

/**

 * g_str_equal:

 * @v1: a key

 * @v2: a key to compare with @v1

 * 

 * Compares two strings for byte-by-byte equality and returns %TRUE 

 * if they are equal. It can be passed to g_hash_table_new() as the 

 * @key_equal_func parameter, when using strings as keys in a #GHashTable.

 *

 * Returns: %TRUE if the two keys match

 */

EXPORT_C gboolean

g_str_equal (gconstpointer v1,

	     gconstpointer v2)

{

  const gchar *string1 = v1;

  const gchar *string2 = v2;

  return strcmp (string1, string2) == 0;

}

/**

 * g_str_hash:

 * @v: a string key

 *

 * Converts a string to a hash value.

 * It can be passed to g_hash_table_new() as the @hash_func 

 * parameter, when using strings as keys in a #GHashTable.

 *

 * Returns: a hash value corresponding to the key

 */

EXPORT_C guint

g_str_hash (gconstpointer v)

{

  /* 31 bit hash function */

  const signed char *p = v;

  guint32 h = *p;

  if (h)

    for (p += 1; *p != '\0'; p++)

      h = (h << 5) - h + *p;

  return h;

}

#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;

    }

}

/* String Chunks.

 */

/**

 * 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

 */

EXPORT_C 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.

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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;

}

/* Strings.

 */

static void

g_string_maybe_expand (GString* string,

		       gsize    len) 

{

  if (string->len + len >= string->allocated_len)

    {

      string->allocated_len = nearest_power (1, string->len + len + 1);

      string->str = g_realloc (string->str, string->allocated_len);

    }

}

/**

 * g_string_sized_new:

 * @dfl_size: the default size of the space allocated to 

 *            hold the string

 *

 * Creates a new #GString, with enough space for @dfl_size 

 * bytes. This is useful if you are going to add a lot of 

 * text to the string and don't want it to be reallocated 

 * too often.

 *

 * Returns: the new #GString

 */

EXPORT_C GString*

g_string_sized_new (gsize dfl_size)    

{

  GString *string = g_slice_new (GString);

  string->allocated_len = 0;

  string->len   = 0;

  string->str   = NULL;

  g_string_maybe_expand (string, MAX (dfl_size, 2));

  string->str[0] = 0;

  return string;

}

/**

 * g_string_new:

 * @init: the initial text to copy into the string

 * 

 * Creates a new #GString, initialized with the given string.

 *

 * Returns: the new #GString

 */

EXPORT_C GString*

g_string_new (const gchar *init)

{

  GString *string;

  if (init == NULL || *init == '\0')

    string = g_string_sized_new (2);

  else 

    {

      gint len;

      len = strlen (init);

      string = g_string_sized_new (len + 2);

      g_string_append_len (string, init, len);

    }

  return string;

}

/**

 * g_string_new_len:

 * @init: initial contents of the string

 * @len: length of @init to use

 *

 * Creates a new #GString with @len bytes of the @init buffer.  

 * Because a length is provided, @init need not be nul-terminated,

 * and can contain embedded nul bytes.

 *

 * Since this function does not stop at nul bytes, it is the caller's

 * responsibility to ensure that @init has at least @len addressable 

 * bytes.

 *

 * Returns: a new #GString

 */

EXPORT_C GString*

g_string_new_len (const gchar *init,

                  gssize       len)    

{

  GString *string;

  if (len < 0)

    return g_string_new (init);

  else

    {

      string = g_string_sized_new (len);

      if (init)

        g_string_append_len (string, init, len);

      return string;

    }

}

/**

 * g_string_free:

 * @string: a #GString

 * @free_segment: if %TRUE the actual character data is freed as well

 *

 * Frees the memory allocated for the #GString.

 * If @free_segment is %TRUE it also frees the character data.

 *

 * Returns: the character data of @string 

 *          (i.e. %NULL if @free_segment is %TRUE)

 */

EXPORT_C gchar*

g_string_free (GString *string,

	       gboolean free_segment)

{

  gchar *segment;

  g_return_val_if_fail (string != NULL, NULL);

  if (free_segment)

    {

      g_free (string->str);

      segment = NULL;

    }

  else

    segment = string->str;

  g_slice_free (GString, string);

  return segment;

}

/**

 * g_string_equal:

 * @v: a #GString

 * @v2: another #GString

 *

 * Compares two strings for equality, returning %TRUE if they are equal. 

 * For use with #GHashTable.

 *

 * Returns: %TRUE if they strings are the same length and contain the 

 *   same bytes

 */

EXPORT_C gboolean

g_string_equal (const GString *v,

                const GString *v2)

{

  gchar *p, *q;

  GString *string1 = (GString *) v;

  GString *string2 = (GString *) v2;

  gsize i = string1->len;    

  if (i != string2->len)

    return FALSE;

  p = string1->str;

  q = string2->str;

  while (i)

    {

      if (*p != *q)

	return FALSE;

      p++;

      q++;

      i--;

    }

  return TRUE;

}

/**

 * g_string_hash:

 * @str: a string to hash

 *

 * Creates a hash code for @str; for use with #GHashTable.

 *

 * Returns: hash code for @str

 */

/* 31 bit hash function */

EXPORT_C guint