RPA Toolkit
added long, double key support for the rmap_t.
[rpatk.git] / rlib / rmap.c
1 #include "rtypes.h"
2 #include "rmap.h"
3 #include "rstring.h"
4 #include "rmem.h"
5
6
7 typedef struct r_mapnode_s {
8         rlink_t active;
9         rlink_t hash;
10         rsize_t index;
11         rlong nbucket;
12         rstr_t *key;
13         union {
14                 rpointer p;
15                 rchar data[0];
16         } value;
17 } r_mapnode_t;
18
19
20 static rboolean r_map_rstrequal(rstr_t *key1, rstr_t *key2)
21 {
22         return (key1->size == key2->size && r_strncmp((const rchar*)key1->str, (const rchar*)key2->str, key1->size) == 0) ? TRUE : FALSE;
23 }
24
25
26 static rulong r_map_rstrhash(const rstr_t *key)
27 {
28         const rchar *str = (const rchar*) key->str;
29         rulong i;
30         rulong size = key->size;
31         rulong hash = 0;
32
33         for (i = 0; i < size; i++, str++) {
34                 hash = *str + (hash << 6) + (hash << 16) - hash;
35         }
36         return hash;
37 }
38
39 void r_mapnode_init(r_mapnode_t *node, const rchar *key, rsize_t size)
40 {
41         node->key = r_rstrdup(key, size);
42         r_list_init(&node->active);
43         r_list_init(&node->hash);
44 }
45
46
47 r_mapnode_t *r_map_getfreenode(rmap_t *map, const rchar *key, rsize_t size)
48 {
49         r_mapnode_t *node = NULL;
50
51         if (r_list_empty(&map->inactive)) {
52                 rlong index = r_carray_add(map->data, NULL);
53                 node = (r_mapnode_t*)r_carray_slot(map->data, index);
54                 r_mapnode_init(node, key, size);
55                 node->index = index;
56         } else {
57                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
58                 r_list_del(&node->active);
59                 r_mapnode_init(node, key, size);
60         }
61         return node;
62 }
63
64
65 robject_t *r_map_copy(const robject_t *obj)
66 {
67         return (robject_t*)NULL;
68 }
69
70
71 void r_map_cleanup(robject_t *obj)
72 {
73         r_mapnode_t *node;
74         rmap_t *map = (rmap_t*)obj;
75
76         while (!r_list_empty(&map->active)) {
77                 node = r_list_entry(r_list_first(&map->active), r_mapnode_t, active);
78                 r_free(node->key);
79                 r_list_del(&node->active);
80         }
81         while (!r_list_empty(&map->inactive)) {
82                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
83                 r_free(node->key);
84                 r_list_del(&node->active);
85         }
86
87         r_carray_destroy(map->data);
88         r_free(map->hash);
89         r_object_cleanup(&map->obj);
90 }
91
92
93 robject_t *r_map_init(robject_t *obj, ruint32 type, r_object_cleanupfun cleanup, r_object_copyfun copy, ruint elt_size, ruint nbits)
94 {
95         rsize_t elt_realsize = R_SIZE_ALIGN(elt_size + sizeof(r_mapnode_t), sizeof(rword));
96         rsize_t hashsize, i;
97         rmap_t *map = (rmap_t*)obj;
98         if (nbits == 0 || nbits > 16) {
99                 R_ASSERT(0);
100                 return NULL;
101         }
102         r_object_init(obj, type, cleanup, copy);
103         map->data = r_carray_create(elt_realsize);
104         map->nbits = nbits;
105         map->elt_size = elt_size;
106         r_list_init(&map->active);
107         r_list_init(&map->inactive);
108         hashsize = r_map_hashsize(map);
109         map->hash = (rlist_t*)r_malloc(sizeof(rlist_t) * hashsize);
110         R_ASSERT(map->hash);
111         for (i = 0; i < hashsize; i++) {
112                 r_list_init(&map->hash[i]);
113         }
114
115         return obj;
116 }
117
118 rmap_t *r_map_create(ruint elt_size, ruint nbits)
119 {
120         rmap_t *map;
121         map = (rmap_t*)r_object_create(sizeof(*map));
122         r_map_init((robject_t*)map, R_OBJECT_MAP, r_map_cleanup, r_map_copy, elt_size, nbits);
123         return map;
124
125 }
126
127
128 void r_map_destroy(rmap_t *map)
129 {
130         r_object_destroy((robject_t*)map);
131 }
132
133
134 rlong r_map_add(rmap_t *map, const rchar *name, rsize_t namesize, rconstpointer pval)
135 {
136         r_mapnode_t *node;
137
138         node = r_map_getfreenode(map, name, namesize);
139         if (pval)
140                 r_memcpy(node->value.data, pval, map->elt_size);
141         node->nbucket = (r_map_rstrhash(node->key) & r_map_hashmask(map));
142         r_list_addt(&map->hash[node->nbucket], &node->hash);
143         r_list_addt(&map->active, &node->active);
144         return node->index;
145 }
146
147
148 rlong r_map_add_s(rmap_t *map, const rchar *name, rconstpointer pval)
149 {
150         return r_map_add(map, name, r_strlen(name), pval);
151 }
152
153
154 rlong r_map_add_l(rmap_t *map, long name, rconstpointer pval)
155 {
156         rchar key[128];
157         r_memset(key, 0, sizeof(key));
158         r_snprintf(key, sizeof(key) - 1, "%ld", name);
159         return r_map_add_s(map, key, pval);
160 }
161
162
163 rlong r_map_add_d(rmap_t *map, double name, rconstpointer pval)
164 {
165         rchar key[128];
166         r_memset(key, 0, sizeof(key));
167         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
168         return r_map_add_s(map, key, pval);
169 }
170
171
172 r_mapnode_t *r_map_node(rmap_t *map, rulong index)
173 {
174         r_mapnode_t *node;
175         if (index >= r_carray_length(map->data))
176                 return NULL;
177         node = (r_mapnode_t*)r_carray_slot(map->data, index);
178         if (r_list_empty(&node->hash))
179                 return NULL;
180         return node;
181 }
182
183
184 const rchar *r_map_key(rmap_t *map, rulong index)
185 {
186         r_mapnode_t *node = r_map_node(map, index);
187         if (!node)
188                 return NULL;
189         return node->key->str;
190 }
191
192
193 rpointer r_map_value(rmap_t *map, rulong index)
194 {
195         r_mapnode_t *node = r_map_node(map, index);
196         if (!node)
197                 return NULL;
198         return (rpointer)node->value.data;
199 }
200
201
202 rlong r_map_setvalue(rmap_t *map, rlong index, rconstpointer pval)
203 {
204         r_mapnode_t *node = r_map_node(map, index);
205         if (!node)
206                 return -1;
207         r_memcpy(node->value.data, pval, map->elt_size);
208         return index;
209 }
210
211
212 rint r_map_delete(rmap_t *map, rulong index)
213 {
214         r_mapnode_t *node = r_map_node(map, index);
215         if (!node)
216                 return -1;
217         r_free(node->key);
218         node->key = NULL;
219         r_list_del(&node->hash);
220         r_list_init(&node->hash);
221         r_list_del(&node->active);
222         r_list_addt(&map->inactive, &node->active);
223         return 0;
224 }
225
226
227 rlong r_map_lookup(rmap_t *map, rlong current, const rchar *name, rsize_t namesize)
228 {
229         rlong found = -1;
230         r_mapnode_t *node;
231         rstr_t lookupstr = {(char*)name, namesize};
232         rulong nbucket;
233         rhead_t *bucket;
234         rlink_t *pos;
235
236         if (current >= 0) {
237                 r_mapnode_t *curnode = r_map_node(map, current);
238                 if (!curnode)
239                         return -1;
240                 nbucket = curnode->nbucket;
241                 bucket = &map->hash[nbucket];
242                 pos = r_list_next(bucket, &curnode->hash);
243         } else {
244                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
245                 bucket = &map->hash[nbucket];
246                 pos = r_list_first(bucket);
247         }
248         for ( ; pos ; pos = r_list_next(bucket, pos)) {
249                 node = r_list_entry(pos, r_mapnode_t, hash);
250                 if (r_map_rstrequal(node->key, &lookupstr)) {
251                         found = node->index;
252                         break;
253                 }
254         }
255
256         return (rlong)found;
257 }
258
259
260 rlong r_map_lookup_s(rmap_t *map, rlong current, const rchar *name)
261 {
262         return r_map_lookup(map, current, name, r_strlen(name));
263 }
264
265
266 rlong r_map_lookup_l(rmap_t *map, rlong current, long name)
267 {
268         rchar key[128];
269         r_memset(key, 0, sizeof(key));
270         r_snprintf(key, sizeof(key) - 1, "%ld", name);
271         return r_map_lookup_s(map, current, key);
272 }
273
274
275 rlong r_map_lookup_d(rmap_t *map, rlong current, double name)
276 {
277         rchar key[128];
278         r_memset(key, 0, sizeof(key));
279         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
280         return r_map_lookup_s(map, current, key);
281 }
282
283
284 rlong r_map_taillookup(rmap_t *map, rlong current, const rchar *name, rsize_t namesize)
285 {
286         rlong found = -1;
287         r_mapnode_t *node;
288         rstr_t lookupstr = {(char*)name, namesize};
289         rulong nbucket;
290         rhead_t *bucket;
291         rlink_t *pos;
292
293         if (current >= 0) {
294                 r_mapnode_t *curnode = r_map_node(map, current);
295                 if (!curnode)
296                         return -1;
297                 nbucket = curnode->nbucket;
298                 bucket = &map->hash[nbucket];
299                 pos = r_list_prev(bucket, &curnode->hash);
300         } else {
301                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
302                 bucket = &map->hash[nbucket];
303                 pos = r_list_last(bucket);
304         }
305         for ( ; pos ; pos = r_list_prev(bucket, pos)) {
306                 node = r_list_entry(pos, r_mapnode_t, hash);
307                 if (r_map_rstrequal(node->key, &lookupstr)) {
308                         found = node->index;
309                         break;
310                 }
311         }
312
313         return (rlong)found;
314 }
315
316
317 rlong r_map_taillookup_s(rmap_t *map, rlong current, const rchar *name)
318 {
319         return r_map_taillookup(map, current, name, r_strlen(name));
320 }
321
322
323 rlong r_map_first(rmap_t *map)
324 {
325         r_mapnode_t *node;
326         rlink_t *pos = r_list_first(&map->active);
327
328         if (!pos)
329                 return -1;
330         node = r_list_entry(pos, r_mapnode_t, active);
331         return node->index;
332 }
333
334
335 rlong r_map_last(rmap_t *map)
336 {
337         r_mapnode_t *node;
338         rlink_t *pos = r_list_last(&map->active);
339
340         if (!pos)
341                 return -1;
342         node = r_list_entry(pos, r_mapnode_t, active);
343         return node->index;
344 }
345
346
347 rlong r_map_next(rmap_t *map, rlong current)
348 {
349         r_mapnode_t *node = r_map_node(map, current);
350         rlink_t *pos;
351
352         if (!node)
353                 return -1;
354         pos = r_list_next(&map->active, &node->active);
355         if (!pos)
356                 return -1;
357         node = r_list_entry(pos, r_mapnode_t, active);
358         return node->index;
359 }
360
361
362 rlong r_map_prev(rmap_t *map, rlong current)
363 {
364         r_mapnode_t *node = r_map_node(map, current);
365         rlink_t *pos;
366
367         if (!node)
368                 return -1;
369         pos = r_list_prev(&map->active, &node->active);
370         if (!pos)
371                 return -1;
372         node = r_list_entry(pos, r_mapnode_t, active);
373         return node->index;
374 }