src/gallium/auxiliary/util/u_hash_table.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 VMware, Inc.
   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 VMWARE 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 <jfonseca@vmware.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    cso_hash_init(&ht->cso);
  89
  90    ht->hash = hash;
  91    ht->compare = compare;
  92
  93    return ht;
  94 }
  95
  96
  97 static inline struct cso_hash_iter
  98 util_hash_table_find_iter(struct util_hash_table *ht,
  99                           void *key,
 100                           unsigned key_hash)
 101 {
 102    struct cso_hash_iter iter;
 103    struct util_hash_table_item *item;
 104
 105    iter = cso_hash_find(&ht->cso, key_hash);
 106    while (!cso_hash_iter_is_null(iter)) {
 107       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 108       if (!ht->compare(item->key, key))
 109          break;
 110       iter = cso_hash_iter_next(iter);
 111    }
 112
 113    return iter;
 114 }
 115
 116
 117 static inline struct util_hash_table_item *
 118 util_hash_table_find_item(struct util_hash_table *ht,
 119                           void *key,
 120                           unsigned key_hash)
 121 {
 122    struct cso_hash_iter iter;
 123    struct util_hash_table_item *item;
 124
 125    iter = cso_hash_find(&ht->cso, key_hash);
 126    while (!cso_hash_iter_is_null(iter)) {
 127       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 128       if (!ht->compare(item->key, key))
 129          return item;
 130       iter = cso_hash_iter_next(iter);
 131    }
 132
 133    return NULL;
 134 }
 135
 136
 137 enum pipe_error
 138 util_hash_table_set(struct util_hash_table *ht,
 139                     void *key,
 140                     void *value)
 141 {
 142    unsigned key_hash;
 143    struct util_hash_table_item *item;
 144    struct cso_hash_iter iter;
 145
 146    assert(ht);
 147    if (!ht)
 148       return PIPE_ERROR_BAD_INPUT;
 149
 150    key_hash = ht->hash(key);
 151
 152    item = util_hash_table_find_item(ht, key, key_hash);
 153    if (item) {
 154       /* TODO: key/value destruction? */
 155       item->value = value;
 156       return PIPE_OK;
 157    }
 158
 159    item = MALLOC_STRUCT(util_hash_table_item);
 160    if (!item)
 161       return PIPE_ERROR_OUT_OF_MEMORY;
 162
 163    item->key = key;
 164    item->value = value;
 165
 166    iter = cso_hash_insert(&ht->cso, key_hash, item);
 167    if(cso_hash_iter_is_null(iter)) {
 168       FREE(item);
 169       return PIPE_ERROR_OUT_OF_MEMORY;
 170    }
 171
 172    return PIPE_OK;
 173 }
 174
 175
 176 void *
 177 util_hash_table_get(struct util_hash_table *ht,
 178                     void *key)
 179 {
 180    unsigned key_hash;
 181    struct util_hash_table_item *item;
 182
 183    assert(ht);
 184    if (!ht)
 185       return NULL;
 186
 187    key_hash = ht->hash(key);
 188
 189    item = util_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 util_hash_table_remove(struct util_hash_table *ht,
 199                        void *key)
 200 {
 201    unsigned key_hash;
 202    struct cso_hash_iter iter;
 203    struct util_hash_table_item *item;
 204
 205    assert(ht);
 206    if (!ht)
 207       return;
 208
 209    key_hash = ht->hash(key);
 210
 211    iter = util_hash_table_find_iter(ht, key, key_hash);
 212    if(cso_hash_iter_is_null(iter))
 213       return;
 214
 215    item = util_hash_table_item(iter);
 216    assert(item);
 217    FREE(item);
 218
 219    cso_hash_erase(&ht->cso, iter);
 220 }
 221
 222
 223 void
 224 util_hash_table_clear(struct util_hash_table *ht)
 225 {
 226    struct cso_hash_iter iter;
 227    struct util_hash_table_item *item;
 228
 229    assert(ht);
 230    if (!ht)
 231       return;
 232
 233    iter = cso_hash_first_node(&ht->cso);
 234    while (!cso_hash_iter_is_null(iter)) {
 235       item = (struct util_hash_table_item *)cso_hash_take(&ht->cso, cso_hash_iter_key(iter));
 236       FREE(item);
 237       iter = cso_hash_first_node(&ht->cso);
 238    }
 239 }
 240
 241
 242 enum pipe_error
 243 util_hash_table_foreach(struct util_hash_table *ht,
 244                      enum pipe_error (*callback)
 245                         (void *key, void *value, void *data),
 246                      void *data)
 247 {
 248    struct cso_hash_iter iter;
 249    struct util_hash_table_item *item;
 250    enum pipe_error result;
 251
 252    assert(ht);
 253    if (!ht)
 254       return PIPE_ERROR_BAD_INPUT;
 255
 256    iter = cso_hash_first_node(&ht->cso);
 257    while (!cso_hash_iter_is_null(iter)) {
 258       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 259       result = callback(item->key, item->value, data);
 260       if(result != PIPE_OK)
 261          return result;
 262       iter = cso_hash_iter_next(iter);
 263    }
 264
 265    return PIPE_OK;
 266 }
 267
 268
 269 static enum pipe_error
 270 util_hash_inc(UNUSED void *k, UNUSED void *v, void *d)
 271 {
 272    ++*(size_t *)d;
 273    return PIPE_OK;
 274 }
 275
 276
 277 size_t
 278 util_hash_table_count(struct util_hash_table *ht)
 279 {
 280         size_t count = 0;
 281         util_hash_table_foreach(ht, util_hash_inc, &count);
 282         return count;
 283 }
 284
 285
 286 void
 287 util_hash_table_destroy(struct util_hash_table *ht)
 288 {
 289    struct cso_hash_iter iter;
 290    struct util_hash_table_item *item;
 291
 292    assert(ht);
 293    if (!ht)
 294       return;
 295
 296    iter = cso_hash_first_node(&ht->cso);
 297    while (!cso_hash_iter_is_null(iter)) {
 298       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 299       FREE(item);
 300       iter = cso_hash_iter_next(iter);
 301    }
 302
 303    cso_hash_deinit(&ht->cso);
 304
 305    FREE(ht);
 306 }