Subversion Repositories HelenOS

Rev

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

  1. /*
  2.  * Copyright (c) 2008 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 libc
  30.  * @{
  31.  */
  32. /** @file
  33.  */
  34.  
  35. /*
  36.  * This is an implementation of generic chained hash table.
  37.  */
  38.  
  39. #include <adt/hash_table.h>
  40. #include <adt/list.h>
  41. #include <unistd.h>
  42. #include <malloc.h>
  43. #include <assert.h>
  44. #include <stdio.h>
  45. #include <string.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 hash table buckets.
  51.  * @param max_keys  Maximal number of keys needed to identify an item.
  52.  * @param op        Hash table operations structure.
  53.  * @return      True on success
  54.  */
  55. int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
  56.     hash_table_operations_t *op)
  57. {
  58.     hash_count_t i;
  59.  
  60.     assert(h);
  61.     assert(op && op->hash && op->compare);
  62.     assert(max_keys > 0);
  63.    
  64.     h->entry = malloc(m * sizeof(link_t));
  65.     if (!h->entry) {
  66.         printf("cannot allocate memory for hash table\n");
  67.         return false;
  68.     }
  69.     memset((void *) h->entry, 0,  m * sizeof(link_t));
  70.    
  71.     for (i = 0; i < m; i++)
  72.         list_initialize(&h->entry[i]);
  73.    
  74.     h->entries = m;
  75.     h->max_keys = max_keys;
  76.     h->op = op;
  77.     return true;
  78. }
  79.  
  80. /** Destroy a hash table instance.
  81.  *
  82.  * @param h     Hash table to be destroyed.
  83.  */
  84. void hash_table_destroy(hash_table_t *h)
  85. {
  86.     assert(h);
  87.     assert(h->entry);
  88.     free(h->entry);
  89. }
  90.  
  91. /** Insert item into a hash table.
  92.  *
  93.  * @param h     Hash table.
  94.  * @param key       Array of all keys necessary to compute hash index.
  95.  * @param item      Item to be inserted into the hash table.
  96.  */
  97. void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
  98. {
  99.     hash_index_t chain;
  100.  
  101.     assert(item);
  102.     assert(h && h->op && h->op->hash && h->op->compare);
  103.  
  104.     chain = h->op->hash(key);
  105.     assert(chain < h->entries);
  106.    
  107.     list_append(item, &h->entry[chain]);
  108. }
  109.  
  110. /** Search hash table for an item matching keys.
  111.  *
  112.  * @param h     Hash table.
  113.  * @param key       Array of all keys needed to compute hash index.
  114.  *
  115.  * @return      Matching item on success, NULL if there is no such item.
  116.  */
  117. link_t *hash_table_find(hash_table_t *h, unsigned long key[])
  118. {
  119.     link_t *cur;
  120.     hash_index_t chain;
  121.  
  122.     assert(h && h->op && h->op->hash && h->op->compare);
  123.  
  124.     chain = h->op->hash(key);
  125.     assert(chain < h->entries);
  126.    
  127.     for (cur = h->entry[chain].next; cur != &h->entry[chain];
  128.         cur = cur->next) {
  129.         if (h->op->compare(key, h->max_keys, cur)) {
  130.             /*
  131.              * The entry is there.
  132.              */
  133.             return cur;
  134.         }
  135.     }
  136.    
  137.     return NULL;
  138. }
  139.  
  140. /** Remove all matching items from hash table.
  141.  *
  142.  * For each removed item, h->remove_callback() is called.
  143.  *
  144.  * @param h     Hash table.
  145.  * @param key       Array of keys that will be compared against items of
  146.  *          the hash table.
  147.  * @param keys      Number of keys in the 'key' array.
  148.  */
  149. void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
  150. {
  151.     hash_index_t chain;
  152.     link_t *cur;
  153.  
  154.     assert(h && h->op && h->op->hash && h->op->compare &&
  155.         h->op->remove_callback);
  156.     assert(keys <= h->max_keys);
  157.    
  158.     if (keys == h->max_keys) {
  159.  
  160.         /*
  161.          * All keys are known, hash_table_find() can be used to find the
  162.          * entry.
  163.          */
  164.    
  165.         cur = hash_table_find(h, key);
  166.         if (cur) {
  167.             list_remove(cur);
  168.             h->op->remove_callback(cur);
  169.         }
  170.         return;
  171.     }
  172.    
  173.     /*
  174.      * Fewer keys were passed.
  175.      * Any partially matching entries are to be removed.
  176.      */
  177.     for (chain = 0; chain < h->entries; chain++) {
  178.         for (cur = h->entry[chain].next; cur != &h->entry[chain];
  179.             cur = cur->next) {
  180.             if (h->op->compare(key, keys, cur)) {
  181.                 link_t *hlp;
  182.                
  183.                 hlp = cur;
  184.                 cur = cur->prev;
  185.                
  186.                 list_remove(hlp);
  187.                 h->op->remove_callback(hlp);
  188.                
  189.                 continue;
  190.             }
  191.         }
  192.     }
  193. }
  194.  
  195. /** @}
  196.  */
  197.