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