RPA Toolkit
Work on rmap_t - 2
[rpatk.git] / rlib / rmap.c
1 #include "rmap.h"
2 #include "rstring.h"
3 #include "rmem.h"
4
5
6 typedef struct r_mapnode_s {
7         rstr_t *key;
8         rsize_t index;
9         rlink_t active;
10         rlink_t hash;
11 } r_mapnode_t;
12
13
14 static rboolean r_map_rstrequal(rstr_t *key1, rstr_t *key2)
15 {
16         return (key1->size == key2->size && r_strncmp((const rchar*)key1->str, (const rchar*)key2->str, key1->size) == 0) ? TRUE : FALSE;
17 }
18
19
20 static rulong r_map_rstrhash(const rstr_t *key)
21 {
22         const rchar *str = (const rchar*) key->str;
23         rulong i;
24         rulong size = key->size;
25         rulong hash = 0;
26
27         for (i = 0; i < size; i++, str++) {
28                 hash = *str + (hash << 6) + (hash << 16) - hash;
29         }
30         return hash;
31 }
32
33 r_mapnode_t *r_mapnode_create(const rchar *key, rsize_t size)
34 {
35         r_mapnode_t *node = (r_mapnode_t *)r_zmalloc(sizeof(*node));
36         node->key = r_rstrdup(key, size);
37         r_list_init(&node->active);
38         r_list_init(&node->hash);
39         return node;
40 }
41
42
43 r_mapnode_t *r_map_allocnode(rmap_t *map, const rchar *key, rsize_t size)
44 {
45         r_mapnode_t *node = NULL;
46
47         if (r_list_empty(&map->inactive)) {
48                 rlong index = r_carray_add(map->data, NULL);
49                 node = r_mapnode_create(key, size);
50                 node->index = index;
51         } else {
52                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
53                 r_list_del(&node->active);
54                 node->key = r_rstrdup(key, size);
55                 r_list_init(&node->active);
56                 r_list_init(&node->hash);
57         }
58         return node;
59 }
60
61
62 void r_mapnode_destroy(r_mapnode_t *node)
63 {
64         if (node)
65                 r_free(node->key);
66         r_free(node);
67 }
68
69
70
71 robject_t *r_map_copy(const robject_t *obj)
72 {
73         return (robject_t*)NULL;
74 }
75
76
77 void r_map_cleanup(robject_t *obj)
78 {
79         r_mapnode_t *node;
80         rmap_t *map = (rmap_t*)obj;
81
82         while (!r_list_empty(&map->active)) {
83                 node = r_list_entry(r_list_first(&map->active), r_mapnode_t, active);
84                 r_list_del(&node->active);
85                 r_mapnode_destroy(node);
86         }
87         while (!r_list_empty(&map->inactive)) {
88                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
89                 r_list_del(&node->active);
90                 r_mapnode_destroy(node);
91         }
92
93         r_carray_destroy(map->data);
94         r_array_destroy(map->nodes);
95         r_free(map->hash);
96         r_object_cleanup(&map->obj);
97 }
98
99
100 robject_t *r_map_init(robject_t *obj, ruint32 type, r_object_cleanupfun cleanup, r_object_copyfun copy, ruint elt_size, ruint nbits)
101 {
102         rsize_t hashsize, i;
103         rmap_t *map = (rmap_t*)obj;
104         if (nbits == 0 || nbits > 16) {
105                 R_ASSERT(0);
106                 return NULL;
107         }
108         r_object_init(obj, type, cleanup, copy);
109         map->data = r_carray_create(elt_size);
110         map->nodes = r_array_create(sizeof(r_mapnode_t*));
111         map->nbits = nbits;
112         r_list_init(&map->active);
113         r_list_init(&map->inactive);
114         hashsize = r_map_hashsize(map);
115         map->hash = (rlist_t*)r_malloc(sizeof(rlist_t) * hashsize);
116         R_ASSERT(map->hash);
117         for (i = 0; i < hashsize; i++) {
118                 r_list_init(&map->hash[i]);
119         }
120
121         return obj;
122 }
123
124 rmap_t *r_map_create(ruint elt_size, ruint nbits)
125 {
126         rmap_t *map;
127         map = (rmap_t*)r_object_create(sizeof(*map));
128         r_map_init((robject_t*)map, R_OBJECT_MAP, r_map_cleanup, r_map_copy, elt_size, nbits);
129         return map;
130
131 }
132
133
134 void r_map_destroy(rmap_t *map)
135 {
136         r_object_destroy((robject_t*)map);
137 }
138
139
140 rlong r_map_add(rmap_t *map, const rchar *name, rsize_t namesize, rconstpointer pval)
141 {
142         r_mapnode_t *node;
143         rlong index = r_carray_add(map->data, pval);
144         rulong nbucket;
145
146         node = r_map_allocnode(map, name, namesize);
147         r_array_replace(map->nodes, index, &node);
148         nbucket = (r_map_rstrhash(node->key) & r_map_hashmask(map));
149         r_list_addt(&map->hash[nbucket], &node->hash);
150         r_list_addt(&map->active, &node->active);
151         return index;
152 }
153
154
155 rlong r_map_add_s(rmap_t *map, const rchar *name, rconstpointer pval)
156 {
157         return r_map_add(map, name, r_strlen(name), pval);
158 }
159
160
161 r_mapnode_t *r_map_node(rmap_t *map, rsize_t index)
162 {
163         r_mapnode_t *node;
164         if (index >= r_array_length(map->nodes))
165                 return NULL;
166         node = r_array_index(map->nodes, index, r_mapnode_t*);
167         return node;
168 }
169
170
171 const rchar *r_map_key(rmap_t *map, rsize_t index)
172 {
173         r_mapnode_t *node = r_map_node(map, index);
174         if (!node)
175                 return NULL;
176         return node->key->str;
177 }
178
179
180 rpointer r_map_value(rmap_t *map, rsize_t index)
181 {
182         r_mapnode_t *node = r_map_node(map, index);
183         if (!node)
184                 return NULL;
185         return r_carray_slot(map->data, node->index);
186 }
187
188
189 rint r_map_delete(rmap_t *map, rsize_t index)
190 {
191         r_mapnode_t *node = r_map_node(map, index);
192         if (!node)
193                 return -1;
194         r_free(node->key);
195         r_list_del(&node->hash);
196         r_list_del(&node->active);
197         r_list_addt(&map->inactive, &node->active);
198         r_array_replace(map->nodes, index, NULL);
199         return 0;
200 }