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 struct hash_table *
  71 hash_table_create(unsigned (*hash)(void *key),
  72                   int (*compare)(void *key1, void *key2))
  73 {
  74    struct hash_table *ht;
  75
  76    ht = MALLOC_STRUCT(hash_table);
  77    if(!ht)
  78       return NULL;
  79
  80    ht->cso = cso_hash_create();
  81    if(!ht->cso) {
  82       FREE(ht);
  83       return NULL;
  84    }
  85
  86    ht->hash = hash;
  87    ht->compare = compare;
  88
  89    return ht;
  90 }
  91
  92
  93 static struct hash_table_item *
  94 hash_table_find_item(struct hash_table *ht,
  95                      void *key,
  96                      unsigned key_hash)
  97 {
  98    struct cso_hash_iter iter;
  99    struct hash_table_item *item;
 100
 101    iter = cso_hash_find(ht->cso, key_hash);
 102    while (!cso_hash_iter_is_null(iter)) {
 103       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 104       if (!ht->compare(item->key, key))
 105          return item;
 106       iter = cso_hash_iter_next(iter);
 107    }
 108
 109    return NULL;
 110 }
 111
 112
 113 enum pipe_error
 114 hash_table_set(struct hash_table *ht,
 115                void *key,
 116                void *value)
 117 {
 118    unsigned key_hash;
 119    struct hash_table_item *item;
 120
 121    assert(ht);
 122
 123    key_hash = ht->hash(key);
 124
 125    item = hash_table_find_item(ht, key, key_hash);
 126    if(item) {
 127       /* TODO: key/value destruction? */
 128       item->value = value;
 129       return PIPE_OK;
 130    }
 131
 132    item = MALLOC_STRUCT(hash_table_item);
 133    if(!item)
 134       return PIPE_ERROR_OUT_OF_MEMORY;
 135
 136    item->key = key;
 137    item->value = value;
 138
 139    cso_hash_insert(ht->cso, key_hash, item);
 140    /* FIXME: there is no OOM propagation in cso_hash */
 141    if(0) {
 142       FREE(item);
 143       return PIPE_ERROR_OUT_OF_MEMORY;
 144    }
 145
 146    return PIPE_OK;
 147 }
 148
 149
 150 void *
 151 hash_table_get(struct hash_table *ht,
 152                void *key)
 153 {
 154    unsigned key_hash;
 155    struct hash_table_item *item;
 156
 157    assert(ht);
 158
 159    key_hash = ht->hash(key);
 160
 161    item = hash_table_find_item(ht, key, key_hash);
 162    if(!item)
 163       return NULL;
 164
 165    return item->value;
 166 }
 167
 168
 169 void
 170 hash_table_remove(struct hash_table *ht,
 171                   void *key)
 172 {
 173    unsigned key_hash;
 174    struct hash_table_item *item;
 175
 176    assert(ht);
 177
 178    key_hash = ht->hash(key);
 179
 180    item = hash_table_find_item(ht, key, key_hash);
 181    if(!item)
 182       return;
 183
 184    /* FIXME: cso_hash_take takes the first element of the collision list
 185     * indiscriminately, so we can not take the item down. */
 186    item->value = NULL;
 187 }
 188
 189
 190 enum pipe_error
 191 hash_table_foreach(struct hash_table *ht,
 192                    enum pipe_error (*callback)(void *key, void *value, void *data),
 193                    void *data)
 194 {
 195    struct cso_hash_iter iter;
 196    struct hash_table_item *item;
 197    enum pipe_error result;
 198
 199    iter = cso_hash_first_node(ht->cso);
 200    while (!cso_hash_iter_is_null(iter)) {
 201       item = (struct hash_table_item *)cso_hash_iter_data(iter);
 202       result = callback(item->key, item->value, data);
 203       if(result != PIPE_OK)
 204          return result;
 205       iter = cso_hash_iter_next(iter);
 206    }
 207
 208    return PIPE_OK;
 209 }
 210
 211
 212 void
 213 hash_table_destroy(struct hash_table *ht)
 214 {
 215    assert(ht);
 216
 217    cso_hash_delete(ht->cso);
 218
 219    FREE(ht);
 220 }