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
26G_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 comparisions */
34#define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) > (v2) ? +1 : (v1) == (v2) ? 0 : -1)
35
36
37/* --- typedefs --- */
38typedef gint  (*GBSearchCompareFunc) (gconstpointer bsearch_node1, /* key */
39                                      gconstpointer bsearch_node2);
40typedef 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 --- */
48typedef struct
49{
50  guint               sizeof_node;
51  GBSearchCompareFunc cmp_nodes;
52  guint               flags;
53} GBSearchConfig;
54typedef 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 --- */
65static inline GBSearchArray*    g_bsearch_array_create    (const GBSearchConfig *bconfig);
66static inline gpointer          g_bsearch_array_get_nth   (GBSearchArray        *barray,
67                                                           const GBSearchConfig *bconfig,
68                                                           guint                 nth);
69static inline guint             g_bsearch_array_get_index (GBSearchArray        *barray,
70                                                           const GBSearchConfig *bconfig,
71                                                           gconstpointer         node_in_array);
72static inline GBSearchArray*    g_bsearch_array_remove    (GBSearchArray        *barray,
73                                                           const GBSearchConfig *bconfig,
74                                                           guint                 index_);
75/* provide uninitialized space at index for node insertion */
76static 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 */
80static 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 */
86static inline GBSearchArray*    g_bsearch_array_replace   (GBSearchArray        *barray,
87                                                           const GBSearchConfig *bconfig,
88                                                           gconstpointer         key_node);
89static 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))
125static inline GBSearchArray*
126g_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_realloc (NULL, size);
137  memset (barray, 0, sizeof (GBSearchArray));
138
139  return barray;
140}
141static inline gpointer
142g_bsearch_array_lookup_fuzzy (GBSearchArray             *barray,
143                              const GBSearchConfig      *bconfig,
144                              gconstpointer              key_node,
145                              const guint                sibling_or_after);
146static inline gpointer
147g_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}
175static inline gpointer
176g_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}
184static inline guint
185g_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}
197static inline GBSearchArray*
198g_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}
222static inline GBSearchArray*
223g_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}
251static inline GBSearchArray*
252g_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}
263static inline GBSearchArray*
264g_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}
292static inline void
293g_bsearch_array_free (GBSearchArray        *barray,
294                      const GBSearchConfig *bconfig)
295{
296  g_return_if_fail (barray != NULL);
297
298  g_free (barray);
299}
300
301G_END_DECLS     /* c++ guards */
302
303#endif  /* !__G_BSEARCH_ARRAY_H__ */
304