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 : : } 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 : 109809 : g_bsearch_array_create (const GBSearchConfig *bconfig)
123 : : {
124 : : GBSearchArray *barray;
125 : : guint size;
126 : :
127 : 109809 : g_return_val_if_fail (bconfig != NULL, NULL);
128 : :
129 : 109809 : size = sizeof (GBSearchArray) + bconfig->sizeof_node;
130 [ + + ]: 109809 : if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
131 [ + - ]: 1054 : size = G_BSEARCH_UPPER_POWER2 (size);
132 : 109809 : barray = (GBSearchArray *) g_malloc (size);
133 : 109809 : memset (barray, 0, sizeof (GBSearchArray));
134 : :
135 : 109809 : 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 : 27581221 : g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
144 : : const GBSearchConfig *bconfig,
145 : : gconstpointer key_node,
146 : : const guint sibling_or_after)
147 : : {
148 : 27581221 : GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
149 : 27581221 : guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray);
150 : 27581221 : guint n_nodes = barray->n_nodes, offs = 0;
151 : 27581221 : guint sizeof_node = bconfig->sizeof_node;
152 : 27581221 : gint cmp = 0;
153 : :
154 [ + + ]: 51789977 : while (offs < n_nodes)
155 : : {
156 : 47080207 : guint i = (offs + n_nodes) >> 1;
157 : :
158 : 47080207 : check = nodes + i * sizeof_node;
159 : 47080207 : cmp = cmp_nodes (key_node, check);
160 [ + + ]: 47080207 : if (cmp == 0)
161 [ + + ]: 22871451 : return sibling_or_after > 1 ? NULL : check;
162 [ + + ]: 24208756 : else if (cmp < 0)
163 : 11122396 : n_nodes = i;
164 : : else /* (cmp > 0) */
165 : 13086360 : offs = i + 1;
166 : : }
167 : :
168 : : /* check is last mismatch, cmp > 0 indicates greater key */
169 [ + + + - : 4709770 : return G_LIKELY (!sibling_or_after) ? NULL : (sibling_or_after > 1 && cmp > 0) ? check + sizeof_node : check;
+ + ]
170 : : }
171 : : static inline gpointer
172 : 18498470 : g_bsearch_array_get_nth (GBSearchArray *barray,
173 : : const GBSearchConfig *bconfig,
174 : : guint nth)
175 : : {
176 : 18498470 : return (G_LIKELY (nth < barray->n_nodes) ?
177 [ + - ]: 18498470 : G_BSEARCH_ARRAY_NODES (barray) + nth * bconfig->sizeof_node :
178 : : NULL);
179 : : }
180 : : static inline guint
181 : 90967 : g_bsearch_array_get_index (GBSearchArray *barray,
182 : : const GBSearchConfig *bconfig,
183 : : gconstpointer node_in_array)
184 : : {
185 : 90967 : guint distance = ((guint8*) node_in_array) - G_BSEARCH_ARRAY_NODES (barray);
186 : :
187 : 90967 : g_return_val_if_fail (node_in_array != NULL, barray->n_nodes);
188 : :
189 : 90967 : distance /= bconfig->sizeof_node;
190 : :
191 : 90967 : return MIN (distance, barray->n_nodes + 1); /* may return one after end */
192 : : }
193 : : static inline GBSearchArray*
194 : 200568 : g_bsearch_array_grow (GBSearchArray *barray,
195 : : const GBSearchConfig *bconfig,
196 : : guint index_)
197 : : {
198 : 200568 : guint old_size = barray->n_nodes * bconfig->sizeof_node;
199 : 200568 : guint new_size = old_size + bconfig->sizeof_node;
200 : : guint8 *node;
201 : :
202 : 200568 : g_return_val_if_fail (index_ <= barray->n_nodes, NULL);
203 : :
204 [ + + ]: 200568 : if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
205 : : {
206 : 91376 : new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
207 : 91376 : old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
208 [ + + ]: 91376 : if (old_size != new_size)
209 : 5053 : barray = (GBSearchArray *) g_realloc (barray, new_size);
210 : : }
211 : : else
212 : 109192 : barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
213 : 200568 : node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
214 : 200568 : memmove (node + bconfig->sizeof_node, node, (barray->n_nodes - index_) * bconfig->sizeof_node);
215 : 200568 : barray->n_nodes += 1;
216 : 200568 : return barray;
217 : : }
218 : : static inline GBSearchArray*
219 : 632868 : g_bsearch_array_insert (GBSearchArray *barray,
220 : : const GBSearchConfig *bconfig,
221 : : gconstpointer key_node)
222 : : {
223 : : guint8 *node;
224 : :
225 [ + + ]: 632868 : if (G_UNLIKELY (!barray->n_nodes))
226 : : {
227 : 109601 : barray = g_bsearch_array_grow (barray, bconfig, 0);
228 : 109601 : node = G_BSEARCH_ARRAY_NODES (barray);
229 : : }
230 : : else
231 : : {
232 : 523267 : node = (guint8 *) g_bsearch_array_lookup_insertion (barray, bconfig, key_node);
233 [ + + ]: 523267 : if (G_LIKELY (node))
234 : : {
235 : 90967 : guint index_ = g_bsearch_array_get_index (barray, bconfig, node);
236 : :
237 : : /* grow and insert */
238 : 90967 : barray = g_bsearch_array_grow (barray, bconfig, index_);
239 : 90967 : node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
240 : : }
241 : : else /* no insertion needed, node already there */
242 : 432300 : return barray;
243 : : }
244 : 200568 : memcpy (node, key_node, bconfig->sizeof_node);
245 : 200568 : return barray;
246 : : }
247 : : static inline GBSearchArray*
248 : 89590 : g_bsearch_array_replace (GBSearchArray *barray,
249 : : const GBSearchConfig *bconfig,
250 : : gconstpointer key_node)
251 : : {
252 : 89590 : guint8 *node = (guint8 *) g_bsearch_array_lookup (barray, bconfig, key_node);
253 [ - + ]: 89590 : if (G_LIKELY (node)) /* expected path */
254 : 0 : memcpy (node, key_node, bconfig->sizeof_node);
255 : : else /* revert to insertion */
256 : 89590 : barray = g_bsearch_array_insert (barray, bconfig, key_node);
257 : 89590 : 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 (node, node + bconfig->sizeof_node, (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 (barray, new_size);
282 : : }
283 : : else
284 : : barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
285 : : }
286 : : return barray;
287 : : }
288 : : static inline void
289 : 106491 : g_bsearch_array_free (GBSearchArray *barray,
290 : : const GBSearchConfig *bconfig)
291 : : {
292 : 106491 : g_return_if_fail (barray != NULL);
293 : :
294 : 106491 : g_free (barray);
295 : : }
296 : :
297 : : G_END_DECLS /* c++ guards */
298 : :
299 : : #endif /* !__G_BSEARCH_ARRAY_H__ */
|
