glib/gbsearcharray.c

   1 /* GObject - GLib Type, Object, Parameter and Signal Library
   2  * Copyright (C) 2000 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   return number ? 1 << g_bit_storage (number - 1) : 0;
  31 }
  32
  33 static inline gpointer
  34 bsearch_array_insert (GBSearchArray *barray,
  35                       gconstpointer  key_node,
  36                       gboolean       replace)
  37 {
  38   gint sizeof_node;
  39   guint8 *check;
  40
  41   sizeof_node = barray->sizeof_node;
  42   if (barray->n_nodes == 0)
  43     {
  44       guint new_size = barray->sizeof_node;
  45
  46       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
  47         new_size = upper_power2 (new_size);
  48       barray->nodes = g_realloc (barray->nodes, new_size);
  49       barray->n_nodes = 1;
  50       check = barray->nodes;
  51       replace = TRUE;
  52     }
  53   else
  54     {
  55       GBSearchCompareFunc cmp_func = barray->cmp_func;
  56       guint n_nodes = barray->n_nodes;
  57       guint8 *nodes = barray->nodes;
  58       gint cmp;
  59       guint i;
  60
  61       nodes -= sizeof_node;
  62       do
  63         {
  64           i = (n_nodes + 1) >> 1;
  65           check = nodes + i * sizeof_node;
  66           cmp = cmp_func (key_node, check);
  67           if (cmp > 0)
  68             {
  69               n_nodes -= i;
  70               nodes = check;
  71             }
  72           else if (cmp < 0)
  73             n_nodes = i - 1;
  74           else /* if (cmp == 0) */
  75             goto SKIP_GROW;
  76         }
  77       while (n_nodes);
  78       /* grow */
  79       if (cmp > 0)
  80         check += sizeof_node;
  81       i = (check - ((guint8*) barray->nodes)) / sizeof_node;
  82       n_nodes = barray->n_nodes++;
  83       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
  84         {
  85           guint new_size = upper_power2 (barray->n_nodes * sizeof_node);
  86           guint old_size = upper_power2 (n_nodes * sizeof_node);
  87
  88           if (new_size != old_size)
  89             barray->nodes = g_realloc (barray->nodes, new_size);
  90         }
  91       else
  92         barray->nodes = g_realloc (barray->nodes, barray->n_nodes * sizeof_node);
  93       check = barray->nodes + i * sizeof_node;
  94       g_memmove (check + sizeof_node, check, (n_nodes - i) * sizeof_node);
  95       replace = TRUE;
  96     SKIP_GROW:
  97     }
  98   if (replace)
  99     memcpy (check, key_node, sizeof_node);
 100
 101   return check;
 102 }
 103
 104 gpointer
 105 g_bsearch_array_insert (GBSearchArray *barray,
 106                         gconstpointer  key_node,
 107                         gboolean       replace_existing)
 108 {
 109   g_return_val_if_fail (barray != NULL, NULL);
 110   g_return_val_if_fail (key_node != NULL, NULL);
 111
 112   return bsearch_array_insert (barray, key_node, replace_existing);
 113 }
 114
 115 void
 116 g_bsearch_array_remove_node (GBSearchArray *barray,
 117                              gpointer       _node_in_array)
 118 {
 119   guint8 *nodes, *bound, *node_in_array = _node_in_array;
 120   guint old_size;
 121
 122   g_return_if_fail (barray != NULL);
 123
 124   nodes = barray->nodes;
 125   old_size = barray->sizeof_node;
 126   old_size *= barray->n_nodes;  /* beware of int widths */
 127   bound = nodes + old_size;
 128
 129   g_return_if_fail (node_in_array >= nodes && node_in_array < bound);
 130
 131   bound -= barray->sizeof_node;
 132   barray->n_nodes -= 1;
 133   g_memmove (node_in_array, node_in_array + barray->sizeof_node, (bound - node_in_array) / barray->sizeof_node);
 134
 135   if ((barray->flags & G_BSEARCH_DEFER_SHRINK) == 0)
 136     {
 137       guint new_size = bound - nodes;   /* old_size - barray->sizeof_node */
 138
 139       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
 140         {
 141           new_size = upper_power2 (new_size);
 142           old_size = upper_power2 (old_size);
 143           if (old_size != new_size)
 144             barray->nodes = g_realloc (barray->nodes, new_size);
 145         }
 146       else
 147         barray->nodes = g_realloc (barray->nodes, new_size);
 148     }
 149 }
 150
 151 void
 152 g_bsearch_array_remove (GBSearchArray *barray,
 153                         gconstpointer  key_node)
 154 {
 155   gpointer node_in_array;
 156
 157   g_return_if_fail (barray != NULL);
 158
 159   node_in_array = g_bsearch_array_lookup (barray, key_node);
 160   if (!node_in_array)
 161     g_warning (G_STRLOC ": unable to remove unexistant node");
 162   else
 163     g_bsearch_array_remove_node (barray, node_in_array);
 164 }