RPA Toolkit
work on RJS object introspection.
[rpatk.git] / rlib / rmap.c
1 /*
2  *  Regular Pattern Analyzer (RPA)
3  *  Copyright (c) 2009-2010 Martin Stoilov
4  *
5  *  This program is free software: you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation, either version 3 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  *
18  *  Martin Stoilov <martin@rpasearch.com>
19  */
20
21 #include "rtypes.h"
22 #include "rlib/rmap.h"
23 #include "rlib/rstring.h"
24 #include "rlib/rmem.h"
25
26
27 typedef struct r_mapnode_s {
28         rlink_t active;
29         rlink_t hash;
30         rstring_t *key;
31         unsigned long index;
32         unsigned long nbucket;
33         union {
34                 rpointer p;
35                 char data[0];
36         } value;
37 } r_mapnode_t;
38
39
40 static rboolean r_map_rstrequal(rstr_t *key1, rstr_t *key2)
41 {
42         return (key1->size == key2->size && r_strncmp((const char*)key1->str, (const char*)key2->str, key1->size) == 0) ? TRUE : FALSE;
43 }
44
45
46 static unsigned long r_map_rstrhash(const rstr_t *key)
47 {
48         const char *str = (const char*) key->str;
49         unsigned long i;
50         unsigned long size = key->size;
51         unsigned long hash = 0;
52
53         for (i = 0; i < size; i++, str++) {
54                 hash = *str + (hash << 6) + (hash << 16) - hash;
55         }
56         return hash;
57 }
58
59 void r_mapnode_init(r_mapnode_t *node, const char *key, unsigned long size)
60 {
61 //      node->key = r_rstrdup(key, size);
62         node->key = r_string_create_strsize(key, size);
63         r_list_init(&node->active);
64         r_list_init(&node->hash);
65 }
66
67
68 r_mapnode_t *r_map_getfreenode(rmap_t *map, const char *key, unsigned long size)
69 {
70         r_mapnode_t *node = NULL;
71
72         if (r_list_empty(&map->inactive)) {
73                 long index = r_carray_add(map->data, NULL);
74                 node = (r_mapnode_t*)r_carray_slot(map->data, index);
75                 r_mapnode_init(node, key, size);
76                 node->index = index;
77         } else {
78                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
79                 r_list_del(&node->active);
80                 r_mapnode_init(node, key, size);
81         }
82         return node;
83 }
84
85
86 robject_t *r_map_copy(const robject_t *obj)
87 {
88         return (robject_t*)NULL;
89 }
90
91
92 void r_map_cleanup(robject_t *obj)
93 {
94         r_mapnode_t *node;
95         rmap_t *map = (rmap_t*)obj;
96
97         while (!r_list_empty(&map->active)) {
98                 node = r_list_entry(r_list_first(&map->active), r_mapnode_t, active);
99                 if (!r_object_gcget((robject_t*)node->key))
100                         r_string_destroy(node->key);
101                 r_list_del(&node->active);
102         }
103         while (!r_list_empty(&map->inactive)) {
104                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
105                 r_list_del(&node->active);
106         }
107
108         r_carray_destroy(map->data);
109         r_free(map->hash);
110         r_object_cleanup(&map->obj);
111 }
112
113
114 robject_t *r_map_init(robject_t *obj, ruint32 type, r_object_cleanupfun cleanup, r_object_copyfun copy, unsigned int elt_size, unsigned int nbits)
115 {
116         unsigned long elt_realsize = R_SIZE_ALIGN(elt_size + sizeof(r_mapnode_t), sizeof(ruword));
117         unsigned long hashsize, i;
118         rmap_t *map = (rmap_t*)obj;
119         if (nbits == 0 || nbits > 16) {
120                 R_ASSERT(0);
121                 return NULL;
122         }
123         r_object_init(obj, type, cleanup, copy);
124         map->data = r_carray_create(elt_realsize);
125         map->nbits = nbits;
126         map->elt_size = elt_size;
127         r_list_init(&map->active);
128         r_list_init(&map->inactive);
129         hashsize = r_map_hashsize(map);
130         map->hash = (rlist_t*)r_malloc(sizeof(rlist_t) * hashsize);
131         R_ASSERT(map->hash);
132         for (i = 0; i < hashsize; i++) {
133                 r_list_init(&map->hash[i]);
134         }
135         return obj;
136 }
137
138 rmap_t *r_map_create(unsigned int elt_size, unsigned int nbits)
139 {
140         rmap_t *map;
141         map = (rmap_t*)r_object_create(sizeof(*map));
142         r_map_init((robject_t*)map, R_OBJECT_MAP, r_map_cleanup, r_map_copy, elt_size, nbits);
143         return map;
144
145 }
146
147
148 void r_map_destroy(rmap_t *map)
149 {
150         r_object_destroy((robject_t*)map);
151 }
152
153
154 long r_map_gckey_add(rmap_t *map, rgc_t* gc, const char *name, unsigned int namesize, rconstpointer pval)
155 {
156         r_mapnode_t *node;
157
158         node = r_map_getfreenode(map, name, namesize);
159         if (pval)
160                 r_memcpy(node->value.data, pval, map->elt_size);
161         node->nbucket = (r_map_rstrhash(R_STRING2RSTR(node->key)) & r_map_hashmask(map));
162         r_list_addt(&map->hash[node->nbucket], &node->hash);
163         r_list_addt(&map->active, &node->active);
164         if (gc)
165                 r_gc_add(gc, (robject_t*)node->key);
166         return node->index;
167 }
168
169
170 long r_map_gckey_add_s(rmap_t *map, rgc_t* gc, const char *name, rconstpointer pval)
171 {
172         return r_map_gckey_add(map, gc, name, r_strlen(name), pval);
173 }
174
175
176 long r_map_gckey_add_d(rmap_t *map, rgc_t* gc, double name, rconstpointer pval)
177 {
178         char key[128];
179         r_memset(key, 0, sizeof(key));
180         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
181         return r_map_gckey_add_s(map, gc, key, pval);
182 }
183
184
185 long r_map_gckey_add_l(rmap_t *map, rgc_t* gc, long name, rconstpointer pval)
186 {
187         char key[128];
188         r_memset(key, 0, sizeof(key));
189         r_snprintf(key, sizeof(key) - 1, "%ld", name);
190         return r_map_gckey_add_s(map, gc, key, pval);
191 }
192
193
194 long r_map_add(rmap_t *map, const char *name, unsigned int namesize, rconstpointer pval)
195 {
196         return r_map_gckey_add(map, NULL, name, namesize, pval);
197 }
198
199
200 long r_map_add_s(rmap_t *map, const char *name, rconstpointer pval)
201 {
202         return r_map_gckey_add_s(map, NULL, name, pval);
203 }
204
205
206 long r_map_add_l(rmap_t *map, long name, rconstpointer pval)
207 {
208         return r_map_gckey_add_l(map, NULL, name, pval);
209 }
210
211
212 long r_map_add_d(rmap_t *map, double name, rconstpointer pval)
213 {
214         return r_map_gckey_add_d(map, NULL, name, pval);
215 }
216
217
218 r_mapnode_t *r_map_node(rmap_t *map, unsigned long index)
219 {
220         r_mapnode_t *node;
221         if (index >= r_carray_length(map->data))
222                 return NULL;
223         node = (r_mapnode_t*)r_carray_slot(map->data, index);
224         if (r_list_empty(&node->hash))
225                 return NULL;
226         return node;
227 }
228
229
230 rstring_t *r_map_key(rmap_t *map, unsigned long index)
231 {
232         r_mapnode_t *node = r_map_node(map, index);
233         if (!node)
234                 return NULL;
235         return node->key;
236 }
237
238
239 rpointer r_map_value(rmap_t *map, unsigned long index)
240 {
241         r_mapnode_t *node = r_map_node(map, index);
242         if (!node)
243                 return NULL;
244         return (rpointer)node->value.data;
245 }
246
247
248 long r_map_setvalue(rmap_t *map, long index, rconstpointer pval)
249 {
250         r_mapnode_t *node = r_map_node(map, index);
251         if (!node)
252                 return -1;
253         r_memcpy(node->value.data, pval, map->elt_size);
254         return index;
255 }
256
257
258 int r_map_delete(rmap_t *map, unsigned long index)
259 {
260         r_mapnode_t *node = r_map_node(map, index);
261         if (!node)
262                 return -1;
263         if (!r_object_gcget((robject_t*)node->key))
264                 r_string_destroy(node->key);
265         node->key = NULL;
266         r_list_del(&node->hash);
267         r_list_init(&node->hash);
268         r_list_del(&node->active);
269         r_list_addt(&map->inactive, &node->active);
270         return 0;
271 }
272
273
274 long r_map_lookup(rmap_t *map, long current, const char *name, unsigned int namesize)
275 {
276         long found = -1;
277         r_mapnode_t *node;
278         rstr_t lookupstr = {(char*)name, namesize};
279         unsigned long nbucket;
280         rhead_t *bucket;
281         rlink_t *pos;
282
283         if (current >= 0) {
284                 r_mapnode_t *curnode = r_map_node(map, current);
285                 if (!curnode)
286                         return -1;
287                 nbucket = curnode->nbucket;
288                 bucket = &map->hash[nbucket];
289                 pos = r_list_next(bucket, &curnode->hash);
290         } else {
291                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
292                 bucket = &map->hash[nbucket];
293                 pos = r_list_first(bucket);
294         }
295         for ( ; pos ; pos = r_list_next(bucket, pos)) {
296                 node = r_list_entry(pos, r_mapnode_t, hash);
297                 if (r_map_rstrequal(R_STRING2RSTR(node->key), &lookupstr)) {
298                         found = node->index;
299                         break;
300                 }
301         }
302
303         return (long)found;
304 }
305
306
307 long r_map_lookup_s(rmap_t *map, long current, const char *name)
308 {
309         return r_map_lookup(map, current, name, r_strlen(name));
310 }
311
312
313 long r_map_lookup_l(rmap_t *map, long current, long name)
314 {
315         char key[128];
316         r_memset(key, 0, sizeof(key));
317         r_snprintf(key, sizeof(key) - 1, "%ld", name);
318         return r_map_lookup_s(map, current, key);
319 }
320
321
322 long r_map_lookup_d(rmap_t *map, long current, double name)
323 {
324         char key[128];
325         r_memset(key, 0, sizeof(key));
326         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
327         return r_map_lookup_s(map, current, key);
328 }
329
330
331 long r_map_taillookup(rmap_t *map, long current, const char *name, unsigned int namesize)
332 {
333         long found = -1;
334         r_mapnode_t *node;
335         rstr_t lookupstr = {(char*)name, namesize};
336         unsigned long nbucket;
337         rhead_t *bucket;
338         rlink_t *pos;
339
340         if (current >= 0) {
341                 r_mapnode_t *curnode = r_map_node(map, current);
342                 if (!curnode)
343                         return -1;
344                 nbucket = curnode->nbucket;
345                 bucket = &map->hash[nbucket];
346                 pos = r_list_prev(bucket, &curnode->hash);
347         } else {
348                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
349                 bucket = &map->hash[nbucket];
350                 pos = r_list_last(bucket);
351         }
352         for ( ; pos ; pos = r_list_prev(bucket, pos)) {
353                 node = r_list_entry(pos, r_mapnode_t, hash);
354                 if (r_map_rstrequal(R_STRING2RSTR(node->key), &lookupstr)) {
355                         found = node->index;
356                         break;
357                 }
358         }
359
360         return (long)found;
361 }
362
363
364 long r_map_taillookup_s(rmap_t *map, long current, const char *name)
365 {
366         return r_map_taillookup(map, current, name, r_strlen(name));
367 }
368
369
370 long r_map_first(rmap_t *map)
371 {
372         r_mapnode_t *node;
373         rlink_t *pos = r_list_first(&map->active);
374
375         if (!pos)
376                 return -1;
377         node = r_list_entry(pos, r_mapnode_t, active);
378         return node->index;
379 }
380
381
382 long r_map_last(rmap_t *map)
383 {
384         r_mapnode_t *node;
385         rlink_t *pos = r_list_last(&map->active);
386
387         if (!pos)
388                 return -1;
389         node = r_list_entry(pos, r_mapnode_t, active);
390         return node->index;
391 }
392
393
394 long r_map_next(rmap_t *map, long current)
395 {
396         r_mapnode_t *node = r_map_node(map, current);
397         rlink_t *pos;
398
399         if (!node)
400                 return -1;
401         pos = r_list_next(&map->active, &node->active);
402         if (!pos)
403                 return -1;
404         node = r_list_entry(pos, r_mapnode_t, active);
405         return node->index;
406 }
407
408
409 long r_map_prev(rmap_t *map, long current)
410 {
411         r_mapnode_t *node = r_map_node(map, current);
412         rlink_t *pos;
413
414         if (!node)
415                 return -1;
416         pos = r_list_prev(&map->active, &node->active);
417         if (!pos)
418                 return -1;
419         node = r_list_entry(pos, r_mapnode_t, active);
420         return node->index;
421 }