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.
22 #define G_IMPLEMENT_INLINES 1
23 #define __G_BSEARCHARRAY_C__
24 #include "gbsearcharray.h"
29 /* --- structures --- */
31 upper_power2 (guint number)
33 #ifdef DISABLE_MEM_POOLS
35 #else /* !DISABLE_MEM_POOLS */
36 return number ? 1 << g_bit_storage (number - 1) : 0;
37 #endif /* !DISABLE_MEM_POOLS */
41 g_bsearch_array_new (GBSearchConfig *bconfig)
43 GBSearchArray *barray;
46 g_return_val_if_fail (bconfig != NULL, NULL);
48 size = sizeof (GBSearchArray) + bconfig->sizeof_node;
49 if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
50 size = upper_power2 (size);
51 barray = g_malloc0 (size);
58 g_bsearch_array_destroy (GBSearchArray *barray,
59 GBSearchConfig *bconfig)
61 g_return_if_fail (barray != NULL);
66 static inline GBSearchArray*
67 bsearch_array_insert (GBSearchArray *barray,
68 GBSearchConfig *bconfig,
69 gconstpointer key_node,
75 sizeof_node = bconfig->sizeof_node;
76 if (barray->n_nodes == 0)
78 guint new_size = sizeof (GBSearchArray) + sizeof_node;
80 if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
81 new_size = upper_power2 (new_size);
82 barray = g_realloc (barray, new_size);
84 check = G_BSEARCH_ARRAY_NODES (barray);
88 GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
89 guint n_nodes = barray->n_nodes;
90 guint8 *nodes = G_BSEARCH_ARRAY_NODES (barray);
97 i = (n_nodes + 1) >> 1;
98 check = nodes + i * sizeof_node;
99 cmp = cmp_nodes (key_node, check);
107 else /* if (cmp == 0) */
110 memcpy (check, key_node, sizeof_node);
117 check += sizeof_node;
118 i = (check - ((guint8*) G_BSEARCH_ARRAY_NODES (barray))) / sizeof_node;
119 n_nodes = barray->n_nodes++;
120 if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
122 guint new_size = upper_power2 (sizeof (GBSearchArray) + barray->n_nodes * sizeof_node);
123 guint old_size = upper_power2 (sizeof (GBSearchArray) + n_nodes * sizeof_node);
125 if (new_size != old_size)
126 barray = g_realloc (barray, new_size);
129 barray = g_realloc (barray, sizeof (GBSearchArray) + barray->n_nodes * sizeof_node);
130 check = ((guint8*) G_BSEARCH_ARRAY_NODES (barray)) + i * sizeof_node;
131 g_memmove (check + sizeof_node, check, (n_nodes - i) * sizeof_node);
133 memcpy (check, key_node, sizeof_node);
139 g_bsearch_array_insert (GBSearchArray *barray,
140 GBSearchConfig *bconfig,
141 gconstpointer key_node,
142 gboolean replace_existing)
144 g_return_val_if_fail (barray != NULL, NULL);
145 g_return_val_if_fail (bconfig != NULL, barray);
146 g_return_val_if_fail (key_node != NULL, barray);
148 return bsearch_array_insert (barray, bconfig, key_node, replace_existing);
152 g_bsearch_array_remove_node (GBSearchArray *barray,
153 GBSearchConfig *bconfig,
154 gpointer _node_in_array)
156 guint8 *nodes, *bound, *node_in_array = _node_in_array;
159 g_return_val_if_fail (barray != NULL, NULL);
160 g_return_val_if_fail (bconfig != NULL, barray);
162 nodes = G_BSEARCH_ARRAY_NODES (barray);
163 old_size = bconfig->sizeof_node;
164 old_size *= barray->n_nodes; /* beware of int widths */
165 bound = nodes + old_size;
167 g_return_val_if_fail (node_in_array >= nodes && node_in_array < bound, barray);
169 bound -= bconfig->sizeof_node;
170 barray->n_nodes -= 1;
171 g_memmove (node_in_array, node_in_array + bconfig->sizeof_node, (bound - node_in_array) / bconfig->sizeof_node);
173 if ((bconfig->flags & G_BSEARCH_ARRAY_DEFER_SHRINK) == 0)
175 guint new_size = bound - nodes; /* old_size - bconfig->sizeof_node */
177 if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
179 new_size = upper_power2 (sizeof (GBSearchArray) + new_size);
180 old_size = upper_power2 (sizeof (GBSearchArray) + old_size);
181 if (old_size != new_size)
182 barray = g_realloc (barray, new_size);
185 barray = g_realloc (barray, sizeof (GBSearchArray) + new_size);
191 g_bsearch_array_remove (GBSearchArray *barray,
192 GBSearchConfig *bconfig,
193 gconstpointer key_node)
195 gpointer node_in_array;
197 g_return_val_if_fail (barray != NULL, NULL);
198 g_return_val_if_fail (bconfig != NULL, barray);
200 node_in_array = g_bsearch_array_lookup (barray, bconfig, key_node);
203 g_warning (G_STRLOC ": unable to remove unexistant node");
207 return g_bsearch_array_remove_node (barray, bconfig, node_in_array);