fchash.c 5.82 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
/*
 * Copyright © 2000 Keith Packard
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of the author(s) not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  The authors make no
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */
#include "fcint.h"
23
#ifndef _WIN32
24
#include <uuid/uuid.h>
25
#endif
26

27
#define FC_HASH_SIZE 227
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

typedef struct _FcHashBucket {
    struct _FcHashBucket  *next;
    void                  *key;
    void                  *value;
} FcHashBucket;

struct _FcHashTable {
    FcHashBucket  *buckets[FC_HASH_SIZE];
    FcHashFunc     hash_func;
    FcCompareFunc  compare_func;
    FcCopyFunc     key_copy_func;
    FcCopyFunc     value_copy_func;
    FcDestroyFunc  key_destroy_func;
    FcDestroyFunc  value_destroy_func;
};


FcBool
FcHashStrCopy (const void  *src,
	       void       **dest)
{
    *dest = FcStrdup (src);

    return *dest != NULL;
}

FcBool
FcHashUuidCopy (const void  *src,
		void       **dest)
{
59
#ifndef _WIN32
60 61
    *dest = malloc (sizeof (uuid_t));
    uuid_copy (*dest, src);
62
#endif
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
    return FcTrue;
}

void
FcHashUuidFree (void *data)
{
    free (data);
}

FcHashTable *
FcHashTableCreate (FcHashFunc    hash_func,
		   FcCompareFunc compare_func,
		   FcCopyFunc    key_copy_func,
		   FcCopyFunc    value_copy_func,
		   FcDestroyFunc key_destroy_func,
		   FcDestroyFunc value_destroy_func)
{
    FcHashTable *ret = malloc (sizeof (FcHashTable));

    if (ret)
    {
	memset (ret->buckets, 0, sizeof (FcHashBucket *) * FC_HASH_SIZE);
	ret->hash_func = hash_func;
	ret->compare_func = compare_func;
	ret->key_copy_func = key_copy_func;
	ret->value_copy_func = value_copy_func;
	ret->key_destroy_func = key_destroy_func;
	ret->value_destroy_func = value_destroy_func;
    }
    return ret;
}

void
FcHashTableDestroy (FcHashTable *table)
{
    int i;

    for (i = 0; i < FC_HASH_SIZE; i++)
    {
	FcHashBucket *bucket = table->buckets[i], *prev;

	while (bucket)
	{
	    if (table->key_destroy_func)
		table->key_destroy_func (bucket->key);
	    if (table->value_destroy_func)
		table->value_destroy_func (bucket->value);
	    prev = bucket;
	    bucket = bucket->next;
	    free (prev);
	}
	table->buckets[i] = NULL;
    }
    free (table);
}

FcBool
FcHashTableFind (FcHashTable  *table,
		 const void   *key,
		 void        **value)
{
    FcHashBucket *bucket;
    FcChar32 hash = table->hash_func (key);

    for (bucket = table->buckets[hash % FC_HASH_SIZE]; bucket; bucket = bucket->next)
    {
	if (!table->compare_func(bucket->key, key))
	{
	    if (table->value_copy_func)
	    {
		if (!table->value_copy_func (bucket->value, value))
		    return FcFalse;
	    }
	    else
		*value = bucket->value;
	    return FcTrue;
	}
    }
    return FcFalse;
}

144 145 146 147 148
static FcBool
FcHashTableAddInternal (FcHashTable *table,
			void        *key,
			void        *value,
			FcBool       replace)
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
{
    FcHashBucket **prev, *bucket, *b;
    FcChar32 hash = table->hash_func (key);
    FcBool ret = FcFalse;

    bucket = (FcHashBucket *) malloc (sizeof (FcHashBucket));
    if (!bucket)
	return FcFalse;
    memset (bucket, 0, sizeof (FcHashBucket));
    if (table->key_copy_func)
	ret |= !table->key_copy_func (key, &bucket->key);
    else
	bucket->key = key;
    if (table->value_copy_func)
	ret |= !table->value_copy_func (value, &bucket->value);
    else
	bucket->value = value;
    if (ret)
    {
    destroy:
	if (bucket->key && table->key_destroy_func)
	    table->key_destroy_func (bucket->key);
	if (bucket->value && table->value_destroy_func)
	    table->value_destroy_func (bucket->value);
	free (bucket);

175
	return !ret;
176
    }
177
  retry:
Akira TAGOH's avatar
Akira TAGOH committed
178
    for (prev = &table->buckets[hash % FC_HASH_SIZE];
179
	 (b = fc_atomic_ptr_get (prev)); prev = &(b->next))
180
    {
181
	if (!table->compare_func (b->key, key))
182 183 184
	{
	    if (replace)
	    {
Alexander Larsson's avatar
Alexander Larsson committed
185
		bucket->next = b->next;
186 187 188 189 190 191
		if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
		    goto retry;
		bucket = b;
	    }
	    else
		ret = FcTrue;
192
	    goto destroy;
193
	}
194
    }
Alexander Larsson's avatar
Alexander Larsson committed
195
    bucket->next = NULL;
196 197
    if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
	goto retry;
198 199 200

    return FcTrue;
}
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216

FcBool
FcHashTableAdd (FcHashTable *table,
		void        *key,
		void        *value)
{
    return FcHashTableAddInternal (table, key, value, FcFalse);
}

FcBool
FcHashTableReplace (FcHashTable *table,
		    void        *key,
		    void        *value)
{
    return FcHashTableAddInternal (table, key, value, FcTrue);
}
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245

FcBool
FcHashTableRemove (FcHashTable *table,
		   void        *key)
{
    FcHashBucket **prev, *bucket;
    FcChar32 hash = table->hash_func (key);
    FcBool ret = FcFalse;

retry:
    for (prev = &table->buckets[hash % FC_HASH_SIZE];
	 (bucket = fc_atomic_ptr_get (prev)); prev = &(bucket->next))
    {
	if (!table->compare_func (bucket->key, key))
	{
	    if (!fc_atomic_ptr_cmpexch (prev, bucket, bucket->next))
		goto retry;
	    if (table->key_destroy_func)
		table->key_destroy_func (bucket->key);
	    if (table->value_destroy_func)
		table->value_destroy_func (bucket->value);
	    free (bucket);
	    ret = FcTrue;
	    break;
	}
    }

    return ret;
}