1 /* GObject - GLib Type, Object, Parameter and Signal Library
2 * Copyright (C) 2000-2001 Tim Janik
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General
15 * Public License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
17 * Boston, MA 02111-1307, USA.
19 * gbsearcharray.h: binary searchable sorted array maintenance
21 #ifndef __G_BSEARCH_ARRAY_H__
22 #define __G_BSEARCH_ARRAY_H__
24 #include <glib/gtypes.h>
25 #include <glib/gutils.h>
26 #include <glib/gmem.h>
27 #include <glib/gmessages.h>
31 /* helper macro to avoid signed overflow for value comparisions */
32 #define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) < (v2) ? -1 : (v1) > (v2))
35 /* --- typedefs --- */
36 typedef union _GBSearchArray GBSearchArray
;
37 typedef struct _GBSearchConfig GBSearchConfig
;
38 typedef gint (*GBSearchCompareFunc
) (gconstpointer bsearch_node1
,
39 gconstpointer bsearch_node2
);
42 G_BSEARCH_ARRAY_ALIGN_POWER2
= 1 << 0,
43 G_BSEARCH_ARRAY_DEFER_SHRINK
= 1 << 1
47 /* --- structures --- */
48 struct _GBSearchConfig
51 GBSearchCompareFunc cmp_nodes
;
57 gpointer alignment_dummy1
;
58 glong alignment_dummy2
;
59 gdouble alignment_dummy3
;
63 /* --- prototypes --- */
64 GBSearchArray
* g_bsearch_array_new (GBSearchConfig
*bconfig
);
65 void g_bsearch_array_destroy (GBSearchArray
*barray
,
66 GBSearchConfig
*bconfig
);
67 GBSearchArray
* g_bsearch_array_insert (GBSearchArray
*barray
,
68 GBSearchConfig
*bconfig
,
69 gconstpointer key_node
,
70 gboolean replace_existing
);
71 GBSearchArray
* g_bsearch_array_remove (GBSearchArray
*barray
,
72 GBSearchConfig
*bconfig
,
73 gconstpointer key_node
);
74 GBSearchArray
* g_bsearch_array_remove_node (GBSearchArray
*barray
,
75 GBSearchConfig
*bconfig
,
76 gpointer node_in_array
);
78 gpointer
g_bsearch_array_lookup (GBSearchArray
*barray
,
79 GBSearchConfig
*bconfig
,
80 gconstpointer key_node
);
82 gpointer
g_bsearch_array_get_nth (GBSearchArray
*barray
,
83 GBSearchConfig
*bconfig
,
86 guint
g_bsearch_array_get_index (GBSearchArray
*barray
,
87 GBSearchConfig
*bconfig
,
88 gpointer node_in_array
);
91 /* initialization of static arrays */
92 #define G_STATIC_BCONFIG(sizeof_node, cmp_nodes, flags) \
93 { (sizeof_node), (cmp_nodes), (flags), }
96 /* --- implementation details --- */
97 #define G_BSEARCH_ARRAY_NODES(barray) ((gpointer) (((guint8*) (barray)) + sizeof (GBSearchArray)))
98 #if defined (G_CAN_INLINE) || defined (__G_BSEARCHARRAY_C__)
99 G_INLINE_FUNC gpointer
100 g_bsearch_array_lookup (GBSearchArray
*barray
,
101 GBSearchConfig
*bconfig
,
102 gconstpointer key_node
)
104 if (barray
->n_nodes
> 0)
106 GBSearchCompareFunc cmp_nodes
= bconfig
->cmp_nodes
;
107 gint sizeof_node
= bconfig
->sizeof_node
;
108 guint n_nodes
= barray
->n_nodes
;
109 guint8
*nodes
= G_BSEARCH_ARRAY_NODES (barray
);
111 nodes
-= sizeof_node
;
118 i
= (n_nodes
+ 1) >> 1;
119 check
= nodes
+ i
* sizeof_node
;
120 cmp
= cmp_nodes (key_node
, check
);
128 else /* if (cmp < 0) */
136 G_INLINE_FUNC gpointer
137 g_bsearch_array_get_nth (GBSearchArray
*barray
,
138 GBSearchConfig
*bconfig
,
141 if (n
< barray
->n_nodes
)
143 guint8
*nodes
= (guint8
*) G_BSEARCH_ARRAY_NODES (barray
);
145 return nodes
+ n
* bconfig
->sizeof_node
;
152 g_bsearch_array_get_index (GBSearchArray
*barray
,
153 GBSearchConfig
*bconfig
,
154 gpointer node_in_array
)
156 guint distance
= ((guint8
*) node_in_array
) - ((guint8
*) G_BSEARCH_ARRAY_NODES (barray
));
158 distance
/= bconfig
->sizeof_node
;
160 return MIN (distance
, barray
->n_nodes
);
162 #endif /* G_CAN_INLINE || __G_BSEARCHARRAY_C__ */
166 #endif /* __G_BSEARCH_ARRAY_H__ */