1 /**
2 * @file hash.c Hashmap table
3 *
4 * Copyright (C) 2010 Creytiv.com
5 */
6 #include <re_types.h>
7 #include <re_mem.h>
8 #include <re_mbuf.h>
9 #include <re_list.h>
10 #include <re_hash.h>
11
12
13 /** Defines a hashmap table */
14 struct hash {
15 struct list *bucket; /**< Bucket with linked lists */
16 uint32_t bsize; /**< Bucket size */
17 };
18
19
hash_destructor(void * data)20 static void hash_destructor(void *data)
21 {
22 struct hash *h = data;
23
24 mem_deref(h->bucket);
25 }
26
27
28 /**
29 * Allocate a new hashmap table
30 *
31 * @param hp Address of hashmap pointer
32 * @param bsize Bucket size
33 *
34 * @return 0 if success, otherwise errorcode
35 */
hash_alloc(struct hash ** hp,uint32_t bsize)36 int hash_alloc(struct hash **hp, uint32_t bsize)
37 {
38 struct hash *h;
39 int err = 0;
40
41 if (!hp || !bsize)
42 return EINVAL;
43
44 /* Validate bucket size */
45 if (bsize & (bsize-1))
46 return EINVAL;
47
48 h = mem_zalloc(sizeof(*h), hash_destructor);
49 if (!h)
50 return ENOMEM;
51
52 h->bsize = bsize;
53
54 h->bucket = mem_zalloc(bsize*sizeof(*h->bucket), NULL);
55 if (!h->bucket) {
56 err = ENOMEM;
57 goto out;
58 }
59
60 out:
61 if (err)
62 mem_deref(h);
63 else
64 *hp = h;
65
66 return err;
67 }
68
69
70 /**
71 * Add an element to the hashmap table
72 *
73 * @param h Hashmap table
74 * @param key Hash key
75 * @param le List element
76 * @param data Element data
77 */
hash_append(struct hash * h,uint32_t key,struct le * le,void * data)78 void hash_append(struct hash *h, uint32_t key, struct le *le, void *data)
79 {
80 if (!h || !le)
81 return;
82
83 list_append(&h->bucket[key & (h->bsize-1)], le, data);
84 }
85
86
87 /**
88 * Unlink an element from the hashmap table
89 *
90 * @param le List element
91 */
hash_unlink(struct le * le)92 void hash_unlink(struct le *le)
93 {
94 list_unlink(le);
95 }
96
97
98 /**
99 * Apply a handler function to all elements in the hashmap with a matching key
100 *
101 * @param h Hashmap table
102 * @param key Hash key
103 * @param ah Apply handler
104 * @param arg Handler argument
105 *
106 * @return List element if traversing stopped, otherwise NULL
107 */
hash_lookup(const struct hash * h,uint32_t key,list_apply_h * ah,void * arg)108 struct le *hash_lookup(const struct hash *h, uint32_t key, list_apply_h *ah,
109 void *arg)
110 {
111 if (!h || !ah)
112 return NULL;
113
114 return list_apply(&h->bucket[key & (h->bsize-1)], true, ah, arg);
115 }
116
117
118 /**
119 * Apply a handler function to all elements in the hashmap
120 *
121 * @param h Hashmap table
122 * @param ah Apply handler
123 * @param arg Handler argument
124 *
125 * @return List element if traversing stopped, otherwise NULL
126 */
hash_apply(const struct hash * h,list_apply_h * ah,void * arg)127 struct le *hash_apply(const struct hash *h, list_apply_h *ah, void *arg)
128 {
129 struct le *le = NULL;
130 uint32_t i;
131
132 if (!h || !ah)
133 return NULL;
134
135 for (i=0; (i<h->bsize) && !le; i++)
136 le = list_apply(&h->bucket[i], true, ah, arg);
137
138 return le;
139 }
140
141
142 /**
143 * Return bucket list for a given index
144 *
145 * @param h Hashmap table
146 * @param key Hash key
147 *
148 * @return Bucket list if valid input, otherwise NULL
149 */
hash_list(const struct hash * h,uint32_t key)150 struct list *hash_list(const struct hash *h, uint32_t key)
151 {
152 return h ? &h->bucket[key & (h->bsize - 1)] : NULL;
153 }
154
155
156 /**
157 * Get hash bucket size
158 *
159 * @param h Hashmap table
160 *
161 * @return hash bucket size
162 */
hash_bsize(const struct hash * h)163 uint32_t hash_bsize(const struct hash *h)
164 {
165 return h ? h->bsize : 0;
166 }
167
168
169 /**
170 * Flush a hashmap and free all elements
171 *
172 * @param h Hashmap table
173 */
hash_flush(struct hash * h)174 void hash_flush(struct hash *h)
175 {
176 uint32_t i;
177
178 if (!h)
179 return;
180
181 for (i=0; i<h->bsize; i++)
182 list_flush(&h->bucket[i]);
183 }
184
185
186 /**
187 * Clear a hashmap without dereferencing the elements
188 *
189 * @param h Hashmap table
190 */
hash_clear(struct hash * h)191 void hash_clear(struct hash *h)
192 {
193 uint32_t i;
194
195 if (!h)
196 return;
197
198 for (i=0; i<h->bsize; i++)
199 list_clear(&h->bucket[i]);
200 }
201
202
203 /**
204 * Calculate a valid hash size from a random size
205 *
206 * @param size Requested size
207 *
208 * @return Valid hash size
209 */
hash_valid_size(uint32_t size)210 uint32_t hash_valid_size(uint32_t size)
211 {
212 uint32_t x;
213
214 for (x=0; (uint32_t)1<<x < size && x < 31; x++)
215 ;
216
217 return 1<<x;
218 }
219