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