diff options
author | Bad Diode <bd@badd10de.dev> | 2024-06-20 19:47:10 +0200 |
---|---|---|
committer | Bad Diode <bd@badd10de.dev> | 2024-06-20 19:47:10 +0200 |
commit | c10fe9d48d40e3fa2a20ee61b79518dfbaeb4db9 (patch) | |
tree | fecf5bc4e9099caccb484015fcc3ea7f22bbe844 /src | |
parent | 46bd782e6c65f7f9807cfc996476d99c7a06848f (diff) | |
download | bdl-c10fe9d48d40e3fa2a20ee61b79518dfbaeb4db9.tar.gz bdl-c10fe9d48d40e3fa2a20ee61b79518dfbaeb4db9.zip |
Add a couple of macros for ergonomic set/map creation
Diffstat (limited to 'src')
-rw-r--r-- | src/badlib.h | 221 | ||||
-rw-r--r-- | src/main.c | 12 |
2 files changed, 148 insertions, 85 deletions
diff --git a/src/badlib.h b/src/badlib.h index 674045a..ada309a 100644 --- a/src/badlib.h +++ b/src/badlib.h | |||
@@ -816,97 +816,148 @@ queue_pop(Queue *l) { | |||
816 | // Map. | 816 | // Map. |
817 | // | 817 | // |
818 | 818 | ||
819 | typedef u64(HashFunc)(void *in); | 819 | // Specialiced commonly used hash sets/maps as macro definitions. There is no |
820 | typedef bool(EqFunc)(void *a, void *b); | 820 | // delete on these ones but are trivial to implement! |
821 | 821 | #define SETDEF(STRUCTNAME, FUNCNAME, KEYTYPE, HASHFUNC, EQFUNC) \ | |
822 | typedef struct MapNode { | 822 | typedef struct STRUCTNAME { \ |
823 | struct MapNode *child[4]; | 823 | struct STRUCTNAME *child[4]; \ |
824 | void *key; | 824 | KEYTYPE key; \ |
825 | void *val; | 825 | } STRUCTNAME; \ |
826 | } MapNode; | 826 | STRUCTNAME *\ |
827 | 827 | FUNCNAME##_lookup(STRUCTNAME **m, KEYTYPE key) {\ | |
828 | typedef struct Map { | 828 | u64 h = HASHFUNC(key);\ |
829 | HashFunc *hash_func; | 829 | while (*m) {\ |
830 | EqFunc *eq_func; | 830 | if (EQFUNC(key, (*m)->key)) {\ |
831 | MapNode *root; | 831 | return *m;\ |
832 | Arena *storage; | 832 | }\ |
833 | } Map; | 833 | h = (h << 2) | (h >> 62);\ |
834 | 834 | m = &(*m)->child[h & 0x3];\ | |
835 | MapNode * | 835 | }\ |
836 | map_upsert(Map *m, void *key, Arena *a) { | 836 | return NULL;\ |
837 | u64 h = m->hash_func(key); | 837 | }\ |
838 | MapNode **item = &m->root; | 838 | STRUCTNAME *\ |
839 | while (*item) { | 839 | FUNCNAME##_insert(STRUCTNAME **m, KEYTYPE key, Arena *a) {\ |
840 | if (m->eq_func(key, (*item)->key)) { | 840 | u64 h = HASHFUNC(key);\ |
841 | return *item; | 841 | while (*m) {\ |
842 | } | 842 | if (EQFUNC(key, (*m)->key)) {\ |
843 | h = (h << 2) | (h >> 62); | 843 | return *m;\ |
844 | item = &(*item)->child[h & 0x3]; | 844 | }\ |
845 | h = (h << 2) | (h >> 62);\ | ||
846 | m = &(*m)->child[h & 0x3];\ | ||
847 | }\ | ||
848 | *m = arena_calloc(sizeof(STRUCTNAME), a);\ | ||
849 | (*m)->key = key;\ | ||
850 | return *m;\ | ||
851 | }\ | ||
852 | typedef Queue STRUCTNAME##Iter;\ | ||
853 | STRUCTNAME##Iter\ | ||
854 | FUNCNAME##_iterator(STRUCTNAME *map, Arena *a) {\ | ||
855 | STRUCTNAME##Iter it = {0};\ | ||
856 | queue_push(&it, map, a);\ | ||
857 | return it;\ | ||
858 | }\ | ||
859 | STRUCTNAME *\ | ||
860 | FUNCNAME##_next(STRUCTNAME##Iter *it, Arena *a) {\ | ||
861 | assert(it);\ | ||
862 | assert(a);\ | ||
863 | while (it->head) {\ | ||
864 | STRUCTNAME *item = (STRUCTNAME *)queue_pop(it);\ | ||
865 | for (sz i = 0; i < 4; i++) {\ | ||
866 | STRUCTNAME *child = item->child[i];\ | ||
867 | if (child) {\ | ||
868 | queue_push(it, child, a);\ | ||
869 | }\ | ||
870 | }\ | ||
871 | return item;\ | ||
872 | }\ | ||
873 | return NULL;\ | ||
845 | } | 874 | } |
846 | *item = arena_calloc(sizeof(MapNode), a); | ||
847 | (*item)->key = key; | ||
848 | return *item; | ||
849 | } | ||
850 | 875 | ||
851 | void | 876 | #define MAPDEF(STRUCTNAME, FUNCNAME, KEYTYPE, VALTYPE, HASHFUNC, EQFUNC) \ |
852 | map_insert(Map *m, void *key, void *val, Arena *a) { | 877 | typedef struct STRUCTNAME { \ |
853 | u64 h = m->hash_func(key); | 878 | struct STRUCTNAME *child[4]; \ |
854 | MapNode **item = &m->root; | 879 | KEYTYPE key; \ |
855 | while (*item) { | 880 | VALTYPE val; \ |
856 | if (m->eq_func(key, (*item)->key)) { | 881 | } STRUCTNAME;\ |
857 | (*item)->val = val; | 882 | STRUCTNAME *\ |
858 | return; | 883 | FUNCNAME##_insert(STRUCTNAME **m, KEYTYPE key, VALTYPE val, Arena *a) {\ |
859 | } | 884 | u64 h = HASHFUNC(key);\ |
860 | h = (h << 2) | (h >> 62); | 885 | while (*m) {\ |
861 | item = &(*item)->child[h & 0x3]; | 886 | if (EQFUNC(key, (*m)->key)) {\ |
862 | } | 887 | (*m)->val = val;\ |
863 | *item = arena_calloc(sizeof(MapNode), a); | 888 | return *m;\ |
864 | (*item)->key = key; | 889 | }\ |
865 | (*item)->val = val; | 890 | h = (h << 2) | (h >> 62);\ |
866 | } | 891 | m = &(*m)->child[h & 0x3];\ |
867 | 892 | }\ | |
868 | MapNode * | 893 | *m = arena_calloc(sizeof(STRUCTNAME), a);\ |
869 | map_lookup(Map *m, void *key) { | 894 | (*m)->key = key;\ |
870 | u64 h = m->hash_func(key); | 895 | (*m)->val = val;\ |
871 | MapNode **item = &m->root; | 896 | return *m;\ |
872 | while (*item) { | 897 | }\ |
873 | if (m->eq_func(key, (*item)->key)) { | 898 | STRUCTNAME *\ |
874 | return *item; | 899 | FUNCNAME##_lookup(STRUCTNAME **m, KEYTYPE key) {\ |
875 | } | 900 | u64 h = HASHFUNC(key);\ |
876 | h = (h << 2) | (h >> 62); | 901 | while (*m) {\ |
877 | item = &(*item)->child[h & 0x3]; | 902 | if (EQFUNC(key, (*m)->key)) {\ |
903 | return *m;\ | ||
904 | }\ | ||
905 | h = (h << 2) | (h >> 62);\ | ||
906 | m = &(*m)->child[h & 0x3];\ | ||
907 | }\ | ||
908 | return NULL;\ | ||
909 | }\ | ||
910 | typedef Queue STRUCTNAME##Iter;\ | ||
911 | STRUCTNAME##Iter\ | ||
912 | FUNCNAME##_iterator(STRUCTNAME *map, Arena *a) {\ | ||
913 | STRUCTNAME##Iter it = {0};\ | ||
914 | queue_push(&it, map, a);\ | ||
915 | return it;\ | ||
916 | }\ | ||
917 | STRUCTNAME *\ | ||
918 | FUNCNAME##_next(STRUCTNAME##Iter *it, Arena *a) {\ | ||
919 | assert(it);\ | ||
920 | assert(a);\ | ||
921 | while (it->head) {\ | ||
922 | STRUCTNAME *item = (STRUCTNAME *)queue_pop(it);\ | ||
923 | for (sz i = 0; i < 4; i++) {\ | ||
924 | STRUCTNAME *child = item->child[i];\ | ||
925 | if (child) {\ | ||
926 | queue_push(it, child, a);\ | ||
927 | }\ | ||
928 | }\ | ||
929 | return item;\ | ||
930 | }\ | ||
931 | return NULL;\ | ||
878 | } | 932 | } |
879 | return NULL; | 933 | |
880 | } | 934 | u64 |
881 | 935 | str_hash(Str s) { | |
882 | typedef struct MapIter { | 936 | u64 h = 0x100; |
883 | Queue queue; | 937 | for (sz i = 0; i < s.size; i++) { |
884 | } MapIter; | 938 | h ^= s.mem[i]; |
885 | 939 | h *= 1111111111111111111u; | |
886 | MapIter | ||
887 | map_iterator(Map map, Arena *a) { | ||
888 | MapIter it = {0}; | ||
889 | queue_push(&it.queue, map.root, a); | ||
890 | return it; | ||
891 | } | ||
892 | |||
893 | MapNode * | ||
894 | map_next(MapIter *it, Arena *a) { | ||
895 | assert(it); | ||
896 | assert(a); | ||
897 | while (it->queue.head) { | ||
898 | MapNode *item = (MapNode *)queue_pop(&it->queue); | ||
899 | for (sz i = 0; i < 4; i++) { | ||
900 | MapNode *child = item->child[i]; | ||
901 | if (child) { | ||
902 | queue_push(&it->queue, child, a); | ||
903 | } | ||
904 | } | ||
905 | return item; | ||
906 | } | 940 | } |
907 | return NULL; | 941 | return h; |
942 | } | ||
943 | |||
944 | bool | ||
945 | _int_eq(sz a, sz b) { | ||
946 | return a == b; | ||
908 | } | 947 | } |
909 | 948 | ||
949 | bool | ||
950 | _int_hash(sz a) { | ||
951 | return a * UINT64_C(11400714819323198485); | ||
952 | } | ||
953 | |||
954 | |||
955 | // Commonly used map/set types. | ||
956 | SETDEF(StrSet, strset, Str, str_hash, str_eq) | ||
957 | MAPDEF(StrIntMap, strintmap, Str, sz, str_hash, str_eq) | ||
958 | SETDEF(IntSet, intset, sz, _int_hash, _int_eq) | ||
959 | MAPDEF(IntStrMap, intstrmap, sz, Str, _int_hash, _int_eq) | ||
960 | |||
910 | // | 961 | // |
911 | // Dynamic arrays. | 962 | // Dynamic arrays. |
912 | // | 963 | // |
@@ -26,6 +26,18 @@ void | |||
26 | process_file(Str path) { | 26 | process_file(Str path) { |
27 | Arena lexer_arena = arena_create(LEXER_MEM, os_allocator); | 27 | Arena lexer_arena = arena_create(LEXER_MEM, os_allocator); |
28 | 28 | ||
29 | StrIntMap *map = NULL; | ||
30 | strintmap_insert(&map, cstr("test"), 1, &lexer_arena); | ||
31 | strintmap_insert(&map, cstr("toast"), 9, &lexer_arena); | ||
32 | strintmap_insert(&map, cstr("waaaa"), 420, &lexer_arena); | ||
33 | strintmap_insert(&map, cstr("test"), 69, &lexer_arena); | ||
34 | StrIntMapIter iter = strintmap_iterator(map, &lexer_arena); | ||
35 | StrIntMap *val = strintmap_next(&iter, &lexer_arena); | ||
36 | while (val) { | ||
37 | println("KEY: %s value: %d", val->key, val->val); | ||
38 | val = strintmap_next(&iter, &lexer_arena); | ||
39 | } | ||
40 | |||
29 | FileContents file = platform_read_file(path, &lexer_arena); | 41 | FileContents file = platform_read_file(path, &lexer_arena); |
30 | if (file.err) { | 42 | if (file.err) { |
31 | eprintln("%s: error: %s", path, cstr("couldn't read the file")); | 43 | eprintln("%s: error: %s", path, cstr("couldn't read the file")); |