Subversion Repositories HelenOS

Rev

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

Rev 3424 Rev 4377
Line 30... Line 30...
30 
 * @{
 30 
 * @{
31 
 */
 31 
 */
32 
 
 32 
 
33 
/**
 33 
/**
34 
 * @file
 34 
 * @file
35 
 * @brief   Implementation of generic chained hash table.
 35 
 * @brief Implementation of generic chained hash table.
36 
 *
 36 
 *
37 
 * This file contains implementation of generic chained hash table.
 37 
 * This file contains implementation of generic chained hash table.
38 
 */
 38 
 */
39 
 
 39 
 
40 
#include <adt/hash_table.h>
 40 
#include <adt/hash_table.h>
Line 54... Line 54...
54 
void hash_table_create(hash_table_t *h, count_t m, count_t max_keys, hash_table_operations_t *op)
 54 
void hash_table_create(hash_table_t *h, count_t m, count_t max_keys, hash_table_operations_t *op)
55 
{
 55 
{
56 
    index_t i;
 56 
    index_t i;
57 
 
 57 
 
58 
    ASSERT(h);
 58 
    ASSERT(h);
- 
 
 59 
    ASSERT(op);
- 
 
 60 
    ASSERT(op->hash);
59 
    ASSERT(op && op->hash && op->compare);
 61 
    ASSERT(op->compare);
60 
    ASSERT(max_keys > 0);
 62 
    ASSERT(max_keys > 0);
61 
   
 63 
   
62 
    h->entry = (link_t *) malloc(m * sizeof(link_t), 0);
 64 
    h->entry = (link_t *) malloc(m * sizeof(link_t), 0);
63 
    if (!h->entry) {
 65 
    if (!h->entry)
64 
        panic("cannot allocate memory for hash table\n");
 66 
        panic("Cannot allocate memory for hash table.");
65 
    }
 67 
   
66 
    memsetb(h->entry, m * sizeof(link_t), 0);
 68 
    memsetb(h->entry, m * sizeof(link_t), 0);
67 
   
 69 
   
68 
    for (i = 0; i < m; i++)
 70 
    for (i = 0; i < m; i++)
69 
        list_initialize(&h->entry[i]);
 71 
        list_initialize(&h->entry[i]);
70 
   
 72 
   
Line 80... Line 82...
80 
 * @param item Item to be inserted into the hash table.
 82 
 * @param item Item to be inserted into the hash table.
81 
 */
 83 
 */
82 
void hash_table_insert(hash_table_t *h, unative_t key[], link_t *item)
 84 
void hash_table_insert(hash_table_t *h, unative_t key[], link_t *item)
83 
{
 85 
{
84 
    index_t chain;
 86 
    index_t chain;
85 
 
 87 
   
86 
    ASSERT(item);
 88 
    ASSERT(item);
- 
 
 89 
    ASSERT(h);
- 
 
 90 
    ASSERT(h->op);
- 
 
 91 
    ASSERT(h->op->hash);
87 
    ASSERT(h && h->op && h->op->hash && h->op->compare);
 92 
    ASSERT(h->op->compare);
88 
 
 93 
   
89 
    chain = h->op->hash(key);
 94 
    chain = h->op->hash(key);
90 
    ASSERT(chain < h->entries);
 95 
    ASSERT(chain < h->entries);
91 
   
 96 
   
92 
    list_append(item, &h->entry[chain]);
 97 
    list_append(item, &h->entry[chain]);
93 
}
 98 
}
Line 101... Line 106...
101 
 */
 106 
 */
102 
link_t *hash_table_find(hash_table_t *h, unative_t key[])
 107 
link_t *hash_table_find(hash_table_t *h, unative_t key[])
103 
{
 108 
{
104 
    link_t *cur;
 109 
    link_t *cur;
105 
    index_t chain;
 110 
    index_t chain;
106 
 
 111 
   
- 
 
 112 
    ASSERT(h);
- 
 
 113 
    ASSERT(h->op);
- 
 
 114 
    ASSERT(h->op->hash);
107 
    ASSERT(h && h->op && h->op->hash && h->op->compare);
 115 
    ASSERT(h->op->compare);
108 
 
 116 
   
109 
    chain = h->op->hash(key);
 117 
    chain = h->op->hash(key);
110 
    ASSERT(chain < h->entries);
 118 
    ASSERT(chain < h->entries);
111 
   
 119 
   
112 
    for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
 120 
    for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
113 
        if (h->op->compare(key, h->max_keys, cur)) {
 121 
        if (h->op->compare(key, h->max_keys, cur)) {
Line 121... Line 129...
121 
    return NULL;
 129 
    return NULL;
122 
}
 130 
}
123 
 
 131 
 
124 
/** Remove all matching items from hash table.
 132 
/** Remove all matching items from hash table.
125 
 *
 133 
 *
126 
 * For each removed item, h->remove_callback() is called.
 134 
 * For each removed item, h->remove_callback() is called (if not NULL).
127 
 *
 135 
 *
128 
 * @param h Hash table.
 136 
 * @param h Hash table.
129 
 * @param key Array of keys that will be compared against items of the hash table.
 137 
 * @param key Array of keys that will be compared against items of the hash table.
130 
 * @param keys Number of keys in the key array.
 138 
 * @param keys Number of keys in the key array.
131 
 */
 139 
 */
132 
void hash_table_remove(hash_table_t *h, unative_t key[], count_t keys)
 140 
void hash_table_remove(hash_table_t *h, unative_t key[], count_t keys)
133 
{
 141 
{
134 
    index_t chain;
 142 
    index_t chain;
135 
    link_t *cur;
 143 
    link_t *cur;
136 
 
 144 
   
- 
 
 145 
    ASSERT(h);
- 
 
 146 
    ASSERT(h->op);
- 
 
 147 
    ASSERT(h->op->hash);
137 
    ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
 148 
    ASSERT(h->op->compare);
138 
    ASSERT(keys <= h->max_keys);
 149 
    ASSERT(keys <= h->max_keys);
139 
   
 150 
   
140 
    if (keys == h->max_keys) {
 151 
    if (keys == h->max_keys) {
141 
 
 152 
   
142 
        /*
 153 
        /*
143 
         * All keys are known, hash_table_find() can be used to find the entry.
 154 
         * All keys are known, hash_table_find() can be used to find the entry.
144 
         */
 155 
         */
145 
   
 156 
   
146 
        cur = hash_table_find(h, key);
 157 
        cur = hash_table_find(h, key);
147 
        if (cur) {
 158 
        if (cur) {
148 
            list_remove(cur);
 159 
            list_remove(cur);
- 
 
 160 
            if (h->op->remove_callback)
149 
            h->op->remove_callback(cur);
 161 
                h->op->remove_callback(cur);
150 
        }
 162 
        }
151 
        return;
 163 
        return;
152 
    }
 164 
    }
153 
   
 165 
   
154 
    /*
 166 
    /*
Line 162... Line 174...
162 
               
 174 
               
163 
                hlp = cur;
 175 
                hlp = cur;
164 
                cur = cur->prev;
 176 
                cur = cur->prev;
165 
               
 177 
               
166 
                list_remove(hlp);
 178 
                list_remove(hlp);
- 
 
 179 
                if (h->op->remove_callback)
167 
                h->op->remove_callback(hlp);
 180 
                    h->op->remove_callback(hlp);
168 
               
 181 
               
169 
                continue;
 182 
                continue;
170 
            }
 183 
            }
171 
        }
 184 
        }
172 
    }
 185 
    }