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