glib/gbsearcharray.c

/* GObject - GLib Type, Object, Parameter and Signal Library
 * Copyright (C) 2000-2001 Tim Janik
 *
 * 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.
 */

#include "config.h"

#define G_IMPLEMENT_INLINES 1
#define __G_BSEARCHARRAY_C__
#include "gbsearcharray.h"

#include	<string.h>


/* --- structures --- */
static inline guint
upper_power2 (guint number)
{
#ifdef	DISABLE_MEM_POOLS
  return number;
#else	/* !DISABLE_MEM_POOLS */
  return number ? 1 << g_bit_storage (number - 1) : 0;
#endif	/* !DISABLE_MEM_POOLS */
}

GBSearchArray*
g_bsearch_array_new (GBSearchConfig *bconfig)
{
  GBSearchArray *barray;
  guint size;

  g_return_val_if_fail (bconfig != NULL, NULL);

  size = sizeof (GBSearchArray) + bconfig->sizeof_node;
  if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
    size = upper_power2 (size);
  barray = g_malloc0 (size);
  barray->n_nodes = 0;

  return barray;
}

void
g_bsearch_array_destroy (GBSearchArray  *barray,
			 GBSearchConfig *bconfig)
{
  g_return_if_fail (barray != NULL);

  g_free (barray);
}

static inline GBSearchArray*
bsearch_array_insert (GBSearchArray  *barray,
		      GBSearchConfig *bconfig,
		      gconstpointer   key_node,
		      gboolean        replace)
{
  gint sizeof_node;
  guint8 *check;
  
  sizeof_node = bconfig->sizeof_node;
  if (barray->n_nodes == 0)
    {
      guint new_size = sizeof (GBSearchArray) + sizeof_node;
      
      if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
	new_size = upper_power2 (new_size);
      barray = g_realloc (barray, new_size);
      barray->n_nodes = 1;
      check = G_BSEARCH_ARRAY_NODES (barray);
    }
  else
    {
      GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
      guint n_nodes = barray->n_nodes;
      guint8 *nodes = G_BSEARCH_ARRAY_NODES (barray);
      gint cmp;
      guint i;
      
      nodes -= sizeof_node;
      do
	{
	  i = (n_nodes + 1) >> 1;
	  check = nodes + i * sizeof_node;
	  cmp = cmp_nodes (key_node, check);
	  if (cmp > 0)
	    {
	      n_nodes -= i;
	      nodes = check;
	    }
	  else if (cmp < 0)
	    n_nodes = i - 1;
	  else /* if (cmp == 0) */
	    {
	      if (replace)
		memcpy (check, key_node, sizeof_node);
	      return barray;
	    }
	}
      while (n_nodes);
      /* grow */
      if (cmp > 0)
	check += sizeof_node;
      i = (check - ((guint8*) G_BSEARCH_ARRAY_NODES (barray))) / sizeof_node;
      n_nodes = barray->n_nodes++;
      if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
	{
	  guint new_size = upper_power2 (sizeof (GBSearchArray) + barray->n_nodes * sizeof_node);
	  guint old_size = upper_power2 (sizeof (GBSearchArray) + n_nodes * sizeof_node);
	  
	  if (new_size != old_size)
	    barray = g_realloc (barray, new_size);
	}
      else
	barray = g_realloc (barray, sizeof (GBSearchArray) + barray->n_nodes * sizeof_node);
      check = ((guint8*) G_BSEARCH_ARRAY_NODES (barray)) + i * sizeof_node;
      g_memmove (check + sizeof_node, check, (n_nodes - i) * sizeof_node);
    }
  memcpy (check, key_node, sizeof_node);
  
  return barray;
}

GBSearchArray*
g_bsearch_array_insert (GBSearchArray  *barray,
			GBSearchConfig *bconfig,
			gconstpointer   key_node,
			gboolean        replace_existing)
{
  g_return_val_if_fail (barray != NULL, NULL);
  g_return_val_if_fail (bconfig != NULL, barray);
  g_return_val_if_fail (key_node != NULL, barray);
  
  return bsearch_array_insert (barray, bconfig, key_node, replace_existing);
}

GBSearchArray*
g_bsearch_array_remove_node (GBSearchArray  *barray,
			     GBSearchConfig *bconfig,
			     gpointer       _node_in_array)
{
  guint8 *nodes, *bound, *node_in_array = _node_in_array;
  guint old_size;
  
  g_return_val_if_fail (barray != NULL, NULL);
  g_return_val_if_fail (bconfig != NULL, barray);
  
  nodes = G_BSEARCH_ARRAY_NODES (barray);
  old_size = bconfig->sizeof_node;
  old_size *= barray->n_nodes;  /* beware of int widths */
  bound = nodes + old_size;
  
  g_return_val_if_fail (node_in_array >= nodes && node_in_array < bound, barray);

  bound -= bconfig->sizeof_node;
  barray->n_nodes -= 1;
  g_memmove (node_in_array, node_in_array + bconfig->sizeof_node, (bound - node_in_array) / bconfig->sizeof_node);
  
  if ((bconfig->flags & G_BSEARCH_ARRAY_DEFER_SHRINK) == 0)
    {
      guint new_size = bound - nodes;   /* old_size - bconfig->sizeof_node */
      
      if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
	{
	  new_size = upper_power2 (sizeof (GBSearchArray) + new_size);
	  old_size = upper_power2 (sizeof (GBSearchArray) + old_size);
	  if (old_size != new_size)
	    barray = g_realloc (barray, new_size);
	}
      else
	barray = g_realloc (barray, sizeof (GBSearchArray) + new_size);
    }
  return barray;
}

GBSearchArray*
g_bsearch_array_remove (GBSearchArray  *barray,
			GBSearchConfig *bconfig,
			gconstpointer   key_node)
{
  gpointer node_in_array;
  
  g_return_val_if_fail (barray != NULL, NULL);
  g_return_val_if_fail (bconfig != NULL, barray);
  
  node_in_array = g_bsearch_array_lookup (barray, bconfig, key_node);
  if (!node_in_array)
    {
      g_warning (G_STRLOC ": unable to remove unexistant node");
      return barray;
    }
  else
    return g_bsearch_array_remove_node (barray, bconfig, node_in_array);
}