2 * Copyright (c) 2006 Jakub Jermar
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
29 /** @addtogroup genericadt
35 * @brief Implementation of generic chained hash table.
37 * This file contains implementation of generic chained hash table.
40 #include <adt/hash_table.h>
43 #include <arch/types.h>
48 /** Create chained hash table.
50 * @param h Hash table structure. Will be initialized by this call.
51 * @param m Number of slots in the hash table.
52 * @param max_keys Maximal number of keys needed to identify an item.
53 * @param op Hash table operations structure.
55 void hash_table_create(hash_table_t
*h
, count_t m
, count_t max_keys
, hash_table_operations_t
*op
)
60 ASSERT(op
&& op
->hash
&& op
->compare
);
63 h
->entry
= malloc(m
* sizeof(link_t
), 0);
65 panic("cannot allocate memory for hash table\n");
67 memsetb((uintptr_t) h
->entry
, m
* sizeof(link_t
), 0);
69 for (i
= 0; i
< m
; i
++)
70 list_initialize(&h
->entry
[i
]);
73 h
->max_keys
= max_keys
;
77 /** Insert item into hash table.
79 * @param h Hash table.
80 * @param key Array of all keys necessary to compute hash index.
81 * @param item Item to be inserted into the hash table.
83 void hash_table_insert(hash_table_t
*h
, unative_t key
[], link_t
*item
)
88 ASSERT(h
&& h
->op
&& h
->op
->hash
&& h
->op
->compare
);
90 chain
= h
->op
->hash(key
);
91 ASSERT(chain
< h
->entries
);
93 list_append(item
, &h
->entry
[chain
]);
96 /** Search hash table for an item matching keys.
98 * @param h Hash table.
99 * @param key Array of all keys needed to compute hash index.
101 * @return Matching item on success, NULL if there is no such item.
103 link_t
*hash_table_find(hash_table_t
*h
, unative_t key
[])
108 ASSERT(h
&& h
->op
&& h
->op
->hash
&& h
->op
->compare
);
110 chain
= h
->op
->hash(key
);
111 ASSERT(chain
< h
->entries
);
113 for (cur
= h
->entry
[chain
].next
; cur
!= &h
->entry
[chain
]; cur
= cur
->next
) {
114 if (h
->op
->compare(key
, h
->max_keys
, cur
)) {
116 * The entry is there.
125 /** Remove all matching items from hash table.
127 * For each removed item, h->remove_callback() is called.
129 * @param h Hash table.
130 * @param key Array of keys that will be compared against items of the hash table.
131 * @param keys Number of keys in the key array.
133 void hash_table_remove(hash_table_t
*h
, unative_t key
[], count_t keys
)
138 ASSERT(h
&& h
->op
&& h
->op
->hash
&& h
->op
->compare
&& h
->op
->remove_callback
);
139 ASSERT(keys
<= h
->max_keys
);
141 if (keys
== h
->max_keys
) {
144 * All keys are known, hash_table_find() can be used to find the entry.
147 cur
= hash_table_find(h
, key
);
150 h
->op
->remove_callback(cur
);
156 * Fewer keys were passed.
157 * Any partially matching entries are to be removed.
159 for (chain
= 0; chain
< h
->entries
; chain
++) {
160 for (cur
= h
->entry
[chain
].next
; cur
!= &h
->entry
[chain
]; cur
= cur
->next
) {
161 if (h
->op
->compare(key
, keys
, cur
)) {
168 h
->op
->remove_callback(hlp
);