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
  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 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 hash_table_item
  65 {
  66    void *key;
  67    void *value;
  68 };
  69
  70
  71 static INLINE struct hash_table_item *
  72 hash_table_item(struct cso_hash_iter iter)
  73 {
  74    return (struct hash_table_item *)cso_hash_iter_data(iter);
  75 }
  76
  77
  78 struct hash_table *
  79 hash_table_create(unsigned (*hash)(void *key),
  80                   int (*compare)(void *key1, void *key2))
  81 {
  82    struct hash_table *ht;
  83
  84    ht = MALLOC_STRUCT(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 hash_table_find_iter(struct hash_table *ht,
 103                      void *key,
 104                      unsigned key_hash)
 105 {
 106    struct cso_hash_iter iter;
 107    struct 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 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 hash_table_item *
 122 hash_table_find_item(struct hash_table *ht,
 123                      void *key,
 124                      unsigned key_hash)
 125 {
 126    struct cso_hash_iter iter;
 127    struct 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 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 hash_table_set(struct hash_table *ht,
 143                void *key,
 144                void *value)
 145 {
 146    unsigned key_hash;
 147    struct hash_table_item *item;
 148    struct cso_hash_iter iter;
 149
 150    assert(ht);
 151
 152    key_hash = ht->hash(key);
 153
 154    item = hash_table_find_item(ht, key, key_hash);
 155    if(item) {
 156       /* TODO: key/value destruction? */
 157       item->value = value;
 158       return PIPE_OK;
 159    }
 160
 161    item = MALLOC_STRUCT(hash_table_item);
 162    if(!item)
 163       return PIPE_ERROR_OUT_OF_MEMORY;
 164
 165    item->key = key;
 166    item->value = value;
 167
 168    iter = cso_hash_insert(ht->cso, key_hash, item);
 169    if(cso_hash_iter_is_null(iter)) {
 170       FREE(item);
 171       return PIPE_ERROR_OUT_OF_MEMORY;
 172    }
 173
 174    return PIPE_OK;
 175 }
 176
 177
 178 void *
 179 hash_table_get(struct hash_table *ht,
 180                void *key)
 181 {
 182    unsigned key_hash;
 183    struct hash_table_item *item;
 184
 185    assert(ht);
 186
 187    key_hash = ht->hash(key);
 188
 189    item = hash_table_find_item(ht, key, key_hash);
 190    if(!item)
 191       return NULL;
 192
 193    return item->value;
 194 }
 195
 196
 197 void
 198 hash_table_remove(struct hash_table *ht,
 199                   void *key)
 200 {
 201    unsigned key_hash;
 202    struct cso_hash_iter iter;
 203    struct hash_table_item *item;
 204
 205    assert(ht);
 206
 207    key_hash = ht->hash(key);
 208
 209    iter = hash_table_find_iter(ht, key, key_hash);
 210    if(cso_hash_iter_is_null(iter))
 211       return;
 212
 213    item = hash_table_item(iter);
 214    assert(item);
 215    FREE(item);
 216
 217    cso_hash_erase(ht->cso, iter);
 218 }
 219
 220
 221 void
 222 hash_table_clear(struct hash_table *ht)
 223 {
 224    struct cso_hash_iter iter;
 225    struct hash_table_item *item;
 226
 227    assert(ht);
 228
 229    iter = cso_hash_first_node(ht->cso);
 230    while (!cso_hash_iter_is_null(iter)) {
 231       item = (struct hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
 232       FREE(item);
 233       iter = cso_hash_first_node(ht->cso);
 234    }
 235 }
 236
 237
 238 enum pipe_error
 239 hash_table_foreach(struct hash_table *ht,
 240                    enum pipe_error (*callback)(void *key, void *value, void *data),
 241                    void *data)
 242 {
 243    struct cso_hash_iter iter;
 244    struct hash_table_item *item;
 245    enum pipe_error result;
 246
 247    assert(ht);
 248
 249    iter = cso_hash_first_node(ht->cso);
 250    while (!cso_hash_iter_is_null(iter)) {
 251       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 252       result = callback(item->key, item->value, data);
 253       if(result != PIPE_OK)
 254          return result;
 255       iter = cso_hash_iter_next(iter);
 256    }
 257
 258    return PIPE_OK;
 259 }
 260
 261
 262 void
 263 hash_table_destroy(struct hash_table *ht)
 264 {
 265    struct cso_hash_iter iter;
 266    struct hash_table_item *item;
 267
 268    assert(ht);
 269
 270    iter = cso_hash_first_node(ht->cso);
 271    while (!cso_hash_iter_is_null(iter)) {
 272       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 273       FREE(item);
 274       iter = cso_hash_iter_next(iter);
 275    }
 276
 277    cso_hash_delete(ht->cso);
 278
 279    FREE(ht);
 280 }