Subversion Repositories HelenOS-historic

Rev

Rev 996 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 996 Rev 997
Line 33... Line 33...
33 
#include <hash_table.h>
 33 
#include <hash_table.h>
34 
#include <list.h>
 34 
#include <list.h>
35 
#include <unistd.h>
 35 
#include <unistd.h>
36 
#include <malloc.h>
 36 
#include <malloc.h>
37 
#include <assert.h>
 37 
#include <assert.h>
- 
 
 38 
#include <stdio.h>
- 
 
 39 
#include <string.h>
38 
 
 40 
 
39 
/** Create chained hash table.
 41 
/** Create chained hash table.
40 
 *
 42 
 *
41 
 * @param h Hash table structure. Will be initialized by this call.
 43 
 * @param h Hash table structure. Will be initialized by this call.
42 
 * @param m Number of slots in the hash table.
 44 
 * @param m Number of slots in the hash table.
43 
 * @param max_keys Maximal number of keys needed to identify an item.
 45 
 * @param max_keys Maximal number of keys needed to identify an item.
44 
 * @param op Hash table operations structure.
 46 
 * @param op Hash table operations structure.
- 
 
 47 
 * @return true on success
45 
 */
 48 
 */
46 
void hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op)
 49 
int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op)
47 
{
 50 
{
48 
    int i;
 51 
    hash_count_t i;
49 
 
 52 
 
50 
    ASSERT(h);
 53 
    assert(h);
51 
    ASSERT(op && op->hash && op->compare);
 54 
    assert(op && op->hash && op->compare);
52 
    ASSERT(max_keys > 0);
 55 
    assert(max_keys > 0);
53 
   
 56 
   
54 
    h->entry = malloc(m * sizeof(link_t *), 0);
 57 
    h->entry = malloc(m * sizeof(link_t *));
55 
    if (!h->entry) {
 58 
    if (!h->entry) {
56 
        panic("cannot allocate memory for hash table\n");
 59 
        printf("cannot allocate memory for hash table\n");
- 
 
 60 
        return false;
57 
    }
 61 
    }
58 
    memsetb((__address) h->entry, m * sizeof(link_t *), 0);
 62 
    memset((void *) h->entry, 0,  m * sizeof(link_t *));
59 
   
 63 
   
60 
    for (i = 0; i < m; i++)
 64 
    for (i = 0; i < m; i++)
61 
        list_initialize(&h->entry[i]);
 65 
        list_initialize(&h->entry[i]);
62 
   
 66 
   
63 
    h->entries = m;
 67 
    h->entries = m;
64 
    h->max_keys = max_keys;
 68 
    h->max_keys = max_keys;
65 
    h->op = op;
 69 
    h->op = op;
- 
 
 70 
    return true;
66 
}
 71 
}
67 
 
 72 
 
68 
/** Insert item into hash table.
 73 
/** Insert item into hash table.
69 
 *
 74 
 *
70 
 * @param h Hash table.
 75 
 * @param h Hash table.
71 
 * @param hey Array of all keys necessary to compute hash index.
 76 
 * @param hey Array of all keys necessary to compute hash index.
72 
 * @param item Item to be inserted into the hash table.
 77 
 * @param item Item to be inserted into the hash table.
73 
 */
 78 
 */
74 
void hash_table_insert(hash_table_t *h, __native key[], link_t *item)
 79 
void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
75 
{
 80 
{
76 
    hash_index_t chain;
 81 
    hash_index_t chain;
77 
 
 82 
 
78 
    ASSERT(item);
 83 
    assert(item);
79 
    ASSERT(h && h->op && h->op->hash && h->op->compare);
 84 
    assert(h && h->op && h->op->hash && h->op->compare);
80 
 
 85 
 
81 
    chain = h->op->hash(key);
 86 
    chain = h->op->hash(key);
82 
    ASSERT(chain < h->entries);
 87 
    assert(chain < h->entries);
83 
   
 88 
   
84 
    list_append(item, &h->entry[chain]);
 89 
    list_append(item, &h->entry[chain]);
85 
}
 90 
}
86 
 
 91 
 
87 
/** Search hash table for an item matching keys.
 92 
/** Search hash table for an item matching keys.
Line 89... Line 94...
89 
 * @param h Hash table.
 94 
 * @param h Hash table.
90 
 * @param key Array of all keys needed to compute hash index.
 95 
 * @param key Array of all keys needed to compute hash index.
91 
 *
 96 
 *
92 
 * @return Matching item on success, NULL if there is no such item.
 97 
 * @return Matching item on success, NULL if there is no such item.
93 
 */
 98 
 */
94 
link_t *hash_table_find(hash_table_t *h, __native key[])
 99 
link_t *hash_table_find(hash_table_t *h, unsigned long key[])
95 
{
 100 
{
96 
    link_t *cur;
 101 
    link_t *cur;
97 
    hash_index_t chain;
 102 
    hash_index_t chain;
98 
 
 103 
 
99 
    ASSERT(h && h->op && h->op->hash && h->op->compare);
 104 
    assert(h && h->op && h->op->hash && h->op->compare);
100 
 
 105 
 
101 
    chain = h->op->hash(key);
 106 
    chain = h->op->hash(key);
102 
    ASSERT(chain < h->entries);
 107 
    assert(chain < h->entries);
103 
   
 108 
   
104 
    /*
 109 
    /*
105 
     * The hash table is not redundant.
 110 
     * The hash table is not redundant.
106 
     * Check if the keys are not in place already.
 111 
     * Check if the keys are not in place already.
107 
     */
 112 
     */
Line 123... Line 128...
123 
 *
 128 
 *
124 
 * @param h Hash table.
 129 
 * @param h Hash table.
125 
 * @param key Array of keys that will be compared against items of the hash table.
 130 
 * @param key Array of keys that will be compared against items of the hash table.
126 
 * @param keys Number of keys in the 'key' array.
 131 
 * @param keys Number of keys in the 'key' array.
127 
 */
 132 
 */
128 
void hash_table_remove(hash_table_t *h, __native key[], hash_count_t keys)
 133 
void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
129 
{
 134 
{
130 
    hash_index_t chain;
 135 
    hash_index_t chain;
131 
    link_t *cur;
 136 
    link_t *cur;
132 
 
 137 
 
133 
    ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
 138 
    assert(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
134 
    ASSERT(keys <= h->max_keys);
 139 
    assert(keys <= h->max_keys);
135 
   
 140 
   
136 
    if (keys == h->max_keys) {
 141 
    if (keys == h->max_keys) {
137 
 
 142 
 
138 
        /*
 143 
        /*
139 
         * All keys are known, hash_table_find() can be used to find the entry.
 144 
         * All keys are known, hash_table_find() can be used to find the entry.