Subversion Repositories HelenOS

Rev

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