src/mesa/program/prog_hash_table.c

   1 /*
   2  * Copyright © 2008 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 /**
  25  * \file hash_table.c
  26  * \brief Implementation of a generic, opaque hash table data type.
  27  *
  28  * \author Ian Romanick <ian.d.romanick@intel.com>
  29  */
  30
  31 #include "main/imports.h"
  32 #include "util/simple_list.h"
  33 #include "hash_table.h"
  34
  35 struct node {
  36    struct node *next;
  37    struct node *prev;
  38 };
  39
  40 struct hash_table {
  41     hash_func_t    hash;
  42     hash_compare_func_t  compare;
  43
  44     unsigned num_buckets;
  45     struct node buckets[1];
  46 };
  47
  48
  49 struct hash_node {
  50     struct node link;
  51     const void *key;
  52     void *data;
  53 };
  54
  55
  56 struct hash_table *
  57 hash_table_ctor(unsigned num_buckets, hash_func_t hash,
  58                 hash_compare_func_t compare)
  59 {
  60     struct hash_table *ht;
  61     unsigned i;
  62
  63
  64     if (num_buckets < 16) {
  65         num_buckets = 16;
  66     }
  67
  68     ht = malloc(sizeof(*ht) + ((num_buckets - 1)
  69                                      * sizeof(ht->buckets[0])));
  70     if (ht != NULL) {
  71         ht->hash = hash;
  72         ht->compare = compare;
  73         ht->num_buckets = num_buckets;
  74
  75         for (i = 0; i < num_buckets; i++) {
  76             make_empty_list(& ht->buckets[i]);
  77         }
  78     }
  79
  80     return ht;
  81 }
  82
  83
  84 void
  85 hash_table_dtor(struct hash_table *ht)
  86 {
  87    hash_table_clear(ht);
  88    free(ht);
  89 }
  90
  91
  92 void
  93 hash_table_clear(struct hash_table *ht)
  94 {
  95    struct node *node;
  96    struct node *temp;
  97    unsigned i;
  98
  99
 100    for (i = 0; i < ht->num_buckets; i++) {
 101       foreach_s(node, temp, & ht->buckets[i]) {
 102          remove_from_list(node);
 103          free(node);
 104       }
 105
 106       assert(is_empty_list(& ht->buckets[i]));
 107    }
 108 }
 109
 110
 111 static struct hash_node *
 112 get_node(struct hash_table *ht, const void *key)
 113 {
 114     const unsigned hash_value = (*ht->hash)(key);
 115     const unsigned bucket = hash_value % ht->num_buckets;
 116     struct node *node;
 117
 118     foreach(node, & ht->buckets[bucket]) {
 119        struct hash_node *hn = (struct hash_node *) node;
 120
 121        if ((*ht->compare)(hn->key, key) == 0) {
 122           return hn;
 123        }
 124     }
 125
 126     return NULL;
 127 }
 128
 129 void *
 130 hash_table_find(struct hash_table *ht, const void *key)
 131 {
 132    struct hash_node *hn = get_node(ht, key);
 133
 134    return (hn == NULL) ? NULL : hn->data;
 135 }
 136
 137 void
 138 hash_table_insert(struct hash_table *ht, void *data, const void *key)
 139 {
 140     const unsigned hash_value = (*ht->hash)(key);
 141     const unsigned bucket = hash_value % ht->num_buckets;
 142     struct hash_node *node;
 143
 144     node = calloc(1, sizeof(*node));
 145     if (node == NULL) {
 146        _mesa_error_no_memory(__func__);
 147        return;
 148     }
 149
 150     node->data = data;
 151     node->key = key;
 152
 153     insert_at_head(& ht->buckets[bucket], & node->link);
 154 }
 155
 156 bool
 157 hash_table_replace(struct hash_table *ht, void *data, const void *key)
 158 {
 159     const unsigned hash_value = (*ht->hash)(key);
 160     const unsigned bucket = hash_value % ht->num_buckets;
 161     struct node *node;
 162     struct hash_node *hn;
 163
 164     foreach(node, & ht->buckets[bucket]) {
 165        hn = (struct hash_node *) node;
 166
 167        if ((*ht->compare)(hn->key, key) == 0) {
 168           hn->data = data;
 169           return true;
 170        }
 171     }
 172
 173     hn = calloc(1, sizeof(*hn));
 174     if (hn == NULL) {
 175        _mesa_error_no_memory(__func__);
 176        return false;
 177     }
 178
 179     hn->data = data;
 180     hn->key = key;
 181
 182     insert_at_head(& ht->buckets[bucket], & hn->link);
 183     return false;
 184 }
 185
 186 void
 187 hash_table_remove(struct hash_table *ht, const void *key)
 188 {
 189    struct node *node = (struct node *) get_node(ht, key);
 190    if (node != NULL) {
 191       remove_from_list(node);
 192       free(node);
 193       return;
 194    }
 195 }
 196
 197 void
 198 hash_table_call_foreach(struct hash_table *ht,
 199                         void (*callback)(const void *key,
 200                                          void *data,
 201                                          void *closure),
 202                         void *closure)
 203 {
 204    unsigned bucket;
 205
 206    for (bucket = 0; bucket < ht->num_buckets; bucket++) {
 207       struct node *node, *temp;
 208       foreach_s(node, temp, &ht->buckets[bucket]) {
 209          struct hash_node *hn = (struct hash_node *) node;
 210
 211          callback(hn->key, hn->data, closure);
 212       }
 213    }
 214 }
 215
 216 unsigned
 217 hash_table_string_hash(const void *key)
 218 {
 219     const char *str = (const char *) key;
 220     unsigned hash = 5381;
 221
 222
 223     while (*str != '\0') {
 224         hash = (hash * 33) + *str;
 225         str++;
 226     }
 227
 228     return hash;
 229 }
 230
 231
 232 unsigned
 233 hash_table_pointer_hash(const void *key)
 234 {
 235    return (unsigned)((uintptr_t) key / sizeof(void *));
 236 }
 237
 238
 239 int
 240 hash_table_pointer_compare(const void *key1, const void *key2)
 241 {
 242    return key1 == key2 ? 0 : 1;
 243 }