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