2.57
xs.h
1/* copyright (c) 2022 - 2024 grunfink et al. / MIT license */
2
3#ifndef _XS_H
4
5#define _XS_H
6
7#include <stdio.h>
8#include <string.h>
9#include <stdlib.h>
10#include <ctype.h>
11#include <unistd.h>
12#include <stdarg.h>
13#include <signal.h>
14#include <errno.h>
15
16typedef enum {
17 XSTYPE_STRING = 0x02, /* C string (\0 delimited) (NOT STORED) */
18 XSTYPE_NUMBER = 0x17, /* double in spirit, stored as a C string (\0 delimited) */
19 XSTYPE_NULL = 0x18, /* Special NULL value */
20 XSTYPE_TRUE = 0x06, /* Boolean */
21 XSTYPE_FALSE = 0x15, /* Boolean */
22 XSTYPE_LIST = 0x1d, /* Sequence of LITEMs up to EOM (with size) */
23 XSTYPE_LITEM = 0x1f, /* Element of a list (any type) */
24 XSTYPE_DICT = 0x1c, /* Sequence of KEYVALs up to EOM (with size) */
25 XSTYPE_KEYVAL = 0x1e, /* key + value (STRING key + any type) */
26 XSTYPE_EOM = 0x19, /* End of Multiple (LIST or DICT) */
27 XSTYPE_DATA = 0x10 /* A block of anonymous data */
28} xstype;
29
30
31/* types */
32typedef char xs_val;
33typedef char xs_str;
34typedef char xs_list;
35typedef char xs_keyval;
36typedef char xs_dict;
37typedef char xs_number;
38typedef char xs_data;
39
40/* size in bytes of the type size */
41#define _XS_TYPE_SIZE 4
42
43/* auto-destroyable strings */
44#define xs __attribute__ ((__cleanup__ (_xs_destroy))) xs_val
45
46/* not really all, just very much */
47#define XS_ALL 0xfffffff
48
49#ifndef xs_countof
50#define xs_countof(a) (sizeof((a)) / sizeof((*a)))
51#endif
52
53void *xs_free(void *ptr);
54void *_xs_realloc(void *ptr, size_t size, const char *file, int line, const char *func);
55#define xs_realloc(ptr, size) _xs_realloc(ptr, size, __FILE__, __LINE__, __func__)
56int _xs_blk_size(int sz);
57void _xs_destroy(char **var);
58#define xs_debug() raise(SIGTRAP)
59xstype xs_type(const xs_val *data);
60int xs_size(const xs_val *data);
61int xs_is_null(const xs_val *data);
62int xs_cmp(const xs_val *v1, const xs_val *v2);
63xs_val *xs_dup(const xs_val *data);
64xs_val *xs_expand(xs_val *data, int offset, int size);
65xs_val *xs_collapse(xs_val *data, int offset, int size);
66xs_val *xs_insert_m(xs_val *data, int offset, const char *mem, int size);
67#define xs_insert(data, offset, data2) xs_insert_m(data, offset, data2, xs_size(data2))
68#define xs_append_m(data, mem, size) xs_insert_m(data, xs_size(data) - 1, mem, size)
69xs_val *xs_stock(int type);
70
71xs_str *xs_str_new(const char *str);
72xs_str *xs_str_new_sz(const char *mem, int sz);
73xs_str *xs_str_wrap_i(const char *prefix, xs_str *str, const char *suffix);
74#define xs_str_prepend_i(str, prefix) xs_str_wrap_i(prefix, str, NULL)
75xs_str *_xs_str_cat(xs_str *str, const char *strs[]);
76#define xs_str_cat(str, ...) _xs_str_cat(str, (const char *[]){ __VA_ARGS__, NULL })
77xs_str *xs_replace_in(xs_str *str, const char *sfrom, const char *sto, int times);
78#define xs_replace_i(str, sfrom, sto) xs_replace_in(str, sfrom, sto, XS_ALL)
79#define xs_replace(str, sfrom, sto) xs_replace_in(xs_dup(str), sfrom, sto, XS_ALL)
80#define xs_replace_n(str, sfrom, sto, times) xs_replace_in(xs_dup(str), sfrom, sto, times)
81xs_str *xs_fmt(const char *fmt, ...);
82int xs_str_in(const char *haystack, const char *needle);
83int xs_between(const char *prefix, const char *str, const char *suffix);
84#define xs_startswith(str, prefix) xs_between(prefix, str, NULL)
85#define xs_endswith(str, suffix) xs_between(NULL, str, suffix)
86xs_str *xs_crop_i(xs_str *str, int start, int end);
87xs_str *xs_lstrip_chars_i(xs_str *str, const char *chars);
88xs_str *xs_rstrip_chars_i(xs_str *str, const char *chars);
89xs_str *xs_strip_chars_i(xs_str *str, const char *chars);
90#define xs_strip_i(str) xs_strip_chars_i(str, " \r\n\t\v\f")
91xs_str *xs_tolower_i(xs_str *str);
92
93xs_list *xs_list_new(void);
94xs_list *xs_list_append_m(xs_list *list, const char *mem, int dsz);
95xs_list *_xs_list_append(xs_list *list, const xs_val *vals[]);
96#define xs_list_append(list, ...) _xs_list_append(list, (const xs_val *[]){ __VA_ARGS__, NULL })
97int xs_list_iter(xs_list **list, const xs_val **value);
98int xs_list_next(const xs_list *list, const xs_val **value, int *ctxt);
99int xs_list_len(const xs_list *list);
100const xs_val *xs_list_get(const xs_list *list, int num);
101xs_list *xs_list_del(xs_list *list, int num);
102xs_list *xs_list_insert(xs_list *list, int num, const xs_val *data);
103xs_list *xs_list_set(xs_list *list, int num, const xs_val *data);
104xs_list *xs_list_dequeue(xs_list *list, xs_val **data, int last);
105#define xs_list_pop(list, data) xs_list_dequeue(list, data, 1)
106#define xs_list_shift(list, data) xs_list_dequeue(list, data, 0)
107int xs_list_in(const xs_list *list, const xs_val *val);
108xs_str *xs_join(const xs_list *list, const char *sep);
109xs_list *xs_split_n(const char *str, const char *sep, int times);
110#define xs_split(str, sep) xs_split_n(str, sep, XS_ALL)
111xs_list *xs_list_cat(xs_list *l1, const xs_list *l2);
112
113int xs_keyval_size(const xs_str *key, const xs_val *value);
114xs_str *xs_keyval_key(const xs_keyval *keyval);
115xs_val *xs_keyval_value(const xs_keyval *keyval);
116xs_keyval *xs_keyval_make(xs_keyval *keyval, const xs_str *key, const xs_val *value);
117
118xs_dict *xs_dict_new(void);
119xs_dict *xs_dict_append(xs_dict *dict, const xs_str *key, const xs_val *value);
120xs_dict *xs_dict_prepend(xs_dict *dict, const xs_str *key, const xs_val *value);
121int xs_dict_next(const xs_dict *dict, const xs_str **key, const xs_val **value, int *ctxt);
122const xs_val *xs_dict_get_def(const xs_dict *dict, const xs_str *key, const xs_val *def);
123#define xs_dict_get(dict, key) xs_dict_get_def(dict, key, NULL)
124xs_dict *xs_dict_del(xs_dict *dict, const xs_str *key);
125xs_dict *xs_dict_set(xs_dict *dict, const xs_str *key, const xs_val *data);
126xs_dict *xs_dict_gc(const xs_dict *dict);
127
128const xs_val *xs_dict_get_path_sep(const xs_dict *dict, const char *path, const char *sep);
129#define xs_dict_get_path(dict, path) xs_dict_get_path_sep(dict, path, ".")
130xs_dict *xs_dict_set_path_sep(xs_dict *dict, const char *path, const xs_val *value, const char *sep);
131#define xs_dict_set_path(dict, path, value) xs_dict_set_path_sep(dict, path, value, ".")
132
133xs_val *xs_val_new(xstype t);
134xs_number *xs_number_new(double f);
135double xs_number_get(const xs_number *v);
136const char *xs_number_str(const xs_number *v);
137
138xs_data *xs_data_new(const void *data, int size);
139int xs_data_size(const xs_data *value);
140void xs_data_get(void *data, const xs_data *value);
141
142void *xs_memmem(const char *haystack, int h_size, const char *needle, int n_size);
143
144unsigned int xs_hash_func(const char *data, int size);
145
146#ifdef XS_ASSERT
147#include <assert.h>
148#define XS_ASSERT_TYPE(v, t) assert(xs_type(v) == t)
149#define XS_ASSERT_TYPE_NULL(v, t) assert(v == NULL || xs_type(v) == t)
150#else
151#define XS_ASSERT_TYPE(v, t) (void)(0)
152#define XS_ASSERT_TYPE_NULL(v, t) (void)(0)
153#endif
154
155#define xs_return(v) xs_val *__r = v; v = NULL; return __r
156
157#define xs_is_true(v) (xs_type((v)) == XSTYPE_TRUE)
158#define xs_is_false(v) (xs_type((v)) == XSTYPE_FALSE)
159
160#ifdef XS_IMPLEMENTATION
161
162void *_xs_realloc(void *ptr, size_t size, const char *file, int line, const char *func)
163{
164 xs_val *ndata = realloc(ptr, size);
165
166 if (ndata == NULL) {
167 fprintf(stderr, "**OUT OF MEMORY**\n");
168 abort();
169 }
170
171#ifdef XS_DEBUG
172 if (ndata != ptr) {
173 int n;
174 FILE *f = fopen("xs_memory.out", "a");
175
176 if (ptr != NULL)
177 fprintf(f, "%p r\n", ptr);
178
179 fprintf(f, "%p a %ld %s:%d: %s", ndata, size, file, line, func);
180
181 if (ptr != NULL) {
182 fprintf(f, " [");
183 for (n = 0; n < 32 && ndata[n]; n++) {
184 if (ndata[n] >= 32 && ndata[n] <= 127)
185 fprintf(f, "%c", ndata[n]);
186 else
187 fprintf(f, "\\%02x", (unsigned char)ndata[n]);
188 }
189 fprintf(f, "]");
190 }
191
192 fprintf(f, "\n");
193
194 fclose(f);
195 }
196#else
197 (void)file;
198 (void)line;
199 (void)func;
200#endif
201
202 return ndata;
203}
204
205
206void *xs_free(void *ptr)
207{
208#ifdef XS_DEBUG
209 if (ptr != NULL) {
210 FILE *f = fopen("xs_memory.out", "a");
211 fprintf(f, "%p b\n", ptr);
212 fclose(f);
213 }
214#endif
215
216 free(ptr);
217 return NULL;
218}
219
220
221void _xs_destroy(char **var)
222{
223/*
224 if (_xs_debug)
225 printf("_xs_destroy %p\n", var);
226*/
227 xs_free(*var);
228}
229
230
231int _xs_blk_size(int sz)
232/* calculates the block size */
233{
234 int blk_size = 4096;
235
236 if (sz < 256)
237 blk_size = 32;
238 else
239 if (sz < 4096)
240 blk_size = 256;
241
242 return ((((sz) + blk_size) / blk_size) * blk_size);
243}
244
245
246xstype xs_type(const xs_val *data)
247/* return the type of data */
248{
249 xstype t;
250
251 if (data == NULL)
252 t = XSTYPE_NULL;
253 else
254 switch (data[0]) {
255 case XSTYPE_NULL:
256 case XSTYPE_TRUE:
257 case XSTYPE_FALSE:
258 case XSTYPE_LIST:
259 case XSTYPE_LITEM:
260 case XSTYPE_DICT:
261 case XSTYPE_KEYVAL:
262 case XSTYPE_NUMBER:
263 case XSTYPE_EOM:
264 case XSTYPE_DATA:
265 t = data[0];
266 break;
267 default:
268 t = XSTYPE_STRING;
269 break;
270 }
271
272 return t;
273}
274
275
276void _xs_put_size(xs_val *ptr, int i)
277/* must match _XS_TYPE_SIZE */
278{
279 memcpy(ptr + 1, &i, sizeof(i));
280}
281
282
283int _xs_get_size(const xs_val *ptr)
284/* must match _XS_TYPE_SIZE */
285{
286 int i;
287 memcpy(&i, ptr + 1, sizeof(i));
288 return i;
289}
290
291
292int xs_size(const xs_val *data)
293/* returns the size of data in bytes */
294{
295 int len = 0;
296 const char *p;
297
298 if (data == NULL)
299 return 0;
300
301 switch (xs_type(data)) {
302 case XSTYPE_STRING:
303 len = strlen(data) + 1;
304 break;
305
306 case XSTYPE_LIST:
307 case XSTYPE_DICT:
308 case XSTYPE_DATA:
309 len = _xs_get_size(data);
310
311 break;
312
313 case XSTYPE_KEYVAL:
314 /* calculate the size of the key and the value */
315 p = data + 1;
316 p += xs_size(p);
317 p += xs_size(p);
318
319 len = p - data;
320
321 break;
322
323 case XSTYPE_LITEM:
324 /* it's the size of the item + 1 */
325 p = data + 1;
326 p += xs_size(p);
327
328 len = p - data;
329
330 break;
331
332 case XSTYPE_NUMBER:
333 len = 1 + xs_size(data + 1);
334
335 break;
336
337 default:
338 len = 1;
339 }
340
341 return len;
342}
343
344
345int xs_is_null(const xs_val *data)
346/* checks for null */
347{
348 return (xs_type(data) == XSTYPE_NULL);
349}
350
351
352int xs_cmp(const xs_val *v1, const xs_val *v2)
353/* compares two values */
354{
355 int s1 = xs_size(v1);
356 int s2 = xs_size(v2);
357 int d = s1 - s2;
358
359 return d == 0 ? memcmp(v1, v2, s1) : d;
360}
361
362
363xs_val *xs_dup(const xs_val *data)
364/* creates a duplicate of data */
365{
366 xs_val *s = NULL;
367
368 if (data) {
369 int sz = xs_size(data);
370 s = xs_realloc(NULL, _xs_blk_size(sz));
371
372 memcpy(s, data, sz);
373 }
374
375 return s;
376}
377
378
379xs_val *xs_expand(xs_val *data, int offset, int size)
380/* opens a hole in data */
381{
382 int sz = xs_size(data);
383 int n;
384
385 sz += size;
386
387 /* open room */
388 data = xs_realloc(data, _xs_blk_size(sz));
389
390 /* move up the rest of the data */
391 for (n = sz - 1; n >= offset + size; n--)
392 data[n] = data[n - size];
393
394 if (xs_type(data) == XSTYPE_LIST ||
395 xs_type(data) == XSTYPE_DICT ||
396 xs_type(data) == XSTYPE_DATA)
397 _xs_put_size(data, sz);
398
399 return data;
400}
401
402
403xs_val *xs_collapse(xs_val *data, int offset, int size)
404/* shrinks data */
405{
406 int sz = xs_size(data);
407 int n;
408
409 /* don't try to delete beyond the limit */
410 if (offset + size > sz)
411 size = sz - offset;
412
413 /* shrink total size */
414 sz -= size;
415
416 for (n = offset; n < sz; n++)
417 data[n] = data[n + size];
418
419 if (xs_type(data) == XSTYPE_LIST ||
420 xs_type(data) == XSTYPE_DICT ||
421 xs_type(data) == XSTYPE_DATA)
422 _xs_put_size(data, sz);
423
424 return xs_realloc(data, _xs_blk_size(sz));
425}
426
427
428xs_val *xs_insert_m(xs_val *data, int offset, const char *mem, int size)
429/* inserts a memory block */
430{
431 data = xs_expand(data, offset, size);
432 memcpy(data + offset, mem, size);
433
434 return data;
435}
436
437
438xs_val *xs_stock(int type)
439/* returns stock values */
440{
441 static xs_val stock_null[] = { XSTYPE_NULL };
442 static xs_val stock_true[] = { XSTYPE_TRUE };
443 static xs_val stock_false[] = { XSTYPE_FALSE };
444 static xs_val stock_0[] = { XSTYPE_NUMBER, '0', '\0' };
445 static xs_val stock_1[] = { XSTYPE_NUMBER, '1', '\0' };
446 static xs_list *stock_list = NULL;
447 static xs_dict *stock_dict = NULL;
448
449 switch (type) {
450 case 0: return stock_0;
451 case 1: return stock_1;
452 case XSTYPE_NULL: return stock_null;
453 case XSTYPE_TRUE: return stock_true;
454 case XSTYPE_FALSE: return stock_false;
455
456 case XSTYPE_LIST:
457 if (stock_list == NULL)
458 stock_list = xs_list_new();
459 return stock_list;
460
461 case XSTYPE_DICT:
462 if (stock_dict == NULL)
463 stock_dict = xs_dict_new();
464 return stock_dict;
465 }
466
467 return NULL;
468}
469
470
471/** strings **/
472
473xs_str *xs_str_new(const char *str)
474/* creates a new string */
475{
476 return xs_insert(NULL, 0, str ? str : "");
477}
478
479
480xs_str *xs_str_new_sz(const char *mem, int sz)
481/* creates a new string from a memory block, adding an asciiz */
482{
483 xs_str *s = xs_realloc(NULL, _xs_blk_size(sz + 1));
484 memcpy(s, mem, sz);
485 s[sz] = '\0';
486
487 return s;
488}
489
490
491xs_str *xs_str_wrap_i(const char *prefix, xs_str *str, const char *suffix)
492/* wraps str with prefix and suffix */
493{
494 XS_ASSERT_TYPE(str, XSTYPE_STRING);
495
496 if (prefix)
497 str = xs_insert_m(str, 0, prefix, strlen(prefix));
498
499 if (suffix)
500 str = xs_insert_m(str, strlen(str), suffix, strlen(suffix));
501
502 return str;
503}
504
505
506xs_str *_xs_str_cat(xs_str *str, const char *strs[])
507/* concatenates all strings after str */
508{
509 int o = strlen(str);
510
511 while (*strs) {
512 int sz = strlen(*strs);
513 str = xs_insert_m(str, o, *strs, sz);
514 o += sz;
515 strs++;
516 }
517
518 return str;
519}
520
521
522xs_str *xs_replace_in(xs_str *str, const char *sfrom, const char *sto, int times)
523/* replaces inline all sfrom with sto */
524{
525 XS_ASSERT_TYPE(str, XSTYPE_STRING);
526
527 int sfsz = strlen(sfrom);
528 int stsz = strlen(sto);
529 int diff = stsz - sfsz;
530 char *ss;
531 int offset = 0;
532
533 while (times > 0 && (ss = strstr(str + offset, sfrom)) != NULL) {
534 int n_offset = ss - str;
535
536 if (diff < 0)
537 str = xs_collapse(str, n_offset, -diff);
538 else
539 if (diff > 0)
540 str = xs_expand(str, n_offset, diff);
541
542 memcpy(str + n_offset, sto, stsz);
543
544 offset = n_offset + stsz;
545
546 times--;
547 }
548
549 return str;
550}
551
552
553xs_str *xs_fmt(const char *fmt, ...)
554/* formats a string with printf()-like marks */
555{
556 int n;
557 xs_str *s = NULL;
558 va_list ap;
559
560 va_start(ap, fmt);
561 n = vsnprintf(s, 0, fmt, ap);
562 va_end(ap);
563
564 if (n > 0) {
565 s = xs_realloc(NULL, _xs_blk_size(n + 1));
566
567 va_start(ap, fmt);
568 vsnprintf(s, n + 1, fmt, ap);
569 va_end(ap);
570 }
571
572 return s;
573}
574
575
576int xs_str_in(const char *haystack, const char *needle)
577/* finds needle in haystack and returns the offset or -1 */
578{
579 char *s;
580 int r = -1;
581
582 if ((s = strstr(haystack, needle)) != NULL)
583 r = s - haystack;
584
585 return r;
586}
587
588
589int xs_between(const char *prefix, const char *str, const char *suffix)
590/* returns true if str starts with prefix and ends with suffix */
591{
592 int sz = strlen(str);
593 int psz = prefix ? strlen(prefix) : 0;
594 int ssz = suffix ? strlen(suffix) : 0;
595
596 if (sz < psz || sz < ssz)
597 return 0;
598
599 if (prefix && memcmp(str, prefix, psz) != 0)
600 return 0;
601
602 if (suffix && memcmp(str + sz - ssz, suffix, ssz) != 0)
603 return 0;
604
605 return 1;
606}
607
608
609xs_str *xs_crop_i(xs_str *str, int start, int end)
610/* crops the string to be only from start to end */
611{
612 XS_ASSERT_TYPE(str, XSTYPE_STRING);
613
614 int sz = strlen(str);
615
616 if (end <= 0)
617 end = sz + end;
618
619 /* crop from the top */
620 str[end] = '\0';
621
622 /* crop from the bottom */
623 str = xs_collapse(str, 0, start);
624
625 return str;
626}
627
628
629xs_str *xs_lstrip_chars_i(xs_str *str, const char *chars)
630/* strips all chars from the start of str */
631{
632 int n;
633
634 for (n = 0; str[n] && strchr(chars, str[n]); n++);
635
636 if (n)
637 str = xs_collapse(str, 0, n);
638
639 return str;
640}
641
642
643xs_str *xs_rstrip_chars_i(xs_str *str, const char *chars)
644/* strips all chars from the end of str */
645{
646 int n;
647
648 for (n = strlen(str); n > 0 && strchr(chars, str[n - 1]); n--);
649 str[n] = '\0';
650
651 return str;
652}
653
654
655xs_str *xs_strip_chars_i(xs_str *str, const char *chars)
656/* strips the string of chars from the start and the end */
657{
658 return xs_lstrip_chars_i(xs_rstrip_chars_i(str, chars), chars);
659}
660
661
662xs_str *xs_tolower_i(xs_str *str)
663/* convert to lowercase */
664{
665 XS_ASSERT_TYPE(str, XSTYPE_STRING);
666
667 int n;
668
669 for (n = 0; str[n]; n++)
670 str[n] = tolower(str[n]);
671
672 return str;
673}
674
675
676/** lists **/
677
678xs_list *xs_list_new(void)
679/* creates a new list */
680{
681 int sz = 1 + _XS_TYPE_SIZE + 1;
682 xs_list *l = xs_realloc(NULL, sz);
683 memset(l, XSTYPE_EOM, sz);
684
685 l[0] = XSTYPE_LIST;
686 _xs_put_size(l, sz);
687
688 return l;
689}
690
691
692xs_list *_xs_list_write_litem(xs_list *list, int offset, const char *mem, int dsz)
693/* writes a list item */
694{
695 XS_ASSERT_TYPE(list, XSTYPE_LIST);
696
697 if (mem == NULL) {
698 mem = xs_stock(XSTYPE_NULL);
699 dsz = xs_size(mem);
700 }
701
702 list = xs_expand(list, offset, dsz + 1);
703
704 list[offset] = XSTYPE_LITEM;
705 memcpy(list + offset + 1, mem, dsz);
706
707 return list;
708}
709
710
711xs_list *xs_list_append_m(xs_list *list, const char *mem, int dsz)
712/* adds a memory block to the list */
713{
714 XS_ASSERT_TYPE(list, XSTYPE_LIST);
715
716 return _xs_list_write_litem(list, xs_size(list) - 1, mem, dsz);
717}
718
719
720xs_list *_xs_list_append(xs_list *list, const xs_val *vals[])
721/* adds several values to the list */
722{
723 /* special case: if the first argument is NULL, just insert it */
724 if (*vals == NULL)
725 return xs_list_append_m(list, NULL, 0);
726
727 while (*vals) {
728 list = xs_list_append_m(list, *vals, xs_size(*vals));
729 vals++;
730 }
731
732 return list;
733}
734
735
736int xs_list_iter(xs_list **list, const xs_val **value)
737/* iterates a list value */
738{
739 int goon = 1;
740
741 xs_val *p = *list;
742
743 /* skip the start of the list */
744 if (xs_type(p) == XSTYPE_LIST)
745 p += 1 + _XS_TYPE_SIZE;
746
747 /* an element? */
748 if (xs_type(p) == XSTYPE_LITEM) {
749 p++;
750
751 *value = p;
752
753 p += xs_size(*value);
754 }
755 else {
756 /* end of list */
757 goon = 0;
758 }
759
760 /* store back the pointer */
761 *list = p;
762
763 return goon;
764}
765
766
767int xs_list_next(const xs_list *list, const xs_val **value, int *ctxt)
768/* iterates a list, with context */
769{
770 if (xs_type(list) != XSTYPE_LIST)
771 return 0;
772
773 int goon = 1;
774
775 const char *p = list;
776
777 /* skip the start of the list */
778 if (*ctxt == 0)
779 *ctxt = 1 + _XS_TYPE_SIZE;
780
781 p += *ctxt;
782
783 /* an element? */
784 if (xs_type(p) == XSTYPE_LITEM) {
785 p++;
786
787 *value = p;
788
789 p += xs_size(*value);
790 }
791 else {
792 /* end of list */
793 goon = 0;
794 }
795
796 /* update the context */
797 *ctxt = p - list;
798
799 return goon;
800}
801
802
803int xs_list_len(const xs_list *list)
804/* returns the number of elements in the list */
805{
806 XS_ASSERT_TYPE_NULL(list, XSTYPE_LIST);
807
808 int c = 0, ct = 0;
809 const xs_val *v;
810
811 while (xs_list_next(list, &v, &ct))
812 c++;
813
814 return c;
815}
816
817
818const xs_val *xs_list_get(const xs_list *list, int num)
819/* returns the element #num */
820{
821 XS_ASSERT_TYPE(list, XSTYPE_LIST);
822
823 if (num < 0)
824 num = xs_list_len(list) + num;
825
826 int c = 0, ct = 0;
827 const xs_val *v;
828
829 while (xs_list_next(list, &v, &ct)) {
830 if (c == num)
831 return v;
832
833 c++;
834 }
835
836 return NULL;
837}
838
839
840xs_list *xs_list_del(xs_list *list, int num)
841/* deletes element #num */
842{
843 XS_ASSERT_TYPE(list, XSTYPE_LIST);
844
845 const xs_val *v;
846
847 if ((v = xs_list_get(list, num)) != NULL)
848 list = xs_collapse(list, v - 1 - list, xs_size(v - 1));
849
850 return list;
851}
852
853
854xs_list *xs_list_insert(xs_list *list, int num, const xs_val *data)
855/* inserts an element at #num position */
856{
857 XS_ASSERT_TYPE(list, XSTYPE_LIST);
858
859 const xs_val *v;
860 int offset;
861
862 if ((v = xs_list_get(list, num)) != NULL)
863 offset = v - list;
864 else
865 offset = xs_size(list);
866
867 return _xs_list_write_litem(list, offset - 1, data, xs_size(data));
868}
869
870
871xs_list *xs_list_set(xs_list *list, int num, const xs_val *data)
872/* sets the element at #num position */
873{
874 XS_ASSERT_TYPE(list, XSTYPE_LIST);
875
876 list = xs_list_del(list, num);
877 list = xs_list_insert(list, num, data);
878
879 return list;
880}
881
882
883xs_list *xs_list_dequeue(xs_list *list, xs_val **data, int last)
884/* gets a copy of the first or last element of a list, shrinking it */
885{
886 XS_ASSERT_TYPE(list, XSTYPE_LIST);
887
888 int ct = 0;
889 const xs_val *v = NULL;
890
891 if (!last) {
892 /* get the first */
893 xs_list_next(list, &v, &ct);
894 }
895 else {
896 /* iterate to the end */
897 while (xs_list_next(list, &v, &ct));
898 }
899
900 if (v != NULL) {
901 *data = xs_dup(v);
902
903 /* collapse from the address of the element */
904 list = xs_collapse(list, v - 1 - list, xs_size(v - 1));
905 }
906
907 return list;
908}
909
910
911int xs_list_in(const xs_list *list, const xs_val *val)
912/* returns the position of val in list or -1 */
913{
914 XS_ASSERT_TYPE_NULL(list, XSTYPE_LIST);
915
916 int n = 0;
917 int ct = 0;
918 const xs_val *v;
919 int sz = xs_size(val);
920
921 while (xs_list_next(list, &v, &ct)) {
922 if (sz == xs_size(v) && memcmp(val, v, sz) == 0)
923 return n;
924
925 n++;
926 }
927
928 return -1;
929}
930
931
932xs_str *xs_join(const xs_list *list, const char *sep)
933/* joins a list into a string */
934{
935 XS_ASSERT_TYPE(list, XSTYPE_LIST);
936
937 xs_str *s = NULL;
938 const xs_val *v;
939 int c = 0;
940 int ct = 0;
941 int offset = 0;
942 int ssz = strlen(sep);
943
944 while (xs_list_next(list, &v, &ct)) {
945 /* refuse to join non-string values */
946 if (xs_type(v) == XSTYPE_STRING) {
947 int sz;
948
949 /* add the separator */
950 if (c != 0 && ssz) {
951 s = xs_realloc(s, offset + ssz);
952 memcpy(s + offset, sep, ssz);
953 offset += ssz;
954 }
955
956 /* add the element */
957 if ((sz = strlen(v)) > 0) {
958 s = xs_realloc(s, offset + sz);
959 memcpy(s + offset, v, sz);
960 offset += sz;
961 }
962
963 c++;
964 }
965 }
966
967 /* null-terminate */
968 s = xs_realloc(s, _xs_blk_size(offset + 1));
969 s[offset] = '\0';
970
971 return s;
972}
973
974
975xs_list *xs_split_n(const char *str, const char *sep, int times)
976/* splits a string into a list upto n times */
977{
978 int sz = strlen(sep);
979 char *ss;
980 xs_list *list;
981
982 list = xs_list_new();
983
984 while (times > 0 && (ss = strstr(str, sep)) != NULL) {
985 /* create a new string with this slice and add it to the list */
986 xs *s = xs_str_new_sz(str, ss - str);
987 list = xs_list_append(list, s);
988
989 /* skip past the separator */
990 str = ss + sz;
991
992 times--;
993 }
994
995 /* add the rest of the string */
996 list = xs_list_append(list, str);
997
998 return list;
999}
1000
1001
1002xs_list *xs_list_cat(xs_list *l1, const xs_list *l2)
1003/* concatenates list l2 to l1 */
1004{
1005 XS_ASSERT_TYPE(l1, XSTYPE_LIST);
1006 XS_ASSERT_TYPE(l2, XSTYPE_LIST);
1007
1008 /* inserts at the end of l1 the content of l2 (skipping header and footer) */
1009 return xs_insert_m(l1, xs_size(l1) - 1,
1010 l2 + 1 + _XS_TYPE_SIZE, xs_size(l2) - (1 + _XS_TYPE_SIZE + 1));
1011}
1012
1013
1014/** keyvals **/
1015
1016int xs_keyval_size(const xs_str *key, const xs_val *value)
1017/* returns the needed size for a keyval */
1018{
1019 return 1 + xs_size(key) + xs_size(value);
1020}
1021
1022
1023xs_str *xs_keyval_key(const xs_keyval *keyval)
1024/* returns a pointer to the key of the keyval */
1025{
1026 return (xs_str *)&keyval[1];
1027}
1028
1029
1030xs_val *xs_keyval_value(const xs_keyval *keyval)
1031/* returns a pointer to the value of the keyval */
1032{
1033 return (xs_val *)&keyval[1 + xs_size(xs_keyval_key(keyval))];
1034}
1035
1036
1037xs_keyval *xs_keyval_make(xs_keyval *keyval, const xs_str *key, const xs_val *value)
1038/* builds a keyval into mem (should have enough size) */
1039{
1040 keyval[0] = XSTYPE_KEYVAL;
1041 memcpy(xs_keyval_key(keyval), key, xs_size(key));
1042 memcpy(xs_keyval_value(keyval), value, xs_size(value));
1043
1044 return keyval;
1045}
1046
1047
1048/** dicts **/
1049
1050typedef struct {
1051 int value_offset; /* offset to value (from dict start) */
1052 int next; /* next node in sequential search */
1053 int child[4]; /* child nodes in hashed search */
1054 char key[]; /* C string key */
1055} ditem_hdr;
1056
1057typedef struct {
1058 int size; /* size of full dict (_XS_TYPE_SIZE) */
1059 int first; /* first node for sequential search */
1060 int root; /* root node for hashed search */
1061 ditem_hdr ditems[]; /* the ditems */
1062} dict_hdr;
1063
1064
1065xs_dict *xs_dict_new(void)
1066/* creates a new dict */
1067{
1068 /* size of dict */
1069 int sz = 1 + sizeof(dict_hdr);
1070
1071 xs_dict *d = xs_realloc(NULL, sz);
1072 memset(d, '\0', sz);
1073
1074 d[0] = XSTYPE_DICT;
1075 _xs_put_size(d, sz);
1076
1077 return d;
1078}
1079
1080static int *_xs_dict_locate(const xs_dict *dict, const char *key)
1081/* locates a ditem */
1082{
1083 unsigned int h = xs_hash_func(key, strlen(key));
1084
1085 /* start from the root */
1086 dict_hdr *dh = (dict_hdr *)(dict + 1);
1087 int *off = &dh->root;
1088
1089 while (*off) {
1090 /* pointer to ditem */
1091 ditem_hdr *di = (ditem_hdr *)(dict + *off);
1092
1093 /* pointer to the key */
1094 const char *d_key = di->key;
1095
1096 if (strcmp(key, d_key) == 0)
1097 break;
1098
1099 off = &di->child[h >> 30];
1100 h <<= 2;
1101 }
1102
1103 return off;
1104}
1105
1106
1107xs_dict *xs_dict_set(xs_dict *dict, const xs_str *key, const xs_val *value)
1108/* sets a key/value pair */
1109{
1110 if (value == NULL)
1111 value = xs_stock(XSTYPE_NULL);
1112
1113 if (xs_type(dict) == XSTYPE_DICT) {
1114 int *o = _xs_dict_locate(dict, key);
1115 int end = xs_size(dict);
1116
1117 if (!*o) {
1118 /* ditem does not exist yet: append to the end */
1119 *o = end;
1120
1121 int ksz = xs_size(key);
1122 int vsz = xs_size(value);
1123 int dsz = sizeof(ditem_hdr) + ksz + vsz;
1124
1125 /* open room in the dict for the full ditem */
1126 dict = xs_expand(dict, end, dsz);
1127
1128 dict_hdr *dh = (dict_hdr *)(dict + 1);
1129
1130 /* build the ditem */
1131 ditem_hdr *di = (ditem_hdr *)(dict + end);
1132 memset(di, '\0', dsz);
1133
1134 /* set the offset to the value */
1135 di->value_offset = end + sizeof(ditem_hdr) + ksz;
1136
1137 /* copy the key */
1138 memcpy(di->key, key, ksz);
1139
1140 /* copy the value */
1141 memcpy(dict + di->value_offset, value, vsz);
1142
1143 /* chain to the sequential list */
1144 di->next = dh->first;
1145 dh->first = end;
1146 }
1147 else {
1148 /* ditem already exists */
1149 ditem_hdr *di = (ditem_hdr *)(dict + *o);
1150
1151 /* get pointer to the value offset */
1152 int *i = &di->value_offset;
1153
1154 /* deleted? recover offset */
1155 if (*i < 0)
1156 *i *= -1;
1157
1158 /* get old value */
1159 xs_val *o_value = dict + *i;
1160
1161 /* will new value fit over the old one? */
1162 if (xs_size(value) <= xs_size(o_value)) {
1163 /* just overwrite */
1164 /* (difference is leaked inside the dict) */
1165 memcpy(o_value, value, xs_size(value));
1166 }
1167 else {
1168 /* not enough room: new value will live at the end of the dict */
1169 /* (old value is leaked inside the dict) */
1170 *i = end;
1171
1172 dict = xs_insert(dict, end, value);
1173 }
1174 }
1175 }
1176
1177 return dict;
1178}
1179
1180
1181xs_dict *xs_dict_append(xs_dict *dict, const xs_str *key, const xs_val *value)
1182/* just an alias (for this implementation it's the same) */
1183{
1184 return xs_dict_set(dict, key, value);
1185}
1186
1187
1188xs_dict *xs_dict_prepend(xs_dict *dict, const xs_str *key, const xs_val *value)
1189/* just an alias (for this implementation it's the same) */
1190{
1191 return xs_dict_set(dict, key, value);
1192}
1193
1194
1195xs_dict *xs_dict_del(xs_dict *dict, const xs_str *key)
1196/* deletes a key/value pair */
1197{
1198 if (xs_type(dict) == XSTYPE_DICT) {
1199 int *o = _xs_dict_locate(dict, key);
1200
1201 if (*o) {
1202 /* found ditem */
1203 ditem_hdr *di = (ditem_hdr *)(dict + *o);
1204
1205 /* deleted ditems have a negative value offset */
1206 di->value_offset *= -1;
1207 }
1208 }
1209
1210 return dict;
1211}
1212
1213
1214const xs_val *xs_dict_get_def(const xs_dict *dict, const xs_str *key, const xs_str *def)
1215/* gets a value by key, or returns def */
1216{
1217 if (xs_type(dict) == XSTYPE_DICT) {
1218 int *o = _xs_dict_locate(dict, key);
1219
1220 if (*o) {
1221 /* found ditem */
1222 ditem_hdr *di = (ditem_hdr *)(dict + *o);
1223
1224 if (di->value_offset > 0)
1225 return dict + di->value_offset;
1226 }
1227 }
1228
1229 return def;
1230}
1231
1232
1233int xs_dict_next(const xs_dict *dict, const xs_str **key, const xs_val **value, int *ctxt)
1234/* dict iterator, with context */
1235{
1236 if (xs_type(dict) != XSTYPE_DICT)
1237 return 0;
1238
1239 if (*ctxt == 0) {
1240 /* at the beginning: get the first sequential item */
1241 const dict_hdr *dh = (dict_hdr *)(dict + 1);
1242 *ctxt = dh->first;
1243 }
1244
1245 *value = NULL;
1246
1247 while (*value == NULL && *ctxt > 0) {
1248 const ditem_hdr *di = (ditem_hdr *)(dict + *ctxt);
1249
1250 /* get value */
1251 if (di->value_offset > 0) {
1252 *value = (xs_val *)(dict + di->value_offset);
1253
1254 /* get key */
1255 *key = (xs_str *)&di->key;
1256 }
1257
1258 /* get offset to next ditem */
1259 *ctxt = di->next ? di->next : -1;
1260 }
1261
1262 return *value != NULL;
1263}
1264
1265
1266xs_dict *xs_dict_gc(const xs_dict *dict)
1267/* creates a copy of dict, but garbage-collected */
1268{
1269 xs_dict *nd = xs_dict_new();
1270 const xs_str *k;
1271 const xs_val *v;
1272 int c = 0;
1273
1274 while (xs_dict_next(dict, &k, &v, &c)) {
1275 if (xs_type(v) == XSTYPE_DICT) {
1276 xs *sd = xs_dict_gc(v);
1277 nd = xs_dict_set(nd, k, sd);
1278 }
1279 else
1280 nd = xs_dict_set(nd, k, v);
1281 }
1282
1283 return nd;
1284}
1285
1286
1287const xs_val *xs_dict_get_path_sep(const xs_dict *dict, const char *path, const char *sep)
1288/* gets a value from dict given a path separated by sep */
1289{
1290 /* split by the separator */
1291 xs *l = xs_split_n(path, sep, 1);
1292
1293 /* only one part? just get */
1294 if (xs_list_len(l) == 1)
1295 return xs_dict_get(dict, path);
1296
1297 const char *prefix = xs_list_get(l, 0);
1298 const char *rest = xs_list_get(l, 1);
1299 const xs_dict *sd = xs_dict_get(dict, prefix);
1300
1301 if (xs_type(sd) == XSTYPE_DICT)
1302 return xs_dict_get_path_sep(sd, rest, sep);
1303
1304 return NULL;
1305}
1306
1307
1308xs_dict *xs_dict_set_path_sep(xs_dict *dict, const char *path, const xs_val *value, const char *sep)
1309/* sets a value into dict given a path separated by sep;
1310 intermediate dicts are created if needed */
1311{
1312 /* split by the separator */
1313 xs *l = xs_split_n(path, sep, 1);
1314
1315 /* only one part? just set */
1316 if (xs_list_len(l) == 1)
1317 return xs_dict_set(dict, path, value);
1318
1319 const char *prefix = xs_list_get(l, 0);
1320 const char *rest = xs_list_get(l, 1);
1321
1322 xs *nd = NULL;
1323
1324 /* does the first part of path exist? */
1325 const xs_dict *cd = xs_dict_get(dict, prefix);
1326
1327 if (xs_type(cd) == XSTYPE_DICT)
1328 nd = xs_dup(cd);
1329 else
1330 nd = xs_dict_new();
1331
1332 /* move down the path */
1333 nd = xs_dict_set_path_sep(nd, rest, value, sep);
1334
1335 /* set */
1336 return xs_dict_set(dict, prefix, nd);
1337}
1338
1339
1340/** other values **/
1341
1342xs_val *xs_val_new(xstype t)
1343/* adds a new special value */
1344{
1345 xs_val *v = xs_realloc(NULL, _xs_blk_size(1));
1346
1347 v[0] = t;
1348
1349 return v;
1350}
1351
1352
1353/** numbers */
1354
1355xs_number *xs_number_new(double f)
1356/* adds a new number value */
1357{
1358 xs_number *v;
1359 char tmp[64];
1360
1361 snprintf(tmp, sizeof(tmp), "%.15lf", f);
1362
1363 /* strip useless zeros */
1364 if (strchr(tmp, '.') != NULL) {
1365 char *ptr;
1366
1367 for (ptr = tmp + strlen(tmp) - 1; *ptr == '0'; ptr--);
1368
1369 if (*ptr != '.')
1370 ptr++;
1371
1372 *ptr = '\0';
1373 }
1374
1375 /* alloc for the marker and the full string */
1376 v = xs_realloc(NULL, _xs_blk_size(1 + xs_size(tmp)));
1377
1378 v[0] = XSTYPE_NUMBER;
1379 memcpy(&v[1], tmp, xs_size(tmp));
1380
1381 return v;
1382}
1383
1384
1385double xs_number_get(const xs_number *v)
1386/* gets the number as a double */
1387{
1388 double f = 0.0;
1389
1390 if (xs_type(v) == XSTYPE_NUMBER)
1391 f = atof(&v[1]);
1392 else
1393 if (xs_type(v) == XSTYPE_STRING)
1394 f = atof(v);
1395
1396 return f;
1397}
1398
1399
1400const char *xs_number_str(const xs_number *v)
1401/* gets the number as a string */
1402{
1403 const char *p = NULL;
1404
1405 if (xs_type(v) == XSTYPE_NUMBER)
1406 p = &v[1];
1407
1408 return p;
1409}
1410
1411
1412/** raw data blocks **/
1413
1414xs_data *xs_data_new(const void *data, int size)
1415/* returns a new raw data value */
1416{
1417 xs_data *v;
1418
1419 /* add the overhead (data type + size) */
1420 int total_size = size + 1 + _XS_TYPE_SIZE;
1421
1422 v = xs_realloc(NULL, _xs_blk_size(total_size));
1423 v[0] = XSTYPE_DATA;
1424
1425 _xs_put_size(v, total_size);
1426
1427 memcpy(&v[1 + _XS_TYPE_SIZE], data, size);
1428
1429 return v;
1430}
1431
1432
1433int xs_data_size(const xs_data *value)
1434/* returns the size of the data stored inside value */
1435{
1436 return _xs_get_size(value) - (1 + _XS_TYPE_SIZE);
1437}
1438
1439
1440void xs_data_get(void *data, const xs_data *value)
1441/* copies the raw data stored inside value into data */
1442{
1443 memcpy(data, &value[1 + _XS_TYPE_SIZE], xs_data_size(value));
1444}
1445
1446
1447void *xs_memmem(const char *haystack, int h_size, const char *needle, int n_size)
1448/* clone of memmem */
1449{
1450 char *p, *r = NULL;
1451 int offset = 0;
1452
1453 while (!r && h_size - offset > n_size &&
1454 (p = memchr(haystack + offset, *needle, h_size - offset))) {
1455 if (memcmp(p, needle, n_size) == 0)
1456 r = p;
1457 else
1458 offset = p - haystack + 1;
1459 }
1460
1461 return r;
1462}
1463
1464
1465unsigned int xs_hash_func(const char *data, int size)
1466/* a general purpose hashing function */
1467{
1468 unsigned int hash = 0x666;
1469 int n;
1470
1471 for (n = 0; n < size; n++) {
1472 hash ^= (unsigned char)data[n];
1473 hash *= 111111111;
1474 }
1475
1476 return hash ^ hash >> 16;
1477}
1478
1479
1480#endif /* XS_IMPLEMENTATION */
1481
1482#endif /* _XS_H */
