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 comparisons */
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#define G_BSEARCH_UPPER_POWER2(n) ((n) ? 1 << g_bit_storage ((n) - 1) : 0)
120#define G_BSEARCH_ARRAY_NODES(barray) (((guint8*) (barray)) + sizeof (GBSearchArray))
121static inline GBSearchArray*
122g_bsearch_array_create (const GBSearchConfig *bconfig)
123{
124 GBSearchArray *barray;
125 guint size;
126
127 g_return_val_if_fail (bconfig != NULL, NULL);
128
129 size = sizeof (GBSearchArray) + bconfig->sizeof_node;
130 if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
131 size = G_BSEARCH_UPPER_POWER2 (size);
132 barray = (GBSearchArray *) g_malloc (n_bytes: size);
133 memset (s: barray, c: 0, n: sizeof (GBSearchArray));
134
135 return barray;
136}
137static inline gpointer
138g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
139 const GBSearchConfig *bconfig,
140 gconstpointer key_node,
141 const guint sibling_or_after);
142static inline gpointer
143g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
144 const GBSearchConfig *bconfig,
145 gconstpointer key_node,
146 const guint sibling_or_after)
147{
148 GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
149 guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray);
150 guint n_nodes = barray->n_nodes, offs = 0;
151 guint sizeof_node = bconfig->sizeof_node;
152 gint cmp = 0;
153
154 while (offs < n_nodes)
155 {
156 guint i = (offs + n_nodes) >> 1;
157
158 check = nodes + i * sizeof_node;
159 cmp = cmp_nodes (key_node, check);
160 if (cmp == 0)
161 return sibling_or_after > 1 ? NULL : check;
162 else if (cmp < 0)
163 n_nodes = i;
164 else /* (cmp > 0) */
165 offs = i + 1;
166 }
167
168 /* check is last mismatch, cmp > 0 indicates greater key */
169 return G_LIKELY (!sibling_or_after) ? NULL : (sibling_or_after > 1 && cmp > 0) ? check + sizeof_node : check;
170}
171static inline gpointer
172g_bsearch_array_get_nth (GBSearchArray *barray,
173 const GBSearchConfig *bconfig,
174 guint nth)
175{
176 return (G_LIKELY (nth < barray->n_nodes) ?
177 G_BSEARCH_ARRAY_NODES (barray) + nth * bconfig->sizeof_node :
178 NULL);
179}
180static inline guint
181g_bsearch_array_get_index (GBSearchArray *barray,
182 const GBSearchConfig *bconfig,
183 gconstpointer node_in_array)
184{
185 guint distance = ((guint8*) node_in_array) - G_BSEARCH_ARRAY_NODES (barray);
186
187 g_return_val_if_fail (node_in_array != NULL, barray->n_nodes);
188
189 distance /= bconfig->sizeof_node;
190
191 return MIN (distance, barray->n_nodes + 1); /* may return one after end */
192}
193static inline GBSearchArray*
194g_bsearch_array_grow (GBSearchArray *barray,
195 const GBSearchConfig *bconfig,
196 guint index_)
197{
198 guint old_size = barray->n_nodes * bconfig->sizeof_node;
199 guint new_size = old_size + bconfig->sizeof_node;
200 guint8 *node;
201
202 g_return_val_if_fail (index_ <= barray->n_nodes, NULL);
203
204 if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
205 {
206 new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
207 old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
208 if (old_size != new_size)
209 barray = (GBSearchArray *) g_realloc (mem: barray, n_bytes: new_size);
210 }
211 else
212 barray = (GBSearchArray *) g_realloc (mem: barray, n_bytes: sizeof (GBSearchArray) + new_size);
213 node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
214 memmove (dest: node + bconfig->sizeof_node, src: node, n: (barray->n_nodes - index_) * bconfig->sizeof_node);
215 barray->n_nodes += 1;
216 return barray;
217}
218static inline GBSearchArray*
219g_bsearch_array_insert (GBSearchArray *barray,
220 const GBSearchConfig *bconfig,
221 gconstpointer key_node)
222{
223 guint8 *node;
224
225 if (G_UNLIKELY (!barray->n_nodes))
226 {
227 barray = g_bsearch_array_grow (barray, bconfig, index_: 0);
228 node = G_BSEARCH_ARRAY_NODES (barray);
229 }
230 else
231 {
232 node = (guint8 *) g_bsearch_array_lookup_insertion (barray, bconfig, key_node);
233 if (G_LIKELY (node))
234 {
235 guint index_ = g_bsearch_array_get_index (barray, bconfig, node_in_array: node);
236
237 /* grow and insert */
238 barray = g_bsearch_array_grow (barray, bconfig, index_);
239 node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
240 }
241 else /* no insertion needed, node already there */
242 return barray;
243 }
244 memcpy (dest: node, src: key_node, n: bconfig->sizeof_node);
245 return barray;
246}
247static inline GBSearchArray*
248g_bsearch_array_replace (GBSearchArray *barray,
249 const GBSearchConfig *bconfig,
250 gconstpointer key_node)
251{
252 guint8 *node = (guint8 *) g_bsearch_array_lookup (barray, bconfig, key_node);
253 if (G_LIKELY (node)) /* expected path */
254 memcpy (dest: node, src: key_node, n: bconfig->sizeof_node);
255 else /* revert to insertion */
256 barray = g_bsearch_array_insert (barray, bconfig, key_node);
257 return barray;
258}
259static inline GBSearchArray*
260g_bsearch_array_remove (GBSearchArray *barray,
261 const GBSearchConfig *bconfig,
262 guint index_)
263{
264 guint8 *node;
265
266 g_return_val_if_fail (index_ < barray->n_nodes, NULL);
267
268 barray->n_nodes -= 1;
269 node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
270 memmove (dest: node, src: node + bconfig->sizeof_node, n: (barray->n_nodes - index_) * bconfig->sizeof_node);
271 if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_AUTO_SHRINK))
272 {
273 guint new_size = barray->n_nodes * bconfig->sizeof_node;
274 guint old_size = new_size + bconfig->sizeof_node;
275
276 if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
277 {
278 new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
279 old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
280 if (old_size != new_size)
281 barray = (GBSearchArray *) g_realloc (mem: barray, n_bytes: new_size);
282 }
283 else
284 barray = (GBSearchArray *) g_realloc (mem: barray, n_bytes: sizeof (GBSearchArray) + new_size);
285 }
286 return barray;
287}
288static inline void
289g_bsearch_array_free (GBSearchArray *barray,
290 const GBSearchConfig *bconfig)
291{
292 g_return_if_fail (barray != NULL);
293
294 g_free (mem: barray);
295}
296
297G_END_DECLS /* c++ guards */
298
299#endif /* !__G_BSEARCH_ARRAY_H__ */
300

source code of gtk/subprojects/glib/glib/gbsearcharray.h