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