gobject/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 = (char *) 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     }
  99   if (replace)
 100     memcpy (check, key_node, sizeof_node);
 101
 102   return check;
 103 }
 104
 105 gpointer
 106 g_bsearch_array_insert (GBSearchArray *barray,
 107                         gconstpointer  key_node,
 108                         gboolean       replace_existing)
 109 {
 110   g_return_val_if_fail (barray != NULL, NULL);
 111   g_return_val_if_fail (key_node != NULL, NULL);
 112
 113   return bsearch_array_insert (barray, key_node, replace_existing);
 114 }
 115
 116 void
 117 g_bsearch_array_remove_node (GBSearchArray *barray,
 118                              gpointer       _node_in_array)
 119 {
 120   guint8 *nodes, *bound, *node_in_array = _node_in_array;
 121   guint old_size;
 122
 123   g_return_if_fail (barray != NULL);
 124
 125   nodes = barray->nodes;
 126   old_size = barray->sizeof_node;
 127   old_size *= barray->n_nodes;  /* beware of int widths */
 128   bound = nodes + old_size;
 129
 130   g_return_if_fail (node_in_array >= nodes && node_in_array < bound);
 131
 132   bound -= barray->sizeof_node;
 133   barray->n_nodes -= 1;
 134   g_memmove (node_in_array, node_in_array + barray->sizeof_node, (bound - node_in_array) / barray->sizeof_node);
 135
 136   if ((barray->flags & G_BSEARCH_DEFER_SHRINK) == 0)
 137     {
 138       guint new_size = bound - nodes;   /* old_size - barray->sizeof_node */
 139
 140       if (barray->flags & G_BSEARCH_ALIGN_POWER2)
 141         {
 142           new_size = upper_power2 (new_size);
 143           old_size = upper_power2 (old_size);
 144           if (old_size != new_size)
 145             barray->nodes = g_realloc (barray->nodes, new_size);
 146         }
 147       else
 148         barray->nodes = g_realloc (barray->nodes, new_size);
 149     }
 150 }
 151
 152 void
 153 g_bsearch_array_remove (GBSearchArray *barray,
 154                         gconstpointer  key_node)
 155 {
 156   gpointer node_in_array;
 157
 158   g_return_if_fail (barray != NULL);
 159
 160   node_in_array = g_bsearch_array_lookup (barray, key_node);
 161   if (!node_in_array)
 162     g_warning (G_STRLOC ": unable to remove unexistant node");
 163   else
 164     g_bsearch_array_remove_node (barray, node_in_array);
 165 }