Beast - Music Synthesizer and Composer  0.11.1+10.g2da35
gbsearcharray.hh
Go to the documentation of this file.
1  // CC0 Public Domain: http://creativecommons.org/publicdomain/zero/1.0/
2 #ifndef __G_BSEARCH_ARRAY_H__
3 #define __G_BSEARCH_ARRAY_H__
4 
5 #include <sfi/glib-extra.hh>
6 #include <string.h>
7 
8 
9 G_BEGIN_DECLS /* c++ guards */
10 
11 /* this implementation is intended to be usable in third-party code
12  * simply by pasting the contents of this file. as such, the
13  * implementation needs to be self-contained within this file.
14  */
15 
16 /* convenience macro to avoid signed overflow for value comparisions */
17 #define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) > (v2) ? +1 : (v1) == (v2) ? 0 : -1)
18 
19 
20 /* --- typedefs --- */
21 typedef gint (*GBSearchCompareFunc) (gconstpointer bsearch_node1, /* key */
22  gconstpointer bsearch_node2);
23 typedef enum
24 {
25  G_BSEARCH_ARRAY_ALIGN_POWER2 = 1 << 0, /* align memory to power2 sizes */
26  G_BSEARCH_ARRAY_AUTO_SHRINK = 1 << 1 /* shrink array upon removal */
27 } GBSearchArrayFlags;
28 
29 
30 /* --- structures --- */
31 typedef struct
32 {
33  guint sizeof_node;
34  GBSearchCompareFunc cmp_nodes;
35  guint flags;
37 typedef union
38 {
39  guint n_nodes;
40  /*< private >*/
41  gpointer alignment_dummy1;
42  glong alignment_dummy2;
43  gdouble alignment_dummy3;
45 
46 
47 /* --- public API --- */
48 static inline GBSearchArray* g_bsearch_array_create (const GBSearchConfig *bconfig);
49 static inline gpointer g_bsearch_array_get_nth (GBSearchArray *barray,
50  const GBSearchConfig *bconfig,
51  guint nth);
52 static inline guint g_bsearch_array_get_index (GBSearchArray *barray,
53  const GBSearchConfig *bconfig,
54  gconstpointer node_in_array);
55 static inline GBSearchArray* g_bsearch_array_remove (GBSearchArray *barray,
56  const GBSearchConfig *bconfig,
57  guint index);
58 static inline GBSearchArray* g_bsearch_array_remove_node (GBSearchArray *barray,
59  const GBSearchConfig *bconfig,
60  gconstpointer node_in_array);
61 /* provide uninitialized space at index for node insertion */
62 static inline GBSearchArray* g_bsearch_array_grow (GBSearchArray *barray,
63  const GBSearchConfig *bconfig,
64  guint index);
65 /* insert key_node into array if it does not exist, otherwise do nothing */
66 static inline GBSearchArray* g_bsearch_array_insert (GBSearchArray *barray,
67  const GBSearchConfig *bconfig,
68  gconstpointer key_node);
69 /* insert key_node into array if it does not exist,
70  * otherwise replace the existing node's contents with key_node
71  */
72 static inline GBSearchArray* g_bsearch_array_replace (GBSearchArray *barray,
73  const GBSearchConfig *bconfig,
74  gconstpointer key_node);
75 static inline void g_bsearch_array_free (GBSearchArray *barray,
76  const GBSearchConfig *bconfig);
77 #define g_bsearch_array_get_n_nodes(barray) (((GBSearchArray*) (barray))->n_nodes)
78 
79 /* g_bsearch_array_lookup():
80  * return NULL or exact match node
81  */
82 #define g_bsearch_array_lookup(barray, bconfig, key_node) \
83  g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 0)
84 
85 /* g_bsearch_array_lookup_sibling():
86  * return NULL for barray->n_nodes==0, otherwise return the
87  * exact match node, or, if there's no such node, return the
88  * node last visited, which is pretty close to an exact match
89  * (will be one off into either direction).
90  */
91 #define g_bsearch_array_lookup_sibling(barray, bconfig, key_node) \
92  g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 1)
93 
94 /* g_bsearch_array_lookup_insertion():
95  * return NULL for barray->n_nodes==0 or exact match, otherwise
96  * return the node where key_node should be inserted (may be one
97  * after end, i.e. g_bsearch_array_get_index(result) <= barray->n_nodes).
98  */
99 #define g_bsearch_array_lookup_insertion(barray, bconfig, key_node) \
100  g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 2)
101 
102 
103 /* --- implementation --- */
104 /* helper macro to cut down realloc()s */
105 #ifdef DISABLE_MEM_POOLS
106 #define G_BSEARCH_UPPER_POWER2(n) (n)
107 #else /* !DISABLE_MEM_POOLS */
108 #define G_BSEARCH_UPPER_POWER2(n) ((n) ? 1 << g_bit_storage ((n) - 1) : 0)
109 #endif /* !DISABLE_MEM_POOLS */
110 #define G_BSEARCH_ARRAY_NODES(barray) (((guint8*) (barray)) + sizeof (GBSearchArray))
111 static inline GBSearchArray*
112 g_bsearch_array_create (const GBSearchConfig *bconfig)
113 {
114  GBSearchArray *barray;
115  guint size;
116 
117  RAPICORN_ASSERT_RETURN (bconfig != NULL, NULL);
118 
119  size = sizeof (GBSearchArray) + bconfig->sizeof_node;
120  if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
121  size = G_BSEARCH_UPPER_POWER2 (size);
122  barray = (GBSearchArray *) g_realloc (NULL, size);
123  memset (barray, 0, sizeof (GBSearchArray));
124 
125  return barray;
126 }
127 static inline gpointer
128 g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
129  const GBSearchConfig *bconfig,
130  gconstpointer key_node,
131  const guint sibling_or_after);
132 static inline gpointer
133 g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
134  const GBSearchConfig *bconfig,
135  gconstpointer key_node,
136  const guint sibling_or_after)
137 {
138  GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
139  guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray);
140  guint n_nodes = barray->n_nodes, offs = 0;
141  guint sizeof_node = bconfig->sizeof_node;
142  gint cmp = 0;
143 
144  while (offs < n_nodes)
145  {
146  guint i = (offs + n_nodes) >> 1;
147 
148  check = nodes + i * sizeof_node;
149  cmp = cmp_nodes (key_node, check);
150  if (cmp == 0)
151  return sibling_or_after > 1 ? NULL : check;
152  else if (cmp < 0)
153  n_nodes = i;
154  else /* (cmp > 0) */
155  offs = i + 1;
156  }
157 
158  /* check is last mismatch, cmp > 0 indicates greater key */
159  return G_LIKELY (!sibling_or_after) ? NULL : (sibling_or_after > 1 && cmp > 0) ? check + sizeof_node : check;
160 }
161 static inline gpointer
162 g_bsearch_array_get_nth (GBSearchArray *barray, const GBSearchConfig *bconfig, guint nth)
163 {
164  return (G_LIKELY (nth < barray->n_nodes) ?
165  G_BSEARCH_ARRAY_NODES (barray) + nth * bconfig->sizeof_node :
166  NULL);
167 }
168 static inline guint
169 g_bsearch_array_get_index (GBSearchArray *barray,
170  const GBSearchConfig *bconfig,
171  gconstpointer node_in_array)
172 {
173  guint distance = ((guint8*) node_in_array) - G_BSEARCH_ARRAY_NODES (barray);
174 
175  RAPICORN_ASSERT_RETURN (node_in_array != NULL, barray->n_nodes);
176 
177  distance /= bconfig->sizeof_node;
178 
179  return MIN (distance, barray->n_nodes + 1); /* may return one after end */
180 }
181 static inline GBSearchArray*
182 g_bsearch_array_grow (GBSearchArray *barray,
183  const GBSearchConfig *bconfig,
184  guint index)
185 {
186  guint old_size = barray->n_nodes * bconfig->sizeof_node;
187  guint new_size = old_size + bconfig->sizeof_node;
188  guint8 *node;
189 
190  RAPICORN_ASSERT_RETURN (index <= barray->n_nodes, NULL);
191 
192  if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
193  {
194  new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
195  old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
196  if (old_size != new_size)
197  barray = (GBSearchArray *) g_realloc (barray, new_size);
198  }
199  else
200  barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
201  node = G_BSEARCH_ARRAY_NODES (barray) + index * bconfig->sizeof_node;
202  memmove (node + bconfig->sizeof_node, node, (barray->n_nodes - index) * bconfig->sizeof_node);
203  barray->n_nodes += 1;
204  return barray;
205 }
206 static inline GBSearchArray*
207 g_bsearch_array_insert (GBSearchArray *barray,
208  const GBSearchConfig *bconfig,
209  gconstpointer key_node)
210 {
211  guint8 *node;
212 
213  if (G_UNLIKELY (!barray->n_nodes))
214  {
215  barray = g_bsearch_array_grow (barray, bconfig, 0);
216  node = G_BSEARCH_ARRAY_NODES (barray);
217  }
218  else
219  {
220  node = (guint8 *) g_bsearch_array_lookup_insertion (barray, bconfig, key_node);
221  if (G_LIKELY (node))
222  {
223  guint index = g_bsearch_array_get_index (barray, bconfig, node);
224 
225  /* grow and insert */
226  barray = g_bsearch_array_grow (barray, bconfig, index);
227  node = G_BSEARCH_ARRAY_NODES (barray) + index * bconfig->sizeof_node;
228  }
229  else /* no insertion needed, node already there */
230  return barray;
231  }
232  memcpy (node, key_node, bconfig->sizeof_node);
233  return barray;
234 }
235 static inline GBSearchArray*
236 g_bsearch_array_replace (GBSearchArray *barray,
237  const GBSearchConfig *bconfig,
238  gconstpointer key_node)
239 {
240  guint8 *node = (guint8 *) g_bsearch_array_lookup (barray, bconfig, key_node);
241  if (G_LIKELY (node)) /* expected path */
242  memcpy (node, key_node, bconfig->sizeof_node);
243  else /* revert to insertion */
244  barray = g_bsearch_array_insert (barray, bconfig, key_node);
245  return barray;
246 }
247 static inline GBSearchArray*
248 g_bsearch_array_remove (GBSearchArray *barray,
249  const GBSearchConfig *bconfig,
250  guint index)
251 {
252  guint8 *node;
253 
254  RAPICORN_ASSERT_RETURN (index < barray->n_nodes, NULL);
255 
256  barray->n_nodes -= 1;
257  node = G_BSEARCH_ARRAY_NODES (barray) + index * bconfig->sizeof_node;
258  memmove (node, node + bconfig->sizeof_node, (barray->n_nodes - index) * bconfig->sizeof_node);
259  if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_AUTO_SHRINK))
260  {
261  guint new_size = barray->n_nodes * bconfig->sizeof_node;
262  guint old_size = new_size + bconfig->sizeof_node;
263 
264  if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
265  {
266  new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
267  old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
268  if (old_size != new_size)
269  barray = (GBSearchArray *) g_realloc (barray, new_size);
270  }
271  else
272  barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
273  }
274  return barray;
275 }
276 static inline GBSearchArray*
277 g_bsearch_array_remove_node (GBSearchArray *barray,
278  const GBSearchConfig *bconfig,
279  gconstpointer node_in_array)
280 {
281  return g_bsearch_array_remove (barray, bconfig, g_bsearch_array_get_index (barray, bconfig, node_in_array));
282 }
283 static inline void
284 g_bsearch_array_free (GBSearchArray *barray,
285  const GBSearchConfig *bconfig)
286 {
287  RAPICORN_ASSERT_RETURN (barray != NULL);
288 
289  g_free (barray);
290 }
291 
292 G_END_DECLS /* c++ guards */
293 
294 #endif /* !__G_BSEARCH_ARRAY_H__ */
bool check(const String &file, const String &mode)
memset
Definition: gbsearcharray.hh:31
Definition: gbsearcharray.hh:37
memcpy
#define RAPICORN_ASSERT_RETURN(cond,...)
memmove