glib/gbsearcharray.c

   1 /* GObject - GLib Type, Object, Parameter and Signal Library
   2  * Copyright (C) 2000-2001 Tim Janik
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General
  15  * Public License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19 #define G_IMPLEMENT_INLINES 1
  20 #define __G_BSEARCHARRAY_C__
  21 #include "gbsearcharray.h"
  22
  23 #include        <string.h>
  24
  25
  26 /* --- structures --- */
  27 static inline guint
  28 upper_power2 (guint number)
  29 {
  30 #ifdef  DISABLE_MEM_POOLS
  31   return number;
  32 #else   /* !DISABLE_MEM_POOLS */
  33   return number ? 1 << g_bit_storage (number - 1) : 0;
  34 #endif  /* !DISABLE_MEM_POOLS */
  35 }
  36
  37 static inline gpointer
  38 bsearch_array_insert (GBSearchArray *barray,
  39                       gconstpointer  key_node,
  40                       gboolean       replace)
  41 {
  42   gint sizeof_node;
  43   guint8 *check;
  44
  45   sizeof_node = barray->sizeof_node;
  46   if (barray->n_nodes == 0)
  47     {
  48       guint new_size = barray->sizeof_node;
  49
  50       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
  51         new_size = upper_power2 (new_size);
  52       barray->nodes = g_realloc (barray->nodes, new_size);
  53       barray->n_nodes = 1;
  54       check = barray->nodes;
  55       replace = TRUE;
  56     }
  57   else
  58     {
  59       GBSearchCompareFunc cmp_func = barray->cmp_func;
  60       guint n_nodes = barray->n_nodes;
  61       guint8 *nodes = barray->nodes;
  62       gint cmp;
  63       guint i;
  64
  65       nodes -= sizeof_node;
  66       do
  67         {
  68           i = (n_nodes + 1) >> 1;
  69           check = nodes + i * sizeof_node;
  70           cmp = cmp_func (key_node, check);
  71           if (cmp > 0)
  72             {
  73               n_nodes -= i;
  74               nodes = check;
  75             }
  76           else if (cmp < 0)
  77             n_nodes = i - 1;
  78           else /* if (cmp == 0) */
  79             goto SKIP_GROW;
  80         }
  81       while (n_nodes);
  82       /* grow */
  83       if (cmp > 0)
  84         check += sizeof_node;
  85       i = (check - ((guint8*) barray->nodes)) / sizeof_node;
  86       n_nodes = barray->n_nodes++;
  87       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
  88         {
  89           guint new_size = upper_power2 (barray->n_nodes * sizeof_node);
  90           guint old_size = upper_power2 (n_nodes * sizeof_node);
  91
  92           if (new_size != old_size)
  93             barray->nodes = g_realloc (barray->nodes, new_size);
  94         }
  95       else
  96         barray->nodes = g_realloc (barray->nodes, barray->n_nodes * sizeof_node);
  97       check = ((guint8*) barray->nodes) + i * sizeof_node;
  98       g_memmove (check + sizeof_node, check, (n_nodes - i) * sizeof_node);
  99       replace = TRUE;
 100     SKIP_GROW:
 101       ;
 102     }
 103   if (replace)
 104     memcpy (check, key_node, sizeof_node);
 105
 106   return check;
 107 }
 108
 109 gpointer
 110 g_bsearch_array_insert (GBSearchArray *barray,
 111                         gconstpointer  key_node,
 112                         gboolean       replace_existing)
 113 {
 114   g_return_val_if_fail (barray != NULL, NULL);
 115   g_return_val_if_fail (key_node != NULL, NULL);
 116
 117   return bsearch_array_insert (barray, key_node, replace_existing);
 118 }
 119
 120 void
 121 g_bsearch_array_remove_node (GBSearchArray *barray,
 122                              gpointer       _node_in_array)
 123 {
 124   guint8 *nodes, *bound, *node_in_array = _node_in_array;
 125   guint old_size;
 126
 127   g_return_if_fail (barray != NULL);
 128
 129   nodes = barray->nodes;
 130   old_size = barray->sizeof_node;
 131   old_size *= barray->n_nodes;  /* beware of int widths */
 132   bound = nodes + old_size;
 133
 134   g_return_if_fail (node_in_array >= nodes && node_in_array < bound);
 135
 136   bound -= barray->sizeof_node;
 137   barray->n_nodes -= 1;
 138   g_memmove (node_in_array, node_in_array + barray->sizeof_node, (bound - node_in_array) / barray->sizeof_node);
 139
 140   if ((barray->flags & G_BSEARCH_DEFER_SHRINK) == 0)
 141     {
 142       guint new_size = bound - nodes;   /* old_size - barray->sizeof_node */
 143
 144       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
 145         {
 146           new_size = upper_power2 (new_size);
 147           old_size = upper_power2 (old_size);
 148           if (old_size != new_size)
 149             barray->nodes = g_realloc (barray->nodes, new_size);
 150         }
 151       else
 152         barray->nodes = g_realloc (barray->nodes, new_size);
 153     }
 154 }
 155
 156 void
 157 g_bsearch_array_remove (GBSearchArray *barray,
 158                         gconstpointer  key_node)
 159 {
 160   gpointer node_in_array;
 161
 162   g_return_if_fail (barray != NULL);
 163
 164   node_in_array = g_bsearch_array_lookup (barray, key_node);
 165   if (!node_in_array)
 166     g_warning (G_STRLOC ": unable to remove unexistant node");
 167   else
 168     g_bsearch_array_remove_node (barray, node_in_array);
 169 }