glib/garray.c - third_party/glib - Git at Google

 /*
  * garray.c - Dynamically-growing arrays for fast index-based access
  *
  * MT-Level: Safe
  *
  * GLIB - Library of useful routines for C programming
  * Copyright 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
  * Copyright 1998  Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library 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
  * Library General Public License for more details.
  *
  * You should have received a copy of the GNU Library 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.
  */

 #ifdef HAVE_CONFIG_H
 #  include <config.h>
 #endif

 #include <string.h>
 #include "glib.h"


 #define MIN_ARRAY_SIZE  16


 typedef struct _GRealArray  GRealArray;

 struct _GRealArray
 {
   guint8 *data;
   guint   len;
   guint   alloc;
   guint   elt_size;
   guint   zero_terminated : 1;
   guint   clear : 1;
 };


 static gint g_nearest_pow        (gint        num);
 static void g_array_maybe_expand (GRealArray *array,
 				  gint        len);


 static GMemChunk *array_mem_chunk = NULL;
 G_THREAD_SPROTECT(array_mem_chunk)


 GArray*
 g_array_new (gboolean zero_terminated,
 	     gboolean clear,
 	     guint    elt_size)
 {
   GRealArray *array;

   g_thread_lock(array_mem_chunk);

   if (!array_mem_chunk)
     array_mem_chunk = g_mem_chunk_new ("array mem chunk",
 				       sizeof (GRealArray),
 				       1024, G_ALLOC_AND_FREE);

   array = g_chunk_new (GRealArray, array_mem_chunk);

   g_thread_unlock(array_mem_chunk);

   array->data            = NULL;
   array->len             = 0;
   array->alloc           = 0;
   array->zero_terminated = (zero_terminated ? 1 : 0);
   array->clear           = (clear ? 1 : 0);
   array->elt_size        = elt_size;

   return (GArray*) array;
 }

 void
 g_array_free (GArray  *array,
 	      gboolean free_segment)
 {
   if (free_segment)
     g_free (array->data);

   g_thread_lock(array_mem_chunk);

   g_mem_chunk_free (array_mem_chunk, array);

   g_thread_unlock(array_mem_chunk);
 }

 GArray*
 g_array_append_vals (GArray       *farray,
 		     gconstpointer data,
 		     guint         len)
 {
   GRealArray *array = (GRealArray*) farray;

   g_array_maybe_expand (array, len);

   memcpy (array->data + array->elt_size * array->len, data, array->elt_size * len);

   array->len += len;

   return farray;
 }

 GArray*
 g_array_prepend_vals (GArray        *farray,
 		      gconstpointer  data,
 		      guint          len)
 {
   GRealArray *array = (GRealArray*) farray;

   g_array_maybe_expand (array, len);

   g_memmove (array->data + array->elt_size * len, array->data, array->elt_size * array->len);

   memcpy (array->data, data, len * array->elt_size);

   array->len += len;

   return farray;
 }

 GArray*
 g_array_set_size (GArray *farray,
 		  guint   length)
 {
   GRealArray *array = (GRealArray*) farray;

   if (array->len < length)
     g_array_maybe_expand (array, length - array->len);

   array->len = length;

   return farray;
 }

 GArray*
 g_array_remove_index (GArray* farray,
 		      guint index)
 {
   GRealArray* array = (GRealArray*) farray;

   g_return_val_if_fail (array, NULL);

   g_return_val_if_fail (index >= 0 && index < array->len, NULL);

   if (index != array->len - 1)
       g_memmove (array->data + array->elt_size * index,
 		 array->data + array->elt_size * (index + 1),
 		 array->elt_size * (array->len - index - 1));

   if (array->zero_terminated)
     memset (array->data + array->elt_size * (array->len - 1), 0,
 	    array->elt_size);

   array->len -= 1;

   return farray;
 }

 GArray*
 g_array_remove_index_fast (GArray* farray,
 			   guint index)
 {
   GRealArray* array = (GRealArray*) farray;

   g_return_val_if_fail (array, NULL);

   g_return_val_if_fail (index >= 0 && index < array->len, NULL);

   if (index != array->len - 1)
     g_memmove (array->data + array->elt_size * index,
 	       array->data + array->elt_size * (array->len - 1),
 	       array->elt_size);

   if (array->zero_terminated)
     memset (array->data + array->elt_size * (array->len - 1), 0,
 	    array->elt_size);

   array->len -= 1;

   return farray;
 }

 static gint
 g_nearest_pow (gint num)
 {
   gint n = 1;

   while (n < num)
     n <<= 1;

   return n;
 }

 static void
 g_array_maybe_expand (GRealArray *array,
 		      gint        len)
 {
   guint want_alloc = (array->len + len + array->zero_terminated) * array->elt_size;

   if (want_alloc > array->alloc)
     {
       guint old_alloc = array->alloc;

       array->alloc = g_nearest_pow (want_alloc);
       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);

       array->data = g_realloc (array->data, array->alloc);

       if (array->clear || array->zero_terminated)
 	memset (array->data + old_alloc, 0, array->alloc - old_alloc);
     }
 }

 /* Pointer Array
  */

 typedef struct _GRealPtrArray  GRealPtrArray;

 struct _GRealPtrArray
 {
   gpointer *pdata;
   guint     len;
   guint     alloc;
 };

 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
 				      gint           len);


 static GMemChunk *ptr_array_mem_chunk = NULL;
 G_THREAD_SPROTECT(ptr_array_mem_chunk)


 GPtrArray*
 g_ptr_array_new (void)
 {
   GRealPtrArray *array;

   g_thread_lock(ptr_array_mem_chunk);

   if (!ptr_array_mem_chunk)
     ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
 					   sizeof (GRealPtrArray),
 					   1024, G_ALLOC_AND_FREE);

   array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);

   g_thread_unlock(ptr_array_mem_chunk);

   array->pdata = NULL;
   array->len = 0;
   array->alloc = 0;

   return (GPtrArray*) array;
 }

 void
 g_ptr_array_free (GPtrArray   *array,
 		  gboolean  free_segment)
 {
   g_return_if_fail (array);

   if (free_segment)
     g_free (array->pdata);

   g_thread_lock(ptr_array_mem_chunk);

   g_mem_chunk_free (ptr_array_mem_chunk, array);

   g_thread_unlock(ptr_array_mem_chunk);
 }

 static void
 g_ptr_array_maybe_expand (GRealPtrArray *array,
 			  gint        len)
 {
   guint old_alloc;

   if ((array->len + len) > array->alloc)
     {
       old_alloc = array->alloc;

       array->alloc = g_nearest_pow (array->len + len);
       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
       if (array->pdata)
 	array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
       else
 	array->pdata = g_new0 (gpointer, array->alloc);

       memset (array->pdata + old_alloc, 0, array->alloc - old_alloc);
     }
 }

 void
 g_ptr_array_set_size  (GPtrArray   *farray,
 		       gint	     length)
 {
   GRealPtrArray* array = (GRealPtrArray*) farray;

   g_return_if_fail (array);

   if (length > array->len)
     g_ptr_array_maybe_expand (array, (length - array->len));

   array->len = length;
 }

 gpointer
 g_ptr_array_remove_index (GPtrArray* farray,
 			  guint index)
 {
   GRealPtrArray* array = (GRealPtrArray*) farray;
   gpointer result;

   g_return_val_if_fail (array, NULL);

   g_return_val_if_fail (index >= 0 && index < array->len, NULL);

   result = array->pdata[index];

   if (index != array->len - 1)
     g_memmove (array->pdata + index, array->pdata + index + 1,
 	       array->len - index - 1);

   array->pdata[array->len - 1] = NULL;

   array->len -= 1;

   return result;
 }

 gpointer
 g_ptr_array_remove_index_fast (GPtrArray* farray,
 			       guint index)
 {
   GRealPtrArray* array = (GRealPtrArray*) farray;
   gpointer result;

   g_return_val_if_fail (array, NULL);

   g_return_val_if_fail (index >= 0 && index < array->len, NULL);

   result = array->pdata[index];

   if (index != array->len - 1)
     array->pdata[index] = array->pdata[array->len - 1];

   array->pdata[array->len - 1] = NULL;

   array->len -= 1;

   return result;
 }

 gboolean
 g_ptr_array_remove (GPtrArray* farray,
 		    gpointer data)
 {
   GRealPtrArray* array = (GRealPtrArray*) farray;
   int i;

   g_return_val_if_fail (array, FALSE);

   for (i = 0; i < array->len; i += 1)
     {
       if (array->pdata[i] == data)
 	{
 	  g_ptr_array_remove_index (farray, i);
 	  return TRUE;
 	}
     }

   return FALSE;
 }

 gboolean
 g_ptr_array_remove_fast (GPtrArray* farray,
 			 gpointer data)
 {
   GRealPtrArray* array = (GRealPtrArray*) farray;
   int i;

   g_return_val_if_fail (array, FALSE);

   for (i = 0; i < array->len; i += 1)
     {
       if (array->pdata[i] == data)
 	{
 	  g_ptr_array_remove_index_fast (farray, i);
 	  return TRUE;
 	}
     }

   return FALSE;
 }

 void
 g_ptr_array_add (GPtrArray* farray,
 		 gpointer data)
 {
   GRealPtrArray* array = (GRealPtrArray*) farray;

   g_return_if_fail (array);

   g_ptr_array_maybe_expand (array, 1);

   array->pdata[array->len++] = data;
 }

 /* Byte arrays
  */

 GByteArray* g_byte_array_new      (void)
 {
   return (GByteArray*) g_array_new (FALSE, FALSE, 1);
 }

 void	    g_byte_array_free     (GByteArray *array,
 			           gboolean    free_segment)
 {
   g_array_free ((GArray*) array, free_segment);
 }

 GByteArray* g_byte_array_append   (GByteArray *array,
 				   const guint8 *data,
 				   guint       len)
 {
   g_array_append_vals ((GArray*) array, (guint8*)data, len);

   return array;
 }

 GByteArray* g_byte_array_prepend  (GByteArray *array,
 				   const guint8 *data,
 				   guint       len)
 {
   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);

   return array;
 }

 GByteArray* g_byte_array_set_size (GByteArray *array,
 				   guint       length)
 {
   g_array_set_size ((GArray*) array, length);

   return array;
 }

 GByteArray* g_byte_array_remove_index (GByteArray *array,
 				       guint index)
 {
   g_array_remove_index((GArray*) array, index);

   return array;
 }

 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
 						   guint index)
 {
   g_array_remove_index_fast((GArray*) array, index);

   return array;
 }
	/*
	* garray.c - Dynamically-growing arrays for fast index-based access
	*
	* MT-Level: Safe
	*
	* GLIB - Library of useful routines for C programming
	* Copyright 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
	* Copyright 1998 Free Software Foundation, Inc.
	*
	* This library is free software; you can redistribute it and/or
	* modify it under the terms of the GNU Library 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
	* Library General Public License for more details.
	*
	* You should have received a copy of the GNU Library 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.
	*/

	#ifdef HAVE_CONFIG_H
	# include <config.h>
	#endif

	#include <string.h>
	#include "glib.h"


	#define MIN_ARRAY_SIZE 16


	typedef struct _GRealArray GRealArray;

	struct _GRealArray
	{
	guint8 *data;
	guint len;
	guint alloc;
	guint elt_size;
	guint zero_terminated : 1;
	guint clear : 1;
	};


	static gint g_nearest_pow (gint num);
	static void g_array_maybe_expand (GRealArray *array,
	gint len);


	static GMemChunk *array_mem_chunk = NULL;
	G_THREAD_SPROTECT(array_mem_chunk)


	GArray*
	g_array_new (gboolean zero_terminated,
	gboolean clear,
	guint elt_size)
	{
	GRealArray *array;

	g_thread_lock(array_mem_chunk);

	if (!array_mem_chunk)
	array_mem_chunk = g_mem_chunk_new ("array mem chunk",
	sizeof (GRealArray),
	1024, G_ALLOC_AND_FREE);

	array = g_chunk_new (GRealArray, array_mem_chunk);

	g_thread_unlock(array_mem_chunk);

	array->data = NULL;
	array->len = 0;
	array->alloc = 0;
	array->zero_terminated = (zero_terminated ? 1 : 0);
	array->clear = (clear ? 1 : 0);
	array->elt_size = elt_size;

	return (GArray*) array;
	}

	void
	g_array_free (GArray *array,
	gboolean free_segment)
	{
	if (free_segment)
	g_free (array->data);

	g_thread_lock(array_mem_chunk);

	g_mem_chunk_free (array_mem_chunk, array);

	g_thread_unlock(array_mem_chunk);
	}

	GArray*
	g_array_append_vals (GArray *farray,
	gconstpointer data,
	guint len)
	{
	GRealArray array = (GRealArray) farray;

	g_array_maybe_expand (array, len);

	memcpy (array->data + array->elt_size * array->len, data, array->elt_size * len);

	array->len += len;

	return farray;
	}

	GArray*
	g_array_prepend_vals (GArray *farray,
	gconstpointer data,
	guint len)
	{
	GRealArray array = (GRealArray) farray;

	g_array_maybe_expand (array, len);

	g_memmove (array->data + array->elt_size * len, array->data, array->elt_size * array->len);

	memcpy (array->data, data, len * array->elt_size);

	array->len += len;

	return farray;
	}

	GArray*
	g_array_set_size (GArray *farray,
	guint length)
	{
	GRealArray array = (GRealArray) farray;

	if (array->len < length)
	g_array_maybe_expand (array, length - array->len);

	array->len = length;

	return farray;
	}

	GArray*
	g_array_remove_index (GArray* farray,
	guint index)
	{
	GRealArray* array = (GRealArray*) farray;

	g_return_val_if_fail (array, NULL);

	g_return_val_if_fail (index >= 0 && index < array->len, NULL);

	if (index != array->len - 1)
	g_memmove (array->data + array->elt_size * index,
	array->data + array->elt_size * (index + 1),
	array->elt_size * (array->len - index - 1));

	if (array->zero_terminated)
	memset (array->data + array->elt_size * (array->len - 1), 0,
	array->elt_size);

	array->len -= 1;

	return farray;
	}

	GArray*
	g_array_remove_index_fast (GArray* farray,
	guint index)
	{
	GRealArray* array = (GRealArray*) farray;

	g_return_val_if_fail (array, NULL);

	g_return_val_if_fail (index >= 0 && index < array->len, NULL);

	if (index != array->len - 1)
	g_memmove (array->data + array->elt_size * index,
	array->data + array->elt_size * (array->len - 1),
	array->elt_size);

	if (array->zero_terminated)
	memset (array->data + array->elt_size * (array->len - 1), 0,
	array->elt_size);

	array->len -= 1;

	return farray;
	}

	static gint
	g_nearest_pow (gint num)
	{
	gint n = 1;

	while (n < num)
	n <<= 1;

	return n;
	}

	static void
	g_array_maybe_expand (GRealArray *array,
	gint len)
	{
	guint want_alloc = (array->len + len + array->zero_terminated) * array->elt_size;

	if (want_alloc > array->alloc)
	{
	guint old_alloc = array->alloc;

	array->alloc = g_nearest_pow (want_alloc);
	array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);

	array->data = g_realloc (array->data, array->alloc);

	if (array->clear \|\| array->zero_terminated)
	memset (array->data + old_alloc, 0, array->alloc - old_alloc);
	}
	}

	/* Pointer Array
	*/

	typedef struct _GRealPtrArray GRealPtrArray;

	struct _GRealPtrArray
	{
	gpointer *pdata;
	guint len;
	guint alloc;
	};

	static void g_ptr_array_maybe_expand (GRealPtrArray *array,
	gint len);


	static GMemChunk *ptr_array_mem_chunk = NULL;
	G_THREAD_SPROTECT(ptr_array_mem_chunk)



	GPtrArray*
	g_ptr_array_new (void)
	{
	GRealPtrArray *array;

	g_thread_lock(ptr_array_mem_chunk);

	if (!ptr_array_mem_chunk)
	ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
	sizeof (GRealPtrArray),
	1024, G_ALLOC_AND_FREE);

	array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);

	g_thread_unlock(ptr_array_mem_chunk);

	array->pdata = NULL;
	array->len = 0;
	array->alloc = 0;

	return (GPtrArray*) array;
	}

	void
	g_ptr_array_free (GPtrArray *array,
	gboolean free_segment)
	{
	g_return_if_fail (array);

	if (free_segment)
	g_free (array->pdata);

	g_thread_lock(ptr_array_mem_chunk);

	g_mem_chunk_free (ptr_array_mem_chunk, array);

	g_thread_unlock(ptr_array_mem_chunk);
	}

	static void
	g_ptr_array_maybe_expand (GRealPtrArray *array,
	gint len)
	{
	guint old_alloc;

	if ((array->len + len) > array->alloc)
	{
	old_alloc = array->alloc;

	array->alloc = g_nearest_pow (array->len + len);
	array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
	if (array->pdata)
	array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
	else
	array->pdata = g_new0 (gpointer, array->alloc);

	memset (array->pdata + old_alloc, 0, array->alloc - old_alloc);
	}
	}

	void
	g_ptr_array_set_size (GPtrArray *farray,
	gint length)
	{
	GRealPtrArray* array = (GRealPtrArray*) farray;

	g_return_if_fail (array);

	if (length > array->len)
	g_ptr_array_maybe_expand (array, (length - array->len));

	array->len = length;
	}

	gpointer
	g_ptr_array_remove_index (GPtrArray* farray,
	guint index)
	{
	GRealPtrArray* array = (GRealPtrArray*) farray;
	gpointer result;

	g_return_val_if_fail (array, NULL);

	g_return_val_if_fail (index >= 0 && index < array->len, NULL);

	result = array->pdata[index];

	if (index != array->len - 1)
	g_memmove (array->pdata + index, array->pdata + index + 1,
	array->len - index - 1);

	array->pdata[array->len - 1] = NULL;

	array->len -= 1;

	return result;
	}

	gpointer
	g_ptr_array_remove_index_fast (GPtrArray* farray,
	guint index)
	{
	GRealPtrArray* array = (GRealPtrArray*) farray;
	gpointer result;

	g_return_val_if_fail (array, NULL);

	g_return_val_if_fail (index >= 0 && index < array->len, NULL);

	result = array->pdata[index];

	if (index != array->len - 1)
	array->pdata[index] = array->pdata[array->len - 1];

	array->pdata[array->len - 1] = NULL;

	array->len -= 1;

	return result;
	}

	gboolean
	g_ptr_array_remove (GPtrArray* farray,
	gpointer data)
	{
	GRealPtrArray* array = (GRealPtrArray*) farray;
	int i;

	g_return_val_if_fail (array, FALSE);

	for (i = 0; i < array->len; i += 1)
	{
	if (array->pdata[i] == data)
	{
	g_ptr_array_remove_index (farray, i);
	return TRUE;
	}
	}

	return FALSE;
	}

	gboolean
	g_ptr_array_remove_fast (GPtrArray* farray,
	gpointer data)
	{
	GRealPtrArray* array = (GRealPtrArray*) farray;
	int i;

	g_return_val_if_fail (array, FALSE);

	for (i = 0; i < array->len; i += 1)
	{
	if (array->pdata[i] == data)
	{
	g_ptr_array_remove_index_fast (farray, i);
	return TRUE;
	}
	}

	return FALSE;
	}

	void
	g_ptr_array_add (GPtrArray* farray,
	gpointer data)
	{
	GRealPtrArray* array = (GRealPtrArray*) farray;

	g_return_if_fail (array);

	g_ptr_array_maybe_expand (array, 1);

	array->pdata[array->len++] = data;
	}

	/* Byte arrays
	*/

	GByteArray* g_byte_array_new (void)
	{
	return (GByteArray*) g_array_new (FALSE, FALSE, 1);
	}

	void g_byte_array_free (GByteArray *array,
	gboolean free_segment)
	{
	g_array_free ((GArray*) array, free_segment);
	}

	GByteArray* g_byte_array_append (GByteArray *array,
	const guint8 *data,
	guint len)
	{
	g_array_append_vals ((GArray) array, (guint8)data, len);

	return array;
	}

	GByteArray* g_byte_array_prepend (GByteArray *array,
	const guint8 *data,
	guint len)
	{
	g_array_prepend_vals ((GArray) array, (guint8)data, len);

	return array;
	}

	GByteArray* g_byte_array_set_size (GByteArray *array,
	guint length)
	{
	g_array_set_size ((GArray*) array, length);

	return array;
	}

	GByteArray* g_byte_array_remove_index (GByteArray *array,
	guint index)
	{
	g_array_remove_index((GArray*) array, index);

	return array;
	}

	GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
	guint index)
	{
	g_array_remove_index_fast((GArray*) array, index);

	return array;
	}