src/fchash.c

   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 #ifndef _WIN32
  24 #include <uuid/uuid.h>
  25 #endif
  26
  27 #define FC_HASH_SIZE 227
  28
  29 typedef struct _FcHashBucket {
  30     struct _FcHashBucket  *next;
  31     void                  *key;
  32     void                  *value;
  33 } FcHashBucket;
  34
  35 struct _FcHashTable {
  36     FcHashBucket  *buckets[FC_HASH_SIZE];
  37     FcHashFunc     hash_func;
  38     FcCompareFunc  compare_func;
  39     FcCopyFunc     key_copy_func;
  40     FcCopyFunc     value_copy_func;
  41     FcDestroyFunc  key_destroy_func;
  42     FcDestroyFunc  value_destroy_func;
  43 };
  44
  45
  46 FcBool
  47 FcHashStrCopy (const void  *src,
  48                void       **dest)
  49 {
  50     *dest = FcStrdup (src);
  51
  52     return *dest != NULL;
  53 }
  54
  55 FcBool
  56 FcHashUuidCopy (const void  *src,
  57                 void       **dest)
  58 {
  59 #ifndef _WIN32
  60     *dest = malloc (sizeof (uuid_t));
  61     uuid_copy (*dest, src);
  62 #endif
  63     return FcTrue;
  64 }
  65
  66 void
  67 FcHashUuidFree (void *data)
  68 {
  69     free (data);
  70 }
  71
  72 FcHashTable *
  73 FcHashTableCreate (FcHashFunc    hash_func,
  74                    FcCompareFunc compare_func,
  75                    FcCopyFunc    key_copy_func,
  76                    FcCopyFunc    value_copy_func,
  77                    FcDestroyFunc key_destroy_func,
  78                    FcDestroyFunc value_destroy_func)
  79 {
  80     FcHashTable *ret = malloc (sizeof (FcHashTable));
  81
  82     if (ret)
  83     {
  84         memset (ret->buckets, 0, sizeof (FcHashBucket *) * FC_HASH_SIZE);
  85         ret->hash_func = hash_func;
  86         ret->compare_func = compare_func;
  87         ret->key_copy_func = key_copy_func;
  88         ret->value_copy_func = value_copy_func;
  89         ret->key_destroy_func = key_destroy_func;
  90         ret->value_destroy_func = value_destroy_func;
  91     }
  92     return ret;
  93 }
  94
  95 void
  96 FcHashTableDestroy (FcHashTable *table)
  97 {
  98     int i;
  99
 100     for (i = 0; i < FC_HASH_SIZE; i++)
 101     {
 102         FcHashBucket *bucket = table->buckets[i], *prev;
 103
 104         while (bucket)
 105         {
 106             if (table->key_destroy_func)
 107                 table->key_destroy_func (bucket->key);
 108             if (table->value_destroy_func)
 109                 table->value_destroy_func (bucket->value);
 110             prev = bucket;
 111             bucket = bucket->next;
 112             free (prev);
 113         }
 114         table->buckets[i] = NULL;
 115     }
 116     free (table);
 117 }
 118
 119 FcBool
 120 FcHashTableFind (FcHashTable  *table,
 121                  const void   *key,
 122                  void        **value)
 123 {
 124     FcHashBucket *bucket;
 125     FcChar32 hash = table->hash_func (key);
 126
 127     for (bucket = table->buckets[hash % FC_HASH_SIZE]; bucket; bucket = bucket->next)
 128     {
 129         if (!table->compare_func(bucket->key, key))
 130         {
 131             if (table->value_copy_func)
 132             {
 133                 if (!table->value_copy_func (bucket->value, value))
 134                     return FcFalse;
 135             }
 136             else
 137                 *value = bucket->value;
 138             return FcTrue;
 139         }
 140     }
 141     return FcFalse;
 142 }
 143
 144 static FcBool
 145 FcHashTableAddInternal (FcHashTable *table,
 146                         void        *key,
 147                         void        *value,
 148                         FcBool       replace)
 149 {
 150     FcHashBucket **prev, *bucket, *b;
 151     FcChar32 hash = table->hash_func (key);
 152     FcBool ret = FcFalse;
 153
 154     bucket = (FcHashBucket *) malloc (sizeof (FcHashBucket));
 155     if (!bucket)
 156         return FcFalse;
 157     memset (bucket, 0, sizeof (FcHashBucket));
 158     if (table->key_copy_func)
 159         ret |= !table->key_copy_func (key, &bucket->key);
 160     else
 161         bucket->key = key;
 162     if (table->value_copy_func)
 163         ret |= !table->value_copy_func (value, &bucket->value);
 164     else
 165         bucket->value = value;
 166     if (ret)
 167     {
 168     destroy:
 169         if (bucket->key && table->key_destroy_func)
 170             table->key_destroy_func (bucket->key);
 171         if (bucket->value && table->value_destroy_func)
 172             table->value_destroy_func (bucket->value);
 173         free (bucket);
 174
 175         return !ret;
 176     }
 177   retry:
 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             if (replace)
 184             {
 185                 bucket->next = b->next;
 186                 if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
 187                     goto retry;
 188                 bucket = b;
 189             }
 190             else
 191                 ret = FcTrue;
 192             goto destroy;
 193         }
 194     }
 195     bucket->next = NULL;
 196     if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
 197         goto retry;
 198
 199     return FcTrue;
 200 }
 201
 202 FcBool
 203 FcHashTableAdd (FcHashTable *table,
 204                 void        *key,
 205                 void        *value)
 206 {
 207     return FcHashTableAddInternal (table, key, value, FcFalse);
 208 }
 209
 210 FcBool
 211 FcHashTableReplace (FcHashTable *table,
 212                     void        *key,
 213                     void        *value)
 214 {
 215     return FcHashTableAddInternal (table, key, value, FcTrue);
 216 }
 217
 218 FcBool
 219 FcHashTableRemove (FcHashTable *table,
 220                    void        *key)
 221 {
 222     FcHashBucket **prev, *bucket;
 223     FcChar32 hash = table->hash_func (key);
 224     FcBool ret = FcFalse;
 225
 226 retry:
 227     for (prev = &table->buckets[hash % FC_HASH_SIZE];
 228          (bucket = fc_atomic_ptr_get (prev)); prev = &(bucket->next))
 229     {
 230         if (!table->compare_func (bucket->key, key))
 231         {
 232             if (!fc_atomic_ptr_cmpexch (prev, bucket, bucket->next))
 233                 goto retry;
 234             if (table->key_destroy_func)
 235                 table->key_destroy_func (bucket->key);
 236             if (table->value_destroy_func)
 237                 table->value_destroy_func (bucket->value);
 238             free (bucket);
 239             ret = FcTrue;
 240             break;
 241         }
 242     }
 243
 244     return ret;
 245 }