kernel/generic/src/adt/hash_table.c

   1 /*
   2  * Copyright (c) 2006 Jakub Jermar
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup genericadt
  30  * @{
  31  */
  32
  33 /**
  34  * @file
  35  * @brief       Implementation of generic chained hash table.
  36  *
  37  * This file contains implementation of generic chained hash table.
  38  */
  39
  40 #include <adt/hash_table.h>
  41 #include <adt/list.h>
  42 #include <typedefs.h>
  43 #include <arch/types.h>
  44 #include <debug.h>
  45 #include <mm/slab.h>
  46 #include <memstr.h>
  47
  48 /** Create chained hash table.
  49  *
  50  * @param h Hash table structure. Will be initialized by this call.
  51  * @param m Number of slots in the hash table.
  52  * @param max_keys Maximal number of keys needed to identify an item.
  53  * @param op Hash table operations structure.
  54  */
  55 void hash_table_create(hash_table_t *h, count_t m, count_t max_keys, hash_table_operations_t *op)
  56 {
  57         int i;
  58
  59         ASSERT(h);
  60         ASSERT(op && op->hash && op->compare);
  61         ASSERT(max_keys > 0);
  62
  63         h->entry = malloc(m * sizeof(link_t), 0);
  64         if (!h->entry) {
  65                 panic("cannot allocate memory for hash table\n");
  66         }
  67         memsetb((uintptr_t) h->entry, m * sizeof(link_t), 0);
  68
  69         for (i = 0; i < m; i++)
  70                 list_initialize(&h->entry[i]);
  71
  72         h->entries = m;
  73         h->max_keys = max_keys;
  74         h->op = op;
  75 }
  76
  77 /** Insert item into hash table.
  78  *
  79  * @param h Hash table.
  80  * @param key Array of all keys necessary to compute hash index.
  81  * @param item Item to be inserted into the hash table.
  82  */
  83 void hash_table_insert(hash_table_t *h, unative_t key[], link_t *item)
  84 {
  85         index_t chain;
  86
  87         ASSERT(item);
  88         ASSERT(h && h->op && h->op->hash && h->op->compare);
  89
  90         chain = h->op->hash(key);
  91         ASSERT(chain < h->entries);
  92
  93         list_append(item, &h->entry[chain]);
  94 }
  95
  96 /** Search hash table for an item matching keys.
  97  *
  98  * @param h Hash table.
  99  * @param key Array of all keys needed to compute hash index.
 100  *
 101  * @return Matching item on success, NULL if there is no such item.
 102  */
 103 link_t *hash_table_find(hash_table_t *h, unative_t key[])
 104 {
 105         link_t *cur;
 106         index_t chain;
 107
 108         ASSERT(h && h->op && h->op->hash && h->op->compare);
 109
 110         chain = h->op->hash(key);
 111         ASSERT(chain < h->entries);
 112
 113         for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
 114                 if (h->op->compare(key, h->max_keys, cur)) {
 115                         /*
 116                          * The entry is there.
 117                          */
 118                         return cur;
 119                 }
 120         }
 121
 122         return NULL;
 123 }
 124
 125 /** Remove all matching items from hash table.
 126  *
 127  * For each removed item, h->remove_callback() is called.
 128  *
 129  * @param h Hash table.
 130  * @param key Array of keys that will be compared against items of the hash table.
 131  * @param keys Number of keys in the key array.
 132  */
 133 void hash_table_remove(hash_table_t *h, unative_t key[], count_t keys)
 134 {
 135         index_t chain;
 136         link_t *cur;
 137
 138         ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
 139         ASSERT(keys <= h->max_keys);
 140
 141         if (keys == h->max_keys) {
 142
 143                 /*
 144                  * All keys are known, hash_table_find() can be used to find the entry.
 145                  */
 146
 147                 cur = hash_table_find(h, key);
 148                 if (cur) {
 149                         list_remove(cur);
 150                         h->op->remove_callback(cur);
 151                 }
 152                 return;
 153         }
 154
 155         /*
 156          * Fewer keys were passed.
 157          * Any partially matching entries are to be removed.
 158          */
 159         for (chain = 0; chain < h->entries; chain++) {
 160                 for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
 161                         if (h->op->compare(key, keys, cur)) {
 162                                 link_t *hlp;
 163
 164                                 hlp = cur;
 165                                 cur = cur->prev;
 166
 167                                 list_remove(hlp);
 168                                 h->op->remove_callback(hlp);
 169
 170                                 continue;
 171                         }
 172                 }
 173         }
 174 }
 175
 176 /** @}
 177  */