Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  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. unsigned
  164. hash_table_string_hash(const void *key)
  165. {
  166.     const char *str = (const char *) key;
  167.     unsigned hash = 5381;
  168.  
  169.  
  170.     while (*str != '\0') {
  171.         hash = (hash * 33) + *str;
  172.         str++;
  173.     }
  174.  
  175.     return hash;
  176. }
  177.  
  178.  
  179. unsigned
  180. hash_table_pointer_hash(const void *key)
  181. {
  182.    return (unsigned)((uintptr_t) key / sizeof(void *));
  183. }
  184.  
  185.  
  186. int
  187. hash_table_pointer_compare(const void *key1, const void *key2)
  188. {
  189.    return key1 == key2 ? 0 : 1;
  190. }
  191.