RPA Toolkit
used types cleaned up... -4
[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         rsize_t index;
31         long nbucket;
32         rstring_t *key;
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, rsize_t 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, rsize_t 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                 if (!r_object_gcget((robject_t*)node->key))
106                         r_string_destroy(node->key);
107                 r_list_del(&node->active);
108         }
109
110         r_carray_destroy(map->data);
111         r_free(map->hash);
112         r_object_cleanup(&map->obj);
113 }
114
115
116 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)
117 {
118         rsize_t elt_realsize = R_SIZE_ALIGN(elt_size + sizeof(r_mapnode_t), sizeof(ruword));
119         rsize_t hashsize, i;
120         rmap_t *map = (rmap_t*)obj;
121         if (nbits == 0 || nbits > 16) {
122                 R_ASSERT(0);
123                 return NULL;
124         }
125         r_object_init(obj, type, cleanup, copy);
126         map->data = r_carray_create(elt_realsize);
127         map->nbits = nbits;
128         map->elt_size = elt_size;
129         r_list_init(&map->active);
130         r_list_init(&map->inactive);
131         hashsize = r_map_hashsize(map);
132         map->hash = (rlist_t*)r_malloc(sizeof(rlist_t) * hashsize);
133         R_ASSERT(map->hash);
134         for (i = 0; i < hashsize; i++) {
135                 r_list_init(&map->hash[i]);
136         }
137
138         return obj;
139 }
140
141 rmap_t *r_map_create(unsigned int elt_size, unsigned int nbits)
142 {
143         rmap_t *map;
144         map = (rmap_t*)r_object_create(sizeof(*map));
145         r_map_init((robject_t*)map, R_OBJECT_MAP, r_map_cleanup, r_map_copy, elt_size, nbits);
146         return map;
147
148 }
149
150
151 void r_map_destroy(rmap_t *map)
152 {
153         r_object_destroy((robject_t*)map);
154 }
155
156
157 long r_map_gckey_add(rmap_t *map, rgc_t* gc, const char *name, unsigned int namesize, rconstpointer pval)
158 {
159         r_mapnode_t *node;
160
161         node = r_map_getfreenode(map, name, namesize);
162         if (pval)
163                 r_memcpy(node->value.data, pval, map->elt_size);
164         node->nbucket = (r_map_rstrhash(R_STRING2RSTR(node->key)) & r_map_hashmask(map));
165         r_list_addt(&map->hash[node->nbucket], &node->hash);
166         r_list_addt(&map->active, &node->active);
167         if (gc)
168                 r_gc_add(gc, (robject_t*)node->key);
169         return node->index;
170 }
171
172
173 long r_map_gckey_add_s(rmap_t *map, rgc_t* gc, const char *name, rconstpointer pval)
174 {
175         return r_map_gckey_add(map, gc, name, r_strlen(name), pval);
176 }
177
178
179 long r_map_gckey_add_d(rmap_t *map, rgc_t* gc, double name, rconstpointer pval)
180 {
181         char key[128];
182         r_memset(key, 0, sizeof(key));
183         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
184         return r_map_gckey_add_s(map, gc, key, pval);
185 }
186
187
188 long r_map_gckey_add_l(rmap_t *map, rgc_t* gc, long name, rconstpointer pval)
189 {
190         char key[128];
191         r_memset(key, 0, sizeof(key));
192         r_snprintf(key, sizeof(key) - 1, "%ld", name);
193         return r_map_gckey_add_s(map, gc, key, pval);
194 }
195
196
197 long r_map_add(rmap_t *map, const char *name, unsigned int namesize, rconstpointer pval)
198 {
199         return r_map_gckey_add(map, NULL, name, namesize, pval);
200 }
201
202
203 long r_map_add_s(rmap_t *map, const char *name, rconstpointer pval)
204 {
205         return r_map_gckey_add_s(map, NULL, name, pval);
206 }
207
208
209 long r_map_add_l(rmap_t *map, long name, rconstpointer pval)
210 {
211         return r_map_gckey_add_l(map, NULL, name, pval);
212 }
213
214
215 long r_map_add_d(rmap_t *map, double name, rconstpointer pval)
216 {
217         return r_map_gckey_add_d(map, NULL, name, pval);
218 }
219
220
221 r_mapnode_t *r_map_node(rmap_t *map, unsigned long index)
222 {
223         r_mapnode_t *node;
224         if (index >= r_carray_length(map->data))
225                 return NULL;
226         node = (r_mapnode_t*)r_carray_slot(map->data, index);
227         if (r_list_empty(&node->hash))
228                 return NULL;
229         return node;
230 }
231
232
233 rstring_t *r_map_key(rmap_t *map, unsigned long index)
234 {
235         r_mapnode_t *node = r_map_node(map, index);
236         if (!node)
237                 return NULL;
238         return node->key;
239 }
240
241
242 rpointer r_map_value(rmap_t *map, unsigned long index)
243 {
244         r_mapnode_t *node = r_map_node(map, index);
245         if (!node)
246                 return NULL;
247         return (rpointer)node->value.data;
248 }
249
250
251 long r_map_setvalue(rmap_t *map, long index, rconstpointer pval)
252 {
253         r_mapnode_t *node = r_map_node(map, index);
254         if (!node)
255                 return -1;
256         r_memcpy(node->value.data, pval, map->elt_size);
257         return index;
258 }
259
260
261 int r_map_delete(rmap_t *map, unsigned long index)
262 {
263         r_mapnode_t *node = r_map_node(map, index);
264         if (!node)
265                 return -1;
266         if (!r_object_gcget((robject_t*)node->key))
267                 r_string_destroy(node->key);
268         node->key = NULL;
269         r_list_del(&node->hash);
270         r_list_init(&node->hash);
271         r_list_del(&node->active);
272         r_list_addt(&map->inactive, &node->active);
273         return 0;
274 }
275
276
277 long r_map_lookup(rmap_t *map, long current, const char *name, unsigned int namesize)
278 {
279         long found = -1;
280         r_mapnode_t *node;
281         rstr_t lookupstr = {(char*)name, namesize};
282         unsigned long nbucket;
283         rhead_t *bucket;
284         rlink_t *pos;
285
286         if (current >= 0) {
287                 r_mapnode_t *curnode = r_map_node(map, current);
288                 if (!curnode)
289                         return -1;
290                 nbucket = curnode->nbucket;
291                 bucket = &map->hash[nbucket];
292                 pos = r_list_next(bucket, &curnode->hash);
293         } else {
294                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
295                 bucket = &map->hash[nbucket];
296                 pos = r_list_first(bucket);
297         }
298         for ( ; pos ; pos = r_list_next(bucket, pos)) {
299                 node = r_list_entry(pos, r_mapnode_t, hash);
300                 if (r_map_rstrequal(R_STRING2RSTR(node->key), &lookupstr)) {
301                         found = node->index;
302                         break;
303                 }
304         }
305
306         return (long)found;
307 }
308
309
310 long r_map_lookup_s(rmap_t *map, long current, const char *name)
311 {
312         return r_map_lookup(map, current, name, r_strlen(name));
313 }
314
315
316 long r_map_lookup_l(rmap_t *map, long current, long name)
317 {
318         char key[128];
319         r_memset(key, 0, sizeof(key));
320         r_snprintf(key, sizeof(key) - 1, "%ld", name);
321         return r_map_lookup_s(map, current, key);
322 }
323
324
325 long r_map_lookup_d(rmap_t *map, long current, double name)
326 {
327         char key[128];
328         r_memset(key, 0, sizeof(key));
329         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
330         return r_map_lookup_s(map, current, key);
331 }
332
333
334 long r_map_taillookup(rmap_t *map, long current, const char *name, unsigned int namesize)
335 {
336         long found = -1;
337         r_mapnode_t *node;
338         rstr_t lookupstr = {(char*)name, namesize};
339         unsigned long nbucket;
340         rhead_t *bucket;
341         rlink_t *pos;
342
343         if (current >= 0) {
344                 r_mapnode_t *curnode = r_map_node(map, current);
345                 if (!curnode)
346                         return -1;
347                 nbucket = curnode->nbucket;
348                 bucket = &map->hash[nbucket];
349                 pos = r_list_prev(bucket, &curnode->hash);
350         } else {
351                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
352                 bucket = &map->hash[nbucket];
353                 pos = r_list_last(bucket);
354         }
355         for ( ; pos ; pos = r_list_prev(bucket, pos)) {
356                 node = r_list_entry(pos, r_mapnode_t, hash);
357                 if (r_map_rstrequal(R_STRING2RSTR(node->key), &lookupstr)) {
358                         found = node->index;
359                         break;
360                 }
361         }
362
363         return (long)found;
364 }
365
366
367 long r_map_taillookup_s(rmap_t *map, long current, const char *name)
368 {
369         return r_map_taillookup(map, current, name, r_strlen(name));
370 }
371
372
373 long r_map_first(rmap_t *map)
374 {
375         r_mapnode_t *node;
376         rlink_t *pos = r_list_first(&map->active);
377
378         if (!pos)
379                 return -1;
380         node = r_list_entry(pos, r_mapnode_t, active);
381         return node->index;
382 }
383
384
385 long r_map_last(rmap_t *map)
386 {
387         r_mapnode_t *node;
388         rlink_t *pos = r_list_last(&map->active);
389
390         if (!pos)
391                 return -1;
392         node = r_list_entry(pos, r_mapnode_t, active);
393         return node->index;
394 }
395
396
397 long r_map_next(rmap_t *map, long current)
398 {
399         r_mapnode_t *node = r_map_node(map, current);
400         rlink_t *pos;
401
402         if (!node)
403                 return -1;
404         pos = r_list_next(&map->active, &node->active);
405         if (!pos)
406                 return -1;
407         node = r_list_entry(pos, r_mapnode_t, active);
408         return node->index;
409 }
410
411
412 long r_map_prev(rmap_t *map, long current)
413 {
414         r_mapnode_t *node = r_map_node(map, current);
415         rlink_t *pos;
416
417         if (!node)
418                 return -1;
419         pos = r_list_prev(&map->active, &node->active);
420         if (!pos)
421                 return -1;
422         node = r_list_entry(pos, r_mapnode_t, active);
423         return node->index;
424 }