From c8e1e71eb526475dd431443345262c2e5a627831 Mon Sep 17 00:00:00 2001 From: Nicholas Noll Date: Sat, 23 Oct 2021 11:17:25 -0700 Subject: chore(rename): libn -> base --- include/base.h | 465 +++++++++++++++++++++++++++++++++++++++++++++ include/base/macro/map.h | 400 ++++++++++++++++++++++++++++++++++++++ include/base/macro/qsort.h | 91 +++++++++ include/libn.h | 465 --------------------------------------------- include/libn/macro/map.h | 400 -------------------------------------- include/libn/macro/qsort.h | 91 --------- 6 files changed, 956 insertions(+), 956 deletions(-) create mode 100644 include/base.h create mode 100644 include/base/macro/map.h create mode 100644 include/base/macro/qsort.h delete mode 100644 include/libn.h delete mode 100644 include/libn/macro/map.h delete mode 100644 include/libn/macro/qsort.h (limited to 'include') diff --git a/include/base.h b/include/base.h new file mode 100644 index 0000000..699786f --- /dev/null +++ b/include/base.h @@ -0,0 +1,465 @@ +#pragma once + +// ------------------------------------------------------------------------ +// standard library + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +typedef wchar_t wchar; + +// ---------------------------------------------------------------------------- +// dynamic array + +typedef struct BufHdr +{ + vlong len; + vlong cap; + byte buf[]; +} BufHdr; + +#define bufhdr(b) ((BufHdr*)((uint8*)(b)-offsetof(BufHdr, buf))) +#define buflen(b) ((b) ? (bufhdr(b)->len) : 0) +#define bufcap(b) ((b) ? (bufhdr(b)->cap) : 0) +#define bufend(b) ((b) + buflen(b)) +#define bufsize(b) ((b) ? (buflen(b) * sizeof((b)[0])) : 0) + +#define buffree(b) ((b) ? (free(bufhdr(b)), (b) = nil) : 0) +#define buffit(b, n) ((n) <= bufcap(b) ? 0 : ((b) = ·bufgrow((b), (n), sizeof(*(b))))) + +#define bufpush(b, ...) (buffit((b), 1 + buflen(b)), (b)[bufhdr(b)->len++] = (__VA_ARGS__)) +#define bufaddn(b, n) (buffit(b, buflen(b)+n), bufhdr(b)->len += n, b+bufhdr(b)->len-n) + +#define bufpop(b) ((b)[--bufhdr(b)->len]) +#define bufdel(b, i) bufdeln((b), (i), 1) +#define bufdeln(b, i, n) (memmove((b)+(i), (b)+(i)+(n), sizeof(*(b))*(bufhdr(b)->len-(n)-(i)), bufhdr(b)->len -= (n)) +#define bufdelswap(b, i) ((b)[i] = bufend(b)[-1], bufhdr(b)->len-=1) + +void* ·bufgrow(void*, vlong, vlong); + +// ----------------------------------------------------------------------------- +// memory allocation + +// TODO(nnoll): Allow for nil iterfaces? +/* allocator interface */ +typedef struct mem·Allocator { + void *(*alloc)(void *heap, uint n, ulong size); + void (*free)(void *heap, void *ptr); +} mem·Allocator; + +extern mem·Allocator sys·Memory; + +typedef struct mem·Reallocator { + void *(*alloc)(void *iface, uint n, ulong size); + void *(*realloc)(void *iface, void *ptr, uint n, ulong size); + void (*free)(void *iface, void *ptr); +} mem·Reallocator; + +extern mem·Reallocator sys·Relocator; + +/* simple memory arena */ +typedef struct mem·Arena mem·Arena; + +mem·Arena *mem·makearena(mem·Allocator from, void*); +void *mem·arenaalloc(mem·Arena *A, uint n, ulong size); +void mem·freearena(mem·Arena *A); + +extern mem·Allocator mem·ArenaAllocator; + +/* generalized memxxx functions */ +void memset64(void *dst, uint64 val, uintptr size); + +// ----------------------------------------------------------------------------- +// coroutines + +typedef struct Coro Coro; + +Coro* coro·make(uintptr stk, uintptr (*func)(Coro*, uintptr)); +uintptr coro·yield(Coro *c, uintptr arg); +error coro·free(Coro *c); + +// ----------------------------------------------------------------------------- +// strings + +typedef byte* string; + +/* string helpers */ +string str·makecap(const byte *s, vlong len, vlong cap); +string str·makelen(const byte *s, vlong len); +string str·make(const byte *s); +string str·makef(const byte *fmt, ...); +void str·free(string s); +int str·len(const string s); +int str·cap(const string s); +void str·clear(string *s); +void str·grow(string *s, vlong delta); +void str·fit(string *s); +int str·appendlen(string *s, vlong len, const byte *b); +int str·append(string *s, const byte* b); +int str·appendf(string *s, const byte* fmt, ...); +int str·appendbyte(string *s, const byte b); +bool str·equals(const string s, const string t); +int str·find(string s, const byte* substr); +void str·lower(string s); +void str·upper(string s); +int str·read(string s, int size, int n, void *buf); +void str·replace(string s, const byte* from, const byte* to); +string* str·split(string s, const byte* tok); +string str·join(vlong len, byte** fields, const byte* sep); + +/* + * UTF-8 functions. + * Perhaps break into own unit + * TODO: Add to(upper|lower|title) + */ +typedef uint32 rune; + +/* + * We have to use the preprocessor to ensure + * we have unsigned constants. Unfortunate... + */ + +#define UTFmax 4 +#define RuneSync 0x80u +#define RuneSelf 0x80u +#define RuneErr 0xFFFDu +#define RuneMax 0x10FFFFu +#define RuneMask 0x1FFFFFu + +/* utf8 helpers */ +int utf8·fullrune(byte *s, int n); +byte *utf8·findrune(byte *s, long i); +byte *utf8·findrrune(byte* s, long c); +int utf8·bytetorune(rune *r, byte *s); +int utf8·runetobyte(byte *s, rune *r); +int utf8·len(byte *s); +int utf8·runelen(rune r); +int utf8·isletter(rune r); +int utf8·isdigit(rune r); +int utf8·isspace(rune r); +int utf8·istitle(rune r); + +// ----------------------------------------------------------------------------- +// i/o + +typedef FILE io·Stream; +typedef struct stat io·Stat; + +enum SeekPos +{ + seek·cur = SEEK_CUR, + seek·set = SEEK_SET, + seek·end = SEEK_END +}; + +/* XXX: change casing */ +enum +{ + ReadOK = R_OK, + WriteOK = W_OK, + ExecOK = X_OK, +}; + +/* file handling */ +io·Stream *io·open(byte *name, byte *mode); +int io·fd(io·Stream *s); +error io·stat(io·Stream *s, io·Stat *buf); +error io·close(io·Stream *s); +byte io·getbyte(io·Stream *s); +error io·ungetbyte(io·Stream *s, byte c); +int io·read(io·Stream *s, int sz, int n, void *buf); +int io·readln(io·Stream *s, int n, byte *buf); +error io·putbyte(io·Stream *s, byte c); +int io·putstring(io·Stream *s, string str); +int io·write(io·Stream *s, int sz, int n, void *buf); +int io·flush(io·Stream *s); +int io·seek(io·Stream *s, long off, enum SeekPos whence); +long io·tell(io·Stream *s); + +/* basic os helpers */ +int os·exists(byte *path, int flag); +byte *os·basename(byte *path); +int os·sep(void); + +/* io interfaces */ +typedef struct io·Reader +{ + int (*read)(void*, int sz, int n, void *buf); +} io·Reader; +extern io·Reader sys·Reader; + +typedef struct io·Peeker +{ + byte (*get)(void*); + error (*unget)(void*, byte); +} io·Peeker; +extern io·Peeker sys·Peeker; + +typedef struct io·Seeker +{ + int (*seek)(void *skr, long off, enum SeekPos whence); + long (*tell)(void *skr); +} io·Seeker; +extern io·Seeker sys·Seeker; + +typedef struct io·SeekReader +{ + io·Seeker; + io·Reader; +} io·SeekReader; +extern io·SeekReader sys·SeekReader; + +typedef struct io·PeekReader +{ + io·Reader; + io·Peeker; +} io·PeekReader; +extern io·PeekReader sys·PeekReader; + +typedef struct io·Writer +{ + int (*write)(void*, int sz, int n, void *buf); +} io·Writer; +extern io·Writer sys·Writer; + +typedef struct io·Putter +{ + error (*put) (void*, byte); + int (*puts)(void*, string); +} io·Putter; +extern io·Putter sys·Putter; + +typedef struct io·PutWriter +{ + io·Writer; + io·Putter; +} io·PutWriter; +extern io·PutWriter sys·PutWriter; + +typedef struct io·ReadWriter +{ + io·Reader; + io·Writer; +} io·ReadWriter; +extern io·ReadWriter sys·ReadWriter; + +/* buffered i/o */ +typedef struct io·Buffer io·Buffer; + +enum +{ + bufio·size = 2*4096, + bufio·ungets = 8, + bufio·eof = -1, + bufio·err = -2, + + bufio·nil = 1 << 0, + bufio·rdr = 1 << 1, + bufio·wtr = 1 << 2, + bufio·end = 1 << 3, +}; + +struct io·Buffer +{ + int state; + int runesize; + void *h; + union { + io·Reader rdr; + io·Writer wtr; + }; + vlong size; + byte *beg, *pos, *end; + byte buf[bufio·size + bufio·ungets]; +}; + +error bufio·initreader(io·Buffer *buf, io·Reader rdr, void *h); +void bufio·finireader(io·Buffer *buf); +int bufio·getbyte(io·Buffer *buf); +error bufio·ungetbyte(io·Buffer *buf, byte c); +rune bufio·getrune(io·Buffer *buf); +error bufio·ungetrune(io·Buffer *buf, rune r); +int bufio·read(io·Buffer *buf, int sz, int n, void *out); + +// ----------------------------------------------------------------------------- +// memory mapped files + +typedef struct mmap·Reader +{ + vlong len; + union { + byte *buf; + ubyte *ubuf; + }; +} mmap·Reader; + +mmap·Reader mmap·open(byte *name); +error mmap·close(mmap·Reader rdr); + +// ----------------------------------------------------------------------------- +// filesystem + +#define iota(x) 1 << (x) +enum +{ + fs·preorder = iota(0), + fs·nolinks = iota(1), + fs·verbose = iota(2), +}; +#undef iota + +typedef struct fs·Walker fs·Walker; +typedef struct fs·History fs·History; + +struct fs·Walker +{ + int fd, lev, max, err; + uchar flags : 4; + fs·History *hist; + struct { + void *data; + int (*func)(void *data, char *relp, char *absp, io·Stat* info); + }; + char *base, *end, path[4096]; +}; + +int fs·init(fs·Walker *, char *path); +void fs·fini(fs·Walker *); +void fs·walk(fs·Walker *); + +// ----------------------------------------------------------------------------- +// libflate +// NOTE: Experimental! + +typedef struct flate·Reader flate·Reader; +typedef struct flate·Writer flate·Writer; + +flate·Reader *flate·openreader(io·Reader rdr, void* r, mem·Allocator mem, void* m); +int flate·read(flate·Reader *rdr, int sz, int n, void *buf); +error flate·closereader(flate·Reader *rdr); + +flate·Writer *flate·openwriter(io·Writer wtr, void* w, mem·Allocator mem, void* m); +int flate·write(flate·Writer *wtr, int sz, int n, void *buf); +error flate·closewriter(flate·Writer *wtr); + +// ----------------------------------------------------------------------------- +// libgz + +typedef void gz·Stream; + +/* interfaces */ +extern io·Reader gz·Reader; +extern io·Peeker gz·Peeker; +extern io·Seeker gz·Seeker; +extern io·SeekReader gz·SeekReader; +extern io·PeekReader gz·PeekReader; + +extern io·Writer gz·Writer; +extern io·Putter gz·Putter; +extern io·PutWriter gz·PutWriter; +extern io·ReadWriter gz·ReadWriter; + +gz·Stream *gz·open(byte *path, byte *mode); +error gz·close(gz·Stream* s); +int gz·read(gz·Stream *s, int sz, int n, void* buf); +int gz·readln(gz·Stream *s, int n, byte *buf); +byte gz·getbyte(gz·Stream *s); +error gz·ungetbyte(gz·Stream *s, byte c); +int gz·write(gz·Stream *s, int sz, int n, void* buf); +error gz·putbyte(gz·Stream *s, byte str); +error gz·putstring(gz·Stream *s, byte *str); +int gz·printf(gz·Stream *s, byte *fmt, ...); +error gz·flush(gz·Stream *s); +int gz·seek(gz·Stream *s, long off, enum SeekPos whence); +long gz·tell(gz·Stream *s); + +// ----------------------------------------------------------------------------- +// libjson +// NOTE: Experimental! + +// ----------------------------------------------------------------------------- +// error handling functions + +void exits(char *s); +void errorf(byte* fmt, ...); +void verrorf(byte* fmt, va_list args); +void panicf(byte *fmt, ...); +void vpanicf(byte *fmt, va_list args); + +// ----------------------------------------------------------------------------- +// sorting + +void sort·ints(uintptr n, int arr[]); +void sort·int8s(uintptr n, int8 arr[]); +void sort·int16s(uintptr n, int16 arr[]); +void sort·int32s(uintptr n, int32 arr[]); +void sort·int64s(uintptr n, int64 arr[]); + +void sort·uints(uintptr n, uint arr[]); +void sort·uint8s(uintptr n, uint8 arr[]); +void sort·uint16s(uintptr n, uint16 arr[]); +void sort·uint32s(uintptr n, uint32 arr[]); +void sort·uint64s(uintptr n, uint64 arr[]); + +void sort·floats(uintptr n, float arr[]); +void sort·doubles(uintptr n, double arr[]); + +void sort·strings(uintptr n, byte* arr[]); + +// ----------------------------------------------------------------------------- +// fast random number generation + +error rng·init(uint64 seed); +double rng·random(void); +double rng·exponential(double lambda); +bool rng·bernoulli(double f); +uint64 rng·randi(int max); +uint64 rng·poisson(double mean); + +// ----------------------------------------------------------------------------- +// variable arguments + +/* from plan9 libc */ + +#define ERRMAX 128 /* max length of error string */ + +#define SET(x) ((x)=0) +#define USED(x) if(x){}else{} +#ifdef __GNUC__ +# if __GNUC__ >= 3 +# undef USED +# define USED(x) ((void)(x)) +# endif +#endif + +extern char *argv0; +#define ARGBEGIN for((argv0?0:(argv0=*argv)),argv++,argc--; \ + argv[0] && argv[0][0]=='-' && argv[0][1]; \ + argc--, argv++) { \ + byte *_args, *_argt; \ + rune _argc; \ + _args = &argv[0][1]; \ + if(_args[0]=='-' && _args[1]==0){ \ + argc--; argv++; break; \ + } \ + _argc = 0; \ + while(*_args && (_args += utf8·bytetorune(&_argc, _args)))\ + switch(_argc) +#define ARGEND SET(_argt);USED(_argt);USED(_argc);USED(_args);}USED(argv);USED(argc); +#define ARGF() (_argt=_args, _args="",\ + (*_argt? _argt: argv[1]? (argc--, *++argv): 0)) +#define EARGF(x) (_argt=_args, _args="",\ + (*_argt? _argt: argv[1]? (argc--, *++argv): ((x), abort(), (char*)0))) + +#define ARGC() _argc diff --git a/include/base/macro/map.h b/include/base/macro/map.h new file mode 100644 index 0000000..7c2f7ae --- /dev/null +++ b/include/base/macro/map.h @@ -0,0 +1,400 @@ +#pragma once + +/* + * Based on khash.h + * Modified to make control more granular and similar to QSORT + */ + +static const double __ac_HASH_UPPER = 0.77; + +#define _roundup32(x) \ + (--(x), (x) |= (x) >> 1, (x) |= (x) >> 2, (x) |= (x) >> 4, (x) |= (x) >> 8, \ + (x) |= (x) >> 16, ++(x)) + +#define __ac_isempty(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 2) +#define __ac_isdel(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 1) +#define __ac_iseither(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 3) +#define __ac_set_isdel_false(flag, i) \ + (flag[i >> 4] &= ~(1ul << ((i & 0xfU) << 1))) +#define __ac_set_isempty_false(flag, i) \ + (flag[i >> 4] &= ~(2ul << ((i & 0xfU) << 1))) +#define __ac_set_isboth_false(flag, i) \ + (flag[i >> 4] &= ~(3ul << ((i & 0xfU) << 1))) +#define __ac_set_isdel_true(flag, i) (flag[i >> 4] |= 1ul << ((i & 0xfU) << 1)) + +#define __ac_fsize(m) ((m) < 16 ? 1 : (m) >> 4) + +#define MAP_STRUCT_BODY(key_t, val_t) \ + int32 n_buckets, size, n_occupied, upper_bound; \ + int32 *flags; \ + key_t *keys; \ + val_t *vals; + +#define MAP_MAKE(type, h, alloc) \ + type *map; \ + map = alloc((h), 1, sizeof(*map)); \ + return map + +#define MAP_FREE(map, mem, heap) \ + mem.free(heap, map->keys); \ + mem.free(heap, map->flags); \ + mem.free(heap, map->vals); \ + mem.free(heap, map); + +#define MAP_RESET(map) \ + if (map && map->flags) { \ + memset(map->flags, 0xaa, __ac_fsize(map->n_buckets) * sizeof(int32)); \ + map->size = map->n_occupied = 0; \ + } + +#define MAP_GET(i, map, key, hashfunc, equalfunc ) \ + int32 k, last, mask, step; \ + if (map->n_buckets) { \ + k = 0; \ + i = 0; \ + last = 0; \ + mask = 0; \ + step = 0; \ + mask = map->n_buckets - 1; \ + k = hashfunc(key); \ + i = k & mask; \ + last = i; \ + while (!__ac_isempty(map->flags, i) && \ + (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + i = map->n_buckets; \ + break; \ + } \ + } \ + if (i < map->n_buckets && __ac_iseither(map->flags, i)) \ + i = map->n_buckets; \ + } else \ + i = 0; + +#define MAP_GROW(map, key_t, val_t, new_n_buckets, hashfunc, mem, heap) \ + int32 *new_flags = nil; \ + int32 j = 1; \ + { \ + _roundup32(new_n_buckets); \ + if (new_n_buckets < 4) \ + new_n_buckets = 4; \ + if (map->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ + j = 0; \ + else { \ + new_flags = mem.alloc(heap, __ac_fsize(new_n_buckets), sizeof(int32)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ + if (map->n_buckets < new_n_buckets) { /* expand */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + if (!new_keys) { \ + mem.free(heap, new_flags); \ + return -1; \ + } \ + memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ + mem.free(heap, map->keys); \ + map->keys = new_keys; \ + val_t *new_vals = mem.alloc(heap, new_n_buckets, sizeof(val_t)); \ + if (!new_vals) { \ + mem.free(heap, new_flags); \ + return -1; \ + } \ + memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ + mem.free(heap, map->vals); \ + map->vals = new_vals; \ + } \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != map->n_buckets; ++j) { \ + if (__ac_iseither(map->flags, j) == 0) { \ + key_t key = map->keys[j]; \ + val_t val; \ + int32 new_mask; \ + new_mask = new_n_buckets - 1; \ + val = map->vals[j]; \ + __ac_set_isdel_true(map->flags, j); \ + while (1) { \ + int32 k, i, step = 0; \ + k = hashfunc(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) \ + i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < map->n_buckets && __ac_iseither(map->flags, i) == 0) { \ + { \ + key_t tmp = map->keys[i]; \ + map->keys[i] = key; \ + key = tmp; \ + } \ + { \ + val_t tmp = map->vals[i]; \ + map->vals[i] = val; \ + val = tmp; \ + } \ + __ac_set_isdel_true(map->flags, i); \ + } else { \ + map->keys[i] = key; \ + map->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (map->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ + mem.free(heap, map->keys); \ + map->keys = new_keys; \ + \ + val_t *new_vals = mem.alloc(heap, new_n_buckets, sizeof(val_t)); \ + memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ + mem.free(heap, map->vals); \ + map->vals = new_vals; \ + } \ + mem.free(heap, map->flags); /* free the working space */ \ + map->flags = new_flags; \ + map->n_buckets = new_n_buckets; \ + map->n_occupied = map->size; \ + map->upper_bound = (int32)(map->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; + +#define MAP_PUT(map, key, val, hashfunc, equalfunc, resizefunc, err) \ + int32 x = 0; \ + if (map->n_occupied >= map->upper_bound) { \ + if (map->n_buckets > (map->size << 1)) { \ + if (resizefunc(map, map->n_buckets - 1) < 0) { \ + *err = -1; \ + return map->n_buckets; \ + } \ + } else if (resizefunc(map, map->n_buckets + 1) < 0) { \ + *err = -1; \ + return map->n_buckets; \ + } \ + } \ + \ + { \ + int32 k, i, site, last, mask = map->n_buckets - 1, step = 0; \ + x = site = map->n_buckets; \ + k = hashfunc(key); \ + i = k & mask; \ + if (__ac_isempty(map->flags, i)) \ + x = i; /* for speed up */ \ + else { \ + last = i; \ + while (!__ac_isempty(map->flags, i) && \ + (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ + if (__ac_isdel(map->flags, i)) \ + site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + x = site; \ + break; \ + } \ + } \ + if (x == map->n_buckets) { \ + if (__ac_isempty(map->flags, i) && site != map->n_buckets) \ + x = site; \ + else \ + x = i; \ + } \ + } \ + } \ + if (__ac_isempty(map->flags, x)) { /* not present at all */ \ + map->keys[x] = key; \ + __ac_set_isboth_false(map->flags, x); \ + ++map->size; \ + ++map->n_occupied; \ + *err = 1; \ + } else if (__ac_isdel(map->flags, x)) { /* deleted */ \ + map->keys[x] = key; \ + __ac_set_isboth_false(map->flags, x); \ + ++map->size; \ + } else \ + *err = 0; \ + return x; + +#define MAP_DEL(map, x) \ + if (x != map->n_buckets && !__ac_iseither(map->flags, x)) { \ + __ac_set_isdel_true(map->flags, x); \ + --map->size; \ + } + +#define KEY_EXIST(m, x) (!__ac_iseither((m)->flags, (x))) + +/* set macro */ + +#define SET_STRUCT_BODY(key_t) \ + int32 n_buckets, size, n_occupied, upper_bound; \ + int32 *flags; \ + key_t *keys \ + +#define SET_MAKE(type, h, alloc) \ + type *set; \ + set = alloc((h), 1, sizeof(*set)); \ + return set + +#define SET_FREE(set, mem, heap) \ + mem.free(heap, set->keys); \ + mem.free(heap, set->flags); \ + mem.free(heap, set) + +#define SET_RESET(set) \ + if (set && set->flags) { \ + memset(set->flags, 0xaa, __ac_fsize(set->n_buckets) * sizeof(int32)); \ + set->size = set->n_occupied = 0; \ + } + +#define SET_GET(i, set, key, hashfunc, equalfunc ) \ + int32 k, last, mask, step; \ + if (set->n_buckets) { \ + k = 0; \ + i = 0; \ + last = 0; \ + mask = 0; \ + step = 0; \ + mask = set->n_buckets - 1; \ + k = hashfunc(key); \ + i = k & mask; \ + last = i; \ + while (!__ac_isempty(set->flags, i) && \ + (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + i = set->n_buckets; \ + break; \ + } \ + } \ + if (i < set->n_buckets && __ac_iseither(set->flags, i)) \ + i = set->n_buckets; \ + } else \ + i = 0; + +#define SET_GROW(set, key_t, new_n_buckets, hashfunc, mem, heap) \ + int32 *new_flags = nil; \ + int32 j = 1; \ + { \ + _roundup32(new_n_buckets); \ + if (new_n_buckets < 4) \ + new_n_buckets = 4; \ + if (set->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ + j = 0; \ + else { \ + new_flags = mem.alloc(heap, __ac_fsize(new_n_buckets), sizeof(int32)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ + if (set->n_buckets < new_n_buckets) { /* expand */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + if (!new_keys) { \ + mem.free(heap, new_flags); \ + return -1; \ + } \ + memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ + mem.free(heap, set->keys); \ + set->keys = new_keys; \ + } \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != set->n_buckets; ++j) { \ + if (__ac_iseither(set->flags, j) == 0) { \ + key_t key = set->keys[j]; \ + int32 new_mask; \ + new_mask = new_n_buckets - 1; \ + __ac_set_isdel_true(set->flags, j); \ + while (1) { \ + int32 k, i, step = 0; \ + k = hashfunc(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) \ + i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < set->n_buckets && __ac_iseither(set->flags, i) == 0) { \ + { \ + key_t tmp = set->keys[i]; \ + set->keys[i] = key; \ + key = tmp; \ + } \ + __ac_set_isdel_true(set->flags, i); \ + } else { \ + set->keys[i] = key; \ + break; \ + } \ + } \ + } \ + } \ + if (set->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ + mem.free(heap, set->keys); \ + set->keys = new_keys; \ + } \ + mem.free(heap, set->flags); /* free the working space */ \ + set->flags = new_flags; \ + set->n_buckets = new_n_buckets; \ + set->n_occupied = set->size; \ + set->upper_bound = (int32)(set->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; + +#define SET_PUT(set, key, hashfunc, equalfunc, resizefunc, err) \ + int32 x = 0; \ + if (set->n_occupied >= set->upper_bound) { \ + if (set->n_buckets > (set->size << 1)) { \ + if (resizefunc(set, set->n_buckets - 1) < 0) { \ + *err = -1; \ + return set->n_buckets; \ + } \ + } else if (resizefunc(set, set->n_buckets + 1) < 0) { \ + *err = -1; \ + return set->n_buckets; \ + } \ + } \ + \ + { \ + int32 k, i, site, last, mask = set->n_buckets - 1, step = 0; \ + x = site = set->n_buckets; \ + k = hashfunc(key); \ + i = k & mask; \ + if (__ac_isempty(set->flags, i)) \ + x = i; /* for speed up */ \ + else { \ + last = i; \ + while (!__ac_isempty(set->flags, i) && \ + (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \ + if (__ac_isdel(set->flags, i)) \ + site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + x = site; \ + break; \ + } \ + } \ + if (x == set->n_buckets) { \ + if (__ac_isempty(set->flags, i) && site != set->n_buckets) \ + x = site; \ + else \ + x = i; \ + } \ + } \ + } \ + if (__ac_isempty(set->flags, x)) { /* not present at all */ \ + set->keys[x] = key; \ + __ac_set_isboth_false(set->flags, x); \ + ++set->size; \ + ++set->n_occupied; \ + *err = 1; \ + } else if (__ac_isdel(set->flags, x)) { /* deleted */ \ + set->keys[x] = key; \ + __ac_set_isboth_false(set->flags, x); \ + ++set->size; \ + } else \ + *err = 0; \ + return x + +#define SET_DEL(set, x) \ + if (x != set->n_buckets && !__ac_iseither(set->flags, x)) { \ + __ac_set_isdel_true(set->flags, x); \ + --set->size; \ + } diff --git a/include/base/macro/qsort.h b/include/base/macro/qsort.h new file mode 100644 index 0000000..6d0acaa --- /dev/null +++ b/include/base/macro/qsort.h @@ -0,0 +1,91 @@ +#pragma once + +/* + * Nicholas Noll (2020) + * Straight implementation of Sedgewick's median qsort + * #ref: "Implementing Quicksort Programs" (1978) + * + * @LEN: name of parameter length + * @QLESS: name of function that computes array[i] < array[j] + * should return a boolean + * @QSWAP: name of function that swaps array[i] <-> array[j] + * this could swap multiple arrays + * + * NOTE: This can perform on strided arrays. + * Make sure to use parens liberally to ensure hygeine! + */ + +#define QSORT(LEN, QLESS, QSWAP) \ + int i, j, m, r, l; \ + struct { \ + int i, j; \ + } *sp, base[48]; \ + sp = base; \ + \ + l = 1; \ + r = LEN-1; \ + \ + if (LEN <= 14) goto ENDOUTER; \ +OUTERLOOP: \ + SWAP((l+r)/2, l+1); \ + \ + if (QLESS(r, l+1)) QSWAP(r, l+1); \ + if (QLESS(r, l)) QSWAP(r, l); \ + if (QLESS(l, l+1)) QSWAP(l, l+1); \ + \ + i = l+1; \ + j = r; \ + \ +INNERLOOP: \ + do ++i; while(QLESS(i, l)); \ + do --j; while(QLESS(l, j)); \ + if (j < i) goto ENDINNER; \ + QSWAP(i, j); \ + goto INNERLOOP; \ + \ +ENDINNER: \ + QSWAP(l, j); \ + \ + if (MAX(j-l, r-i+1) <= 14) { \ + if (sp == base) { \ + goto ENDOUTER; \ + } else { \ + l = sp[-1].i; \ + r = sp[-1].j; \ + sp--; \ + } \ + } else { \ + if (MIN(j-l, r-i+1) <= 14) { \ + if (j-l > r-i+1) { \ + l = l; \ + r = j-1; \ + } else { \ + l = i; \ + r = r; \ + } \ + } else { \ + if (j-l > r-i+1) { \ + sp->i = l; \ + sp->j = j-1; \ + sp++; \ + \ + l = i; \ + r = r; \ + } else { \ + sp->i = i; \ + sp->j = r; \ + sp++; \ + \ + l = l; \ + r = j-1; \ + } \ + } \ + } \ + goto OUTERLOOP; \ + \ +ENDOUTER: \ + for (i = 1; i < LEN; i++) { \ + for (j = i; j > 0 && QLESS(j, j-1); j--) { \ + QSWAP(j, j-1); \ + } \ + } diff --git a/include/libn.h b/include/libn.h deleted file mode 100644 index 699786f..0000000 --- a/include/libn.h +++ /dev/null @@ -1,465 +0,0 @@ -#pragma once - -// ------------------------------------------------------------------------ -// standard library - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -typedef wchar_t wchar; - -// ---------------------------------------------------------------------------- -// dynamic array - -typedef struct BufHdr -{ - vlong len; - vlong cap; - byte buf[]; -} BufHdr; - -#define bufhdr(b) ((BufHdr*)((uint8*)(b)-offsetof(BufHdr, buf))) -#define buflen(b) ((b) ? (bufhdr(b)->len) : 0) -#define bufcap(b) ((b) ? (bufhdr(b)->cap) : 0) -#define bufend(b) ((b) + buflen(b)) -#define bufsize(b) ((b) ? (buflen(b) * sizeof((b)[0])) : 0) - -#define buffree(b) ((b) ? (free(bufhdr(b)), (b) = nil) : 0) -#define buffit(b, n) ((n) <= bufcap(b) ? 0 : ((b) = ·bufgrow((b), (n), sizeof(*(b))))) - -#define bufpush(b, ...) (buffit((b), 1 + buflen(b)), (b)[bufhdr(b)->len++] = (__VA_ARGS__)) -#define bufaddn(b, n) (buffit(b, buflen(b)+n), bufhdr(b)->len += n, b+bufhdr(b)->len-n) - -#define bufpop(b) ((b)[--bufhdr(b)->len]) -#define bufdel(b, i) bufdeln((b), (i), 1) -#define bufdeln(b, i, n) (memmove((b)+(i), (b)+(i)+(n), sizeof(*(b))*(bufhdr(b)->len-(n)-(i)), bufhdr(b)->len -= (n)) -#define bufdelswap(b, i) ((b)[i] = bufend(b)[-1], bufhdr(b)->len-=1) - -void* ·bufgrow(void*, vlong, vlong); - -// ----------------------------------------------------------------------------- -// memory allocation - -// TODO(nnoll): Allow for nil iterfaces? -/* allocator interface */ -typedef struct mem·Allocator { - void *(*alloc)(void *heap, uint n, ulong size); - void (*free)(void *heap, void *ptr); -} mem·Allocator; - -extern mem·Allocator sys·Memory; - -typedef struct mem·Reallocator { - void *(*alloc)(void *iface, uint n, ulong size); - void *(*realloc)(void *iface, void *ptr, uint n, ulong size); - void (*free)(void *iface, void *ptr); -} mem·Reallocator; - -extern mem·Reallocator sys·Relocator; - -/* simple memory arena */ -typedef struct mem·Arena mem·Arena; - -mem·Arena *mem·makearena(mem·Allocator from, void*); -void *mem·arenaalloc(mem·Arena *A, uint n, ulong size); -void mem·freearena(mem·Arena *A); - -extern mem·Allocator mem·ArenaAllocator; - -/* generalized memxxx functions */ -void memset64(void *dst, uint64 val, uintptr size); - -// ----------------------------------------------------------------------------- -// coroutines - -typedef struct Coro Coro; - -Coro* coro·make(uintptr stk, uintptr (*func)(Coro*, uintptr)); -uintptr coro·yield(Coro *c, uintptr arg); -error coro·free(Coro *c); - -// ----------------------------------------------------------------------------- -// strings - -typedef byte* string; - -/* string helpers */ -string str·makecap(const byte *s, vlong len, vlong cap); -string str·makelen(const byte *s, vlong len); -string str·make(const byte *s); -string str·makef(const byte *fmt, ...); -void str·free(string s); -int str·len(const string s); -int str·cap(const string s); -void str·clear(string *s); -void str·grow(string *s, vlong delta); -void str·fit(string *s); -int str·appendlen(string *s, vlong len, const byte *b); -int str·append(string *s, const byte* b); -int str·appendf(string *s, const byte* fmt, ...); -int str·appendbyte(string *s, const byte b); -bool str·equals(const string s, const string t); -int str·find(string s, const byte* substr); -void str·lower(string s); -void str·upper(string s); -int str·read(string s, int size, int n, void *buf); -void str·replace(string s, const byte* from, const byte* to); -string* str·split(string s, const byte* tok); -string str·join(vlong len, byte** fields, const byte* sep); - -/* - * UTF-8 functions. - * Perhaps break into own unit - * TODO: Add to(upper|lower|title) - */ -typedef uint32 rune; - -/* - * We have to use the preprocessor to ensure - * we have unsigned constants. Unfortunate... - */ - -#define UTFmax 4 -#define RuneSync 0x80u -#define RuneSelf 0x80u -#define RuneErr 0xFFFDu -#define RuneMax 0x10FFFFu -#define RuneMask 0x1FFFFFu - -/* utf8 helpers */ -int utf8·fullrune(byte *s, int n); -byte *utf8·findrune(byte *s, long i); -byte *utf8·findrrune(byte* s, long c); -int utf8·bytetorune(rune *r, byte *s); -int utf8·runetobyte(byte *s, rune *r); -int utf8·len(byte *s); -int utf8·runelen(rune r); -int utf8·isletter(rune r); -int utf8·isdigit(rune r); -int utf8·isspace(rune r); -int utf8·istitle(rune r); - -// ----------------------------------------------------------------------------- -// i/o - -typedef FILE io·Stream; -typedef struct stat io·Stat; - -enum SeekPos -{ - seek·cur = SEEK_CUR, - seek·set = SEEK_SET, - seek·end = SEEK_END -}; - -/* XXX: change casing */ -enum -{ - ReadOK = R_OK, - WriteOK = W_OK, - ExecOK = X_OK, -}; - -/* file handling */ -io·Stream *io·open(byte *name, byte *mode); -int io·fd(io·Stream *s); -error io·stat(io·Stream *s, io·Stat *buf); -error io·close(io·Stream *s); -byte io·getbyte(io·Stream *s); -error io·ungetbyte(io·Stream *s, byte c); -int io·read(io·Stream *s, int sz, int n, void *buf); -int io·readln(io·Stream *s, int n, byte *buf); -error io·putbyte(io·Stream *s, byte c); -int io·putstring(io·Stream *s, string str); -int io·write(io·Stream *s, int sz, int n, void *buf); -int io·flush(io·Stream *s); -int io·seek(io·Stream *s, long off, enum SeekPos whence); -long io·tell(io·Stream *s); - -/* basic os helpers */ -int os·exists(byte *path, int flag); -byte *os·basename(byte *path); -int os·sep(void); - -/* io interfaces */ -typedef struct io·Reader -{ - int (*read)(void*, int sz, int n, void *buf); -} io·Reader; -extern io·Reader sys·Reader; - -typedef struct io·Peeker -{ - byte (*get)(void*); - error (*unget)(void*, byte); -} io·Peeker; -extern io·Peeker sys·Peeker; - -typedef struct io·Seeker -{ - int (*seek)(void *skr, long off, enum SeekPos whence); - long (*tell)(void *skr); -} io·Seeker; -extern io·Seeker sys·Seeker; - -typedef struct io·SeekReader -{ - io·Seeker; - io·Reader; -} io·SeekReader; -extern io·SeekReader sys·SeekReader; - -typedef struct io·PeekReader -{ - io·Reader; - io·Peeker; -} io·PeekReader; -extern io·PeekReader sys·PeekReader; - -typedef struct io·Writer -{ - int (*write)(void*, int sz, int n, void *buf); -} io·Writer; -extern io·Writer sys·Writer; - -typedef struct io·Putter -{ - error (*put) (void*, byte); - int (*puts)(void*, string); -} io·Putter; -extern io·Putter sys·Putter; - -typedef struct io·PutWriter -{ - io·Writer; - io·Putter; -} io·PutWriter; -extern io·PutWriter sys·PutWriter; - -typedef struct io·ReadWriter -{ - io·Reader; - io·Writer; -} io·ReadWriter; -extern io·ReadWriter sys·ReadWriter; - -/* buffered i/o */ -typedef struct io·Buffer io·Buffer; - -enum -{ - bufio·size = 2*4096, - bufio·ungets = 8, - bufio·eof = -1, - bufio·err = -2, - - bufio·nil = 1 << 0, - bufio·rdr = 1 << 1, - bufio·wtr = 1 << 2, - bufio·end = 1 << 3, -}; - -struct io·Buffer -{ - int state; - int runesize; - void *h; - union { - io·Reader rdr; - io·Writer wtr; - }; - vlong size; - byte *beg, *pos, *end; - byte buf[bufio·size + bufio·ungets]; -}; - -error bufio·initreader(io·Buffer *buf, io·Reader rdr, void *h); -void bufio·finireader(io·Buffer *buf); -int bufio·getbyte(io·Buffer *buf); -error bufio·ungetbyte(io·Buffer *buf, byte c); -rune bufio·getrune(io·Buffer *buf); -error bufio·ungetrune(io·Buffer *buf, rune r); -int bufio·read(io·Buffer *buf, int sz, int n, void *out); - -// ----------------------------------------------------------------------------- -// memory mapped files - -typedef struct mmap·Reader -{ - vlong len; - union { - byte *buf; - ubyte *ubuf; - }; -} mmap·Reader; - -mmap·Reader mmap·open(byte *name); -error mmap·close(mmap·Reader rdr); - -// ----------------------------------------------------------------------------- -// filesystem - -#define iota(x) 1 << (x) -enum -{ - fs·preorder = iota(0), - fs·nolinks = iota(1), - fs·verbose = iota(2), -}; -#undef iota - -typedef struct fs·Walker fs·Walker; -typedef struct fs·History fs·History; - -struct fs·Walker -{ - int fd, lev, max, err; - uchar flags : 4; - fs·History *hist; - struct { - void *data; - int (*func)(void *data, char *relp, char *absp, io·Stat* info); - }; - char *base, *end, path[4096]; -}; - -int fs·init(fs·Walker *, char *path); -void fs·fini(fs·Walker *); -void fs·walk(fs·Walker *); - -// ----------------------------------------------------------------------------- -// libflate -// NOTE: Experimental! - -typedef struct flate·Reader flate·Reader; -typedef struct flate·Writer flate·Writer; - -flate·Reader *flate·openreader(io·Reader rdr, void* r, mem·Allocator mem, void* m); -int flate·read(flate·Reader *rdr, int sz, int n, void *buf); -error flate·closereader(flate·Reader *rdr); - -flate·Writer *flate·openwriter(io·Writer wtr, void* w, mem·Allocator mem, void* m); -int flate·write(flate·Writer *wtr, int sz, int n, void *buf); -error flate·closewriter(flate·Writer *wtr); - -// ----------------------------------------------------------------------------- -// libgz - -typedef void gz·Stream; - -/* interfaces */ -extern io·Reader gz·Reader; -extern io·Peeker gz·Peeker; -extern io·Seeker gz·Seeker; -extern io·SeekReader gz·SeekReader; -extern io·PeekReader gz·PeekReader; - -extern io·Writer gz·Writer; -extern io·Putter gz·Putter; -extern io·PutWriter gz·PutWriter; -extern io·ReadWriter gz·ReadWriter; - -gz·Stream *gz·open(byte *path, byte *mode); -error gz·close(gz·Stream* s); -int gz·read(gz·Stream *s, int sz, int n, void* buf); -int gz·readln(gz·Stream *s, int n, byte *buf); -byte gz·getbyte(gz·Stream *s); -error gz·ungetbyte(gz·Stream *s, byte c); -int gz·write(gz·Stream *s, int sz, int n, void* buf); -error gz·putbyte(gz·Stream *s, byte str); -error gz·putstring(gz·Stream *s, byte *str); -int gz·printf(gz·Stream *s, byte *fmt, ...); -error gz·flush(gz·Stream *s); -int gz·seek(gz·Stream *s, long off, enum SeekPos whence); -long gz·tell(gz·Stream *s); - -// ----------------------------------------------------------------------------- -// libjson -// NOTE: Experimental! - -// ----------------------------------------------------------------------------- -// error handling functions - -void exits(char *s); -void errorf(byte* fmt, ...); -void verrorf(byte* fmt, va_list args); -void panicf(byte *fmt, ...); -void vpanicf(byte *fmt, va_list args); - -// ----------------------------------------------------------------------------- -// sorting - -void sort·ints(uintptr n, int arr[]); -void sort·int8s(uintptr n, int8 arr[]); -void sort·int16s(uintptr n, int16 arr[]); -void sort·int32s(uintptr n, int32 arr[]); -void sort·int64s(uintptr n, int64 arr[]); - -void sort·uints(uintptr n, uint arr[]); -void sort·uint8s(uintptr n, uint8 arr[]); -void sort·uint16s(uintptr n, uint16 arr[]); -void sort·uint32s(uintptr n, uint32 arr[]); -void sort·uint64s(uintptr n, uint64 arr[]); - -void sort·floats(uintptr n, float arr[]); -void sort·doubles(uintptr n, double arr[]); - -void sort·strings(uintptr n, byte* arr[]); - -// ----------------------------------------------------------------------------- -// fast random number generation - -error rng·init(uint64 seed); -double rng·random(void); -double rng·exponential(double lambda); -bool rng·bernoulli(double f); -uint64 rng·randi(int max); -uint64 rng·poisson(double mean); - -// ----------------------------------------------------------------------------- -// variable arguments - -/* from plan9 libc */ - -#define ERRMAX 128 /* max length of error string */ - -#define SET(x) ((x)=0) -#define USED(x) if(x){}else{} -#ifdef __GNUC__ -# if __GNUC__ >= 3 -# undef USED -# define USED(x) ((void)(x)) -# endif -#endif - -extern char *argv0; -#define ARGBEGIN for((argv0?0:(argv0=*argv)),argv++,argc--; \ - argv[0] && argv[0][0]=='-' && argv[0][1]; \ - argc--, argv++) { \ - byte *_args, *_argt; \ - rune _argc; \ - _args = &argv[0][1]; \ - if(_args[0]=='-' && _args[1]==0){ \ - argc--; argv++; break; \ - } \ - _argc = 0; \ - while(*_args && (_args += utf8·bytetorune(&_argc, _args)))\ - switch(_argc) -#define ARGEND SET(_argt);USED(_argt);USED(_argc);USED(_args);}USED(argv);USED(argc); -#define ARGF() (_argt=_args, _args="",\ - (*_argt? _argt: argv[1]? (argc--, *++argv): 0)) -#define EARGF(x) (_argt=_args, _args="",\ - (*_argt? _argt: argv[1]? (argc--, *++argv): ((x), abort(), (char*)0))) - -#define ARGC() _argc diff --git a/include/libn/macro/map.h b/include/libn/macro/map.h deleted file mode 100644 index 7c2f7ae..0000000 --- a/include/libn/macro/map.h +++ /dev/null @@ -1,400 +0,0 @@ -#pragma once - -/* - * Based on khash.h - * Modified to make control more granular and similar to QSORT - */ - -static const double __ac_HASH_UPPER = 0.77; - -#define _roundup32(x) \ - (--(x), (x) |= (x) >> 1, (x) |= (x) >> 2, (x) |= (x) >> 4, (x) |= (x) >> 8, \ - (x) |= (x) >> 16, ++(x)) - -#define __ac_isempty(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 2) -#define __ac_isdel(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 1) -#define __ac_iseither(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 3) -#define __ac_set_isdel_false(flag, i) \ - (flag[i >> 4] &= ~(1ul << ((i & 0xfU) << 1))) -#define __ac_set_isempty_false(flag, i) \ - (flag[i >> 4] &= ~(2ul << ((i & 0xfU) << 1))) -#define __ac_set_isboth_false(flag, i) \ - (flag[i >> 4] &= ~(3ul << ((i & 0xfU) << 1))) -#define __ac_set_isdel_true(flag, i) (flag[i >> 4] |= 1ul << ((i & 0xfU) << 1)) - -#define __ac_fsize(m) ((m) < 16 ? 1 : (m) >> 4) - -#define MAP_STRUCT_BODY(key_t, val_t) \ - int32 n_buckets, size, n_occupied, upper_bound; \ - int32 *flags; \ - key_t *keys; \ - val_t *vals; - -#define MAP_MAKE(type, h, alloc) \ - type *map; \ - map = alloc((h), 1, sizeof(*map)); \ - return map - -#define MAP_FREE(map, mem, heap) \ - mem.free(heap, map->keys); \ - mem.free(heap, map->flags); \ - mem.free(heap, map->vals); \ - mem.free(heap, map); - -#define MAP_RESET(map) \ - if (map && map->flags) { \ - memset(map->flags, 0xaa, __ac_fsize(map->n_buckets) * sizeof(int32)); \ - map->size = map->n_occupied = 0; \ - } - -#define MAP_GET(i, map, key, hashfunc, equalfunc ) \ - int32 k, last, mask, step; \ - if (map->n_buckets) { \ - k = 0; \ - i = 0; \ - last = 0; \ - mask = 0; \ - step = 0; \ - mask = map->n_buckets - 1; \ - k = hashfunc(key); \ - i = k & mask; \ - last = i; \ - while (!__ac_isempty(map->flags, i) && \ - (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ - i = (i + (++step)) & mask; \ - if (i == last) { \ - i = map->n_buckets; \ - break; \ - } \ - } \ - if (i < map->n_buckets && __ac_iseither(map->flags, i)) \ - i = map->n_buckets; \ - } else \ - i = 0; - -#define MAP_GROW(map, key_t, val_t, new_n_buckets, hashfunc, mem, heap) \ - int32 *new_flags = nil; \ - int32 j = 1; \ - { \ - _roundup32(new_n_buckets); \ - if (new_n_buckets < 4) \ - new_n_buckets = 4; \ - if (map->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ - j = 0; \ - else { \ - new_flags = mem.alloc(heap, __ac_fsize(new_n_buckets), sizeof(int32)); \ - if (!new_flags) return -1; \ - memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ - if (map->n_buckets < new_n_buckets) { /* expand */ \ - key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ - if (!new_keys) { \ - mem.free(heap, new_flags); \ - return -1; \ - } \ - memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ - mem.free(heap, map->keys); \ - map->keys = new_keys; \ - val_t *new_vals = mem.alloc(heap, new_n_buckets, sizeof(val_t)); \ - if (!new_vals) { \ - mem.free(heap, new_flags); \ - return -1; \ - } \ - memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ - mem.free(heap, map->vals); \ - map->vals = new_vals; \ - } \ - } \ - } \ - if (j) { /* rehashing is needed */ \ - for (j = 0; j != map->n_buckets; ++j) { \ - if (__ac_iseither(map->flags, j) == 0) { \ - key_t key = map->keys[j]; \ - val_t val; \ - int32 new_mask; \ - new_mask = new_n_buckets - 1; \ - val = map->vals[j]; \ - __ac_set_isdel_true(map->flags, j); \ - while (1) { \ - int32 k, i, step = 0; \ - k = hashfunc(key); \ - i = k & new_mask; \ - while (!__ac_isempty(new_flags, i)) \ - i = (i + (++step)) & new_mask; \ - __ac_set_isempty_false(new_flags, i); \ - if (i < map->n_buckets && __ac_iseither(map->flags, i) == 0) { \ - { \ - key_t tmp = map->keys[i]; \ - map->keys[i] = key; \ - key = tmp; \ - } \ - { \ - val_t tmp = map->vals[i]; \ - map->vals[i] = val; \ - val = tmp; \ - } \ - __ac_set_isdel_true(map->flags, i); \ - } else { \ - map->keys[i] = key; \ - map->vals[i] = val; \ - break; \ - } \ - } \ - } \ - } \ - if (map->n_buckets > new_n_buckets) { /* shrink the hash table */ \ - key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ - memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ - mem.free(heap, map->keys); \ - map->keys = new_keys; \ - \ - val_t *new_vals = mem.alloc(heap, new_n_buckets, sizeof(val_t)); \ - memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ - mem.free(heap, map->vals); \ - map->vals = new_vals; \ - } \ - mem.free(heap, map->flags); /* free the working space */ \ - map->flags = new_flags; \ - map->n_buckets = new_n_buckets; \ - map->n_occupied = map->size; \ - map->upper_bound = (int32)(map->n_buckets * __ac_HASH_UPPER + 0.5); \ - } \ - return 0; - -#define MAP_PUT(map, key, val, hashfunc, equalfunc, resizefunc, err) \ - int32 x = 0; \ - if (map->n_occupied >= map->upper_bound) { \ - if (map->n_buckets > (map->size << 1)) { \ - if (resizefunc(map, map->n_buckets - 1) < 0) { \ - *err = -1; \ - return map->n_buckets; \ - } \ - } else if (resizefunc(map, map->n_buckets + 1) < 0) { \ - *err = -1; \ - return map->n_buckets; \ - } \ - } \ - \ - { \ - int32 k, i, site, last, mask = map->n_buckets - 1, step = 0; \ - x = site = map->n_buckets; \ - k = hashfunc(key); \ - i = k & mask; \ - if (__ac_isempty(map->flags, i)) \ - x = i; /* for speed up */ \ - else { \ - last = i; \ - while (!__ac_isempty(map->flags, i) && \ - (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ - if (__ac_isdel(map->flags, i)) \ - site = i; \ - i = (i + (++step)) & mask; \ - if (i == last) { \ - x = site; \ - break; \ - } \ - } \ - if (x == map->n_buckets) { \ - if (__ac_isempty(map->flags, i) && site != map->n_buckets) \ - x = site; \ - else \ - x = i; \ - } \ - } \ - } \ - if (__ac_isempty(map->flags, x)) { /* not present at all */ \ - map->keys[x] = key; \ - __ac_set_isboth_false(map->flags, x); \ - ++map->size; \ - ++map->n_occupied; \ - *err = 1; \ - } else if (__ac_isdel(map->flags, x)) { /* deleted */ \ - map->keys[x] = key; \ - __ac_set_isboth_false(map->flags, x); \ - ++map->size; \ - } else \ - *err = 0; \ - return x; - -#define MAP_DEL(map, x) \ - if (x != map->n_buckets && !__ac_iseither(map->flags, x)) { \ - __ac_set_isdel_true(map->flags, x); \ - --map->size; \ - } - -#define KEY_EXIST(m, x) (!__ac_iseither((m)->flags, (x))) - -/* set macro */ - -#define SET_STRUCT_BODY(key_t) \ - int32 n_buckets, size, n_occupied, upper_bound; \ - int32 *flags; \ - key_t *keys \ - -#define SET_MAKE(type, h, alloc) \ - type *set; \ - set = alloc((h), 1, sizeof(*set)); \ - return set - -#define SET_FREE(set, mem, heap) \ - mem.free(heap, set->keys); \ - mem.free(heap, set->flags); \ - mem.free(heap, set) - -#define SET_RESET(set) \ - if (set && set->flags) { \ - memset(set->flags, 0xaa, __ac_fsize(set->n_buckets) * sizeof(int32)); \ - set->size = set->n_occupied = 0; \ - } - -#define SET_GET(i, set, key, hashfunc, equalfunc ) \ - int32 k, last, mask, step; \ - if (set->n_buckets) { \ - k = 0; \ - i = 0; \ - last = 0; \ - mask = 0; \ - step = 0; \ - mask = set->n_buckets - 1; \ - k = hashfunc(key); \ - i = k & mask; \ - last = i; \ - while (!__ac_isempty(set->flags, i) && \ - (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \ - i = (i + (++step)) & mask; \ - if (i == last) { \ - i = set->n_buckets; \ - break; \ - } \ - } \ - if (i < set->n_buckets && __ac_iseither(set->flags, i)) \ - i = set->n_buckets; \ - } else \ - i = 0; - -#define SET_GROW(set, key_t, new_n_buckets, hashfunc, mem, heap) \ - int32 *new_flags = nil; \ - int32 j = 1; \ - { \ - _roundup32(new_n_buckets); \ - if (new_n_buckets < 4) \ - new_n_buckets = 4; \ - if (set->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ - j = 0; \ - else { \ - new_flags = mem.alloc(heap, __ac_fsize(new_n_buckets), sizeof(int32)); \ - if (!new_flags) return -1; \ - memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ - if (set->n_buckets < new_n_buckets) { /* expand */ \ - key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ - if (!new_keys) { \ - mem.free(heap, new_flags); \ - return -1; \ - } \ - memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ - mem.free(heap, set->keys); \ - set->keys = new_keys; \ - } \ - } \ - } \ - if (j) { /* rehashing is needed */ \ - for (j = 0; j != set->n_buckets; ++j) { \ - if (__ac_iseither(set->flags, j) == 0) { \ - key_t key = set->keys[j]; \ - int32 new_mask; \ - new_mask = new_n_buckets - 1; \ - __ac_set_isdel_true(set->flags, j); \ - while (1) { \ - int32 k, i, step = 0; \ - k = hashfunc(key); \ - i = k & new_mask; \ - while (!__ac_isempty(new_flags, i)) \ - i = (i + (++step)) & new_mask; \ - __ac_set_isempty_false(new_flags, i); \ - if (i < set->n_buckets && __ac_iseither(set->flags, i) == 0) { \ - { \ - key_t tmp = set->keys[i]; \ - set->keys[i] = key; \ - key = tmp; \ - } \ - __ac_set_isdel_true(set->flags, i); \ - } else { \ - set->keys[i] = key; \ - break; \ - } \ - } \ - } \ - } \ - if (set->n_buckets > new_n_buckets) { /* shrink the hash table */ \ - key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ - memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ - mem.free(heap, set->keys); \ - set->keys = new_keys; \ - } \ - mem.free(heap, set->flags); /* free the working space */ \ - set->flags = new_flags; \ - set->n_buckets = new_n_buckets; \ - set->n_occupied = set->size; \ - set->upper_bound = (int32)(set->n_buckets * __ac_HASH_UPPER + 0.5); \ - } \ - return 0; - -#define SET_PUT(set, key, hashfunc, equalfunc, resizefunc, err) \ - int32 x = 0; \ - if (set->n_occupied >= set->upper_bound) { \ - if (set->n_buckets > (set->size << 1)) { \ - if (resizefunc(set, set->n_buckets - 1) < 0) { \ - *err = -1; \ - return set->n_buckets; \ - } \ - } else if (resizefunc(set, set->n_buckets + 1) < 0) { \ - *err = -1; \ - return set->n_buckets; \ - } \ - } \ - \ - { \ - int32 k, i, site, last, mask = set->n_buckets - 1, step = 0; \ - x = site = set->n_buckets; \ - k = hashfunc(key); \ - i = k & mask; \ - if (__ac_isempty(set->flags, i)) \ - x = i; /* for speed up */ \ - else { \ - last = i; \ - while (!__ac_isempty(set->flags, i) && \ - (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \ - if (__ac_isdel(set->flags, i)) \ - site = i; \ - i = (i + (++step)) & mask; \ - if (i == last) { \ - x = site; \ - break; \ - } \ - } \ - if (x == set->n_buckets) { \ - if (__ac_isempty(set->flags, i) && site != set->n_buckets) \ - x = site; \ - else \ - x = i; \ - } \ - } \ - } \ - if (__ac_isempty(set->flags, x)) { /* not present at all */ \ - set->keys[x] = key; \ - __ac_set_isboth_false(set->flags, x); \ - ++set->size; \ - ++set->n_occupied; \ - *err = 1; \ - } else if (__ac_isdel(set->flags, x)) { /* deleted */ \ - set->keys[x] = key; \ - __ac_set_isboth_false(set->flags, x); \ - ++set->size; \ - } else \ - *err = 0; \ - return x - -#define SET_DEL(set, x) \ - if (x != set->n_buckets && !__ac_iseither(set->flags, x)) { \ - __ac_set_isdel_true(set->flags, x); \ - --set->size; \ - } diff --git a/include/libn/macro/qsort.h b/include/libn/macro/qsort.h deleted file mode 100644 index 6d0acaa..0000000 --- a/include/libn/macro/qsort.h +++ /dev/null @@ -1,91 +0,0 @@ -#pragma once - -/* - * Nicholas Noll (2020) - * Straight implementation of Sedgewick's median qsort - * #ref: "Implementing Quicksort Programs" (1978) - * - * @LEN: name of parameter length - * @QLESS: name of function that computes array[i] < array[j] - * should return a boolean - * @QSWAP: name of function that swaps array[i] <-> array[j] - * this could swap multiple arrays - * - * NOTE: This can perform on strided arrays. - * Make sure to use parens liberally to ensure hygeine! - */ - -#define QSORT(LEN, QLESS, QSWAP) \ - int i, j, m, r, l; \ - struct { \ - int i, j; \ - } *sp, base[48]; \ - sp = base; \ - \ - l = 1; \ - r = LEN-1; \ - \ - if (LEN <= 14) goto ENDOUTER; \ -OUTERLOOP: \ - SWAP((l+r)/2, l+1); \ - \ - if (QLESS(r, l+1)) QSWAP(r, l+1); \ - if (QLESS(r, l)) QSWAP(r, l); \ - if (QLESS(l, l+1)) QSWAP(l, l+1); \ - \ - i = l+1; \ - j = r; \ - \ -INNERLOOP: \ - do ++i; while(QLESS(i, l)); \ - do --j; while(QLESS(l, j)); \ - if (j < i) goto ENDINNER; \ - QSWAP(i, j); \ - goto INNERLOOP; \ - \ -ENDINNER: \ - QSWAP(l, j); \ - \ - if (MAX(j-l, r-i+1) <= 14) { \ - if (sp == base) { \ - goto ENDOUTER; \ - } else { \ - l = sp[-1].i; \ - r = sp[-1].j; \ - sp--; \ - } \ - } else { \ - if (MIN(j-l, r-i+1) <= 14) { \ - if (j-l > r-i+1) { \ - l = l; \ - r = j-1; \ - } else { \ - l = i; \ - r = r; \ - } \ - } else { \ - if (j-l > r-i+1) { \ - sp->i = l; \ - sp->j = j-1; \ - sp++; \ - \ - l = i; \ - r = r; \ - } else { \ - sp->i = i; \ - sp->j = r; \ - sp++; \ - \ - l = l; \ - r = j-1; \ - } \ - } \ - } \ - goto OUTERLOOP; \ - \ -ENDOUTER: \ - for (i = 1; i < LEN; i++) { \ - for (j = i; j > 0 && QLESS(j, j-1); j--) { \ - QSWAP(j, j-1); \ - } \ - } -- cgit v1.2.1