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 GBSearchArray*
  28 g_bsearch_array_new (guint16             sizeof_node,
  29                      GBSearchCompareFunc node_cmp_func,
  30                      GBSearchArrayFlags  flags)
  31 {
  32   GBSearchArray *barray;
  33
  34   g_return_val_if_fail (sizeof_node > 0, NULL);
  35   g_return_val_if_fail (node_cmp_func != NULL, NULL);
  36
  37   barray = g_new0 (GBSearchArray, 1);
  38   barray->sizeof_node = sizeof_node;
  39   barray->cmp_nodes = node_cmp_func;
  40   barray->flags = flags;
  41
  42   return barray;
  43 }
  44
  45 void
  46 g_bsearch_array_destroy (GBSearchArray *barray)
  47 {
  48   g_return_if_fail (barray != NULL);
  49
  50 #if 0
  51   if (barray->destroy_node)
  52     while (barray->n_nodes)
  53       {
  54         barray->destroy_node (((guint8*) barray->nodes) + (barray->n_nodes - 1) * barray->sizeof_node);
  55         barray->n_nodes--;
  56       }
  57 #endif
  58   g_free (barray->nodes);
  59   g_free (barray);
  60 }
  61
  62 static inline guint
  63 upper_power2 (guint number)
  64 {
  65 #ifdef  DISABLE_MEM_POOLS
  66   return number;
  67 #else   /* !DISABLE_MEM_POOLS */
  68   return number ? 1 << g_bit_storage (number - 1) : 0;
  69 #endif  /* !DISABLE_MEM_POOLS */
  70 }
  71
  72 static inline gpointer
  73 bsearch_array_insert (GBSearchArray *barray,
  74                       gconstpointer  key_node,
  75                       gboolean       replace)
  76 {
  77   gint sizeof_node;
  78   guint8 *check;
  79
  80   sizeof_node = barray->sizeof_node;
  81   if (barray->n_nodes == 0)
  82     {
  83       guint new_size = barray->sizeof_node;
  84
  85       if (barray->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
  86         new_size = upper_power2 (new_size);
  87       barray->nodes = g_realloc (barray->nodes, new_size);
  88       barray->n_nodes = 1;
  89       check = barray->nodes;
  90     }
  91   else
  92     {
  93       GBSearchCompareFunc cmp_nodes = barray->cmp_nodes;
  94       guint n_nodes = barray->n_nodes;
  95       guint8 *nodes = barray->nodes;
  96       gint cmp;
  97       guint i;
  98
  99       nodes -= sizeof_node;
 100       do
 101         {
 102           i = (n_nodes + 1) >> 1;
 103           check = nodes + i * sizeof_node;
 104           cmp = cmp_nodes (key_node, check);
 105           if (cmp > 0)
 106             {
 107               n_nodes -= i;
 108               nodes = check;
 109             }
 110           else if (cmp < 0)
 111             n_nodes = i - 1;
 112           else /* if (cmp == 0) */
 113             {
 114               if (replace)
 115                 {
 116 #if 0
 117                   if (barray->destroy_node)
 118                     barray->destroy_node (check);
 119 #endif
 120                   memcpy (check, key_node, sizeof_node);
 121                 }
 122               return check;
 123             }
 124         }
 125       while (n_nodes);
 126       /* grow */
 127       if (cmp > 0)
 128         check += sizeof_node;
 129       i = (check - ((guint8*) barray->nodes)) / sizeof_node;
 130       n_nodes = barray->n_nodes++;
 131       if (barray->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
 132         {
 133           guint new_size = upper_power2 (barray->n_nodes * sizeof_node);
 134           guint old_size = upper_power2 (n_nodes * sizeof_node);
 135
 136           if (new_size != old_size)
 137             barray->nodes = g_realloc (barray->nodes, new_size);
 138         }
 139       else
 140         barray->nodes = g_realloc (barray->nodes, barray->n_nodes * sizeof_node);
 141       check = ((guint8*) barray->nodes) + i * sizeof_node;
 142       g_memmove (check + sizeof_node, check, (n_nodes - i) * sizeof_node);
 143     }
 144   memcpy (check, key_node, sizeof_node);
 145
 146   return check;
 147 }
 148
 149 gpointer
 150 g_bsearch_array_insert (GBSearchArray *barray,
 151                         gconstpointer  key_node,
 152                         gboolean       replace_existing)
 153 {
 154   g_return_val_if_fail (barray != NULL, NULL);
 155   g_return_val_if_fail (key_node != NULL, NULL);
 156
 157   return bsearch_array_insert (barray, key_node, replace_existing);
 158 }
 159
 160 void
 161 g_bsearch_array_remove_node (GBSearchArray *barray,
 162                              gpointer       _node_in_array)
 163 {
 164   guint8 *nodes, *bound, *node_in_array = _node_in_array;
 165   guint old_size;
 166
 167   g_return_if_fail (barray != NULL);
 168
 169   nodes = barray->nodes;
 170   old_size = barray->sizeof_node;
 171   old_size *= barray->n_nodes;  /* beware of int widths */
 172   bound = nodes + old_size;
 173
 174   g_return_if_fail (node_in_array >= nodes && node_in_array < bound);
 175
 176 #if 0
 177   if (barray->destroy_node)
 178     barray->destroy_node (node_in_array);
 179 #endif
 180   bound -= barray->sizeof_node;
 181   barray->n_nodes -= 1;
 182   g_memmove (node_in_array, node_in_array + barray->sizeof_node, (bound - node_in_array) / barray->sizeof_node);
 183
 184   if ((barray->flags & G_BSEARCH_ARRAY_DEFER_SHRINK) == 0)
 185     {
 186       guint new_size = bound - nodes;   /* old_size - barray->sizeof_node */
 187
 188       if (barray->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
 189         {
 190           new_size = upper_power2 (new_size);
 191           old_size = upper_power2 (old_size);
 192           if (old_size != new_size)
 193             barray->nodes = g_realloc (barray->nodes, new_size);
 194         }
 195       else
 196         barray->nodes = g_realloc (barray->nodes, new_size);
 197     }
 198 }
 199
 200 void
 201 g_bsearch_array_remove (GBSearchArray *barray,
 202                         gconstpointer  key_node)
 203 {
 204   gpointer node_in_array;
 205
 206   g_return_if_fail (barray != NULL);
 207
 208   node_in_array = g_bsearch_array_lookup (barray, key_node);
 209   if (!node_in_array)
 210     g_warning (G_STRLOC ": unable to remove unexistant node");
 211   else
 212     g_bsearch_array_remove_node (barray, node_in_array);
 213 }