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