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