1 /*
2 * Copyright © 2000 Keith Packard
3 *
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided that
6 * the above copyright notice appear in all copies and that both that
7 * copyright notice and this permission notice appear in supporting
8 * documentation, and that the name of the author(s) not be used in
9 * advertising or publicity pertaining to distribution of the software without
10 * specific, written prior permission. The authors make no
11 * representations about the suitability of this software for any purpose. It
12 * is provided "as is" without express or implied warranty.
13 *
14 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
16 * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
19 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
20 * PERFORMANCE OF THIS SOFTWARE.
21 */
22 #include "fcint.h"
23
24 #define FC_HASH_SIZE 227
25
26 typedef struct _FcHashBucket {
27 struct _FcHashBucket *next;
28 void *key;
29 void *value;
30 } FcHashBucket;
31
32 struct _FcHashTable {
33 FcHashBucket *buckets[FC_HASH_SIZE];
34 FcHashFunc hash_func;
35 FcCompareFunc compare_func;
36 FcCopyFunc key_copy_func;
37 FcCopyFunc value_copy_func;
38 FcDestroyFunc key_destroy_func;
39 FcDestroyFunc value_destroy_func;
40 };
41
42
43 FcBool
44 FcHashStrCopy (const void *src,
45 void **dest)
46 {
47 *dest = FcStrdup (src);
48
49 return *dest != NULL;
50 }
51
52 FcHashTable *
53 FcHashTableCreate (FcHashFunc hash_func,
54 FcCompareFunc compare_func,
55 FcCopyFunc key_copy_func,
56 FcCopyFunc value_copy_func,
57 FcDestroyFunc key_destroy_func,
58 FcDestroyFunc value_destroy_func)
59 {
60 FcHashTable *ret = malloc (sizeof (FcHashTable));
61
62 if (ret)
63 {
64 memset (ret->buckets, 0, sizeof (FcHashBucket *) * FC_HASH_SIZE);
65 ret->hash_func = hash_func;
66 ret->compare_func = compare_func;
67 ret->key_copy_func = key_copy_func;
68 ret->value_copy_func = value_copy_func;
69 ret->key_destroy_func = key_destroy_func;
70 ret->value_destroy_func = value_destroy_func;
71 }
72 return ret;
73 }
74
75 void
76 FcHashTableDestroy (FcHashTable *table)
77 {
78 int i;
79
80 for (i = 0; i < FC_HASH_SIZE; i++)
81 {
82 FcHashBucket *bucket = table->buckets[i], *prev;
83
84 while (bucket)
85 {
86 if (table->key_destroy_func)
87 table->key_destroy_func (bucket->key);
88 if (table->value_destroy_func)
89 table->value_destroy_func (bucket->value);
90 prev = bucket;
91 bucket = bucket->next;
92 free (prev);
93 }
94 table->buckets[i] = NULL;
95 }
96 free (table);
97 }
98
99 FcBool
100 FcHashTableFind (FcHashTable *table,
101 const void *key,
102 void **value)
103 {
104 FcHashBucket *bucket;
105 FcChar32 hash = table->hash_func (key);
106
107 for (bucket = table->buckets[hash % FC_HASH_SIZE]; bucket; bucket = bucket->next)
108 {
109 if (!table->compare_func(bucket->key, key))
110 {
111 if (table->value_copy_func)
112 {
113 if (!table->value_copy_func (bucket->value, value))
114 return FcFalse;
115 }
116 else
117 *value = bucket->value;
118 return FcTrue;
119 }
120 }
121 return FcFalse;
122 }
123
124 static FcBool
125 FcHashTableAddInternal (FcHashTable *table,
126 void *key,
127 void *value,
128 FcBool replace)
129 {
130 FcHashBucket **prev, *bucket, *b;
131 FcChar32 hash = table->hash_func (key);
132 FcBool ret = FcFalse;
133
134 bucket = (FcHashBucket *) malloc (sizeof (FcHashBucket));
135 if (!bucket)
136 return FcFalse;
137 memset (bucket, 0, sizeof (FcHashBucket));
138 if (table->key_copy_func)
139 ret |= !table->key_copy_func (key, &bucket->key);
140 else
141 bucket->key = key;
142 if (table->value_copy_func)
143 ret |= !table->value_copy_func (value, &bucket->value);
144 else
145 bucket->value = value;
146 if (ret)
147 {
148 destroy:
149 if (bucket->key && table->key_destroy_func)
150 table->key_destroy_func (bucket->key);
151 if (bucket->value && table->value_destroy_func)
152 table->value_destroy_func (bucket->value);
153 free (bucket);
154
155 return !ret;
156 }
157 retry:
158 for (prev = &table->buckets[hash % FC_HASH_SIZE];
159 (b = fc_atomic_ptr_get (prev)); prev = &(b->next))
160 {
161 if (!table->compare_func (b->key, key))
162 {
163 if (replace)
164 {
165 bucket->next = b->next;
166 if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
167 goto retry;
168 bucket = b;
169 }
170 else
171 ret = FcTrue;
172 goto destroy;
173 }
174 }
175 bucket->next = NULL;
176 if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
177 goto retry;
178
179 return FcTrue;
180 }
181
182 FcBool
183 FcHashTableAdd (FcHashTable *table,
184 void *key,
185 void *value)
186 {
187 return FcHashTableAddInternal (table, key, value, FcFalse);
188 }
189
190 FcBool
191 FcHashTableReplace (FcHashTable *table,
192 void *key,
193 void *value)
194 {
195 return FcHashTableAddInternal (table, key, value, FcTrue);
196 }
197
198 FcBool
199 FcHashTableRemove (FcHashTable *table,
200 void *key)
201 {
202 FcHashBucket **prev, *bucket;
203 FcChar32 hash = table->hash_func (key);
204 FcBool ret = FcFalse;
205
206 retry:
207 for (prev = &table->buckets[hash % FC_HASH_SIZE];
208 (bucket = fc_atomic_ptr_get (prev)); prev = &(bucket->next))
209 {
210 if (!table->compare_func (bucket->key, key))
211 {
212 if (!fc_atomic_ptr_cmpexch (prev, bucket, bucket->next))
213 goto retry;
214 if (table->key_destroy_func)
215 table->key_destroy_func (bucket->key);
216 if (table->value_destroy_func)
217 table->value_destroy_func (bucket->value);
218 free (bucket);
219 ret = FcTrue;
220 break;
221 }
222 }
223
224 return ret;
225 }