Subversion Repositories HelenOS

Rev

Rev 4263 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  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 <arch/types.h>
  43. #include <debug.h>
  44. #include <mm/slab.h>
  45. #include <memstr.h>
  46.  
  47. /** Create chained hash table.
  48.  *
  49.  * @param h Hash table structure. Will be initialized by this call.
  50.  * @param m Number of slots in the hash table.
  51.  * @param max_keys Maximal number of keys needed to identify an item.
  52.  * @param op Hash table operations structure.
  53.  */
  54. void hash_table_create(hash_table_t *h, size_t m, size_t max_keys, hash_table_operations_t *op)
  55. {
  56.     size_t i;
  57.  
  58.     ASSERT(h);
  59.     ASSERT(op);
  60.     ASSERT(op->hash);
  61.     ASSERT(op->compare);
  62.     ASSERT(max_keys > 0);
  63.    
  64.     h->entry = (link_t *) malloc(m * sizeof(link_t), 0);
  65.     if (!h->entry)
  66.         panic("Cannot allocate memory for hash table.");
  67.    
  68.     memsetb(h->entry, m * sizeof(link_t), 0);
  69.    
  70.     for (i = 0; i < m; i++)
  71.         list_initialize(&h->entry[i]);
  72.    
  73.     h->entries = m;
  74.     h->max_keys = max_keys;
  75.     h->op = op;
  76. }
  77.  
  78. /** Insert item into hash table.
  79.  *
  80.  * @param h Hash table.
  81.  * @param key Array of all keys necessary to compute hash index.
  82.  * @param item Item to be inserted into the hash table.
  83.  */
  84. void hash_table_insert(hash_table_t *h, unative_t key[], link_t *item)
  85. {
  86.     size_t chain;
  87.    
  88.     ASSERT(item);
  89.     ASSERT(h);
  90.     ASSERT(h->op);
  91.     ASSERT(h->op->hash);
  92.     ASSERT(h->op->compare);
  93.    
  94.     chain = h->op->hash(key);
  95.     ASSERT(chain < h->entries);
  96.    
  97.     list_append(item, &h->entry[chain]);
  98. }
  99.  
  100. /** Search hash table for an item matching keys.
  101.  *
  102.  * @param h Hash table.
  103.  * @param key Array of all keys needed to compute hash index.
  104.  *
  105.  * @return Matching item on success, NULL if there is no such item.
  106.  */
  107. link_t *hash_table_find(hash_table_t *h, unative_t key[])
  108. {
  109.     link_t *cur;
  110.     size_t chain;
  111.    
  112.     ASSERT(h);
  113.     ASSERT(h->op);
  114.     ASSERT(h->op->hash);
  115.     ASSERT(h->op->compare);
  116.    
  117.     chain = h->op->hash(key);
  118.     ASSERT(chain < h->entries);
  119.    
  120.     for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
  121.         if (h->op->compare(key, h->max_keys, cur)) {
  122.             /*
  123.              * The entry is there.
  124.              */
  125.             return cur;
  126.         }
  127.     }
  128.    
  129.     return NULL;
  130. }
  131.  
  132. /** Remove all matching items from hash table.
  133.  *
  134.  * For each removed item, h->remove_callback() is called (if not NULL).
  135.  *
  136.  * @param h Hash table.
  137.  * @param key Array of keys that will be compared against items of the hash table.
  138.  * @param keys Number of keys in the key array.
  139.  */
  140. void hash_table_remove(hash_table_t *h, unative_t key[], size_t keys)
  141. {
  142.     size_t chain;
  143.     link_t *cur;
  144.    
  145.     ASSERT(h);
  146.     ASSERT(h->op);
  147.     ASSERT(h->op->hash);
  148.     ASSERT(h->op->compare);
  149.     ASSERT(keys <= h->max_keys);
  150.    
  151.     if (keys == h->max_keys) {
  152.    
  153.         /*
  154.          * All keys are known, hash_table_find() can be used to find the entry.
  155.          */
  156.    
  157.         cur = hash_table_find(h, key);
  158.         if (cur) {
  159.             list_remove(cur);
  160.             if (h->op->remove_callback)
  161.                 h->op->remove_callback(cur);
  162.         }
  163.         return;
  164.     }
  165.    
  166.     /*
  167.      * Fewer keys were passed.
  168.      * Any partially matching entries are to be removed.
  169.      */
  170.     for (chain = 0; chain < h->entries; chain++) {
  171.         for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
  172.             if (h->op->compare(key, keys, cur)) {
  173.                 link_t *hlp;
  174.                
  175.                 hlp = cur;
  176.                 cur = cur->prev;
  177.                
  178.                 list_remove(hlp);
  179.                 if (h->op->remove_callback)
  180.                     h->op->remove_callback(hlp);
  181.                
  182.                 continue;
  183.             }
  184.         }
  185.     }
  186. }
  187.  
  188. /** @}
  189.  */
  190.