Subversion Repositories HelenOS

Rev

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

Rev 3790 Rev 4246
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.");
 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 131... Line 139...
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);
- 
 
 148 
    ASSERT(h->op->compare);
137 
    ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
 149 
    ASSERT(h->op->remove_callback);
138 
    ASSERT(keys <= h->max_keys);
 150 
    ASSERT(keys <= h->max_keys);
139 
   
 151 
   
140 
    if (keys == h->max_keys) {
 152 
    if (keys == h->max_keys) {
141 
 
 153 
   
142 
        /*
 154 
        /*
143 
         * All keys are known, hash_table_find() can be used to find the entry.
 155 
         * All keys are known, hash_table_find() can be used to find the entry.
144 
         */
 156 
         */
145 
   
 157 
   
146 
        cur = hash_table_find(h, key);
 158 
        cur = hash_table_find(h, key);