35,8 → 35,6 |
#include <unistd.h> |
#include <malloc.h> |
#include <assert.h> |
#include <stdio.h> |
#include <string.h> |
|
/** Create chained hash table. |
* |
44,22 → 42,20 |
* @param m Number of slots in the hash table. |
* @param max_keys Maximal number of keys needed to identify an item. |
* @param op Hash table operations structure. |
* @return true on success |
*/ |
int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op) |
void hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op) |
{ |
hash_count_t i; |
int i; |
|
assert(h); |
assert(op && op->hash && op->compare); |
assert(max_keys > 0); |
ASSERT(h); |
ASSERT(op && op->hash && op->compare); |
ASSERT(max_keys > 0); |
|
h->entry = malloc(m * sizeof(link_t *)); |
h->entry = malloc(m * sizeof(link_t *), 0); |
if (!h->entry) { |
printf("cannot allocate memory for hash table\n"); |
return false; |
panic("cannot allocate memory for hash table\n"); |
} |
memset((void *) h->entry, 0, m * sizeof(link_t *)); |
memsetb((__address) h->entry, m * sizeof(link_t *), 0); |
|
for (i = 0; i < m; i++) |
list_initialize(&h->entry[i]); |
67,7 → 63,6 |
h->entries = m; |
h->max_keys = max_keys; |
h->op = op; |
return true; |
} |
|
/** Insert item into hash table. |
76,15 → 71,15 |
* @param hey Array of all keys necessary to compute hash index. |
* @param item Item to be inserted into the hash table. |
*/ |
void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item) |
void hash_table_insert(hash_table_t *h, __native key[], link_t *item) |
{ |
hash_index_t chain; |
|
assert(item); |
assert(h && h->op && h->op->hash && h->op->compare); |
ASSERT(item); |
ASSERT(h && h->op && h->op->hash && h->op->compare); |
|
chain = h->op->hash(key); |
assert(chain < h->entries); |
ASSERT(chain < h->entries); |
|
list_append(item, &h->entry[chain]); |
} |
96,15 → 91,15 |
* |
* @return Matching item on success, NULL if there is no such item. |
*/ |
link_t *hash_table_find(hash_table_t *h, unsigned long key[]) |
link_t *hash_table_find(hash_table_t *h, __native key[]) |
{ |
link_t *cur; |
hash_index_t chain; |
|
assert(h && h->op && h->op->hash && h->op->compare); |
ASSERT(h && h->op && h->op->hash && h->op->compare); |
|
chain = h->op->hash(key); |
assert(chain < h->entries); |
ASSERT(chain < h->entries); |
|
/* |
* The hash table is not redundant. |
130,13 → 125,13 |
* @param key Array of keys that will be compared against items of the hash table. |
* @param keys Number of keys in the 'key' array. |
*/ |
void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys) |
void hash_table_remove(hash_table_t *h, __native key[], hash_count_t keys) |
{ |
hash_index_t chain; |
link_t *cur; |
|
assert(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback); |
assert(keys <= h->max_keys); |
ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback); |
ASSERT(keys <= h->max_keys); |
|
if (keys == h->max_keys) { |
|