reactos/dll/opengl/mesa/src/mesa/program/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 "main/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
 146     node->data = data;
 147     node->key = key;
 148
 149     insert_at_head(& ht->buckets[bucket], & node->link);
 150 }
 151
 152 void
 153 hash_table_replace(struct hash_table *ht, void *data, const void *key)
 154 {
 155     const unsigned hash_value = (*ht->hash)(key);
 156     const unsigned bucket = hash_value % ht->num_buckets;
 157     struct node *node;
 158     struct hash_node *hn;
 159
 160     foreach(node, & ht->buckets[bucket]) {
 161        hn = (struct hash_node *) node;
 162
 163        if ((*ht->compare)(hn->key, key) == 0) {
 164           hn->data = data;
 165           return;
 166        }
 167     }
 168
 169     hn = calloc(1, sizeof(*hn));
 170
 171     hn->data = data;
 172     hn->key = key;
 173
 174     insert_at_head(& ht->buckets[bucket], & hn->link);
 175 }
 176
 177 void
 178 hash_table_remove(struct hash_table *ht, const void *key)
 179 {
 180    struct node *node = (struct node *) get_node(ht, key);
 181    if (node != NULL) {
 182       remove_from_list(node);
 183       free(node);
 184       return;
 185    }
 186 }
 187
 188 void
 189 hash_table_call_foreach(struct hash_table *ht,
 190                         void (*callback)(const void *key,
 191                                          void *data,
 192                                          void *closure),
 193                         void *closure)
 194 {
 195    int bucket;
 196
 197    for (bucket = 0; bucket < ht->num_buckets; bucket++) {
 198       struct node *node, *temp;
 199       foreach_s(node, temp, &ht->buckets[bucket]) {
 200          struct hash_node *hn = (struct hash_node *) node;
 201
 202          callback(hn->key, hn->data, closure);
 203       }
 204    }
 205 }
 206
 207 unsigned
 208 hash_table_string_hash(const void *key)
 209 {
 210     const char *str = (const char *) key;
 211     unsigned hash = 5381;
 212
 213
 214     while (*str != '\0') {
 215         hash = (hash * 33) + *str;
 216         str++;
 217     }
 218
 219     return hash;
 220 }
 221
 222
 223 unsigned
 224 hash_table_pointer_hash(const void *key)
 225 {
 226    return (unsigned)((uintptr_t) key / sizeof(void *));
 227 }
 228
 229
 230 int
 231 hash_table_pointer_compare(const void *key1, const void *key2)
 232 {
 233    return key1 == key2 ? 0 : 1;
 234 }