src/gallium/auxiliary/util/u_hash_table.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /**
  29  * @file
  30  * General purpose hash table implementation.
  31  *
  32  * Just uses the cso_hash for now, but it might be better switch to a linear
  33  * probing hash table implementation at some point -- as it is said they have
  34  * better lookup and cache performance and it appears to be possible to write
  35  * a lock-free implementation of such hash tables .
  36  *
  37  * @author José Fonseca <jrfonseca@tungstengraphics.com>
  38  */
  39
  40
  41 #include "pipe/p_compiler.h"
  42 #include "util/u_debug.h"
  43
  44 #include "cso_cache/cso_hash.h"
  45
  46 #include "util/u_memory.h"
  47 #include "util/u_hash_table.h"
  48
  49
  50 struct util_hash_table
  51 {
  52    struct cso_hash *cso;
  53
  54    /** Hash function */
  55    unsigned (*hash)(void *key);
  56
  57    /** Compare two keys */
  58    int (*compare)(void *key1, void *key2);
  59
  60    /* TODO: key, value destructors? */
  61 };
  62
  63
  64 struct util_hash_table_item
  65 {
  66    void *key;
  67    void *value;
  68 };
  69
  70
  71 static INLINE struct util_hash_table_item *
  72 util_hash_table_item(struct cso_hash_iter iter)
  73 {
  74    return (struct util_hash_table_item *)cso_hash_iter_data(iter);
  75 }
  76
  77
  78 struct util_hash_table *
  79 util_hash_table_create(unsigned (*hash)(void *key),
  80                        int (*compare)(void *key1, void *key2))
  81 {
  82    struct util_hash_table *ht;
  83
  84    ht = MALLOC_STRUCT(util_hash_table);
  85    if(!ht)
  86       return NULL;
  87
  88    ht->cso = cso_hash_create();
  89    if(!ht->cso) {
  90       FREE(ht);
  91       return NULL;
  92    }
  93
  94    ht->hash = hash;
  95    ht->compare = compare;
  96
  97    return ht;
  98 }
  99
 100
 101 static INLINE struct cso_hash_iter
 102 util_hash_table_find_iter(struct util_hash_table *ht,
 103                           void *key,
 104                           unsigned key_hash)
 105 {
 106    struct cso_hash_iter iter;
 107    struct util_hash_table_item *item;
 108
 109    iter = cso_hash_find(ht->cso, key_hash);
 110    while (!cso_hash_iter_is_null(iter)) {
 111       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 112       if (!ht->compare(item->key, key))
 113          break;
 114       iter = cso_hash_iter_next(iter);
 115    }
 116
 117    return iter;
 118 }
 119
 120
 121 static INLINE struct util_hash_table_item *
 122 util_hash_table_find_item(struct util_hash_table *ht,
 123                           void *key,
 124                           unsigned key_hash)
 125 {
 126    struct cso_hash_iter iter;
 127    struct util_hash_table_item *item;
 128
 129    iter = cso_hash_find(ht->cso, key_hash);
 130    while (!cso_hash_iter_is_null(iter)) {
 131       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 132       if (!ht->compare(item->key, key))
 133          return item;
 134       iter = cso_hash_iter_next(iter);
 135    }
 136
 137    return NULL;
 138 }
 139
 140
 141 enum pipe_error
 142 util_hash_table_set(struct util_hash_table *ht,
 143                     void *key,
 144                     void *value)
 145 {
 146    unsigned key_hash;
 147    struct util_hash_table_item *item;
 148    struct cso_hash_iter iter;
 149
 150    assert(ht);
 151    if (!ht)
 152       return PIPE_ERROR_BAD_INPUT;
 153
 154    key_hash = ht->hash(key);
 155
 156    item = util_hash_table_find_item(ht, key, key_hash);
 157    if(item) {
 158       /* TODO: key/value destruction? */
 159       item->value = value;
 160       return PIPE_OK;
 161    }
 162
 163    item = MALLOC_STRUCT(util_hash_table_item);
 164    if(!item)
 165       return PIPE_ERROR_OUT_OF_MEMORY;
 166
 167    item->key = key;
 168    item->value = value;
 169
 170    iter = cso_hash_insert(ht->cso, key_hash, item);
 171    if(cso_hash_iter_is_null(iter)) {
 172       FREE(item);
 173       return PIPE_ERROR_OUT_OF_MEMORY;
 174    }
 175
 176    return PIPE_OK;
 177 }
 178
 179
 180 void *
 181 util_hash_table_get(struct util_hash_table *ht,
 182                     void *key)
 183 {
 184    unsigned key_hash;
 185    struct util_hash_table_item *item;
 186
 187    assert(ht);
 188    if (!ht)
 189       return NULL;
 190
 191    key_hash = ht->hash(key);
 192
 193    item = util_hash_table_find_item(ht, key, key_hash);
 194    if(!item)
 195       return NULL;
 196
 197    return item->value;
 198 }
 199
 200
 201 void
 202 util_hash_table_remove(struct util_hash_table *ht,
 203                        void *key)
 204 {
 205    unsigned key_hash;
 206    struct cso_hash_iter iter;
 207    struct util_hash_table_item *item;
 208
 209    assert(ht);
 210    if (!ht)
 211       return;
 212
 213    key_hash = ht->hash(key);
 214
 215    iter = util_hash_table_find_iter(ht, key, key_hash);
 216    if(cso_hash_iter_is_null(iter))
 217       return;
 218
 219    item = util_hash_table_item(iter);
 220    assert(item);
 221    FREE(item);
 222
 223    cso_hash_erase(ht->cso, iter);
 224 }
 225
 226
 227 void
 228 util_hash_table_clear(struct util_hash_table *ht)
 229 {
 230    struct cso_hash_iter iter;
 231    struct util_hash_table_item *item;
 232
 233    assert(ht);
 234    if (!ht)
 235       return;
 236
 237    iter = cso_hash_first_node(ht->cso);
 238    while (!cso_hash_iter_is_null(iter)) {
 239       item = (struct util_hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
 240       FREE(item);
 241       iter = cso_hash_first_node(ht->cso);
 242    }
 243 }
 244
 245
 246 enum pipe_error
 247 util_hash_table_foreach(struct util_hash_table *ht,
 248                      enum pipe_error (*callback)
 249                         (void *key, void *value, void *data),
 250                      void *data)
 251 {
 252    struct cso_hash_iter iter;
 253    struct util_hash_table_item *item;
 254    enum pipe_error result;
 255
 256    assert(ht);
 257    if (!ht)
 258       return PIPE_ERROR_BAD_INPUT;
 259
 260    iter = cso_hash_first_node(ht->cso);
 261    while (!cso_hash_iter_is_null(iter)) {
 262       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 263       result = callback(item->key, item->value, data);
 264       if(result != PIPE_OK)
 265          return result;
 266       iter = cso_hash_iter_next(iter);
 267    }
 268
 269    return PIPE_OK;
 270 }
 271
 272
 273 void
 274 util_hash_table_destroy(struct util_hash_table *ht)
 275 {
 276    struct cso_hash_iter iter;
 277    struct util_hash_table_item *item;
 278
 279    assert(ht);
 280    if (!ht)
 281       return;
 282
 283    iter = cso_hash_first_node(ht->cso);
 284    while (!cso_hash_iter_is_null(iter)) {
 285       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 286       FREE(item);
 287       iter = cso_hash_iter_next(iter);
 288    }
 289
 290    cso_hash_delete(ht->cso);
 291
 292    FREE(ht);
 293 }