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    if (!cso_hash_init(&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 util_hash_table_find_iter(struct util_hash_table *ht,
 102                           void *key,
 103                           unsigned key_hash)
 104 {
 105    struct cso_hash_iter iter;
 106    struct util_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 util_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 util_hash_table_item *
 121 util_hash_table_find_item(struct util_hash_table *ht,
 122                           void *key,
 123                           unsigned key_hash)
 124 {
 125    struct cso_hash_iter iter;
 126    struct util_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 util_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 util_hash_table_set(struct util_hash_table *ht,
 142                     void *key,
 143                     void *value)
 144 {
 145    unsigned key_hash;
 146    struct util_hash_table_item *item;
 147    struct cso_hash_iter iter;
 148
 149    assert(ht);
 150    if (!ht)
 151       return PIPE_ERROR_BAD_INPUT;
 152
 153    key_hash = ht->hash(key);
 154
 155    item = util_hash_table_find_item(ht, key, key_hash);
 156    if (item) {
 157       /* TODO: key/value destruction? */
 158       item->value = value;
 159       return PIPE_OK;
 160    }
 161
 162    item = MALLOC_STRUCT(util_hash_table_item);
 163    if (!item)
 164       return PIPE_ERROR_OUT_OF_MEMORY;
 165
 166    item->key = key;
 167    item->value = value;
 168
 169    iter = cso_hash_insert(&ht->cso, key_hash, item);
 170    if(cso_hash_iter_is_null(iter)) {
 171       FREE(item);
 172       return PIPE_ERROR_OUT_OF_MEMORY;
 173    }
 174
 175    return PIPE_OK;
 176 }
 177
 178
 179 void *
 180 util_hash_table_get(struct util_hash_table *ht,
 181                     void *key)
 182 {
 183    unsigned key_hash;
 184    struct util_hash_table_item *item;
 185
 186    assert(ht);
 187    if (!ht)
 188       return NULL;
 189
 190    key_hash = ht->hash(key);
 191
 192    item = util_hash_table_find_item(ht, key, key_hash);
 193    if (!item)
 194       return NULL;
 195
 196    return item->value;
 197 }
 198
 199
 200 void
 201 util_hash_table_remove(struct util_hash_table *ht,
 202                        void *key)
 203 {
 204    unsigned key_hash;
 205    struct cso_hash_iter iter;
 206    struct util_hash_table_item *item;
 207
 208    assert(ht);
 209    if (!ht)
 210       return;
 211
 212    key_hash = ht->hash(key);
 213
 214    iter = util_hash_table_find_iter(ht, key, key_hash);
 215    if(cso_hash_iter_is_null(iter))
 216       return;
 217
 218    item = util_hash_table_item(iter);
 219    assert(item);
 220    FREE(item);
 221
 222    cso_hash_erase(&ht->cso, iter);
 223 }
 224
 225
 226 void
 227 util_hash_table_clear(struct util_hash_table *ht)
 228 {
 229    struct cso_hash_iter iter;
 230    struct util_hash_table_item *item;
 231
 232    assert(ht);
 233    if (!ht)
 234       return;
 235
 236    iter = cso_hash_first_node(&ht->cso);
 237    while (!cso_hash_iter_is_null(iter)) {
 238       item = (struct util_hash_table_item *)cso_hash_take(&ht->cso, cso_hash_iter_key(iter));
 239       FREE(item);
 240       iter = cso_hash_first_node(&ht->cso);
 241    }
 242 }
 243
 244
 245 enum pipe_error
 246 util_hash_table_foreach(struct util_hash_table *ht,
 247                      enum pipe_error (*callback)
 248                         (void *key, void *value, void *data),
 249                      void *data)
 250 {
 251    struct cso_hash_iter iter;
 252    struct util_hash_table_item *item;
 253    enum pipe_error result;
 254
 255    assert(ht);
 256    if (!ht)
 257       return PIPE_ERROR_BAD_INPUT;
 258
 259    iter = cso_hash_first_node(&ht->cso);
 260    while (!cso_hash_iter_is_null(iter)) {
 261       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 262       result = callback(item->key, item->value, data);
 263       if(result != PIPE_OK)
 264          return result;
 265       iter = cso_hash_iter_next(iter);
 266    }
 267
 268    return PIPE_OK;
 269 }
 270
 271
 272 static enum pipe_error
 273 util_hash_inc(UNUSED void *k, UNUSED void *v, void *d)
 274 {
 275    ++*(size_t *)d;
 276    return PIPE_OK;
 277 }
 278
 279
 280 size_t
 281 util_hash_table_count(struct util_hash_table *ht)
 282 {
 283         size_t count = 0;
 284         util_hash_table_foreach(ht, util_hash_inc, &count);
 285         return count;
 286 }
 287
 288
 289 void
 290 util_hash_table_destroy(struct util_hash_table *ht)
 291 {
 292    struct cso_hash_iter iter;
 293    struct util_hash_table_item *item;
 294
 295    assert(ht);
 296    if (!ht)
 297       return;
 298
 299    iter = cso_hash_first_node(&ht->cso);
 300    while (!cso_hash_iter_is_null(iter)) {
 301       item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
 302       FREE(item);
 303       iter = cso_hash_iter_next(iter);
 304    }
 305
 306    cso_hash_deinit(&ht->cso);
 307
 308    FREE(ht);
 309 }