Add comment from darco about what the "Palette Browser" dock dialog was intended...
[synfig.git] / synfig-osx / trunk / launcher / x-hash.c
1 /* x-hash.c - basic hash tables
2    $Id: x-hash.c,v 1.7 2003/07/17 05:25:44 jharper Exp $
3
4    Copyright (c) 2002 Apple Computer, Inc. All rights reserved.
5
6    Permission is hereby granted, free of charge, to any person
7    obtaining a copy of this software and associated documentation files
8    (the "Software"), to deal in the Software without restriction,
9    including without limitation the rights to use, copy, modify, merge,
10    publish, distribute, sublicense, and/or sell copies of the Software,
11    and to permit persons to whom the Software is furnished to do so,
12    subject to the following conditions:
13
14    The above copyright notice and this permission notice shall be
15    included in all copies or substantial portions of the Software.
16
17    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20    NONINFRINGEMENT.  IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
21    HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
24    DEALINGS IN THE SOFTWARE.
25
26    Except as contained in this notice, the name(s) of the above
27    copyright holders shall not be used in advertising or otherwise to
28    promote the sale, use or other dealings in this Software without
29    prior written authorization. */
30
31 #include "x-hash.h"
32 #include "x-list.h"
33 #include <stdlib.h>
34 #include <assert.h>
35
36 struct x_hash_table_struct {
37     unsigned int bucket_index;
38     unsigned int total_keys;
39     x_list **buckets;
40
41     x_hash_fun *hash_key;
42     x_compare_fun *compare_keys;
43     x_destroy_fun *destroy_key;
44     x_destroy_fun *destroy_value;
45 };
46
47 #define ITEM_NEW(k, v) X_PFX (list_prepend) ((x_list *) (k), v)
48 #define ITEM_FREE(i) X_PFX (list_free_1) (i)
49 #define ITEM_KEY(i) ((void *) (i)->next)
50 #define ITEM_VALUE(i) ((i)->data)
51
52 #define SPLIT_THRESHOLD_FACTOR 2
53
54 /* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */
55 static const unsigned int bucket_sizes[] = {
56     29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157,
57     98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
58     25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
59     1610612741
60 };
61
62 #define N_BUCKET_SIZES (sizeof (bucket_sizes) / sizeof (bucket_sizes[0]))
63
64 static inline unsigned int
65 hash_table_total_buckets (x_hash_table *h)
66 {
67     return bucket_sizes[h->bucket_index];
68 }
69
70 static inline void
71 hash_table_destroy_item (x_hash_table *h, void *k, void *v)
72 {
73     if (h->destroy_key != 0)
74         (*h->destroy_key) (k);
75
76     if (h->destroy_value != 0)
77         (*h->destroy_value) (v);
78 }
79
80 static inline unsigned int
81 hash_table_hash_key (x_hash_table *h, void *k)
82 {
83     if (h->hash_key != 0)
84         return (*h->hash_key) (k);
85     else
86         return (unsigned int) k;
87 }
88
89 static inline int
90 hash_table_compare_keys (x_hash_table *h, void *k1, void *k2)
91 {
92     if (h->compare_keys == 0)
93         return k1 == k2;
94     else
95         return (*h->compare_keys) (k1, k2) == 0;
96 }
97
98 static void
99 hash_table_split (x_hash_table *h)
100 {
101     x_list **new, **old;
102     x_list *node, *item, *next;
103     int new_size, old_size;
104     unsigned int b;
105     int i;
106
107     if (h->bucket_index == N_BUCKET_SIZES - 1)
108         return;
109
110     old_size = hash_table_total_buckets (h);
111     old = h->buckets;
112
113     h->bucket_index++;
114
115     new_size = hash_table_total_buckets (h);
116     new = calloc (new_size, sizeof (x_list *));
117
118     if (new == 0)
119     {
120         h->bucket_index--;
121         return;
122     }
123
124     for (i = 0; i < old_size; i++)
125     {
126         for (node = old[i]; node != 0; node = next)
127         {
128             next = node->next;
129             item = node->data;
130
131             b = hash_table_hash_key (h, ITEM_KEY (item)) % new_size;
132
133             node->next = new[b];
134             new[b] = node;
135         }
136     }
137
138     h->buckets = new;
139     free (old);
140 }
141
142 X_EXTERN x_hash_table *
143 X_PFX (hash_table_new) (x_hash_fun *hash,
144                         x_compare_fun *compare,
145                         x_destroy_fun *key_destroy,
146                         x_destroy_fun *value_destroy)
147 {
148     x_hash_table *h;
149
150     h = calloc (1, sizeof (x_hash_table));
151     if (h == 0)
152         return 0;
153
154     h->bucket_index = 0;
155     h->buckets = calloc (hash_table_total_buckets (h), sizeof (x_list *));
156
157     if (h->buckets == 0)
158     {
159         free (h);
160         return 0;
161     }
162     
163     h->hash_key = hash;
164     h->compare_keys = compare;
165     h->destroy_key = key_destroy;
166     h->destroy_value = value_destroy;
167
168     return h;
169 }
170
171 X_EXTERN void
172 X_PFX (hash_table_free) (x_hash_table *h)
173 {
174     int n, i;
175     x_list *node, *item;
176
177     assert (h != NULL);
178
179     n = hash_table_total_buckets (h);
180
181     for (i = 0; i < n; i++)
182     {
183         for (node = h->buckets[i]; node != 0; node = node->next)
184         {
185             item = node->data;
186             hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
187             ITEM_FREE (item);
188         }
189         X_PFX (list_free) (h->buckets[i]);
190     }
191
192     free (h->buckets);
193     free (h);
194 }
195
196 X_EXTERN unsigned int
197 X_PFX (hash_table_size) (x_hash_table *h)
198 {
199     assert (h != NULL);
200
201     return h->total_keys;
202 }
203
204 static void
205 hash_table_modify (x_hash_table *h, void *k, void *v, int replace)
206 {
207     unsigned int hash_value;
208     x_list *node, *item;
209
210     assert (h != NULL);
211
212     hash_value = hash_table_hash_key (h, k);
213
214     for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
215          node != 0; node = node->next)
216     {
217         item = node->data;
218
219         if (hash_table_compare_keys (h, ITEM_KEY (item), k))
220         {
221             if (replace)
222             {
223                 hash_table_destroy_item (h, ITEM_KEY (item),
224                                          ITEM_VALUE (item));
225                 ITEM_KEY (item) = k;
226                 ITEM_VALUE (item) = v;
227             }
228             else
229             {
230                 hash_table_destroy_item (h, k, ITEM_VALUE (item));
231                 ITEM_VALUE (item) = v;
232             }
233             return;
234         }
235     }
236
237     /* Key isn't already in the table. Insert it. */
238
239     if (h->total_keys + 1
240         > hash_table_total_buckets (h) * SPLIT_THRESHOLD_FACTOR)
241     {
242         hash_table_split (h);
243     }
244
245     hash_value = hash_value % hash_table_total_buckets (h);
246     h->buckets[hash_value] = X_PFX (list_prepend) (h->buckets[hash_value],
247                                                    ITEM_NEW (k, v));
248     h->total_keys++;
249 }
250
251 X_EXTERN void
252 X_PFX (hash_table_insert) (x_hash_table *h, void *k, void *v)
253 {
254     hash_table_modify (h, k, v, 0);
255 }
256
257 X_EXTERN void
258 X_PFX (hash_table_replace) (x_hash_table *h, void *k, void *v)
259 {
260     hash_table_modify (h, k, v, 1);
261 }
262
263 X_EXTERN void
264 X_PFX (hash_table_remove) (x_hash_table *h, void *k)
265 {
266     unsigned int hash_value;
267     x_list **ptr, *item;
268
269     assert (h != NULL);
270
271     hash_value = hash_table_hash_key (h, k);
272
273     for (ptr = &h->buckets[hash_value % hash_table_total_buckets (h)];
274          *ptr != 0; ptr = &((*ptr)->next))
275     {
276         item = (*ptr)->data;
277
278         if (hash_table_compare_keys (h, ITEM_KEY (item), k))
279         {
280             hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
281             ITEM_FREE (item);
282             item = *ptr;
283             *ptr = item->next;
284             X_PFX (list_free_1) (item);
285             h->total_keys--;
286             return;
287         }
288     }
289 }
290
291 X_EXTERN void *
292 X_PFX (hash_table_lookup) (x_hash_table *h, void *k, void **k_ret)
293 {
294     unsigned int hash_value;
295     x_list *node, *item;
296
297     assert (h != NULL);
298
299     hash_value = hash_table_hash_key (h, k);
300
301     for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
302          node != 0; node = node->next)
303     {
304         item = node->data;
305
306         if (hash_table_compare_keys (h, ITEM_KEY (item), k))
307         {
308             if (k_ret != 0)
309                 *k_ret = ITEM_KEY (item);
310
311             return ITEM_VALUE (item);
312         }
313     }
314
315     if (k_ret != 0)
316         *k_ret = 0;
317
318     return 0;
319 }
320
321 X_EXTERN void
322 X_PFX (hash_table_foreach) (x_hash_table *h,
323                             x_hash_foreach_fun *fun, void *data)
324 {
325     int i, n;
326     x_list *node, *item;
327
328     assert (h != NULL);
329
330     n = hash_table_total_buckets (h);
331
332     for (i = 0; i < n; i++)
333     {
334         for (node = h->buckets[i]; node != 0; node = node->next)
335         {
336             item = node->data;
337             (*fun) (ITEM_KEY (item), ITEM_VALUE (item), data);
338         }
339     }
340 }