source: trunk/third/glib2/glib/gbsearcharray.h @ 20721

Revision 20721, 11.8 KB checked in by ghudson, 20 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r20720, which included commits to RCS files with non-trunk default branches.
Line 
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
26G_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 --- */
38typedef gint  (*GBSearchCompareFunc) (gconstpointer bsearch_node1, /* key */
39                                      gconstpointer bsearch_node2);
40typedef 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 --- */
48typedef struct
49{
50  guint               sizeof_node;
51  GBSearchCompareFunc cmp_nodes;
52  guint               flags;
53} GBSearchConfig;
54typedef 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 --- */
65static inline GBSearchArray*    g_bsearch_array_create    (const GBSearchConfig *bconfig);
66static inline gpointer          g_bsearch_array_get_nth   (GBSearchArray        *barray,
67                                                           const GBSearchConfig *bconfig,
68                                                           guint                 nth);
69static inline guint             g_bsearch_array_get_index (GBSearchArray        *barray,
70                                                           const GBSearchConfig *bconfig,
71                                                           gconstpointer         node_in_array);
72static inline GBSearchArray*    g_bsearch_array_remove    (GBSearchArray        *barray,
73                                                           const GBSearchConfig *bconfig,
74                                                           guint                 index);
75/* provide uninitialized space at index for node insertion */
76static 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 */
80static 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 */
86static inline GBSearchArray*    g_bsearch_array_replace   (GBSearchArray        *barray,
87                                                           const GBSearchConfig *bconfig,
88                                                           gconstpointer         key_node);
89static 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))
125static inline GBSearchArray*
126g_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}
141static inline gpointer
142g_bsearch_array_lookup_fuzzy (GBSearchArray             *barray,
143                              const GBSearchConfig      *bconfig,
144                              gconstpointer              key_node,
145                              const guint                sibling_or_after);
146static inline gpointer
147g_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}
175static inline gpointer
176g_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}
184static inline guint
185g_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}
197static inline GBSearchArray*
198g_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}
222static inline GBSearchArray*
223g_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}
251static inline GBSearchArray*
252g_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}
263static inline GBSearchArray*
264g_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}
292static inline void
293g_bsearch_array_free (GBSearchArray        *barray,
294                      const GBSearchConfig *bconfig)
295{
296  g_return_if_fail (barray != NULL);
297
298  g_free (barray);
299}
300
301G_END_DECLS     /* c++ guards */
302
303#endif  /* !__G_BSEARCH_ARRAY_H__ */
Note: See TracBrowser for help on using the repository browser.