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