← Back to branch summary

~martin-decky/helenos/rcu

« back to all changes in this revision

Viewing changes to uspace/lib/libc/generic/adt/hash_table.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
uspace/lib/libc/generic/adt/hash_table.c
 
1
/*
 
2
 * Copyright (c) 2008 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
/** @addtogroup libc
 
30
 * @{
 
31
 */
 
32
/** @file
 
33
 */
 
34
 
 
35
/*
 
36
 * This is an implementation of generic chained hash table.
 
37
 */
 
38
 
 
39
#include <adt/hash_table.h>
 
40
#include <adt/list.h>
 
41
#include <unistd.h>
 
42
#include <malloc.h>
 
43
#include <assert.h>
 
44
#include <stdio.h>
 
45
#include <string.h>
 
46
 
 
47
/** Create chained hash table.
 
48
 *
 
49
 * @param h             Hash table structure. Will be initialized by this call.
 
50
 * @param m             Number of hash table buckets.
 
51
 * @param max_keys      Maximal number of keys needed to identify an item.
 
52
 * @param op            Hash table operations structure.
 
53
 * @return              True on success
 
54
 */
 
55
int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
 
56
    hash_table_operations_t *op)
 
57
{
 
58
        hash_count_t i;
 
59
 
 
60
        assert(h);
 
61
        assert(op && op->hash && op->compare);
 
62
        assert(max_keys > 0);
 
63
        
 
64
        h->entry = malloc(m * sizeof(link_t));
 
65
        if (!h->entry) {
 
66
                printf("cannot allocate memory for hash table\n");
 
67
                return false;
 
68
        }
 
69
        memset((void *) h->entry, 0,  m * sizeof(link_t));
 
70
        
 
71
        for (i = 0; i < m; i++)
 
72
                list_initialize(&h->entry[i]);
 
73
        
 
74
        h->entries = m;
 
75
        h->max_keys = max_keys;
 
76
        h->op = op;
 
77
        return true;
 
78
}
 
79
 
 
80
/** Destroy a hash table instance.
 
81
 *
 
82
 * @param h             Hash table to be destroyed.
 
83
 */
 
84
void hash_table_destroy(hash_table_t *h)
 
85
{
 
86
        assert(h);
 
87
        assert(h->entry);
 
88
        free(h->entry);
 
89
}
 
90
 
 
91
/** Insert item into a hash table.
 
92
 *
 
93
 * @param h             Hash table.
 
94
 * @param key           Array of all keys necessary to compute hash index.
 
95
 * @param item          Item to be inserted into the hash table.
 
96
 */
 
97
void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
 
98
{
 
99
        hash_index_t chain;
 
100
 
 
101
        assert(item);
 
102
        assert(h && h->op && h->op->hash && h->op->compare);
 
103
 
 
104
        chain = h->op->hash(key);
 
105
        assert(chain < h->entries);
 
106
        
 
107
        list_append(item, &h->entry[chain]);
 
108
}
 
109
 
 
110
/** Search hash table for an item matching keys.
 
111
 *
 
112
 * @param h             Hash table.
 
113
 * @param key           Array of all keys needed to compute hash index.
 
114
 *
 
115
 * @return              Matching item on success, NULL if there is no such item.
 
116
 */
 
117
link_t *hash_table_find(hash_table_t *h, unsigned long key[])
 
118
{
 
119
        link_t *cur;
 
120
        hash_index_t chain;
 
121
 
 
122
        assert(h && h->op && h->op->hash && h->op->compare);
 
123
 
 
124
        chain = h->op->hash(key);
 
125
        assert(chain < h->entries);
 
126
        
 
127
        for (cur = h->entry[chain].next; cur != &h->entry[chain];
 
128
            cur = cur->next) {
 
129
                if (h->op->compare(key, h->max_keys, cur)) {
 
130
                        /*
 
131
                         * The entry is there.
 
132
                         */
 
133
                        return cur;
 
134
                }
 
135
        }
 
136
        
 
137
        return NULL;
 
138
}
 
139
 
 
140
/** Remove all matching items from hash table.
 
141
 *
 
142
 * For each removed item, h->remove_callback() is called.
 
143
 *
 
144
 * @param h             Hash table.
 
145
 * @param key           Array of keys that will be compared against items of
 
146
 *                      the hash table.
 
147
 * @param keys          Number of keys in the 'key' array.
 
148
 */
 
149
void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
 
150
{
 
151
        hash_index_t chain;
 
152
        link_t *cur;
 
153
 
 
154
        assert(h && h->op && h->op->hash && h->op->compare &&
 
155
            h->op->remove_callback);
 
156
        assert(keys <= h->max_keys);
 
157
        
 
158
        if (keys == h->max_keys) {
 
159
 
 
160
                /*
 
161
                 * All keys are known, hash_table_find() can be used to find the
 
162
                 * entry.
 
163
                 */
 
164
        
 
165
                cur = hash_table_find(h, key);
 
166
                if (cur) {
 
167
                        list_remove(cur);
 
168
                        h->op->remove_callback(cur);
 
169
                }
 
170
                return;
 
171
        }
 
172
        
 
173
        /*
 
174
         * Fewer keys were passed.
 
175
         * Any partially matching entries are to be removed.
 
176
         */
 
177
        for (chain = 0; chain < h->entries; chain++) {
 
178
                for (cur = h->entry[chain].next; cur != &h->entry[chain];
 
179
                    cur = cur->next) {
 
180
                        if (h->op->compare(key, keys, cur)) {
 
181
                                link_t *hlp;
 
182
                                
 
183
                                hlp = cur;
 
184
                                cur = cur->prev;
 
185
                                
 
186
                                list_remove(hlp);
 
187
                                h->op->remove_callback(hlp);
 
188
                                
 
189
                                continue;
 
190
                        }
 
191
                }
 
192
        }
 
193
}
 
194
 
 
195
/** @}
 
196
 */