|
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 comparisions */ |
|
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_realloc (NULL, 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__ */ |