amdgpu/util_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 util_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 #ifdef HAVE_CONFIG_H
  42 #include "config.h"
  43 #endif
  44
  45 #include "util_hash_table.h"
  46 #include "util_hash.h"
  47
  48 #include <stdlib.h>
  49 #include <assert.h>
  50
  51 struct util_hash_table
  52 {
  53         struct util_hash *head;
  54
  55         /** Hash function */
  56         unsigned (*make_hash)(void *key);
  57
  58         /** Compare two keys */
  59         int (*compare)(void *key1, void *key2);
  60 };
  61
  62 struct util_hash_table_item
  63 {
  64         void *key;
  65         void *value;
  66 };
  67
  68
  69 static struct util_hash_table_item *
  70 util_hash_table_item(struct util_hash_iter iter)
  71 {
  72         return (struct util_hash_table_item *)util_hash_iter_data(iter);
  73 }
  74
  75 drm_private struct util_hash_table *
  76 util_hash_table_create(unsigned (*hash)(void *key),
  77                        int (*compare)(void *key1, void *key2))
  78 {
  79         struct util_hash_table *ht;
  80
  81         ht = malloc(sizeof(struct util_hash_table));
  82         if(!ht)
  83                 return NULL;
  84
  85         ht->head = util_hash_create();
  86         if(!ht->head) {
  87                 free(ht);
  88                 return NULL;
  89         }
  90
  91         ht->make_hash = hash;
  92         ht->compare = compare;
  93
  94         return ht;
  95 }
  96
  97 static struct util_hash_iter
  98 util_hash_table_find_iter(struct util_hash_table *ht,
  99                           void *key, unsigned key_hash)
 100 {
 101         struct util_hash_iter iter;
 102         struct util_hash_table_item *item;
 103
 104         iter = util_hash_find(ht->head, key_hash);
 105         while (!util_hash_iter_is_null(iter)) {
 106                 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
 107                 if (!ht->compare(item->key, key))
 108                         break;
 109                 iter = util_hash_iter_next(iter);
 110         }
 111
 112         return iter;
 113 }
 114
 115 static struct util_hash_table_item *
 116 util_hash_table_find_item(struct util_hash_table *ht,
 117                           void *key, unsigned key_hash)
 118 {
 119         struct util_hash_iter iter;
 120         struct util_hash_table_item *item;
 121
 122         iter = util_hash_find(ht->head, key_hash);
 123         while (!util_hash_iter_is_null(iter)) {
 124                 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
 125                 if (!ht->compare(item->key, key))
 126                         return item;
 127                 iter = util_hash_iter_next(iter);
 128         }
 129
 130         return NULL;
 131 }
 132
 133 drm_private void
 134 util_hash_table_set(struct util_hash_table *ht, void *key, void *value)
 135 {
 136         unsigned key_hash;
 137         struct util_hash_table_item *item;
 138         struct util_hash_iter iter;
 139
 140         assert(ht);
 141         if (!ht)
 142                 return;
 143
 144         key_hash = ht->make_hash(key);
 145
 146         item = util_hash_table_find_item(ht, key, key_hash);
 147         if(item) {
 148                 /* TODO: key/value destruction? */
 149                 item->value = value;
 150                 return;
 151         }
 152
 153         item = malloc(sizeof(struct util_hash_table_item));
 154         if(!item)
 155                 return;
 156
 157         item->key = key;
 158         item->value = value;
 159
 160         iter = util_hash_insert(ht->head, key_hash, item);
 161         if(util_hash_iter_is_null(iter)) {
 162                 free(item);
 163                 return;
 164         }
 165 }
 166
 167 drm_private void *util_hash_table_get(struct util_hash_table *ht, void *key)
 168 {
 169         unsigned key_hash;
 170         struct util_hash_table_item *item;
 171
 172         assert(ht);
 173         if (!ht)
 174                 return NULL;
 175
 176         key_hash = ht->make_hash(key);
 177
 178         item = util_hash_table_find_item(ht, key, key_hash);
 179         if(!item)
 180                 return NULL;
 181
 182         return item->value;
 183 }
 184
 185 drm_private void util_hash_table_remove(struct util_hash_table *ht, void *key)
 186 {
 187         unsigned key_hash;
 188         struct util_hash_iter iter;
 189         struct util_hash_table_item *item;
 190
 191         assert(ht);
 192         if (!ht)
 193                 return;
 194
 195         key_hash = ht->make_hash(key);
 196
 197         iter = util_hash_table_find_iter(ht, key, key_hash);
 198         if(util_hash_iter_is_null(iter))
 199                 return;
 200
 201         item = util_hash_table_item(iter);
 202         assert(item);
 203         free(item);
 204
 205         util_hash_erase(ht->head, iter);
 206 }
 207
 208 drm_private void util_hash_table_clear(struct util_hash_table *ht)
 209 {
 210         struct util_hash_iter iter;
 211         struct util_hash_table_item *item;
 212
 213         assert(ht);
 214         if (!ht)
 215                 return;
 216
 217         iter = util_hash_first_node(ht->head);
 218         while (!util_hash_iter_is_null(iter)) {
 219                 item = (struct util_hash_table_item *)util_hash_take(ht->head, util_hash_iter_key(iter));
 220                 free(item);
 221                 iter = util_hash_first_node(ht->head);
 222         }
 223 }
 224
 225 drm_private void util_hash_table_foreach(struct util_hash_table *ht,
 226                         void (*callback)(void *key, void *value, void *data),
 227                         void *data)
 228 {
 229         struct util_hash_iter iter;
 230         struct util_hash_table_item *item;
 231
 232         assert(ht);
 233         if (!ht)
 234                 return;
 235
 236         iter = util_hash_first_node(ht->head);
 237         while (!util_hash_iter_is_null(iter)) {
 238                 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
 239                 callback(item->key, item->value, data);
 240                 iter = util_hash_iter_next(iter);
 241         }
 242 }
 243
 244 drm_private void util_hash_table_destroy(struct util_hash_table *ht)
 245 {
 246         struct util_hash_iter iter;
 247         struct util_hash_table_item *item;
 248
 249         assert(ht);
 250         if (!ht)
 251                 return;
 252
 253         iter = util_hash_first_node(ht->head);
 254         while (!util_hash_iter_is_null(iter)) {
 255                 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
 256                 free(item);
 257                 iter = util_hash_iter_next(iter);
 258         }
 259
 260         util_hash_delete(ht->head);
 261         free(ht);
 262 }