BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file NCDModuleIndex.c
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 #include <string.h>
31 #include <stdlib.h>
32  
33 #include <misc/offset.h>
34 #include <misc/balloc.h>
35 #include <misc/bsize.h>
36 #include <misc/hashfun.h>
37 #include <misc/compare.h>
38 #include <misc/substring.h>
39 #include <base/BLog.h>
40  
41 #include "NCDModuleIndex.h"
42  
43 #include <generated/blog_channel_NCDModuleIndex.h>
44  
45 #include "NCDModuleIndex_mhash.h"
46 #include <structure/CHash_impl.h>
47  
48 #include "NCDModuleIndex_func_vec.h"
49 #include <structure/Vector_impl.h>
50  
51 #include "NCDModuleIndex_fhash.h"
52 #include <structure/CHash_impl.h>
53  
54 static int string_pointer_comparator (void *user, void *v1, void *v2)
55 {
56 const char **s1 = v1;
57 const char **s2 = v2;
58 int cmp = strcmp(*s1, *s2);
59 return B_COMPARE(cmp, 0);
60 }
61  
62 static struct NCDModuleIndex_module * find_module (NCDModuleIndex *o, const char *type)
63 {
64 NCDModuleIndex__MHashRef ref = NCDModuleIndex__MHash_Lookup(&o->modules_hash, 0, type);
65 ASSERT(!ref.link || !strcmp(ref.link->imodule.module.type, type))
66 return ref.link;
67 }
68  
69 #ifndef NDEBUG
70 static struct NCDModuleIndex_base_type * find_base_type (NCDModuleIndex *o, const char *base_type)
71 {
72 BAVLNode *node = BAVL_LookupExact(&o->base_types_tree, &base_type);
73 if (!node) {
74 return NULL;
75 }
76  
77 struct NCDModuleIndex_base_type *bt = UPPER_OBJECT(node, struct NCDModuleIndex_base_type, base_types_tree_node);
78 ASSERT(!strcmp(bt->base_type, base_type))
79  
80 return bt;
81 }
82 #endif
83  
84 static int add_method (const char *type, const struct NCDInterpModule *module, NCDMethodIndex *method_index, int *out_method_id)
85 {
86 ASSERT(type)
87 ASSERT(module)
88 ASSERT(method_index)
89 ASSERT(out_method_id)
90  
91 const char search[] = "::";
92 size_t search_len = sizeof(search) - 1;
93  
94 size_t table[sizeof(search) - 1];
95 build_substring_backtrack_table_reverse(MemRef_Make(search, search_len), table);
96  
97 size_t pos;
98 if (!find_substring_reverse(MemRef_MakeCstr(type), MemRef_Make(search, search_len), table, &pos)) {
99 *out_method_id = -1;
100 return 1;
101 }
102  
103 ASSERT(pos >= 0)
104 ASSERT(pos <= strlen(type) - search_len)
105 ASSERT(!memcmp(type + pos, search, search_len))
106  
107 int method_id = NCDMethodIndex_AddMethod(method_index, type, pos, type + pos + search_len, module);
108 if (method_id < 0) {
109 BLog(BLOG_ERROR, "NCDMethodIndex_AddMethod failed");
110 return 0;
111 }
112  
113 *out_method_id = method_id;
114 return 1;
115 }
116  
117 int NCDModuleIndex_Init (NCDModuleIndex *o, NCDStringIndex *string_index)
118 {
119 ASSERT(string_index)
120  
121 // init modules hash
122 if (!NCDModuleIndex__MHash_Init(&o->modules_hash, NCDMODULEINDEX_MODULES_HASH_SIZE)) {
123 BLog(BLOG_ERROR, "NCDModuleIndex__MHash_Init failed");
124 goto fail0;
125 }
126  
127 #ifndef NDEBUG
128 // init base types tree
129 BAVL_Init(&o->base_types_tree, OFFSET_DIFF(struct NCDModuleIndex_base_type, base_type, base_types_tree_node), string_pointer_comparator, NULL);
130 #endif
131  
132 // init groups list
133 LinkedList0_Init(&o->groups_list);
134  
135 // init method index
136 if (!NCDMethodIndex_Init(&o->method_index, string_index)) {
137 BLog(BLOG_ERROR, "NCDMethodIndex_Init failed");
138 goto fail1;
139 }
140  
141 // init functions vector
142 if (!NCDModuleIndex__FuncVec_Init(&o->func_vec, NCDMODULEINDEX_FUNCTIONS_VEC_INITIAL_SIZE)) {
143 BLog(BLOG_ERROR, "NCDModuleIndex__FuncVec_Init failed");
144 goto fail2;
145 }
146  
147 // init functions hash
148 if (!NCDModuleIndex__FuncHash_Init(&o->func_hash, NCDMODULEINDEX_FUNCTIONS_HASH_SIZE)) {
149 BLog(BLOG_ERROR, "NCDModuleIndex__FuncHash_Init failed");
150 goto fail3;
151 }
152  
153 DebugObject_Init(&o->d_obj);
154 return 1;
155  
156 fail3:
157 NCDModuleIndex__FuncVec_Free(&o->func_vec);
158 fail2:
159 NCDMethodIndex_Free(&o->method_index);
160 fail1:
161 NCDModuleIndex__MHash_Free(&o->modules_hash);
162 fail0:
163 return 0;
164 }
165  
166 void NCDModuleIndex_Free (NCDModuleIndex *o)
167 {
168 DebugObject_Free(&o->d_obj);
169  
170 // free groups
171 LinkedList0Node *ln;
172 while (ln = LinkedList0_GetFirst(&o->groups_list)) {
173 struct NCDModuleIndex_group *ig = UPPER_OBJECT(ln, struct NCDModuleIndex_group, groups_list_node);
174 if (ig->igroup.group.func_globalfree) {
175 ig->igroup.group.func_globalfree(&ig->igroup);
176 }
177 BFree(ig->igroup.strings);
178 LinkedList0_Remove(&o->groups_list, &ig->groups_list_node);
179 BFree(ig);
180 }
181  
182 #ifndef NDEBUG
183 // free base types
184 BAVLNode *tn;
185 while (tn = BAVL_GetFirst(&o->base_types_tree)) {
186 struct NCDModuleIndex_base_type *bt = UPPER_OBJECT(tn, struct NCDModuleIndex_base_type, base_types_tree_node);
187 BAVL_Remove(&o->base_types_tree, &bt->base_types_tree_node);
188 BFree(bt);
189 }
190 #endif
191  
192 // free functions hash
193 NCDModuleIndex__FuncHash_Free(&o->func_hash);
194  
195 // free functions vector
196 NCDModuleIndex__FuncVec_Free(&o->func_vec);
197  
198 // free method index
199 NCDMethodIndex_Free(&o->method_index);
200  
201 // free modules hash
202 NCDModuleIndex__MHash_Free(&o->modules_hash);
203 }
204  
205 int NCDModuleIndex_AddGroup (NCDModuleIndex *o, const struct NCDModuleGroup *group, const struct NCDModuleInst_iparams *iparams, NCDStringIndex *string_index)
206 {
207 DebugObject_Access(&o->d_obj);
208 ASSERT(group)
209 ASSERT(iparams)
210 ASSERT(string_index)
211  
212 // count modules in the group
213 size_t num_modules = 0;
214 if (group->modules) {
215 while (group->modules[num_modules].type) {
216 num_modules++;
217 }
218 }
219  
220 // compute allocation size
221 bsize_t size = bsize_add(bsize_fromsize(sizeof(struct NCDModuleIndex_group)), bsize_mul(bsize_fromsize(num_modules), bsize_fromsize(sizeof(struct NCDModuleIndex_module))));
222  
223 // allocate group
224 struct NCDModuleIndex_group *ig = BAllocSize(size);
225 if (!ig) {
226 BLog(BLOG_ERROR, "BAllocSize failed");
227 goto fail0;
228 }
229  
230 // insert to groups list
231 LinkedList0_Prepend(&o->groups_list, &ig->groups_list_node);
232  
233 // copy NCDModuleGroup
234 ig->igroup.group = *group;
235  
236 if (!group->strings) {
237 // not resolving strings
238 ig->igroup.strings = NULL;
239 } else {
240 // compute number of strings
241 size_t num_strings = 0;
242 while (group->strings[num_strings]) {
243 num_strings++;
244 }
245  
246 // allocate array for string IDs
247 ig->igroup.strings = BAllocArray(num_strings, sizeof(ig->igroup.strings[0]));
248 if (!ig->igroup.strings) {
249 BLog(BLOG_ERROR, "BAllocArray failed");
250 goto fail1;
251 }
252  
253 // map strings to IDs
254 for (size_t i = 0; i < num_strings; i++) {
255 ig->igroup.strings[i] = NCDStringIndex_Get(string_index, group->strings[i]);
256 if (ig->igroup.strings[i] < 0) {
257 BLog(BLOG_ERROR, "NCDStringIndex_Get failed");
258 goto fail2;
259 }
260 }
261 }
262  
263 // call group init function
264 if (group->func_globalinit) {
265 if (!group->func_globalinit(&ig->igroup, iparams)) {
266 BLog(BLOG_ERROR, "func_globalinit failed");
267 goto fail2;
268 }
269 }
270  
271 size_t num_inited_modules = 0;
272  
273 // initialize modules
274 if (group->modules) {
275 for (size_t i = 0; i < num_modules; i++) {
276 const struct NCDModule *nm = &group->modules[i];
277 struct NCDModuleIndex_module *m = &ig->modules[i];
278  
279 // make sure a module with this name doesn't exist already
280 if (find_module(o, nm->type)) {
281 BLog(BLOG_ERROR, "module type '%s' already exists", nm->type);
282 goto loop_fail0;
283 }
284  
285 // copy NCDModule structure
286 m->imodule.module = *nm;
287  
288 // determine base type
289 const char *base_type = (nm->base_type ? nm->base_type : nm->type);
290 ASSERT(base_type)
291  
292 // map base type to ID
293 m->imodule.base_type_id = NCDStringIndex_Get(string_index, base_type);
294 if (m->imodule.base_type_id < 0) {
295 BLog(BLOG_ERROR, "NCDStringIndex_Get failed");
296 goto loop_fail0;
297 }
298  
299 // set group pointer
300 m->imodule.group = &ig->igroup;
301  
302 // register method
303 if (!add_method(nm->type, &m->imodule, &o->method_index, &m->method_id)) {
304 goto loop_fail0;
305 }
306  
307 #ifndef NDEBUG
308 // ensure that this base_type does not appear in any other groups
309 struct NCDModuleIndex_base_type *bt = find_base_type(o, base_type);
310 if (bt) {
311 if (bt->group != ig) {
312 BLog(BLOG_ERROR, "module base type '%s' already exists in another module group", base_type);
313 goto loop_fail1;
314 }
315 } else {
316 if (!(bt = BAlloc(sizeof(*bt)))) {
317 BLog(BLOG_ERROR, "BAlloc failed");
318 goto loop_fail1;
319 }
320 bt->base_type = base_type;
321 bt->group = ig;
322 ASSERT_EXECUTE(BAVL_Insert(&o->base_types_tree, &bt->base_types_tree_node, NULL))
323 }
324 #endif
325  
326 // insert to modules hash
327 NCDModuleIndex__MHashRef ref = {m, m};
328 int res = NCDModuleIndex__MHash_Insert(&o->modules_hash, 0, ref, NULL);
329 ASSERT_EXECUTE(res)
330  
331 num_inited_modules++;
332 continue;
333  
334 #ifndef NDEBUG
335 loop_fail1:
336 if (m->method_id >= 0) {
337 NCDMethodIndex_RemoveMethod(&o->method_index, m->method_id);
338 }
339 #endif
340 loop_fail0:
341 goto fail3;
342 }
343 }
344  
345 size_t prev_func_count = NCDModuleIndex__FuncVec_Count(&o->func_vec);
346  
347 if (group->functions) {
348 for (struct NCDModuleFunction const *mfunc = group->functions; mfunc->func_name; mfunc++) {
349 NCD_string_id_t func_name_id = NCDStringIndex_Get(string_index, mfunc->func_name);
350 if (func_name_id < 0) {
351 BLog(BLOG_ERROR, "NCDStringIndex_Get failed");
352 goto fail4;
353 }
354  
355 NCDModuleIndex__FuncHashRef lookup_ref = NCDModuleIndex__FuncHash_Lookup(&o->func_hash, o, func_name_id);
356 if (lookup_ref.link >= 0) {
357 BLog(BLOG_ERROR, "Function already exists: %s", mfunc->func_name);
358 goto fail4;
359 }
360  
361 size_t func_index;
362 struct NCDModuleIndex__Func *func = NCDModuleIndex__FuncVec_Push(&o->func_vec, &func_index);
363 if (!func) {
364 BLog(BLOG_ERROR, "NCDModuleIndex__FuncVec_Push failed");
365 goto fail4;
366 }
367  
368 func->ifunc.function = *mfunc;
369 func->ifunc.func_name_id = func_name_id;
370 func->ifunc.group = &ig->igroup;
371  
372 NCDModuleIndex__FuncHashRef ref = {func, func_index};
373 int res = NCDModuleIndex__FuncHash_Insert(&o->func_hash, o, ref, NULL);
374 ASSERT_EXECUTE(res)
375 }
376 }
377  
378 return 1;
379  
380 fail4:
381 while (NCDModuleIndex__FuncVec_Count(&o->func_vec) > prev_func_count) {
382 size_t func_index;
383 struct NCDModuleIndex__Func *func = NCDModuleIndex__FuncVec_Pop(&o->func_vec, &func_index);
384 NCDModuleIndex__FuncHashRef ref = {func, func_index};
385 NCDModuleIndex__FuncHash_Remove(&o->func_hash, o, ref);
386 }
387 fail3:
388 while (num_inited_modules-- > 0) {
389 struct NCDModuleIndex_module *m = &ig->modules[num_inited_modules];
390 NCDModuleIndex__MHashRef ref = {m, m};
391 NCDModuleIndex__MHash_Remove(&o->modules_hash, 0, ref);
392 #ifndef NDEBUG
393 const struct NCDModule *nm = &group->modules[num_inited_modules];
394 const char *base_type = (nm->base_type ? nm->base_type : nm->type);
395 struct NCDModuleIndex_base_type *bt = find_base_type(o, base_type);
396 if (bt) {
397 ASSERT(bt->group == ig)
398 BAVL_Remove(&o->base_types_tree, &bt->base_types_tree_node);
399 BFree(bt);
400 }
401 #endif
402 if (m->method_id >= 0) {
403 NCDMethodIndex_RemoveMethod(&o->method_index, m->method_id);
404 }
405 }
406 if (group->func_globalfree) {
407 group->func_globalfree(&ig->igroup);
408 }
409 fail2:
410 BFree(ig->igroup.strings);
411 fail1:
412 LinkedList0_Remove(&o->groups_list, &ig->groups_list_node);
413 BFree(ig);
414 fail0:
415 return 0;
416 }
417  
418 const struct NCDInterpModule * NCDModuleIndex_FindModule (NCDModuleIndex *o, const char *type)
419 {
420 DebugObject_Access(&o->d_obj);
421 ASSERT(type)
422  
423 struct NCDModuleIndex_module *m = find_module(o, type);
424 if (!m) {
425 return NULL;
426 }
427  
428 return &m->imodule;
429 }
430  
431 int NCDModuleIndex_GetMethodNameId (NCDModuleIndex *o, const char *method_name)
432 {
433 DebugObject_Access(&o->d_obj);
434 ASSERT(method_name)
435  
436 return NCDMethodIndex_GetMethodNameId(&o->method_index, method_name);
437 }
438  
439 const struct NCDInterpModule * NCDModuleIndex_GetMethodModule (NCDModuleIndex *o, NCD_string_id_t obj_type, int method_name_id)
440 {
441 DebugObject_Access(&o->d_obj);
442  
443 return NCDMethodIndex_GetMethodModule(&o->method_index, obj_type, method_name_id);
444 }
445  
446 const struct NCDInterpFunction * NCDModuleIndex_FindFunction (NCDModuleIndex *o, NCD_string_id_t func_name_id)
447 {
448 DebugObject_Access(&o->d_obj);
449  
450 NCDModuleIndex__FuncHashRef lookup_ref = NCDModuleIndex__FuncHash_Lookup(&o->func_hash, o, func_name_id);
451 if (lookup_ref.link < 0) {
452 return NULL;
453 }
454  
455 return &lookup_ref.ptr->ifunc;
456 }