00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00040 #include <adt/hash_table.h>
00041 #include <adt/list.h>
00042 #include <typedefs.h>
00043 #include <arch/types.h>
00044 #include <debug.h>
00045 #include <mm/slab.h>
00046 #include <memstr.h>
00047
00055 void hash_table_create(hash_table_t *h, count_t m, count_t max_keys, hash_table_operations_t *op)
00056 {
00057 int 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), 0);
00064 if (!h->entry) {
00065 panic("cannot allocate memory for hash table\n");
00066 }
00067 memsetb((__address) h->entry, m * sizeof(link_t), 0);
00068
00069 for (i = 0; i < m; i++)
00070 list_initialize(&h->entry[i]);
00071
00072 h->entries = m;
00073 h->max_keys = max_keys;
00074 h->op = op;
00075 }
00076
00083 void hash_table_insert(hash_table_t *h, __native key[], link_t *item)
00084 {
00085 index_t chain;
00086
00087 ASSERT(item);
00088 ASSERT(h && h->op && h->op->hash && h->op->compare);
00089
00090 chain = h->op->hash(key);
00091 ASSERT(chain < h->entries);
00092
00093 list_append(item, &h->entry[chain]);
00094 }
00095
00103 link_t *hash_table_find(hash_table_t *h, __native key[])
00104 {
00105 link_t *cur;
00106 index_t chain;
00107
00108 ASSERT(h && h->op && h->op->hash && h->op->compare);
00109
00110 chain = h->op->hash(key);
00111 ASSERT(chain < h->entries);
00112
00113 for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
00114 if (h->op->compare(key, h->max_keys, cur)) {
00115
00116
00117
00118 return cur;
00119 }
00120 }
00121
00122 return NULL;
00123 }
00124
00133 void hash_table_remove(hash_table_t *h, __native key[], count_t keys)
00134 {
00135 index_t chain;
00136 link_t *cur;
00137
00138 ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
00139 ASSERT(keys <= h->max_keys);
00140
00141 if (keys == h->max_keys) {
00142
00143
00144
00145
00146
00147 cur = hash_table_find(h, key);
00148 if (cur) {
00149 list_remove(cur);
00150 h->op->remove_callback(cur);
00151 }
00152 return;
00153 }
00154
00155
00156
00157
00158
00159 for (chain = 0; chain < h->entries; chain++) {
00160 for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
00161 if (h->op->compare(key, keys, cur)) {
00162 link_t *hlp;
00163
00164 hlp = cur;
00165 cur = cur->prev;
00166
00167 list_remove(hlp);
00168 h->op->remove_callback(hlp);
00169
00170 continue;
00171 }
00172 }
00173 }
00174 }
00175