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 | #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)) |
121 | static inline GBSearchArray* |
122 | g_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 | } |
137 | static inline gpointer |
138 | g_bsearch_array_lookup_fuzzy (GBSearchArray *barray, |
139 | const GBSearchConfig *bconfig, |
140 | gconstpointer key_node, |
141 | const guint sibling_or_after); |
142 | static inline gpointer |
143 | g_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 | } |
171 | static inline gpointer |
172 | g_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 | } |
180 | static inline guint |
181 | g_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 | } |
193 | static inline GBSearchArray* |
194 | g_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 | } |
218 | static inline GBSearchArray* |
219 | g_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 | } |
247 | static inline GBSearchArray* |
248 | g_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 | } |
259 | static inline GBSearchArray* |
260 | g_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 | } |
288 | static inline void |
289 | g_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 | |
297 | G_END_DECLS /* c++ guards */ |
298 | |
299 | #endif /* !__G_BSEARCH_ARRAY_H__ */ |
300 | |