BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file NCDVal.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 <limits.h>
32 #include <stdlib.h>
33 #include <stddef.h>
34 #include <stdarg.h>
35  
36 #include <misc/balloc.h>
37 #include <misc/strdup.h>
38 #include <misc/offset.h>
39 #include <structure/CAvl.h>
40 #include <base/BLog.h>
41  
42 #include "NCDVal.h"
43  
44 #include <generated/blog_channel_NCDVal.h>
45  
46 #define NCDVAL_FIRST_SIZE 256
47 #define NCDVAL_MAX_DEPTH 32
48  
49 #define TYPE_MASK_EXTERNAL_TYPE ((1 << 3) - 1)
50 #define TYPE_MASK_INTERNAL_TYPE ((1 << 5) - 1)
51 #define TYPE_SHIFT_DEPTH 5
52  
53 #define STOREDSTRING_TYPE (NCDVAL_STRING | (0 << 3))
54 #define IDSTRING_TYPE (NCDVAL_STRING | (1 << 3))
55 #define EXTERNALSTRING_TYPE (NCDVAL_STRING | (2 << 3))
56  
57 #define NCDVAL_INSTR_PLACEHOLDER 0
58 #define NCDVAL_INSTR_REINSERT 1
59 #define NCDVAL_INSTR_BUMPDEPTH 2
60  
61 struct NCDVal__ref {
62 NCDVal__idx next;
63 BRefTarget *target;
64 };
65  
66 struct NCDVal__string {
67 int type;
68 NCDVal__idx length;
69 char data[];
70 };
71  
72 struct NCDVal__list {
73 int type;
74 NCDVal__idx maxcount;
75 NCDVal__idx count;
76 NCDVal__idx elem_indices[];
77 };
78  
79 struct NCDVal__mapelem {
80 NCDVal__idx key_idx;
81 NCDVal__idx val_idx;
82 NCDVal__idx tree_child[2];
83 NCDVal__idx tree_parent;
84 int8_t tree_balance;
85 };
86  
87 struct NCDVal__idstring {
88 int type;
89 NCD_string_id_t string_id;
90 };
91  
92 struct NCDVal__externalstring {
93 int type;
94 const char *data;
95 size_t length;
96 struct NCDVal__ref ref;
97 };
98  
99 typedef struct NCDVal__mapelem NCDVal__maptree_entry;
100 typedef NCDValMem *NCDVal__maptree_arg;
101  
102 #include "NCDVal_maptree.h"
103 #include <structure/CAvl_decl.h>
104  
105 struct NCDVal__map {
106 int type;
107 NCDVal__idx maxcount;
108 NCDVal__idx count;
109 NCDVal__MapTree tree;
110 struct NCDVal__mapelem elems[];
111 };
112  
113 struct NCDVal__instr {
114 int type;
115 union {
116 struct {
117 NCDVal__idx plid;
118 NCDVal__idx plidx;
119 } placeholder;
120 struct {
121 NCDVal__idx mapidx;
122 NCDVal__idx elempos;
123 } reinsert;
124 struct {
125 NCDVal__idx parent_idx;
126 NCDVal__idx child_idx_idx;
127 } bumpdepth;
128 };
129 };
130  
131 static int make_type (int internal_type, int depth)
132 {
133 ASSERT(internal_type == NCDVAL_LIST ||
134 internal_type == NCDVAL_MAP ||
135 internal_type == STOREDSTRING_TYPE ||
136 internal_type == IDSTRING_TYPE ||
137 internal_type == EXTERNALSTRING_TYPE)
138 ASSERT(depth >= 0)
139 ASSERT(depth <= NCDVAL_MAX_DEPTH)
140  
141 return (internal_type | (depth << TYPE_SHIFT_DEPTH));
142 }
143  
144 static int get_external_type (int type)
145 {
146 return (type & TYPE_MASK_EXTERNAL_TYPE);
147 }
148  
149 static int get_internal_type (int type)
150 {
151 return (type & TYPE_MASK_INTERNAL_TYPE);
152 }
153  
154 static int get_depth (int type)
155 {
156 return (type >> TYPE_SHIFT_DEPTH);
157 }
158  
159 static int bump_depth (int *type_ptr, int elem_depth)
160 {
161 if (get_depth(*type_ptr) < elem_depth + 1) {
162 if (elem_depth + 1 > NCDVAL_MAX_DEPTH) {
163 return 0;
164 }
165 *type_ptr = make_type(get_internal_type(*type_ptr), elem_depth + 1);
166 }
167  
168 return 1;
169 }
170  
171 static void * buffer_at (NCDValMem *o, NCDVal__idx idx)
172 {
173 ASSERT(idx >= 0)
174 ASSERT(idx < o->used)
175  
176 return ((o->size == NCDVAL_FASTBUF_SIZE) ? o->fastbuf : o->allocd_buf) + idx;
177 }
178  
179 static NCDVal__idx buffer_allocate (NCDValMem *o, NCDVal__idx alloc_size, NCDVal__idx align)
180 {
181 NCDVal__idx mod = o->used % align;
182 NCDVal__idx align_extra = mod ? (align - mod) : 0;
183  
184 if (alloc_size > NCDVAL_MAXIDX - align_extra) {
185 return -1;
186 }
187 NCDVal__idx aligned_alloc_size = align_extra + alloc_size;
188  
189 if (aligned_alloc_size > o->size - o->used) {
190 NCDVal__idx newsize = (o->size == NCDVAL_FASTBUF_SIZE) ? NCDVAL_FIRST_SIZE : o->size;
191 while (aligned_alloc_size > newsize - o->used) {
192 if (newsize > NCDVAL_MAXIDX / 2) {
193 return -1;
194 }
195 newsize *= 2;
196 }
197  
198 char *newbuf;
199  
200 if (o->size == NCDVAL_FASTBUF_SIZE) {
201 newbuf = malloc(newsize);
202 if (!newbuf) {
203 return -1;
204 }
205 memcpy(newbuf, o->fastbuf, o->used);
206 } else {
207 newbuf = realloc(o->allocd_buf, newsize);
208 if (!newbuf) {
209 return -1;
210 }
211 }
212  
213 o->size = newsize;
214 o->allocd_buf = newbuf;
215 }
216  
217 NCDVal__idx idx = o->used + align_extra;
218 o->used += aligned_alloc_size;
219  
220 return idx;
221 }
222  
223 static NCDValRef make_ref (NCDValMem *mem, NCDVal__idx idx)
224 {
225 ASSERT(idx == -1 || mem)
226  
227 NCDValRef ref = {mem, idx};
228 return ref;
229 }
230  
231 static void assert_mem (NCDValMem *mem)
232 {
233 ASSERT(mem)
234 ASSERT(mem->string_index)
235 ASSERT(mem->size == NCDVAL_FASTBUF_SIZE || mem->size >= NCDVAL_FIRST_SIZE)
236 ASSERT(mem->used >= 0)
237 ASSERT(mem->used <= mem->size)
238 }
239  
240 static void assert_external (NCDValMem *mem, const void *e_buf, size_t e_len)
241 {
242 #ifndef NDEBUG
243 const char *e_cbuf = e_buf;
244 char *buf = (mem->size == NCDVAL_FASTBUF_SIZE) ? mem->fastbuf : mem->allocd_buf;
245 ASSERT(e_cbuf >= buf + mem->size || e_cbuf + e_len <= buf)
246 #endif
247 }
248  
249 static void assert_val_only (NCDValMem *mem, NCDVal__idx idx)
250 {
251 // placeholders
252 if (idx < -1) {
253 return;
254 }
255  
256 ASSERT(idx >= 0)
257 ASSERT(idx + sizeof(int) <= mem->used)
258  
259 #ifndef NDEBUG
260 int *type_ptr = buffer_at(mem, idx);
261  
262 ASSERT(get_depth(*type_ptr) >= 0)
263 ASSERT(get_depth(*type_ptr) <= NCDVAL_MAX_DEPTH)
264  
265 switch (get_internal_type(*type_ptr)) {
266 case STOREDSTRING_TYPE: {
267 ASSERT(idx + sizeof(struct NCDVal__string) <= mem->used)
268 struct NCDVal__string *str_e = buffer_at(mem, idx);
269 ASSERT(str_e->length >= 0)
270 ASSERT(idx + sizeof(struct NCDVal__string) + str_e->length + 1 <= mem->used)
271 } break;
272 case NCDVAL_LIST: {
273 ASSERT(idx + sizeof(struct NCDVal__list) <= mem->used)
274 struct NCDVal__list *list_e = buffer_at(mem, idx);
275 ASSERT(list_e->maxcount >= 0)
276 ASSERT(list_e->count >= 0)
277 ASSERT(list_e->count <= list_e->maxcount)
278 ASSERT(idx + sizeof(struct NCDVal__list) + list_e->maxcount * sizeof(NCDVal__idx) <= mem->used)
279 } break;
280 case NCDVAL_MAP: {
281 ASSERT(idx + sizeof(struct NCDVal__map) <= mem->used)
282 struct NCDVal__map *map_e = buffer_at(mem, idx);
283 ASSERT(map_e->maxcount >= 0)
284 ASSERT(map_e->count >= 0)
285 ASSERT(map_e->count <= map_e->maxcount)
286 ASSERT(idx + sizeof(struct NCDVal__map) + map_e->maxcount * sizeof(struct NCDVal__mapelem) <= mem->used)
287 } break;
288 case IDSTRING_TYPE: {
289 ASSERT(idx + sizeof(struct NCDVal__idstring) <= mem->used)
290 struct NCDVal__idstring *ids_e = buffer_at(mem, idx);
291 ASSERT(ids_e->string_id >= 0)
292 } break;
293 case EXTERNALSTRING_TYPE: {
294 ASSERT(idx + sizeof(struct NCDVal__externalstring) <= mem->used)
295 struct NCDVal__externalstring *exs_e = buffer_at(mem, idx);
296 ASSERT(exs_e->data)
297 ASSERT(!exs_e->ref.target || exs_e->ref.next >= -1)
298 ASSERT(!exs_e->ref.target || exs_e->ref.next < mem->used)
299 } break;
300 default: ASSERT(0);
301 }
302 #endif
303 }
304  
305 static void assert_val (NCDValRef val)
306 {
307 assert_mem(val.mem);
308 assert_val_only(val.mem, val.idx);
309 }
310  
311 static NCDValMapElem make_map_elem (NCDVal__idx elemidx)
312 {
313 ASSERT(elemidx >= 0 || elemidx == -1)
314  
315 NCDValMapElem me = {elemidx};
316 return me;
317 }
318  
319 static void assert_map_elem_only (NCDValRef map, NCDVal__idx elemidx)
320 {
321 #ifndef NDEBUG
322 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
323 ASSERT(elemidx >= map.idx + offsetof(struct NCDVal__map, elems))
324 ASSERT(elemidx < map.idx + offsetof(struct NCDVal__map, elems) + map_e->count * sizeof(struct NCDVal__mapelem))
325  
326 struct NCDVal__mapelem *me_e = buffer_at(map.mem, elemidx);
327 assert_val_only(map.mem, me_e->key_idx);
328 assert_val_only(map.mem, me_e->val_idx);
329 #endif
330 }
331  
332 static void assert_map_elem (NCDValRef map, NCDValMapElem me)
333 {
334 ASSERT(NCDVal_IsMap(map))
335 assert_map_elem_only(map, me.elemidx);
336 }
337  
338 static NCDVal__idx make_map_elem_idx (NCDVal__idx mapidx, NCDVal__idx pos)
339 {
340 return mapidx + offsetof(struct NCDVal__map, elems) + pos * sizeof(struct NCDVal__mapelem);
341 }
342  
343 static int get_val_depth (NCDValRef val)
344 {
345 ASSERT(val.idx != -1)
346  
347 // handle placeholders
348 if (val.idx < 0) {
349 return 0;
350 }
351  
352 int *elem_type_ptr = buffer_at(val.mem, val.idx);
353 int depth = get_depth(*elem_type_ptr);
354 ASSERT(depth >= 0)
355 ASSERT(depth <= NCDVAL_MAX_DEPTH)
356  
357 return depth;
358 }
359  
360 static void register_ref (NCDValMem *o, NCDVal__idx refidx, struct NCDVal__ref *ref)
361 {
362 ASSERT(ref == buffer_at(o, refidx))
363 ASSERT(ref->target)
364  
365 ref->next = o->first_ref;
366 o->first_ref = refidx;
367 }
368  
369 #include "NCDVal_maptree.h"
370 #include <structure/CAvl_impl.h>
371  
372 void NCDValMem_Init (NCDValMem *o, NCDStringIndex *string_index)
373 {
374 ASSERT(string_index)
375  
376 o->string_index = string_index;
377 o->size = NCDVAL_FASTBUF_SIZE;
378 o->used = 0;
379 o->first_ref = -1;
380 }
381  
382 void NCDValMem_Free (NCDValMem *o)
383 {
384 assert_mem(o);
385  
386 NCDVal__idx refidx = o->first_ref;
387 while (refidx != -1) {
388 struct NCDVal__ref *ref = buffer_at(o, refidx);
389 ASSERT(ref->target)
390 BRefTarget_Deref(ref->target);
391 refidx = ref->next;
392 }
393  
394 if (o->size != NCDVAL_FASTBUF_SIZE) {
395 BFree(o->allocd_buf);
396 }
397 }
398  
399 int NCDValMem_InitCopy (NCDValMem *o, NCDValMem *other)
400 {
401 assert_mem(other);
402  
403 o->string_index = other->string_index;
404 o->size = other->size;
405 o->used = other->used;
406 o->first_ref = other->first_ref;
407  
408 if (other->size == NCDVAL_FASTBUF_SIZE) {
409 memcpy(o->fastbuf, other->fastbuf, other->used);
410 } else {
411 o->allocd_buf = BAlloc(other->size);
412 if (!o->allocd_buf) {
413 goto fail0;
414 }
415 memcpy(o->allocd_buf, other->allocd_buf, other->used);
416 }
417  
418 NCDVal__idx refidx = o->first_ref;
419 while (refidx != -1) {
420 struct NCDVal__ref *ref = buffer_at(o, refidx);
421 ASSERT(ref->target)
422 if (!BRefTarget_Ref(ref->target)) {
423 goto fail1;
424 }
425 refidx = ref->next;
426 }
427  
428 return 1;
429  
430 fail1:;
431 NCDVal__idx undo_refidx = o->first_ref;
432 while (undo_refidx != refidx) {
433 struct NCDVal__ref *ref = buffer_at(o, undo_refidx);
434 BRefTarget_Deref(ref->target);
435 undo_refidx = ref->next;
436 }
437 if (other->size != NCDVAL_FASTBUF_SIZE) {
438 BFree(o->allocd_buf);
439 }
440 fail0:
441 return 0;
442 }
443  
444 NCDStringIndex * NCDValMem_StringIndex (NCDValMem *o)
445 {
446 assert_mem(o);
447  
448 return o->string_index;
449 }
450  
451 void NCDVal_Assert (NCDValRef val)
452 {
453 ASSERT(val.idx == -1 || (assert_val(val), 1))
454 }
455  
456 int NCDVal_IsInvalid (NCDValRef val)
457 {
458 NCDVal_Assert(val);
459  
460 return (val.idx == -1);
461 }
462  
463 int NCDVal_IsPlaceholder (NCDValRef val)
464 {
465 NCDVal_Assert(val);
466  
467 return (val.idx < -1);
468 }
469  
470 int NCDVal_Type (NCDValRef val)
471 {
472 assert_val(val);
473  
474 if (val.idx < -1) {
475 return NCDVAL_PLACEHOLDER;
476 }
477  
478 int *type_ptr = buffer_at(val.mem, val.idx);
479  
480 return get_external_type(*type_ptr);
481 }
482  
483 NCDValRef NCDVal_NewInvalid (void)
484 {
485 NCDValRef ref = {NULL, -1};
486 return ref;
487 }
488  
489 NCDValRef NCDVal_NewPlaceholder (NCDValMem *mem, int plid)
490 {
491 assert_mem(mem);
492 ASSERT(plid >= 0)
493 ASSERT(plid < NCDVAL_TOPPLID)
494  
495 NCDValRef ref = {mem, NCDVAL_MINIDX + plid};
496 return ref;
497 }
498  
499 int NCDVal_PlaceholderId (NCDValRef val)
500 {
501 ASSERT(NCDVal_IsPlaceholder(val))
502  
503 return (val.idx - NCDVAL_MINIDX);
504 }
505  
506 NCDValRef NCDVal_NewCopy (NCDValMem *mem, NCDValRef val)
507 {
508 assert_mem(mem);
509 assert_val(val);
510  
511 if (val.idx < -1) {
512 return NCDVal_NewPlaceholder(mem, NCDVal_PlaceholderId(val));
513 }
514  
515 void *ptr = buffer_at(val.mem, val.idx);
516  
517 switch (get_internal_type(*(int *)ptr)) {
518 case STOREDSTRING_TYPE: {
519 struct NCDVal__string *str_e = ptr;
520  
521 NCDVal__idx size = sizeof(struct NCDVal__string) + str_e->length + 1;
522 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__string));
523 if (idx < 0) {
524 goto fail;
525 }
526  
527 str_e = buffer_at(val.mem, val.idx);
528 struct NCDVal__string *new_str_e = buffer_at(mem, idx);
529  
530 memcpy(new_str_e, str_e, size);
531  
532 return make_ref(mem, idx);
533 } break;
534  
535 case NCDVAL_LIST: {
536 struct NCDVal__list *list_e = ptr;
537  
538 NCDVal__idx size = sizeof(struct NCDVal__list) + list_e->maxcount * sizeof(NCDVal__idx);
539 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__list));
540 if (idx < 0) {
541 goto fail;
542 }
543  
544 list_e = buffer_at(val.mem, val.idx);
545 struct NCDVal__list *new_list_e = buffer_at(mem, idx);
546  
547 *new_list_e = *list_e;
548  
549 NCDVal__idx count = list_e->count;
550  
551 for (NCDVal__idx i = 0; i < count; i++) {
552 NCDValRef elem_copy = NCDVal_NewCopy(mem, make_ref(val.mem, list_e->elem_indices[i]));
553 if (NCDVal_IsInvalid(elem_copy)) {
554 goto fail;
555 }
556  
557 list_e = buffer_at(val.mem, val.idx);
558 new_list_e = buffer_at(mem, idx);
559  
560 new_list_e->elem_indices[i] = elem_copy.idx;
561 }
562  
563 return make_ref(mem, idx);
564 } break;
565  
566 case NCDVAL_MAP: {
567 size_t count = NCDVal_MapCount(val);
568  
569 NCDValRef copy = NCDVal_NewMap(mem, count);
570 if (NCDVal_IsInvalid(copy)) {
571 goto fail;
572 }
573  
574 for (NCDValMapElem e = NCDVal_MapFirst(val); !NCDVal_MapElemInvalid(e); e = NCDVal_MapNext(val, e)) {
575 NCDValRef key_copy = NCDVal_NewCopy(mem, NCDVal_MapElemKey(val, e));
576 NCDValRef val_copy = NCDVal_NewCopy(mem, NCDVal_MapElemVal(val, e));
577 if (NCDVal_IsInvalid(key_copy) || NCDVal_IsInvalid(val_copy)) {
578 goto fail;
579 }
580  
581 int inserted;
582 if (!NCDVal_MapInsert(copy, key_copy, val_copy, &inserted)) {
583 goto fail;
584 }
585 ASSERT_EXECUTE(inserted)
586 }
587  
588 return copy;
589 } break;
590  
591 case IDSTRING_TYPE: {
592 NCDVal__idx size = sizeof(struct NCDVal__idstring);
593 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__idstring));
594 if (idx < 0) {
595 goto fail;
596 }
597  
598 struct NCDVal__idstring *ids_e = buffer_at(val.mem, val.idx);
599 struct NCDVal__idstring *new_ids_e = buffer_at(mem, idx);
600  
601 *new_ids_e = *ids_e;
602  
603 return make_ref(mem, idx);
604 } break;
605  
606 case EXTERNALSTRING_TYPE: {
607 struct NCDVal__externalstring *exs_e = ptr;
608  
609 return NCDVal_NewExternalString(mem, exs_e->data, exs_e->length, exs_e->ref.target);
610 } break;
611  
612 default: ASSERT(0);
613 }
614  
615 ASSERT(0);
616  
617 fail:
618 return NCDVal_NewInvalid();
619 }
620  
621 int NCDVal_Compare (NCDValRef val1, NCDValRef val2)
622 {
623 assert_val(val1);
624 assert_val(val2);
625  
626 int type1 = NCDVal_Type(val1);
627 int type2 = NCDVal_Type(val2);
628  
629 if (type1 != type2) {
630 return (type1 > type2) - (type1 < type2);
631 }
632  
633 switch (type1) {
634 case NCDVAL_STRING: {
635 size_t len1 = NCDVal_StringLength(val1);
636 size_t len2 = NCDVal_StringLength(val2);
637 size_t min_len = len1 < len2 ? len1 : len2;
638  
639 int cmp = NCDVal_StringMemCmp(val1, val2, 0, 0, min_len);
640 if (cmp) {
641 return (cmp > 0) - (cmp < 0);
642 }
643  
644 return (len1 > len2) - (len1 < len2);
645 } break;
646  
647 case NCDVAL_LIST: {
648 size_t count1 = NCDVal_ListCount(val1);
649 size_t count2 = NCDVal_ListCount(val2);
650 size_t min_count = count1 < count2 ? count1 : count2;
651  
652 for (size_t i = 0; i < min_count; i++) {
653 NCDValRef ev1 = NCDVal_ListGet(val1, i);
654 NCDValRef ev2 = NCDVal_ListGet(val2, i);
655  
656 int cmp = NCDVal_Compare(ev1, ev2);
657 if (cmp) {
658 return cmp;
659 }
660 }
661  
662 return (count1 > count2) - (count1 < count2);
663 } break;
664  
665 case NCDVAL_MAP: {
666 NCDValMapElem e1 = NCDVal_MapOrderedFirst(val1);
667 NCDValMapElem e2 = NCDVal_MapOrderedFirst(val2);
668  
669 while (1) {
670 int inv1 = NCDVal_MapElemInvalid(e1);
671 int inv2 = NCDVal_MapElemInvalid(e2);
672 if (inv1 || inv2) {
673 return inv2 - inv1;
674 }
675  
676 NCDValRef key1 = NCDVal_MapElemKey(val1, e1);
677 NCDValRef key2 = NCDVal_MapElemKey(val2, e2);
678  
679 int cmp = NCDVal_Compare(key1, key2);
680 if (cmp) {
681 return cmp;
682 }
683  
684 NCDValRef value1 = NCDVal_MapElemVal(val1, e1);
685 NCDValRef value2 = NCDVal_MapElemVal(val2, e2);
686  
687 cmp = NCDVal_Compare(value1, value2);
688 if (cmp) {
689 return cmp;
690 }
691  
692 e1 = NCDVal_MapOrderedNext(val1, e1);
693 e2 = NCDVal_MapOrderedNext(val2, e2);
694 }
695 } break;
696  
697 case NCDVAL_PLACEHOLDER: {
698 int plid1 = NCDVal_PlaceholderId(val1);
699 int plid2 = NCDVal_PlaceholderId(val2);
700  
701 return (plid1 > plid2) - (plid1 < plid2);
702 } break;
703  
704 default:
705 ASSERT(0);
706 return 0;
707 }
708 }
709  
710 NCDValSafeRef NCDVal_ToSafe (NCDValRef val)
711 {
712 NCDVal_Assert(val);
713  
714 NCDValSafeRef sval = {val.idx};
715 return sval;
716 }
717  
718 NCDValRef NCDVal_FromSafe (NCDValMem *mem, NCDValSafeRef sval)
719 {
720 assert_mem(mem);
721 ASSERT(sval.idx == -1 || (assert_val_only(mem, sval.idx), 1))
722  
723 NCDValRef val = {mem, sval.idx};
724 return val;
725 }
726  
727 NCDValRef NCDVal_Moved (NCDValMem *mem, NCDValRef val)
728 {
729 assert_mem(mem);
730 ASSERT(val.idx == -1 || (assert_val_only(mem, val.idx), 1))
731  
732 NCDValRef val2 = {mem, val.idx};
733 return val2;
734 }
735  
736 int NCDVal_IsSafeRefPlaceholder (NCDValSafeRef sval)
737 {
738 return (sval.idx < -1);
739 }
740  
741 int NCDVal_GetSafeRefPlaceholderId (NCDValSafeRef sval)
742 {
743 ASSERT(NCDVal_IsSafeRefPlaceholder(sval))
744  
745 return (sval.idx - NCDVAL_MINIDX);
746 }
747  
748 int NCDVal_IsString (NCDValRef val)
749 {
750 assert_val(val);
751  
752 return NCDVal_Type(val) == NCDVAL_STRING;
753 }
754  
755 int NCDVal_IsStoredString (NCDValRef val)
756 {
757 assert_val(val);
758  
759 return !(val.idx < -1) && get_internal_type(*(int *)buffer_at(val.mem, val.idx)) == STOREDSTRING_TYPE;
760 }
761  
762 int NCDVal_IsIdString (NCDValRef val)
763 {
764 assert_val(val);
765  
766 return !(val.idx < -1) && get_internal_type(*(int *)buffer_at(val.mem, val.idx)) == IDSTRING_TYPE;
767 }
768  
769 int NCDVal_IsExternalString (NCDValRef val)
770 {
771 assert_val(val);
772  
773 return !(val.idx < -1) && get_internal_type(*(int *)buffer_at(val.mem, val.idx)) == EXTERNALSTRING_TYPE;
774 }
775  
776 int NCDVal_IsStringNoNulls (NCDValRef val)
777 {
778 assert_val(val);
779  
780 return NCDVal_Type(val) == NCDVAL_STRING && !NCDVal_StringHasNulls(val);
781 }
782  
783 NCDValRef NCDVal_NewString (NCDValMem *mem, const char *data)
784 {
785 assert_mem(mem);
786 ASSERT(data)
787 assert_external(mem, data, strlen(data));
788  
789 return NCDVal_NewStringBin(mem, (const uint8_t *)data, strlen(data));
790 }
791  
792 NCDValRef NCDVal_NewStringBin (NCDValMem *mem, const uint8_t *data, size_t len)
793 {
794 assert_mem(mem);
795 ASSERT(len == 0 || data)
796 assert_external(mem, data, len);
797  
798 if (len > NCDVAL_MAXIDX - sizeof(struct NCDVal__string) - 1) {
799 goto fail;
800 }
801  
802 NCDVal__idx size = sizeof(struct NCDVal__string) + len + 1;
803 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__string));
804 if (idx < 0) {
805 goto fail;
806 }
807  
808 struct NCDVal__string *str_e = buffer_at(mem, idx);
809 str_e->type = make_type(STOREDSTRING_TYPE, 0);
810 str_e->length = len;
811 if (len > 0) {
812 memcpy(str_e->data, data, len);
813 }
814 str_e->data[len] = '\0';
815  
816 return make_ref(mem, idx);
817  
818 fail:
819 return NCDVal_NewInvalid();
820 }
821  
822 NCDValRef NCDVal_NewStringBinMr (NCDValMem *mem, MemRef data)
823 {
824 return NCDVal_NewStringBin(mem, (uint8_t const *)data.ptr, data.len);
825 }
826  
827 NCDValRef NCDVal_NewStringUninitialized (NCDValMem *mem, size_t len)
828 {
829 assert_mem(mem);
830  
831 if (len > NCDVAL_MAXIDX - sizeof(struct NCDVal__string) - 1) {
832 goto fail;
833 }
834  
835 NCDVal__idx size = sizeof(struct NCDVal__string) + len + 1;
836 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__string));
837 if (idx < 0) {
838 goto fail;
839 }
840  
841 struct NCDVal__string *str_e = buffer_at(mem, idx);
842 str_e->type = make_type(STOREDSTRING_TYPE, 0);
843 str_e->length = len;
844 str_e->data[len] = '\0';
845  
846 return make_ref(mem, idx);
847  
848 fail:
849 return NCDVal_NewInvalid();
850 }
851  
852 NCDValRef NCDVal_NewIdString (NCDValMem *mem, NCD_string_id_t string_id)
853 {
854 assert_mem(mem);
855 ASSERT(string_id >= 0)
856  
857 NCDVal__idx size = sizeof(struct NCDVal__idstring);
858 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__idstring));
859 if (idx < 0) {
860 goto fail;
861 }
862  
863 struct NCDVal__idstring *ids_e = buffer_at(mem, idx);
864 ids_e->type = make_type(IDSTRING_TYPE, 0);
865 ids_e->string_id = string_id;
866  
867 return make_ref(mem, idx);
868  
869 fail:
870 return NCDVal_NewInvalid();
871 }
872  
873 NCDValRef NCDVal_NewExternalString (NCDValMem *mem, const char *data, size_t len,
874 BRefTarget *ref_target)
875 {
876 assert_mem(mem);
877 ASSERT(data)
878 assert_external(mem, data, len);
879  
880 NCDVal__idx size = sizeof(struct NCDVal__externalstring);
881 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__externalstring));
882 if (idx < 0) {
883 goto fail;
884 }
885  
886 if (ref_target) {
887 if (!BRefTarget_Ref(ref_target)) {
888 goto fail;
889 }
890 }
891  
892 struct NCDVal__externalstring *exs_e = buffer_at(mem, idx);
893 exs_e->type = make_type(EXTERNALSTRING_TYPE, 0);
894 exs_e->data = data;
895 exs_e->length = len;
896 exs_e->ref.target = ref_target;
897  
898 if (ref_target) {
899 register_ref(mem, idx + offsetof(struct NCDVal__externalstring, ref), &exs_e->ref);
900 }
901  
902 return make_ref(mem, idx);
903  
904 fail:
905 return NCDVal_NewInvalid();
906 }
907  
908 const char * NCDVal_StringData (NCDValRef string)
909 {
910 ASSERT(NCDVal_IsString(string))
911  
912 void *ptr = buffer_at(string.mem, string.idx);
913  
914 switch (get_internal_type(*(int *)ptr)) {
915 case STOREDSTRING_TYPE: {
916 struct NCDVal__string *str_e = ptr;
917 return str_e->data;
918 } break;
919  
920 case IDSTRING_TYPE: {
921 struct NCDVal__idstring *ids_e = ptr;
922 const char *value = NCDStringIndex_Value(string.mem->string_index, ids_e->string_id).ptr;
923 return value;
924 } break;
925  
926 case EXTERNALSTRING_TYPE: {
927 struct NCDVal__externalstring *exs_e = ptr;
928 return exs_e->data;
929 } break;
930  
931 default:
932 ASSERT(0);
933 return NULL;
934 }
935 }
936  
937 size_t NCDVal_StringLength (NCDValRef string)
938 {
939 ASSERT(NCDVal_IsString(string))
940  
941 void *ptr = buffer_at(string.mem, string.idx);
942  
943 switch (get_internal_type(*(int *)ptr)) {
944 case STOREDSTRING_TYPE: {
945 struct NCDVal__string *str_e = ptr;
946 return str_e->length;
947 } break;
948  
949 case IDSTRING_TYPE: {
950 struct NCDVal__idstring *ids_e = ptr;
951 return NCDStringIndex_Value(string.mem->string_index, ids_e->string_id).len;
952 } break;
953  
954 case EXTERNALSTRING_TYPE: {
955 struct NCDVal__externalstring *exs_e = ptr;
956 return exs_e->length;
957 } break;
958  
959 default:
960 ASSERT(0);
961 return 0;
962 }
963 }
964  
965 MemRef NCDVal_StringMemRef (NCDValRef string)
966 {
967 ASSERT(NCDVal_IsString(string))
968  
969 void *ptr = buffer_at(string.mem, string.idx);
970  
971 switch (get_internal_type(*(int *)ptr)) {
972 case STOREDSTRING_TYPE: {
973 struct NCDVal__string *str_e = ptr;
974 return MemRef_Make(str_e->data, str_e->length);
975 } break;
976  
977 case IDSTRING_TYPE: {
978 struct NCDVal__idstring *ids_e = ptr;
979 return NCDStringIndex_Value(string.mem->string_index, ids_e->string_id);
980 } break;
981  
982 case EXTERNALSTRING_TYPE: {
983 struct NCDVal__externalstring *exs_e = ptr;
984 return MemRef_Make(exs_e->data, exs_e->length);
985 } break;
986  
987 default: {
988 ASSERT(0);
989 return MemRef_Make(NULL, 0);
990 } break;
991 }
992 }
993  
994 int NCDVal_StringNullTerminate (NCDValRef string, NCDValNullTermString *out)
995 {
996 ASSERT(NCDVal_IsString(string))
997 ASSERT(out)
998  
999 void *ptr = buffer_at(string.mem, string.idx);
1000  
1001 switch (get_internal_type(*(int *)ptr)) {
1002 case STOREDSTRING_TYPE: {
1003 struct NCDVal__string *str_e = ptr;
1004 out->data = str_e->data;
1005 out->is_allocated = 0;
1006 return 1;
1007 } break;
1008  
1009 case IDSTRING_TYPE: {
1010 struct NCDVal__idstring *ids_e = ptr;
1011 out->data = (char *)NCDStringIndex_Value(string.mem->string_index, ids_e->string_id).ptr;
1012 out->is_allocated = 0;
1013 return 1;
1014 } break;
1015  
1016 case EXTERNALSTRING_TYPE: {
1017 struct NCDVal__externalstring *exs_e = ptr;
1018  
1019 char *copy = b_strdup_bin(exs_e->data, exs_e->length);
1020 if (!copy) {
1021 return 0;
1022 }
1023  
1024 out->data = copy;
1025 out->is_allocated = 1;
1026 return 1;
1027 } break;
1028  
1029 default:
1030 ASSERT(0);
1031 return 0;
1032 }
1033 }
1034  
1035 NCDValNullTermString NCDValNullTermString_NewDummy (void)
1036 {
1037 NCDValNullTermString nts;
1038 nts.data = NULL;
1039 nts.is_allocated = 0;
1040 return nts;
1041 }
1042  
1043 void NCDValNullTermString_Free (NCDValNullTermString *o)
1044 {
1045 if (o->is_allocated) {
1046 BFree(o->data);
1047 }
1048 }
1049  
1050 NCD_string_id_t NCDVal_IdStringId (NCDValRef idstring)
1051 {
1052 ASSERT(NCDVal_IsIdString(idstring))
1053  
1054 struct NCDVal__idstring *ids_e = buffer_at(idstring.mem, idstring.idx);
1055 return ids_e->string_id;
1056 }
1057  
1058 BRefTarget * NCDVal_ExternalStringTarget (NCDValRef externalstring)
1059 {
1060 ASSERT(NCDVal_IsExternalString(externalstring))
1061  
1062 struct NCDVal__externalstring *exs_e = buffer_at(externalstring.mem, externalstring.idx);
1063 return exs_e->ref.target;
1064 }
1065  
1066 int NCDVal_StringHasNulls (NCDValRef string)
1067 {
1068 ASSERT(NCDVal_IsString(string))
1069  
1070 void *ptr = buffer_at(string.mem, string.idx);
1071  
1072 switch (get_internal_type(*(int *)ptr)) {
1073 case IDSTRING_TYPE: {
1074 struct NCDVal__idstring *ids_e = ptr;
1075 return NCDStringIndex_HasNulls(string.mem->string_index, ids_e->string_id);
1076 } break;
1077  
1078 case STOREDSTRING_TYPE:
1079 case EXTERNALSTRING_TYPE: {
1080 return MemRef_FindChar(NCDVal_StringMemRef(string), '\0', NULL);
1081 } break;
1082  
1083 default:
1084 ASSERT(0);
1085 return 0;
1086 }
1087 }
1088  
1089 int NCDVal_StringEquals (NCDValRef string, const char *data)
1090 {
1091 ASSERT(NCDVal_IsString(string))
1092 ASSERT(data)
1093  
1094 size_t data_len = strlen(data);
1095  
1096 return NCDVal_StringLength(string) == data_len && NCDVal_StringRegionEquals(string, 0, data_len, data);
1097 }
1098  
1099 int NCDVal_StringEqualsId (NCDValRef string, NCD_string_id_t string_id)
1100 {
1101 ASSERT(NCDVal_IsString(string))
1102 ASSERT(string_id >= 0)
1103  
1104 void *ptr = buffer_at(string.mem, string.idx);
1105  
1106 switch (get_internal_type(*(int *)ptr)) {
1107 case STOREDSTRING_TYPE: {
1108 struct NCDVal__string *str_e = ptr;
1109 return MemRef_Equal(NCDStringIndex_Value(string.mem->string_index, string_id), MemRef_Make(str_e->data, str_e->length));
1110 } break;
1111  
1112 case IDSTRING_TYPE: {
1113 struct NCDVal__idstring *ids_e = ptr;
1114 return ids_e->string_id == string_id;
1115 } break;
1116  
1117 case EXTERNALSTRING_TYPE: {
1118 struct NCDVal__externalstring *exs_e = ptr;
1119 return MemRef_Equal(NCDStringIndex_Value(string.mem->string_index, string_id), MemRef_Make(exs_e->data, exs_e->length));
1120 } break;
1121  
1122 default:
1123 ASSERT(0);
1124 return 0;
1125 }
1126 }
1127  
1128 int NCDVal_StringMemCmp (NCDValRef string1, NCDValRef string2, size_t start1, size_t start2, size_t length)
1129 {
1130 ASSERT(NCDVal_IsString(string1))
1131 ASSERT(NCDVal_IsString(string2))
1132 ASSERT(start1 <= NCDVal_StringLength(string1))
1133 ASSERT(start2 <= NCDVal_StringLength(string2))
1134 ASSERT(length <= NCDVal_StringLength(string1) - start1)
1135 ASSERT(length <= NCDVal_StringLength(string2) - start2)
1136  
1137 return memcmp(NCDVal_StringData(string1) + start1, NCDVal_StringData(string2) + start2, length);
1138 }
1139  
1140 void NCDVal_StringCopyOut (NCDValRef string, size_t start, size_t length, char *dst)
1141 {
1142 ASSERT(NCDVal_IsString(string))
1143 ASSERT(start <= NCDVal_StringLength(string))
1144 ASSERT(length <= NCDVal_StringLength(string) - start)
1145  
1146 memcpy(dst, NCDVal_StringData(string) + start, length);
1147 }
1148  
1149 int NCDVal_StringRegionEquals (NCDValRef string, size_t start, size_t length, const char *data)
1150 {
1151 ASSERT(NCDVal_IsString(string))
1152 ASSERT(start <= NCDVal_StringLength(string))
1153 ASSERT(length <= NCDVal_StringLength(string) - start)
1154  
1155 return !memcmp(NCDVal_StringData(string) + start, data, length);
1156 }
1157  
1158 int NCDVal_IsList (NCDValRef val)
1159 {
1160 assert_val(val);
1161  
1162 return NCDVal_Type(val) == NCDVAL_LIST;
1163 }
1164  
1165 NCDValRef NCDVal_NewList (NCDValMem *mem, size_t maxcount)
1166 {
1167 assert_mem(mem);
1168  
1169 if (maxcount > (NCDVAL_MAXIDX - sizeof(struct NCDVal__list)) / sizeof(NCDVal__idx)) {
1170 goto fail;
1171 }
1172  
1173 NCDVal__idx size = sizeof(struct NCDVal__list) + maxcount * sizeof(NCDVal__idx);
1174 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__list));
1175 if (idx < 0) {
1176 goto fail;
1177 }
1178  
1179 struct NCDVal__list *list_e = buffer_at(mem, idx);
1180 list_e->type = make_type(NCDVAL_LIST, 0);
1181 list_e->maxcount = maxcount;
1182 list_e->count = 0;
1183  
1184 return make_ref(mem, idx);
1185  
1186 fail:
1187 return NCDVal_NewInvalid();
1188 }
1189  
1190 int NCDVal_ListAppend (NCDValRef list, NCDValRef elem)
1191 {
1192 ASSERT(NCDVal_IsList(list))
1193 ASSERT(NCDVal_ListCount(list) < NCDVal_ListMaxCount(list))
1194 ASSERT(elem.mem == list.mem)
1195 assert_val_only(list.mem, elem.idx);
1196  
1197 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1198  
1199 int new_type = list_e->type;
1200 if (!bump_depth(&new_type, get_val_depth(elem))) {
1201 return 0;
1202 }
1203  
1204 list_e->type = new_type;
1205 list_e->elem_indices[list_e->count++] = elem.idx;
1206  
1207 return 1;
1208 }
1209  
1210 size_t NCDVal_ListCount (NCDValRef list)
1211 {
1212 ASSERT(NCDVal_IsList(list))
1213  
1214 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1215  
1216 return list_e->count;
1217 }
1218  
1219 size_t NCDVal_ListMaxCount (NCDValRef list)
1220 {
1221 ASSERT(NCDVal_IsList(list))
1222  
1223 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1224  
1225 return list_e->maxcount;
1226 }
1227  
1228 NCDValRef NCDVal_ListGet (NCDValRef list, size_t pos)
1229 {
1230 ASSERT(NCDVal_IsList(list))
1231 ASSERT(pos < NCDVal_ListCount(list))
1232  
1233 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1234  
1235 ASSERT(pos < list_e->count)
1236 assert_val_only(list.mem, list_e->elem_indices[pos]);
1237  
1238 return make_ref(list.mem, list_e->elem_indices[pos]);
1239 }
1240  
1241 int NCDVal_ListRead (NCDValRef list, int num, ...)
1242 {
1243 ASSERT(NCDVal_IsList(list))
1244 ASSERT(num >= 0)
1245  
1246 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1247  
1248 if (num != list_e->count) {
1249 return 0;
1250 }
1251  
1252 va_list ap;
1253 va_start(ap, num);
1254  
1255 for (int i = 0; i < num; i++) {
1256 NCDValRef *dest = va_arg(ap, NCDValRef *);
1257 *dest = make_ref(list.mem, list_e->elem_indices[i]);
1258 }
1259  
1260 va_end(ap);
1261  
1262 return 1;
1263 }
1264  
1265 int NCDVal_ListReadStart (NCDValRef list, int start, int num, ...)
1266 {
1267 ASSERT(NCDVal_IsList(list))
1268 ASSERT(start <= NCDVal_ListCount(list))
1269 ASSERT(num >= 0)
1270  
1271 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1272  
1273 if (num != list_e->count - start) {
1274 return 0;
1275 }
1276  
1277 va_list ap;
1278 va_start(ap, num);
1279  
1280 for (int i = 0; i < num; i++) {
1281 NCDValRef *dest = va_arg(ap, NCDValRef *);
1282 *dest = make_ref(list.mem, list_e->elem_indices[start + i]);
1283 }
1284  
1285 va_end(ap);
1286  
1287 return 1;
1288 }
1289  
1290 int NCDVal_ListReadHead (NCDValRef list, int num, ...)
1291 {
1292 ASSERT(NCDVal_IsList(list))
1293 ASSERT(num >= 0)
1294  
1295 struct NCDVal__list *list_e = buffer_at(list.mem, list.idx);
1296  
1297 if (num > list_e->count) {
1298 return 0;
1299 }
1300  
1301 va_list ap;
1302 va_start(ap, num);
1303  
1304 for (int i = 0; i < num; i++) {
1305 NCDValRef *dest = va_arg(ap, NCDValRef *);
1306 *dest = make_ref(list.mem, list_e->elem_indices[i]);
1307 }
1308  
1309 va_end(ap);
1310  
1311 return 1;
1312 }
1313  
1314 int NCDVal_IsMap (NCDValRef val)
1315 {
1316 assert_val(val);
1317  
1318 return NCDVal_Type(val) == NCDVAL_MAP;
1319 }
1320  
1321 NCDValRef NCDVal_NewMap (NCDValMem *mem, size_t maxcount)
1322 {
1323 assert_mem(mem);
1324  
1325 if (maxcount > (NCDVAL_MAXIDX - sizeof(struct NCDVal__map)) / sizeof(struct NCDVal__mapelem)) {
1326 goto fail;
1327 }
1328  
1329 NCDVal__idx size = sizeof(struct NCDVal__map) + maxcount * sizeof(struct NCDVal__mapelem);
1330 NCDVal__idx idx = buffer_allocate(mem, size, __alignof(struct NCDVal__map));
1331 if (idx < 0) {
1332 goto fail;
1333 }
1334  
1335 struct NCDVal__map *map_e = buffer_at(mem, idx);
1336 map_e->type = make_type(NCDVAL_MAP, 0);
1337 map_e->maxcount = maxcount;
1338 map_e->count = 0;
1339 NCDVal__MapTree_Init(&map_e->tree);
1340  
1341 return make_ref(mem, idx);
1342  
1343 fail:
1344 return NCDVal_NewInvalid();
1345 }
1346  
1347 int NCDVal_MapInsert (NCDValRef map, NCDValRef key, NCDValRef val, int *out_inserted)
1348 {
1349 ASSERT(NCDVal_IsMap(map))
1350 ASSERT(NCDVal_MapCount(map) < NCDVal_MapMaxCount(map))
1351 ASSERT(key.mem == map.mem)
1352 ASSERT(val.mem == map.mem)
1353 assert_val_only(map.mem, key.idx);
1354 assert_val_only(map.mem, val.idx);
1355  
1356 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1357  
1358 int new_type = map_e->type;
1359 if (!bump_depth(&new_type, get_val_depth(key)) || !bump_depth(&new_type, get_val_depth(val))) {
1360 goto fail0;
1361 }
1362  
1363 NCDVal__idx elemidx = make_map_elem_idx(map.idx, map_e->count);
1364  
1365 struct NCDVal__mapelem *me_e = buffer_at(map.mem, elemidx);
1366 ASSERT(me_e == &map_e->elems[map_e->count])
1367 me_e->key_idx = key.idx;
1368 me_e->val_idx = val.idx;
1369  
1370 int res = NCDVal__MapTree_Insert(&map_e->tree, map.mem, NCDVal__MapTreeDeref(map.mem, elemidx), NULL);
1371 if (!res) {
1372 if (out_inserted) {
1373 *out_inserted = 0;
1374 }
1375 return 1;
1376 }
1377  
1378 map_e->type = new_type;
1379 map_e->count++;
1380  
1381 if (out_inserted) {
1382 *out_inserted = 1;
1383 }
1384 return 1;
1385  
1386 fail0:
1387 return 0;
1388 }
1389  
1390 size_t NCDVal_MapCount (NCDValRef map)
1391 {
1392 ASSERT(NCDVal_IsMap(map))
1393  
1394 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1395  
1396 return map_e->count;
1397 }
1398  
1399 size_t NCDVal_MapMaxCount (NCDValRef map)
1400 {
1401 ASSERT(NCDVal_IsMap(map))
1402  
1403 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1404  
1405 return map_e->maxcount;
1406 }
1407  
1408 int NCDVal_MapElemInvalid (NCDValMapElem me)
1409 {
1410 ASSERT(me.elemidx >= 0 || me.elemidx == -1)
1411  
1412 return me.elemidx < 0;
1413 }
1414  
1415 NCDValMapElem NCDVal_MapFirst (NCDValRef map)
1416 {
1417 ASSERT(NCDVal_IsMap(map))
1418  
1419 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1420  
1421 if (map_e->count == 0) {
1422 return make_map_elem(-1);
1423 }
1424  
1425 NCDVal__idx elemidx = make_map_elem_idx(map.idx, 0);
1426 assert_map_elem_only(map, elemidx);
1427  
1428 return make_map_elem(elemidx);
1429 }
1430  
1431 NCDValMapElem NCDVal_MapNext (NCDValRef map, NCDValMapElem me)
1432 {
1433 assert_map_elem(map, me);
1434  
1435 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1436 ASSERT(map_e->count > 0)
1437  
1438 NCDVal__idx last_elemidx = make_map_elem_idx(map.idx, map_e->count - 1);
1439 ASSERT(me.elemidx <= last_elemidx)
1440  
1441 if (me.elemidx == last_elemidx) {
1442 return make_map_elem(-1);
1443 }
1444  
1445 NCDVal__idx elemidx = me.elemidx + sizeof(struct NCDVal__mapelem);
1446 assert_map_elem_only(map, elemidx);
1447  
1448 return make_map_elem(elemidx);
1449 }
1450  
1451 NCDValMapElem NCDVal_MapOrderedFirst (NCDValRef map)
1452 {
1453 ASSERT(NCDVal_IsMap(map))
1454  
1455 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1456  
1457 NCDVal__MapTreeRef ref = NCDVal__MapTree_GetFirst(&map_e->tree, map.mem);
1458 ASSERT(ref.link == -1 || (assert_map_elem_only(map, ref.link), 1))
1459  
1460 return make_map_elem(ref.link);
1461 }
1462  
1463 NCDValMapElem NCDVal_MapOrderedNext (NCDValRef map, NCDValMapElem me)
1464 {
1465 assert_map_elem(map, me);
1466  
1467 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1468  
1469 NCDVal__MapTreeRef ref = NCDVal__MapTree_GetNext(&map_e->tree, map.mem, NCDVal__MapTreeDeref(map.mem, me.elemidx));
1470 ASSERT(ref.link == -1 || (assert_map_elem_only(map, ref.link), 1))
1471  
1472 return make_map_elem(ref.link);
1473 }
1474  
1475 NCDValRef NCDVal_MapElemKey (NCDValRef map, NCDValMapElem me)
1476 {
1477 assert_map_elem(map, me);
1478  
1479 struct NCDVal__mapelem *me_e = buffer_at(map.mem, me.elemidx);
1480  
1481 return make_ref(map.mem, me_e->key_idx);
1482 }
1483  
1484 NCDValRef NCDVal_MapElemVal (NCDValRef map, NCDValMapElem me)
1485 {
1486 assert_map_elem(map, me);
1487  
1488 struct NCDVal__mapelem *me_e = buffer_at(map.mem, me.elemidx);
1489  
1490 return make_ref(map.mem, me_e->val_idx);
1491 }
1492  
1493 NCDValMapElem NCDVal_MapFindKey (NCDValRef map, NCDValRef key)
1494 {
1495 ASSERT(NCDVal_IsMap(map))
1496 assert_val(key);
1497  
1498 struct NCDVal__map *map_e = buffer_at(map.mem, map.idx);
1499  
1500 NCDVal__MapTreeRef ref = NCDVal__MapTree_LookupExact(&map_e->tree, map.mem, key);
1501 ASSERT(ref.link == -1 || (assert_map_elem_only(map, ref.link), 1))
1502  
1503 return make_map_elem(ref.link);
1504 }
1505  
1506 NCDValRef NCDVal_MapGetValue (NCDValRef map, const char *key_str)
1507 {
1508 ASSERT(NCDVal_IsMap(map))
1509 ASSERT(key_str)
1510  
1511 NCDValMem mem;
1512 mem.string_index = map.mem->string_index;
1513 mem.size = NCDVAL_FASTBUF_SIZE;
1514 mem.used = sizeof(struct NCDVal__externalstring);
1515 mem.first_ref = -1;
1516  
1517 struct NCDVal__externalstring *exs_e = (void *)mem.fastbuf;
1518 exs_e->type = make_type(EXTERNALSTRING_TYPE, 0);
1519 exs_e->data = key_str;
1520 exs_e->length = strlen(key_str);
1521 exs_e->ref.target = NULL;
1522  
1523 NCDValRef key = make_ref(&mem, 0);
1524  
1525 NCDValMapElem elem = NCDVal_MapFindKey(map, key);
1526 if (NCDVal_MapElemInvalid(elem)) {
1527 return NCDVal_NewInvalid();
1528 }
1529  
1530 return NCDVal_MapElemVal(map, elem);
1531 }
1532  
1533 static void replaceprog_build_recurser (NCDValMem *mem, NCDVal__idx idx, size_t *out_num_instr, NCDValReplaceProg *prog)
1534 {
1535 ASSERT(idx >= 0)
1536 assert_val_only(mem, idx);
1537 ASSERT(out_num_instr)
1538  
1539 *out_num_instr = 0;
1540  
1541 void *ptr = buffer_at(mem, idx);
1542  
1543 struct NCDVal__instr instr;
1544  
1545 switch (get_internal_type(*((int *)(ptr)))) {
1546 case STOREDSTRING_TYPE:
1547 case IDSTRING_TYPE:
1548 case EXTERNALSTRING_TYPE: {
1549 } break;
1550  
1551 case NCDVAL_LIST: {
1552 struct NCDVal__list *list_e = ptr;
1553  
1554 for (NCDVal__idx i = 0; i < list_e->count; i++) {
1555 int elem_changed = 0;
1556  
1557 if (list_e->elem_indices[i] < -1) {
1558 if (prog) {
1559 instr.type = NCDVAL_INSTR_PLACEHOLDER;
1560 instr.placeholder.plid = list_e->elem_indices[i] - NCDVAL_MINIDX;
1561 instr.placeholder.plidx = idx + offsetof(struct NCDVal__list, elem_indices) + i * sizeof(NCDVal__idx);
1562 prog->instrs[prog->num_instrs++] = instr;
1563 }
1564 (*out_num_instr)++;
1565 elem_changed = 1;
1566 } else {
1567 size_t elem_num_instr;
1568 replaceprog_build_recurser(mem, list_e->elem_indices[i], &elem_num_instr, prog);
1569 (*out_num_instr) += elem_num_instr;
1570 if (elem_num_instr > 0) {
1571 elem_changed = 1;
1572 }
1573 }
1574  
1575 if (elem_changed) {
1576 if (prog) {
1577 instr.type = NCDVAL_INSTR_BUMPDEPTH;
1578 instr.bumpdepth.parent_idx = idx;
1579 instr.bumpdepth.child_idx_idx = idx + offsetof(struct NCDVal__list, elem_indices) + i * sizeof(NCDVal__idx);
1580 prog->instrs[prog->num_instrs++] = instr;
1581 }
1582 (*out_num_instr)++;
1583 }
1584 }
1585 } break;
1586  
1587 case NCDVAL_MAP: {
1588 struct NCDVal__map *map_e = ptr;
1589  
1590 for (NCDVal__idx i = 0; i < map_e->count; i++) {
1591 int key_changed = 0;
1592 int val_changed = 0;
1593  
1594 if (map_e->elems[i].key_idx < -1) {
1595 if (prog) {
1596 instr.type = NCDVAL_INSTR_PLACEHOLDER;
1597 instr.placeholder.plid = map_e->elems[i].key_idx - NCDVAL_MINIDX;
1598 instr.placeholder.plidx = idx + offsetof(struct NCDVal__map, elems) + i * sizeof(struct NCDVal__mapelem) + offsetof(struct NCDVal__mapelem, key_idx);
1599 prog->instrs[prog->num_instrs++] = instr;
1600 }
1601 (*out_num_instr)++;
1602 key_changed = 1;
1603 } else {
1604 size_t key_num_instr;
1605 replaceprog_build_recurser(mem, map_e->elems[i].key_idx, &key_num_instr, prog);
1606 (*out_num_instr) += key_num_instr;
1607 if (key_num_instr > 0) {
1608 key_changed = 1;
1609 }
1610 }
1611  
1612 if (map_e->elems[i].val_idx < -1) {
1613 if (prog) {
1614 instr.type = NCDVAL_INSTR_PLACEHOLDER;
1615 instr.placeholder.plid = map_e->elems[i].val_idx - NCDVAL_MINIDX;
1616 instr.placeholder.plidx = idx + offsetof(struct NCDVal__map, elems) + i * sizeof(struct NCDVal__mapelem) + offsetof(struct NCDVal__mapelem, val_idx);
1617 prog->instrs[prog->num_instrs++] = instr;
1618 }
1619 (*out_num_instr)++;
1620 val_changed = 1;
1621 } else {
1622 size_t val_num_instr;
1623 replaceprog_build_recurser(mem, map_e->elems[i].val_idx, &val_num_instr, prog);
1624 (*out_num_instr) += val_num_instr;
1625 if (val_num_instr > 0) {
1626 val_changed = 1;
1627 }
1628 }
1629  
1630 if (key_changed) {
1631 if (prog) {
1632 instr.type = NCDVAL_INSTR_REINSERT;
1633 instr.reinsert.mapidx = idx;
1634 instr.reinsert.elempos = i;
1635 prog->instrs[prog->num_instrs++] = instr;
1636 }
1637 (*out_num_instr)++;
1638  
1639 if (prog) {
1640 instr.type = NCDVAL_INSTR_BUMPDEPTH;
1641 instr.bumpdepth.parent_idx = idx;
1642 instr.bumpdepth.child_idx_idx = idx + offsetof(struct NCDVal__map, elems) + i * sizeof(struct NCDVal__mapelem) + offsetof(struct NCDVal__mapelem, key_idx);
1643 prog->instrs[prog->num_instrs++] = instr;
1644 }
1645 (*out_num_instr)++;
1646 }
1647  
1648 if (val_changed) {
1649 if (prog) {
1650 instr.type = NCDVAL_INSTR_BUMPDEPTH;
1651 instr.bumpdepth.parent_idx = idx;
1652 instr.bumpdepth.child_idx_idx = idx + offsetof(struct NCDVal__map, elems) + i * sizeof(struct NCDVal__mapelem) + offsetof(struct NCDVal__mapelem, val_idx);
1653 prog->instrs[prog->num_instrs++] = instr;
1654 }
1655 (*out_num_instr)++;
1656 }
1657 }
1658 } break;
1659  
1660 default: ASSERT(0);
1661 }
1662 }
1663  
1664 int NCDValReplaceProg_Init (NCDValReplaceProg *o, NCDValRef val)
1665 {
1666 assert_val(val);
1667 ASSERT(!NCDVal_IsPlaceholder(val))
1668  
1669 size_t num_instrs;
1670 replaceprog_build_recurser(val.mem, val.idx, &num_instrs, NULL);
1671  
1672 if (!(o->instrs = BAllocArray(num_instrs, sizeof(o->instrs[0])))) {
1673 BLog(BLOG_ERROR, "BAllocArray failed");
1674 return 0;
1675 }
1676  
1677 o->num_instrs = 0;
1678  
1679 size_t num_instrs2;
1680 replaceprog_build_recurser(val.mem, val.idx, &num_instrs2, o);
1681  
1682 ASSERT(num_instrs2 == num_instrs)
1683 ASSERT(o->num_instrs == num_instrs)
1684  
1685 return 1;
1686 }
1687  
1688 void NCDValReplaceProg_Free (NCDValReplaceProg *o)
1689 {
1690 BFree(o->instrs);
1691 }
1692  
1693 int NCDValReplaceProg_Execute (NCDValReplaceProg prog, NCDValMem *mem, NCDVal_replace_func replace, void *arg)
1694 {
1695 assert_mem(mem);
1696 ASSERT(replace)
1697  
1698 for (size_t i = 0; i < prog.num_instrs; i++) {
1699 struct NCDVal__instr instr = prog.instrs[i];
1700  
1701 switch (instr.type) {
1702 case NCDVAL_INSTR_PLACEHOLDER: {
1703 #ifndef NDEBUG
1704 NCDVal__idx *check_plptr = buffer_at(mem, instr.placeholder.plidx);
1705 ASSERT(*check_plptr < -1)
1706 ASSERT(*check_plptr - NCDVAL_MINIDX == instr.placeholder.plid)
1707 #endif
1708 NCDValRef repval;
1709 if (!replace(arg, instr.placeholder.plid, mem, &repval) || NCDVal_IsInvalid(repval)) {
1710 return 0;
1711 }
1712 ASSERT(repval.mem == mem)
1713  
1714 NCDVal__idx *plptr = buffer_at(mem, instr.placeholder.plidx);
1715 *plptr = repval.idx;
1716 } break;
1717  
1718 case NCDVAL_INSTR_REINSERT: {
1719 assert_val_only(mem, instr.reinsert.mapidx);
1720 struct NCDVal__map *map_e = buffer_at(mem, instr.reinsert.mapidx);
1721 ASSERT(get_internal_type(map_e->type) == NCDVAL_MAP)
1722 ASSERT(instr.reinsert.elempos >= 0)
1723 ASSERT(instr.reinsert.elempos < map_e->count)
1724  
1725 NCDVal__MapTreeRef ref = {&map_e->elems[instr.reinsert.elempos], make_map_elem_idx(instr.reinsert.mapidx, instr.reinsert.elempos)};
1726 NCDVal__MapTree_Remove(&map_e->tree, mem, ref);
1727 if (!NCDVal__MapTree_Insert(&map_e->tree, mem, ref, NULL)) {
1728 BLog(BLOG_ERROR, "duplicate key in map");
1729 return 0;
1730 }
1731 } break;
1732  
1733 case NCDVAL_INSTR_BUMPDEPTH: {
1734 assert_val_only(mem, instr.bumpdepth.parent_idx);
1735 int *parent_type_ptr = buffer_at(mem, instr.bumpdepth.parent_idx);
1736  
1737 NCDVal__idx *child_type_idx_ptr = buffer_at(mem, instr.bumpdepth.child_idx_idx);
1738 assert_val_only(mem, *child_type_idx_ptr);
1739 int *child_type_ptr = buffer_at(mem, *child_type_idx_ptr);
1740  
1741 if (!bump_depth(parent_type_ptr, get_depth(*child_type_ptr))) {
1742 BLog(BLOG_ERROR, "depth limit exceeded");
1743 return 0;
1744 }
1745 } break;
1746  
1747 default: ASSERT(0);
1748 }
1749 }
1750  
1751 return 1;
1752 }