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