Subversion Repositories HelenOS-historic

Rev

Rev 997 | Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
996 cejka 1 
/*
2 
 * Copyright (C) 2006 Jakub Jermar
3 
 * All rights reserved.
4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
8 
 *
9 
 * - Redistributions of source code must retain the above copyright
10 
 *   notice, this list of conditions and the following disclaimer.
11 
 * - Redistributions in binary form must reproduce the above copyright
12 
 *   notice, this list of conditions and the following disclaimer in the
13 
 *   documentation and/or other materials provided with the distribution.
14 
 * - The name of the author may not be used to endorse or promote products
15 
 *   derived from this software without specific prior written permission.
16 
 *
17 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
 */
28 
 
29 
/*
30 
 * This is an implementation of generic chained hash table.
31 
 */
32 
 
33 
#include <hash_table.h>
34 
#include <list.h>
35 
#include <unistd.h>
36 
#include <malloc.h>
37 
#include <assert.h>
38 
 
39 
/** Create chained hash table.
40 
 *
41 
 * @param h Hash table structure. Will be initialized by this call.
42 
 * @param m Number of slots in the hash table.
43 
 * @param max_keys Maximal number of keys needed to identify an item.
44 
 * @param op Hash table operations structure.
45 
 */
46 
void hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op)
47 
{
48 
    int i;
49 
 
50 
    ASSERT(h);
51 
    ASSERT(op && op->hash && op->compare);
52 
    ASSERT(max_keys > 0);
53 
 
54 
    h->entry = malloc(m * sizeof(link_t *), 0);
55 
    if (!h->entry) {
56 
        panic("cannot allocate memory for hash table\n");
57 
    }
58 
    memsetb((__address) h->entry, m * sizeof(link_t *), 0);
59 
 
60 
    for (i = 0; i < m; i++)
61 
        list_initialize(&h->entry[i]);
62 
 
63 
    h->entries = m;
64 
    h->max_keys = max_keys;
65 
    h->op = op;
66 
}
67 
 
68 
/** Insert item into hash table.
69 
 *
70 
 * @param h Hash table.
71 
 * @param hey Array of all keys necessary to compute hash index.
72 
 * @param item Item to be inserted into the hash table.
73 
 */
74 
void hash_table_insert(hash_table_t *h, __native key[], link_t *item)
75 
{
76 
    hash_index_t chain;
77 
 
78 
    ASSERT(item);
79 
    ASSERT(h && h->op && h->op->hash && h->op->compare);
80 
 
81 
    chain = h->op->hash(key);
82 
    ASSERT(chain < h->entries);
83 
 
84 
    list_append(item, &h->entry[chain]);
85 
}
86 
 
87 
/** Search hash table for an item matching keys.
88 
 *
89 
 * @param h Hash table.
90 
 * @param key Array of all keys needed to compute hash index.
91 
 *
92 
 * @return Matching item on success, NULL if there is no such item.
93 
 */
94 
link_t *hash_table_find(hash_table_t *h, __native key[])
95 
{
96 
    link_t *cur;
97 
    hash_index_t chain;
98 
 
99 
    ASSERT(h && h->op && h->op->hash && h->op->compare);
100 
 
101 
    chain = h->op->hash(key);
102 
    ASSERT(chain < h->entries);
103 
 
104 
    /*
105 
     * The hash table is not redundant.
106 
     * Check if the keys are not in place already.
107 
     */
108 
    for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
109 
        if (h->op->compare(key, h->max_keys, cur)) {
110 
            /*
111 
             * The entry is there.
112 
             */
113 
            return cur;
114 
        }
115 
    }
116 
 
117 
    return NULL;
118 
}
119 
 
120 
/** Remove all matching items from hash table.
121 
 *
122 
 * For each removed item, h->remove_callback() is called.
123 
 *
124 
 * @param h Hash table.
125 
 * @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.
127 
 */
128 
void hash_table_remove(hash_table_t *h, __native key[], hash_count_t keys)
129 
{
130 
    hash_index_t chain;
131 
    link_t *cur;
132 
 
133 
    ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
134 
    ASSERT(keys <= h->max_keys);
135 
 
136 
    if (keys == h->max_keys) {
137 
 
138 
        /*
139 
         * All keys are known, hash_table_find() can be used to find the entry.
140 
         */
141 
 
142 
        cur = hash_table_find(h, key);
143 
        if (cur) {
144 
            list_remove(cur);
145 
            h->op->remove_callback(cur);
146 
        }
147 
        return;
148 
    }
149 
 
150 
    /*
151 
     * Fewer keys were passed.
152 
     * Any partially matching entries are to be removed.
153 
     */
154 
    for (chain = 0; chain < h->entries; chain++) {
155 
        for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
156 
            if (h->op->compare(key, keys, cur)) {
157 
                link_t *hlp;
158 
 
159 
                hlp = cur;
160 
                cur = cur->prev;
161 
 
162 
                list_remove(hlp);
163 
                h->op->remove_callback(hlp);
164 
 
165 
                continue;
166 
            }
167 
        }
168 
    }
169 
}