Rev 996 | Rev 1202 | 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. |