+ guint n_nodes;
+ /*< private >*/
+ gpointer alignment_dummy1;
+ glong alignment_dummy2;
+ gdouble alignment_dummy3;
+} GBSearchArray;
+
+
+/* --- public API --- */
+static inline GBSearchArray* g_bsearch_array_create (const GBSearchConfig *bconfig);
+static inline gpointer g_bsearch_array_get_nth (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ guint nth);
+static inline guint g_bsearch_array_get_index (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ gconstpointer node_in_array);
+static inline GBSearchArray* g_bsearch_array_remove (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ guint index_);
+/* provide uninitialized space at index for node insertion */
+static inline GBSearchArray* g_bsearch_array_grow (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ guint index);
+/* insert key_node into array if it does not exist, otherwise do nothing */
+static inline GBSearchArray* g_bsearch_array_insert (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ gconstpointer key_node);
+/* insert key_node into array if it does not exist,
+ * otherwise replace the existing node's contents with key_node
+ */
+static inline GBSearchArray* g_bsearch_array_replace (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ gconstpointer key_node);
+static inline void g_bsearch_array_free (GBSearchArray *barray,
+ const GBSearchConfig *bconfig);
+#define g_bsearch_array_get_n_nodes(barray) (((GBSearchArray*) (barray))->n_nodes)
+
+/* g_bsearch_array_lookup():
+ * return NULL or exact match node
+ */
+#define g_bsearch_array_lookup(barray, bconfig, key_node) \
+ g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 0)
+
+/* g_bsearch_array_lookup_sibling():
+ * return NULL for barray->n_nodes==0, otherwise return the
+ * exact match node, or, if there's no such node, return the
+ * node last visited, which is pretty close to an exact match
+ * (will be one off into either direction).
+ */
+#define g_bsearch_array_lookup_sibling(barray, bconfig, key_node) \
+ g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 1)
+
+/* g_bsearch_array_lookup_insertion():
+ * return NULL for barray->n_nodes==0 or exact match, otherwise
+ * return the node where key_node should be inserted (may be one
+ * after end, i.e. g_bsearch_array_get_index(result) <= barray->n_nodes).
+ */
+#define g_bsearch_array_lookup_insertion(barray, bconfig, key_node) \
+ g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 2)
+
+
+/* --- implementation --- */
+/* helper macro to cut down realloc()s */
+#ifdef DISABLE_MEM_POOLS
+#define G_BSEARCH_UPPER_POWER2(n) (n)
+#else /* !DISABLE_MEM_POOLS */
+#define G_BSEARCH_UPPER_POWER2(n) ((n) ? 1 << g_bit_storage ((n) - 1) : 0)
+#endif /* !DISABLE_MEM_POOLS */
+#define G_BSEARCH_ARRAY_NODES(barray) (((guint8*) (barray)) + sizeof (GBSearchArray))
+static inline GBSearchArray*
+g_bsearch_array_create (const GBSearchConfig *bconfig)
+{
+ GBSearchArray *barray;
+ guint size;
+
+ g_return_val_if_fail (bconfig != NULL, NULL);
+
+ size = sizeof (GBSearchArray) + bconfig->sizeof_node;
+ if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
+ size = G_BSEARCH_UPPER_POWER2 (size);
+ barray = (GBSearchArray *) g_malloc (size);
+ memset (barray, 0, sizeof (GBSearchArray));
+
+ return barray;
+}
+static inline gpointer
+g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ gconstpointer key_node,
+ const guint sibling_or_after);
+static inline gpointer
+g_bsearch_array_lookup_fuzzy (GBSearchArray *barray,
+ const GBSearchConfig *bconfig,
+ gconstpointer key_node,
+ const guint sibling_or_after)
+{
+ GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
+ guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray);
+ guint n_nodes = barray->n_nodes, offs = 0;
+ guint sizeof_node = bconfig->sizeof_node;
+ gint cmp = 0;
+
+ while (offs < n_nodes)