RPA Toolkit
e49118815ba9756bc824b9620620bd4f8d066775
[rpatk.git] / rlib / rhash.c
1 #include "rmem.h"
2 #include "rstring.h"
3 #include "rhash.h"
4
5
6 typedef struct rhash_node_s {
7         rlink_t lnk;
8         rconstpointer key;
9         rpointer value;
10 } rhash_node_t;
11
12
13 static rhash_node_t *r_hash_node_create()
14 {
15         rhash_node_t *node;
16
17         return (rhash_node_t *)r_malloc(sizeof(*node));
18 }
19
20
21 static void r_hash_node_destroy(rhash_node_t *node)
22 {
23         r_free(node);
24 }
25
26
27 static rhash_node_t *r_hash_node_lookup(rhash_t* hash, rconstpointer key)
28 {
29         ruint nbucket = hash->hfunc(key) & r_hash_mask(hash);
30         rhash_node_t *node;
31         rlink_t *pos;
32
33         r_list_foreach(pos, &hash->buckets[nbucket]) {
34                 node = r_list_entry(pos, rhash_node_t, lnk);
35                 if (hash->eqfunc(node->key, key)) {
36                         return node;
37                 }
38         }
39         return NULL;
40 }
41
42
43 ruint r_hash_strhash(rconstpointer key)
44 {
45         const rchar *str = (const rchar*) key;
46         ruint hash = 0;
47         int c;
48
49         while ((c = *str++))
50                 hash = c + (hash << 6) + (hash << 16) - hash;
51         return hash;
52 }
53
54
55 rboolean r_hash_strequal(rconstpointer key1, rconstpointer key2)
56 {
57         return r_strcmp((const rchar*)key1, (const rchar*)key2) ? FALSE : TRUE;
58 }
59
60
61 ruint r_hash_strnhash(rconstpointer key)
62 {
63         const rstring_t *k = (const rstring_t *)key;
64         const rchar *str = (const rchar*) k->str;
65         ruint i;
66         ruint size = k->size;
67         ruint hash = 0;
68
69         for (i = 0; i < size; i++, str++) {
70                 hash = *str + (hash << 6) + (hash << 16) - hash;
71         }
72         return hash;
73 }
74
75
76 rboolean r_hash_strnequal(rconstpointer key1, rconstpointer key2)
77 {
78         const rstring_t *k1 = (const rstring_t *)key1;
79         const rstring_t *k2 = (const rstring_t *)key2;
80
81         return (k1->size == k2->size && r_strncmp((const rchar*)k1->str, (const rchar*)k2->str, k1->size) == 0) ? TRUE : FALSE;
82 }
83
84
85 rhash_t *r_hash_create(ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfunc)
86 {
87         rhash_t *hash;
88
89         hash = (rhash_t*)r_malloc(sizeof(*hash));
90         if (!hash)
91                 return NULL;
92         r_memset(hash, 0, sizeof(*hash));
93         if (!r_hash_init(hash, nbits, eqfunc, hfunc)) {
94                 r_hash_destroy(hash);
95                 return NULL;
96         }
97         return hash;
98 }
99
100
101 static void r_ref_destroy(rref_t *ref)
102 {
103         r_hash_destroy((rhash_t*)ref);
104 }
105
106
107 rhash_t *r_hash_init(rhash_t *hash, ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfunc)
108 {
109         ruint i;
110         rsize_t size;
111
112         r_ref_init(&hash->ref, 1, RREF_TYPE_NONE, r_ref_destroy);
113         hash->nbits = nbits;
114         hash->eqfunc = eqfunc;
115         hash->hfunc = hfunc;
116         hash->buckets = (rlist_t*)r_malloc(sizeof(rlist_t) * r_hash_size(hash));
117         if (!hash->buckets)
118                 return NULL;
119         size = r_hash_size(hash);
120         for (i = 0; i < size; i++) {
121                 r_list_init(&hash->buckets[i]);
122         }
123         return hash;
124 }
125
126
127 void r_hash_destroy(rhash_t *hash)
128 {
129         r_hash_cleanup(hash);
130         r_free(hash);
131 }
132
133
134 void r_hash_cleanup(rhash_t *hash)
135 {
136         r_hash_removeall(hash);
137         r_free(hash->buckets);
138 }
139
140
141 void r_hash_insert(rhash_t* hash, rconstpointer key, rpointer value)
142 {
143         ruint nbucket = hash->hfunc(key) & r_hash_mask(hash);
144         rhash_node_t *node = r_hash_node_create();
145         rhead_t *buckethead = &hash->buckets[nbucket];
146         if (node) {
147                 r_list_init(&node->lnk);
148                 node->key = key;
149                 node->value = value;
150         }
151         r_list_addt(buckethead, &node->lnk);
152
153 }
154
155
156 void r_hash_remove(rhash_t* hash, rconstpointer key)
157 {
158         rhash_node_t *node;
159
160         while ((node = r_hash_node_lookup(hash, key)) != NULL) {
161                 r_list_del(&node->lnk);
162                 r_hash_node_destroy(node);
163         }
164 }
165
166
167 void r_hash_removeall(rhash_t* hash)
168 {
169         ruint nbucket;
170         rhead_t *head;
171         rhash_node_t *node;
172
173         for (nbucket = 0; nbucket < r_hash_size(hash); nbucket++) {
174                 head = &hash->buckets[nbucket];
175                 while (!r_list_empty(head)) {
176                         node = r_list_entry(r_list_first(head), rhash_node_t, lnk);
177                         r_list_del(&node->lnk);
178                         r_hash_node_destroy(node);
179                 }
180         }
181 }
182
183
184 rpointer r_hash_lookup(rhash_t* hash, rconstpointer key)
185 {
186         rhash_node_t *node = r_hash_node_lookup(hash, key);
187         if (node)
188                 return node->value;
189         return NULL;
190 }