hash_table.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006 Jakub Jermar
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00035 /*
00036  * This is an implementation of generic chained hash table.
00037  */
00038 
00039 #include <libadt/hash_table.h>
00040 #include <libadt/list.h>
00041 #include <unistd.h>
00042 #include <malloc.h>
00043 #include <assert.h>
00044 #include <stdio.h>
00045 #include <string.h>
00046 
00055 int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op)
00056 {
00057         hash_count_t i;
00058 
00059         assert(h);
00060         assert(op && op->hash && op->compare);
00061         assert(max_keys > 0);
00062         
00063         h->entry = malloc(m * sizeof(link_t));
00064         if (!h->entry) {
00065                 printf("cannot allocate memory for hash table\n");
00066                 return false;
00067         }
00068         memset((void *) h->entry, 0,  m * sizeof(link_t));
00069         
00070         for (i = 0; i < m; i++)
00071                 list_initialize(&h->entry[i]);
00072         
00073         h->entries = m;
00074         h->max_keys = max_keys;
00075         h->op = op;
00076         return true;
00077 }
00078 
00085 void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
00086 {
00087         hash_index_t chain;
00088 
00089         assert(item);
00090         assert(h && h->op && h->op->hash && h->op->compare);
00091 
00092         chain = h->op->hash(key);
00093         assert(chain < h->entries);
00094         
00095         list_append(item, &h->entry[chain]);
00096 }
00097 
00105 link_t *hash_table_find(hash_table_t *h, unsigned long key[])
00106 {
00107         link_t *cur;
00108         hash_index_t chain;
00109 
00110         assert(h && h->op && h->op->hash && h->op->compare);
00111 
00112         chain = h->op->hash(key);
00113         assert(chain < h->entries);
00114         
00115         for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
00116                 if (h->op->compare(key, h->max_keys, cur)) {
00117                         /*
00118                          * The entry is there.
00119                          */
00120                         return cur;
00121                 }
00122         }
00123         
00124         return NULL;
00125 }
00126 
00135 void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
00136 {
00137         hash_index_t chain;
00138         link_t *cur;
00139 
00140         assert(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
00141         assert(keys <= h->max_keys);
00142         
00143         if (keys == h->max_keys) {
00144 
00145                 /*
00146                  * All keys are known, hash_table_find() can be used to find the entry.
00147                  */
00148         
00149                 cur = hash_table_find(h, key);
00150                 if (cur) {
00151                         list_remove(cur);
00152                         h->op->remove_callback(cur);
00153                 }
00154                 return;
00155         }
00156         
00157         /*
00158          * Fewer keys were passed.
00159          * Any partially matching entries are to be removed.
00160          */
00161         for (chain = 0; chain < h->entries; chain++) {
00162                 for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
00163                         if (h->op->compare(key, keys, cur)) {
00164                                 link_t *hlp;
00165                                 
00166                                 hlp = cur;
00167                                 cur = cur->prev;
00168                                 
00169                                 list_remove(hlp);
00170                                 h->op->remove_callback(hlp);
00171                                 
00172                                 continue;
00173                         }
00174                 }
00175         }
00176 }
00177 
00178 

Generated on Sun Jun 18 18:00:18 2006 for HelenOS Userspace (ia64) by  doxygen 1.4.6