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
26typedef struct _FcHashBucket {
27    struct _FcHashBucket  *next;
28    void                  *key;
29    void                  *value;
30} FcHashBucket;
31
32struct _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
43FcBool
44FcHashStrCopy (const void  *src,
45	       void       **dest)
46{
47    *dest = FcStrdup (src);
48
49    return *dest != NULL;
50}
51
52FcHashTable *
53FcHashTableCreate (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
75void
76FcHashTableDestroy (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
99FcBool
100FcHashTableFind (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
124static FcBool
125FcHashTableAddInternal (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
182FcBool
183FcHashTableAdd (FcHashTable *table,
184		void        *key,
185		void        *value)
186{
187    return FcHashTableAddInternal (table, key, value, FcFalse);
188}
189
190FcBool
191FcHashTableReplace (FcHashTable *table,
192		    void        *key,
193		    void        *value)
194{
195    return FcHashTableAddInternal (table, key, value, FcTrue);
196}
197
198FcBool
199FcHashTableRemove (FcHashTable *table,
200		   void        *key)
201{
202    FcHashBucket **prev, *bucket;
203    FcChar32 hash = table->hash_func (key);
204    FcBool ret = FcFalse;
205
206retry:
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}
226