glib/gbsearcharray.h

   1 /* GBSearchArray - Binary Searchable Array implementation
   2  * Copyright (C) 2000-2003 Tim Janik
   3  *
   4  * This software is provided "as is"; redistribution and modification
   5  * is permitted, provided that the following disclaimer is retained.
   6  *
   7  * This software is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10  * In no event shall the authors or contributors be liable for any
  11  * direct, indirect, incidental, special, exemplary, or consequential
  12  * damages (including, but not limited to, procurement of substitute
  13  * goods or services; loss of use, data, or profits; or business
  14  * interruption) however caused and on any theory of liability, whether
  15  * in contract, strict liability, or tort (including negligence or
  16  * otherwise) arising in any way out of the use of this software, even
  17  * if advised of the possibility of such damage.
  18  */
  19 #ifndef __G_BSEARCH_ARRAY_H__
  20 #define __G_BSEARCH_ARRAY_H__
  21
  22 #include <glib.h>
  23 #include <string.h>
  24
  25
  26 G_BEGIN_DECLS   /* c++ guards */
  27
  28 /* this implementation is intended to be usable in third-party code
  29  * simply by pasting the contents of this file. as such, the
  30  * implementation needs to be self-contained within this file.
  31  */
  32
  33 /* convenience macro to avoid signed overflow for value comparisons */
  34 #define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) > (v2) ? +1 : (v1) == (v2) ? 0 : -1)
  35
  36
  37 /* --- typedefs --- */
  38 typedef gint  (*GBSearchCompareFunc) (gconstpointer bsearch_node1, /* key */
  39                                       gconstpointer bsearch_node2);
  40 typedef enum
  41 {
  42   G_BSEARCH_ARRAY_ALIGN_POWER2  = 1 << 0, /* align memory to power2 sizes */
  43   G_BSEARCH_ARRAY_AUTO_SHRINK  = 1 << 1   /* shrink array upon removal */
  44 } GBSearchArrayFlags;
  45
  46
  47 /* --- structures --- */
  48 typedef struct
  49 {
  50   guint               sizeof_node;
  51   GBSearchCompareFunc cmp_nodes;
  52   guint               flags;
  53 } GBSearchConfig;
  54 typedef union
  55 {
  56   guint    n_nodes;
  57   /*< private >*/
  58   gpointer alignment_dummy1;
  59   glong    alignment_dummy2;
  60   gdouble  alignment_dummy3;
  61 } GBSearchArray;
  62
  63
  64 /* --- public API --- */
  65 static inline GBSearchArray*    g_bsearch_array_create    (const GBSearchConfig *bconfig);
  66 static inline gpointer          g_bsearch_array_get_nth   (GBSearchArray        *barray,
  67                                                            const GBSearchConfig *bconfig,
  68                                                            guint                 nth);
  69 static inline guint             g_bsearch_array_get_index (GBSearchArray        *barray,
  70                                                            const GBSearchConfig *bconfig,
  71                                                            gconstpointer         node_in_array);
  72 static inline GBSearchArray*    g_bsearch_array_remove    (GBSearchArray        *barray,
  73                                                            const GBSearchConfig *bconfig,
  74                                                            guint                 index_);
  75 /* provide uninitialized space at index for node insertion */
  76 static inline GBSearchArray*    g_bsearch_array_grow      (GBSearchArray        *barray,
  77                                                            const GBSearchConfig *bconfig,
  78                                                            guint                 index);
  79 /* insert key_node into array if it does not exist, otherwise do nothing */
  80 static inline GBSearchArray*    g_bsearch_array_insert    (GBSearchArray        *barray,
  81                                                            const GBSearchConfig *bconfig,
  82                                                            gconstpointer         key_node);
  83 /* insert key_node into array if it does not exist,
  84  * otherwise replace the existing node's contents with key_node
  85  */
  86 static inline GBSearchArray*    g_bsearch_array_replace   (GBSearchArray        *barray,
  87                                                            const GBSearchConfig *bconfig,
  88                                                            gconstpointer         key_node);
  89 static inline void              g_bsearch_array_free      (GBSearchArray        *barray,
  90                                                            const GBSearchConfig *bconfig);
  91 #define g_bsearch_array_get_n_nodes(barray)     (((GBSearchArray*) (barray))->n_nodes)
  92
  93 /* g_bsearch_array_lookup():
  94  * return NULL or exact match node
  95  */
  96 #define g_bsearch_array_lookup(barray, bconfig, key_node)       \
  97     g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 0)
  98
  99 /* g_bsearch_array_lookup_sibling():
 100  * return NULL for barray->n_nodes==0, otherwise return the
 101  * exact match node, or, if there's no such node, return the
 102  * node last visited, which is pretty close to an exact match
 103  * (will be one off into either direction).
 104  */
 105 #define g_bsearch_array_lookup_sibling(barray, bconfig, key_node)       \
 106     g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 1)
 107
 108 /* g_bsearch_array_lookup_insertion():
 109  * return NULL for barray->n_nodes==0 or exact match, otherwise
 110  * return the node where key_node should be inserted (may be one
 111  * after end, i.e. g_bsearch_array_get_index(result) <= barray->n_nodes).
 112  */
 113 #define g_bsearch_array_lookup_insertion(barray, bconfig, key_node)     \
 114     g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 2)
 115
 116
 117 /* --- implementation --- */
 118 /* helper macro to cut down realloc()s */
 119 #ifdef  DISABLE_MEM_POOLS
 120 #define G_BSEARCH_UPPER_POWER2(n)       (n)
 121 #else   /* !DISABLE_MEM_POOLS */
 122 #define G_BSEARCH_UPPER_POWER2(n)       ((n) ? 1 << g_bit_storage ((n) - 1) : 0)
 123 #endif  /* !DISABLE_MEM_POOLS */
 124 #define G_BSEARCH_ARRAY_NODES(barray)    (((guint8*) (barray)) + sizeof (GBSearchArray))
 125 static inline GBSearchArray*
 126 g_bsearch_array_create (const GBSearchConfig *bconfig)
 127 {
 128   GBSearchArray *barray;
 129   guint size;
 130
 131   g_return_val_if_fail (bconfig != NULL, NULL);
 132
 133   size = sizeof (GBSearchArray) + bconfig->sizeof_node;
 134   if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
 135     size = G_BSEARCH_UPPER_POWER2 (size);
 136   barray = (GBSearchArray *) g_malloc (size);
 137   memset (barray, 0, sizeof (GBSearchArray));
 138
 139   return barray;
 140 }
 141 static inline gpointer
 142 g_bsearch_array_lookup_fuzzy (GBSearchArray             *barray,
 143                               const GBSearchConfig      *bconfig,
 144                               gconstpointer              key_node,
 145                               const guint                sibling_or_after);
 146 static inline gpointer
 147 g_bsearch_array_lookup_fuzzy (GBSearchArray        *barray,
 148                               const GBSearchConfig *bconfig,
 149                               gconstpointer         key_node,
 150                               const guint           sibling_or_after)
 151 {
 152   GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
 153   guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray);
 154   guint n_nodes = barray->n_nodes, offs = 0;
 155   guint sizeof_node = bconfig->sizeof_node;
 156   gint cmp = 0;
 157
 158   while (offs < n_nodes)
 159     {
 160       guint i = (offs + n_nodes) >> 1;
 161
 162       check = nodes + i * sizeof_node;
 163       cmp = cmp_nodes (key_node, check);
 164       if (cmp == 0)
 165         return sibling_or_after > 1 ? NULL : check;
 166       else if (cmp < 0)
 167         n_nodes = i;
 168       else /* (cmp > 0) */
 169         offs = i + 1;
 170     }
 171
 172   /* check is last mismatch, cmp > 0 indicates greater key */
 173   return G_LIKELY (!sibling_or_after) ? NULL : (sibling_or_after > 1 && cmp > 0) ? check + sizeof_node : check;
 174 }
 175 static inline gpointer
 176 g_bsearch_array_get_nth (GBSearchArray        *barray,
 177                          const GBSearchConfig *bconfig,
 178                          guint                 nth)
 179 {
 180   return (G_LIKELY (nth < barray->n_nodes) ?
 181           G_BSEARCH_ARRAY_NODES (barray) + nth * bconfig->sizeof_node :
 182           NULL);
 183 }
 184 static inline guint
 185 g_bsearch_array_get_index (GBSearchArray        *barray,
 186                            const GBSearchConfig *bconfig,
 187                            gconstpointer         node_in_array)
 188 {
 189   guint distance = ((guint8*) node_in_array) - G_BSEARCH_ARRAY_NODES (barray);
 190
 191   g_return_val_if_fail (node_in_array != NULL, barray->n_nodes);
 192
 193   distance /= bconfig->sizeof_node;
 194
 195   return MIN (distance, barray->n_nodes + 1); /* may return one after end */
 196 }
 197 static inline GBSearchArray*
 198 g_bsearch_array_grow (GBSearchArray        *barray,
 199                       const GBSearchConfig *bconfig,
 200                       guint                 index_)
 201 {
 202   guint old_size = barray->n_nodes * bconfig->sizeof_node;
 203   guint new_size = old_size + bconfig->sizeof_node;
 204   guint8 *node;
 205
 206   g_return_val_if_fail (index_ <= barray->n_nodes, NULL);
 207
 208   if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
 209     {
 210       new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
 211       old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
 212       if (old_size != new_size)
 213         barray = (GBSearchArray *) g_realloc (barray, new_size);
 214     }
 215   else
 216     barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
 217   node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
 218   g_memmove (node + bconfig->sizeof_node, node, (barray->n_nodes - index_) * bconfig->sizeof_node);
 219   barray->n_nodes += 1;
 220   return barray;
 221 }
 222 static inline GBSearchArray*
 223 g_bsearch_array_insert (GBSearchArray        *barray,
 224                         const GBSearchConfig *bconfig,
 225                         gconstpointer         key_node)
 226 {
 227   guint8 *node;
 228
 229   if (G_UNLIKELY (!barray->n_nodes))
 230     {
 231       barray = g_bsearch_array_grow (barray, bconfig, 0);
 232       node = G_BSEARCH_ARRAY_NODES (barray);
 233     }
 234   else
 235     {
 236       node = (guint8 *) g_bsearch_array_lookup_insertion (barray, bconfig, key_node);
 237       if (G_LIKELY (node))
 238         {
 239           guint index_ = g_bsearch_array_get_index (barray, bconfig, node);
 240
 241           /* grow and insert */
 242           barray = g_bsearch_array_grow (barray, bconfig, index_);
 243           node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
 244         }
 245       else /* no insertion needed, node already there */
 246         return barray;
 247     }
 248   memcpy (node, key_node, bconfig->sizeof_node);
 249   return barray;
 250 }
 251 static inline GBSearchArray*
 252 g_bsearch_array_replace (GBSearchArray        *barray,
 253                          const GBSearchConfig *bconfig,
 254                          gconstpointer         key_node)
 255 {
 256   guint8 *node = (guint8 *) g_bsearch_array_lookup (barray, bconfig, key_node);
 257   if (G_LIKELY (node))  /* expected path */
 258     memcpy (node, key_node, bconfig->sizeof_node);
 259   else                  /* revert to insertion */
 260     barray = g_bsearch_array_insert (barray, bconfig, key_node);
 261   return barray;
 262 }
 263 static inline GBSearchArray*
 264 g_bsearch_array_remove (GBSearchArray        *barray,
 265                         const GBSearchConfig *bconfig,
 266                         guint                 index_)
 267 {
 268   guint8 *node;
 269
 270   g_return_val_if_fail (index_ < barray->n_nodes, NULL);
 271
 272   barray->n_nodes -= 1;
 273   node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
 274   g_memmove (node, node + bconfig->sizeof_node, (barray->n_nodes - index_) * bconfig->sizeof_node);
 275   if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_AUTO_SHRINK))
 276     {
 277       guint new_size = barray->n_nodes * bconfig->sizeof_node;
 278       guint old_size = new_size + bconfig->sizeof_node;
 279
 280       if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
 281         {
 282           new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
 283           old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
 284           if (old_size != new_size)
 285             barray = (GBSearchArray *) g_realloc (barray, new_size);
 286         }
 287       else
 288         barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
 289     }
 290   return barray;
 291 }
 292 static inline void
 293 g_bsearch_array_free (GBSearchArray        *barray,
 294                       const GBSearchConfig *bconfig)
 295 {
 296   g_return_if_fail (barray != NULL);
 297
 298   g_free (barray);
 299 }
 300
 301 G_END_DECLS     /* c++ guards */
 302
 303 #endif  /* !__G_BSEARCH_ARRAY_H__ */