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 void *
 112 hash_table_find(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->data;
 123        }
 124     }
 125
 126     return NULL;
 127 }
 128
 129
 130 void
 131 hash_table_insert(struct hash_table *ht, void *data, const void *key)
 132 {
 133     const unsigned hash_value = (*ht->hash)(key);
 134     const unsigned bucket = hash_value % ht->num_buckets;
 135     struct hash_node *node;
 136
 137     node = calloc(1, sizeof(*node));
 138
 139     node->data = data;
 140     node->key = key;
 141
 142     insert_at_head(& ht->buckets[bucket], & node->link);
 143 }
 144
 145 void
 146 hash_table_remove(struct hash_table *ht, const void *key)
 147 {
 148     const unsigned hash_value = (*ht->hash)(key);
 149     const unsigned bucket = hash_value % ht->num_buckets;
 150     struct node *node;
 151
 152     foreach(node, & ht->buckets[bucket]) {
 153        struct hash_node *hn = (struct hash_node *) node;
 154
 155        if ((*ht->compare)(hn->key, key) == 0) {
 156           remove_from_list(node);
 157           free(node);
 158           return;
 159        }
 160     }
 161 }
 162
 163 void
 164 hash_table_call_foreach(struct hash_table *ht,
 165                         void (*callback)(const void *key,
 166                                          void *data,
 167                                          void *closure),
 168                         void *closure)
 169 {
 170    int bucket;
 171
 172    for (bucket = 0; bucket < ht->num_buckets; bucket++) {
 173       struct node *node, *temp;
 174       foreach_s(node, temp, &ht->buckets[bucket]) {
 175          struct hash_node *hn = (struct hash_node *) node;
 176
 177          callback(hn->key, hn->data, closure);
 178       }
 179    }
 180 }
 181
 182 unsigned
 183 hash_table_string_hash(const void *key)
 184 {
 185     const char *str = (const char *) key;
 186     unsigned hash = 5381;
 187
 188
 189     while (*str != '\0') {
 190         hash = (hash * 33) + *str;
 191         str++;
 192     }
 193
 194     return hash;
 195 }
 196
 197
 198 unsigned
 199 hash_table_pointer_hash(const void *key)
 200 {
 201    return (unsigned)((uintptr_t) key / sizeof(void *));
 202 }
 203
 204
 205 int
 206 hash_table_pointer_compare(const void *key1, const void *key2)
 207 {
 208    return key1 == key2 ? 0 : 1;
 209 }