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 "pipe/p_debug.h"
  43 #include "pipe/p_util.h"
  44
  45 #include "cso_cache/cso_hash.h"
  46 #include "u_hash_table.h"
  47
  48
  49 struct hash_table
  50 {
  51    struct cso_hash *cso;
  52
  53    /** Hash function */
  54    unsigned (*hash)(void *key);
  55
  56    /** Compare two keys */
  57    int (*compare)(void *key1, void *key2);
  58
  59    /* TODO: key, value destructors? */
  60 };
  61
  62
  63 struct hash_table_item
  64 {
  65    void *key;
  66    void *value;
  67 };
  68
  69
  70 static INLINE struct hash_table_item *
  71 hash_table_item(struct cso_hash_iter iter)
  72 {
  73    return (struct hash_table_item *)cso_hash_iter_data(iter);
  74 }
  75
  76
  77 struct hash_table *
  78 hash_table_create(unsigned (*hash)(void *key),
  79                   int (*compare)(void *key1, void *key2))
  80 {
  81    struct hash_table *ht;
  82
  83    ht = MALLOC_STRUCT(hash_table);
  84    if(!ht)
  85       return NULL;
  86
  87    ht->cso = cso_hash_create();
  88    if(!ht->cso) {
  89       FREE(ht);
  90       return NULL;
  91    }
  92
  93    ht->hash = hash;
  94    ht->compare = compare;
  95
  96    return ht;
  97 }
  98
  99
 100 static INLINE struct cso_hash_iter
 101 hash_table_find_iter(struct hash_table *ht,
 102                      void *key,
 103                      unsigned key_hash)
 104 {
 105    struct cso_hash_iter iter;
 106    struct hash_table_item *item;
 107
 108    iter = cso_hash_find(ht->cso, key_hash);
 109    while (!cso_hash_iter_is_null(iter)) {
 110       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 111       if (!ht->compare(item->key, key))
 112          break;
 113       iter = cso_hash_iter_next(iter);
 114    }
 115
 116    return iter;
 117 }
 118
 119
 120 static INLINE struct hash_table_item *
 121 hash_table_find_item(struct hash_table *ht,
 122                      void *key,
 123                      unsigned key_hash)
 124 {
 125    struct cso_hash_iter iter;
 126    struct hash_table_item *item;
 127
 128    iter = cso_hash_find(ht->cso, key_hash);
 129    while (!cso_hash_iter_is_null(iter)) {
 130       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 131       if (!ht->compare(item->key, key))
 132          return item;
 133       iter = cso_hash_iter_next(iter);
 134    }
 135
 136    return NULL;
 137 }
 138
 139
 140 enum pipe_error
 141 hash_table_set(struct hash_table *ht,
 142                void *key,
 143                void *value)
 144 {
 145    unsigned key_hash;
 146    struct hash_table_item *item;
 147    struct cso_hash_iter iter;
 148
 149    assert(ht);
 150
 151    key_hash = ht->hash(key);
 152
 153    item = hash_table_find_item(ht, key, key_hash);
 154    if(item) {
 155       /* TODO: key/value destruction? */
 156       item->value = value;
 157       return PIPE_OK;
 158    }
 159
 160    item = MALLOC_STRUCT(hash_table_item);
 161    if(!item)
 162       return PIPE_ERROR_OUT_OF_MEMORY;
 163
 164    item->key = key;
 165    item->value = value;
 166
 167    iter = cso_hash_insert(ht->cso, key_hash, item);
 168    if(cso_hash_iter_is_null(iter)) {
 169       FREE(item);
 170       return PIPE_ERROR_OUT_OF_MEMORY;
 171    }
 172
 173    return PIPE_OK;
 174 }
 175
 176
 177 void *
 178 hash_table_get(struct hash_table *ht,
 179                void *key)
 180 {
 181    unsigned key_hash;
 182    struct hash_table_item *item;
 183
 184    assert(ht);
 185
 186    key_hash = ht->hash(key);
 187
 188    item = hash_table_find_item(ht, key, key_hash);
 189    if(!item)
 190       return NULL;
 191
 192    return item->value;
 193 }
 194
 195
 196 void
 197 hash_table_remove(struct hash_table *ht,
 198                   void *key)
 199 {
 200    unsigned key_hash;
 201    struct cso_hash_iter iter;
 202    struct hash_table_item *item;
 203
 204    assert(ht);
 205
 206    key_hash = ht->hash(key);
 207
 208    iter = hash_table_find_iter(ht, key, key_hash);
 209    if(cso_hash_iter_is_null(iter))
 210       return;
 211
 212    item = hash_table_item(iter);
 213    assert(item);
 214    FREE(item);
 215
 216    cso_hash_erase(ht->cso, iter);
 217 }
 218
 219
 220 void
 221 hash_table_clear(struct hash_table *ht)
 222 {
 223    struct cso_hash_iter iter;
 224    struct hash_table_item *item;
 225
 226    assert(ht);
 227
 228    iter = cso_hash_first_node(ht->cso);
 229    while (!cso_hash_iter_is_null(iter)) {
 230       item = (struct hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
 231       FREE(item);
 232       iter = cso_hash_first_node(ht->cso);
 233    }
 234 }
 235
 236
 237 enum pipe_error
 238 hash_table_foreach(struct hash_table *ht,
 239                    enum pipe_error (*callback)(void *key, void *value, void *data),
 240                    void *data)
 241 {
 242    struct cso_hash_iter iter;
 243    struct hash_table_item *item;
 244    enum pipe_error result;
 245
 246    assert(ht);
 247
 248    iter = cso_hash_first_node(ht->cso);
 249    while (!cso_hash_iter_is_null(iter)) {
 250       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 251       result = callback(item->key, item->value, data);
 252       if(result != PIPE_OK)
 253          return result;
 254       iter = cso_hash_iter_next(iter);
 255    }
 256
 257    return PIPE_OK;
 258 }
 259
 260
 261 void
 262 hash_table_destroy(struct hash_table *ht)
 263 {
 264    struct cso_hash_iter iter;
 265    struct hash_table_item *item;
 266
 267    assert(ht);
 268
 269    iter = cso_hash_first_node(ht->cso);
 270    while (!cso_hash_iter_is_null(iter)) {
 271       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 272       FREE(item);
 273       iter = cso_hash_iter_next(iter);
 274    }
 275
 276    cso_hash_delete(ht->cso);
 277
 278    FREE(ht);
 279 }