• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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*
g_bsearch_array_create(const GBSearchConfig * bconfig)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
g_bsearch_array_lookup_fuzzy(GBSearchArray * barray,const GBSearchConfig * bconfig,gconstpointer key_node,const guint sibling_or_after)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
g_bsearch_array_get_nth(GBSearchArray * barray,const GBSearchConfig * bconfig,guint nth)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
g_bsearch_array_get_index(GBSearchArray * barray,const GBSearchConfig * bconfig,gconstpointer node_in_array)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*
g_bsearch_array_grow(GBSearchArray * barray,const GBSearchConfig * bconfig,guint index_)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*
g_bsearch_array_insert(GBSearchArray * barray,const GBSearchConfig * bconfig,gconstpointer key_node)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*
g_bsearch_array_replace(GBSearchArray * barray,const GBSearchConfig * bconfig,gconstpointer key_node)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*
g_bsearch_array_remove(GBSearchArray * barray,const GBSearchConfig * bconfig,guint index_)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
g_bsearch_array_free(GBSearchArray * barray,const GBSearchConfig * bconfig)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__ */
304