Add Queue and map iteratorsHEAD main

author: Bad Diode <bd@badd10de.dev> 2024-06-12 17:12:38 +0200
committer: Bad Diode <bd@badd10de.dev> 2024-06-12 17:12:38 +0200
commit: 94b95f76ddbc5552c7356753d07bf081a3ae3bb6 (patch)
tree: fe2df5e386f03b504642a8b21795fb6cead9350c
parent: 872d0a536280550c7742f0ea805fdfefddd44d9f (diff)
download: mic-main.tar.gz
mic-main.zip
2 files changed, 201 insertions, 146 deletions
diff --git a/src/app.c b/src/app.c
index 3d28077..371c132 100644
--- a/src/app.c
+++ b/src/app.c
@@ -2,6 +2,11 @@
 #include "app.h"
 #include "platform.h"
+#include <stdio.h>
+#include <ctype.h>
+#define printstr(s) if (s) printf("%.*s", (int)(s)->size, (s)->mem);
+#define printstrln(s) if (s) printf("%.*s\n", (int)(s)->size, (s)->mem);
 static inline bool
 app_init(AppState *s, PlatformAPI p) {
    p.log("INIT");
@@ -53,10 +58,6 @@ profile_end(PlatformAPI p, char *name) {
 }
-#include <stdio.h>
-#define printstr(s) printf("%.*s", (int)(s)->size, (s)->mem);
-#define printstrln(s) printf("%.*s\n", (int)(s)->size, (s)->mem);
 bool
 eq_func(void *a, void *b) {
    Str *x = a;
@@ -76,7 +77,7 @@ hash_func(void *x) {
 }
 void
-print_node(HashNode *item) {
+print_node(MapNode *item) {
    if (!item) {
        return;
    }
@@ -85,7 +86,7 @@ print_node(HashNode *item) {
    printstr((Str*)item->key);
    printf("\\n%ld\", shape=record]\n", (sz)item->val);
    for (sz i = 0; i < 4; i++) {
-        HashNode *child = item->child[i];
+        MapNode *child = item->child[i];
        if (child) {
            printstr((Str*)item->key);
            printf(" -> ");
@@ -96,7 +97,7 @@ print_node(HashNode *item) {
 }
 void
-print_map(HashMap m) {
+print_map(Map m) {
    if (m.root == NULL) {
        return;
    }
@@ -105,16 +106,28 @@ print_map(HashMap m) {
    printf("}\n");
 }
+void
+iterate_map(Map map, Arena *scratch) {
+    MapIter it = map_iterator(map, scratch);
+    MapNode *item;
+    while ((item = map_next(&it, scratch)) != NULL) {
+        Str *key = item->key;
+        printf("{ ");
+        printstr(key);
+        printf(", %ld }\n", (sz)item->val);
+    }
+}
 // Find how many of the given strings are unique.
 sz
-unique(Str *strings, sz len, Arena scratch) {
+unique(Str *strings, sz len, Arena *scratch) {
    sz count = 0;
-    HashMap map = {
+    Map map = {
        .eq_func = eq_func,
        .hash_func = hash_func,
    };
    for (sz i = 0; i < len; i++) {
-        HashNode *item = upsert(&map, &strings[i], &scratch);
+        MapNode *item = map_upsert(&map, &strings[i], scratch);
        sz cnt = (sz)item->val;
        item->val = (void*)(++cnt);
        if ((sz)item->val <= 1) {
@@ -122,12 +135,10 @@ unique(Str *strings, sz len, Arena scratch) {
        }
    }
    // print_map(map);
+    // iterate_map(map, scratch);
    return count;
 }
-#include <stdio.h>
-#include <ctype.h>
 sz 
 token_split(Str s) {
    if (s.size) {
@@ -170,72 +181,56 @@ token_split(Str s) {
                return splitter.size;
            }
        }
-        // splitter = cstr("digraph");
-        // if(str_eq((Str){s.mem, splitter.size}, splitter)) {
-        //     return splitter.size;
-        // }
-        // splitter = cstr("node");
-        // if(str_eq((Str){s.mem, splitter.size}, splitter)) {
-        //     return splitter.size;
-        // }
-        // splitter = cstr("STRICT");
-        // if(str_eq((Str){s.mem, splitter.size}, splitter)) {
-        //     return splitter.size;
-        // }
-        // splitter = cstr("graph");
-        // if(str_eq((Str){s.mem, splitter.size}, splitter)) {
-        //     return splitter.size;
-        // }
    }
+    // iterate_map(map, scratch);
    return 0;
 }
+sz
+unique_tokenize(Str data, Arena *scratch) {
+    (void)data;
+    sz count = 0;
+    Map map = {
+        .eq_func = eq_func,
+        .hash_func = hash_func,
+    };
+    Str strings[] = {
+        cstr("a"),
+        cstr("b"),
+        cstr("c"),
+        cstr("d"),
+        cstr("e"),
+        cstr("f"),
+        cstr("g"),
+    };
+    for (sz i = 0; i < len(strings); i++) {
+        map_insert(&map, &strings[i], (void*)i, scratch);
+    }
+    iterate_map(map, scratch);
+    // print_map(map);
+    return count;
+}
 static inline bool
 app_step(AppState *s, PlatformAPI p) {
    // Passing an arena by value makes the operation self cleaning.
    Arena scratch = s->scratch;
-    // TODO: split a file into "words" or "tokens" 
+    Queue q = {0};
-    // Str strings[] = {
+    queue_push(&q, &cstr("HI!"), &scratch);
-    //     cstr("test"),
+    queue_push(&q, &cstr("HO!"), &scratch);
-    //     cstr("test"),
+    queue_push(&q, &cstr("HU!"), &scratch);
-    //     cstr("test"),
+    Str *val;
-    //     cstr("toast"),
+    val = queue_peek(&q); printstrln(val);
-    //     cstr("test"),
+    val = queue_pop(&q); printstrln(val);
-    //     cstr("helllo"),
+    val = queue_pop(&q); printstrln(val);
-    //     cstr("dummy"),
+    val = queue_pop(&q); printstrln(val);
-    //     cstr("sasfdladsf"),
+    // Str file_name = cstr("WebstersEnglishDictionary.txt");
-    //     cstr("yodog"),
+    Str file_name = cstr("./README.md");
-    //     cstr("kazuya"),
-    //     cstr("hello"),
-    //     cstr("world"),
-    //     cstr("what"),
-    //     cstr("hello"),
-    //     cstr("whot"),
-    // };
-    // sz u = unique(strings, len(strings), scratch);
-    // // return false;
-    // p.log("unique: %ld", u);
-    // u8 * p1 = arena_malloc(10, &scratch);
-    // u8 * p2 = arena_malloc(8, &scratch);
-    // u8 * p3 = arena_malloc(8, &scratch);
-    // p.log("scratch size: %ld", scratch.size);
-    // p.log("ptraddr1: 0x%x", p1);
-    // p.log("ptraddr2: 0x%x", p2);
-    // p.log("ptraddr3: 0x%x", p3);
-    // p.log("base: 0x%x", scratch.beg);
-    Str file_name = cstr("WebstersEnglishDictionary.txt");
-    // Str file_name = cstr("test.dot");
    FileContents file_content;
    profile("reading_file") {
        file_content = p.read_file(file_name, &scratch);
    }
    if (!file_content.err) {
-        // p.log("file content: `%.*s` (size: %ld)\n" 
-        //     "%.*s", 
-        //     file_content.path.size, file_content.path.mem, 
-        //     file_content.data.size,
-        //     MIN(50, file_content.data.size), file_content.data.mem);
        Str data = file_content.data;
        profile("str_replace_all") {
            str_replace_all(&data, cstr("\n"), cstr(" "));
@@ -243,37 +238,22 @@ app_step(AppState *s, PlatformAPI p) {
        Str *tokens = NULL;
        array_init(tokens, 256, &scratch);
        profile("create_tokens") {
-        while (data.size > 0) {
+            while (data.size > 0) {
-        //     // Str line = str_split(&data, cstr("\n")); printstrln(&line);
+                // Str token = str_split(&data, cstr(" ")); 
-        //     // Str line = str_split(&data, cstr("\n")); printstrln(&line);
+                Str token = str_split_fn(&data, token_split); 
-        //     // Str token = str_split(&data, cstr(" ")); 
+                if (token.size > 0) {
-            Str token = str_split_fn(&data, token_split); 
+                    array_push(tokens, token, &scratch);
-            if (token.size > 0) {
+                }
-                // printstrln(&token);
-        //         // printf("has_prefix: `app_`: %d ", str_has_prefix(token, cstr("app_")));
-        //         // printf("has_suffix: `API`: %d ", str_has_suffix(token, cstr("API")));
-        //         // printf("token_size: %03ld | ", token.size); printstr(&token);
-        //         // printf(" -> ");
-        //         // token = str_remove_prefix(token, cstr("app_")); printstr(&token)
-        //         // printf(" -> ");
-        //         // token = str_remove_suffix(token, cstr("API")); printstr(&token)
-                // p.log("N: %ld", array_size(tokens));
-                array_push(tokens, token, &scratch);
-        //         // printf("\n");
            }
        }
-        }
-        // for (sz i = 0; i < array_size(tokens); i++) {
-        //     // printstrln(&tokens[i]);
-        // }
-        // for (sz i = 0; i < len(strings); i++) {
-        //     array_push(tokens, strings[i], &scratch);
-        // }
        sz u;
        profile("find unique") {
-            u = unique(tokens, array_size(tokens), scratch);
+            u = unique(tokens, array_size(tokens), &scratch);
+        }
+        p.log("unique: %ld", u);
+        profile("find unique (directly)") {
+            u = unique_tokenize(file_content.data, &scratch);
        }
-        // return false;
        p.log("unique: %ld", u);
    } else {
        Str err_msg = err_str[file_content.err];
@@ -281,16 +261,16 @@ app_step(AppState *s, PlatformAPI p) {
            err_msg.size, err_msg.mem,
            file_name.size, file_name.mem);
    }
-    // p.log("Used memory: scratch -> %lld/%lld KB, perm -> %lld/%lld KB", 
-    //       scratch.size / 1024, 
-    //       scratch.cap / 1024,
-    //       s->perm.size / 1024, 
-    //       s->perm.cap / 1024);
    p.log("Used memory: scratch -> %lld/%lld MB, perm -> %lld/%lld MB", 
          scratch.size / 1024 / 1024, 
          scratch.cap / 1024 / 1024,
          s->perm.size / 1024 / 1024, 
          s->perm.cap / 1024 / 1024);
+    // p.log("Used memory: scratch -> %lld/%lld KB, perm -> %lld/%lld KB", 
+    //       scratch.size / 1024, 
+    //       scratch.cap / 1024,
+    //       s->perm.size / 1024, 
+    //       s->perm.cap / 1024);
    // p.log("Used memory: scratch -> %lld/%lld B, perm -> %lld/%lld B", 
    //       scratch.size, 
    //       scratch.cap,
diff --git a/src/shorthand.h b/src/shorthand.h
index 879b8ed..f70c792 100644
--- a/src/shorthand.h
+++ b/src/shorthand.h
@@ -3,15 +3,10 @@
 // TODO:
 // - Add string operations.
-//     - eq
 //     - sub
 //     - contains
-//     - remove_prefix
-//     - remove_suffix
 //     - find_first
 //     - find_last
-//     - pop_split
-//     - split
 // - Add string buffer operations.
 //     - make
 //     - append
@@ -19,7 +14,6 @@
 //     - remove
 //     - to_str
 // - Add math operations for vectors and matrices.
-// - Add darray and hash_map.
 // - Can we remove the PlatformAPI function pointers and just use extern
 //   references?
 // - Breakdown this file in the different library parts.
@@ -277,7 +271,7 @@ arena_calloc(sz size, void *ctx) {
 void
 arena_free(void *ptr, sz size, void *ctx) {
-    // Undo the latest allocation.
+    // Undo the latest allocation if possible.
    Arena *a = (Arena *)ctx;
    sz padding = -size & (ARENA_ALIGNMENT - 1);
    size += padding;
@@ -288,6 +282,9 @@ arena_free(void *ptr, sz size, void *ctx) {
 void *
 arena_realloc(void *ptr, sz old_size, sz new_size, void *ctx) {
+    // This function can avoid copying memory around if we could just extend the
+    // latest allocation, otherwise a new malloc will be performed (keeping the
+    // previous data alive!).
    Arena *a = (Arena *)ctx;
    sz old_padding = -old_size & (ARENA_ALIGNMENT - 1);
    old_size += old_padding;
@@ -328,27 +325,84 @@ arena_reset(Arena *a) {
    a->size = 0;
 }
-struct HashTable;
+//
+// Queue.
+//
+typedef struct QueueVal {
+    struct QueueVal *next;
+    void *val;
+} QueueVal;
+typedef struct Queue {
+    struct QueueVal *head;
+    struct QueueVal *tail;
+    sz size;
+} Queue;
+void
+queue_push(Queue *l, void *val, Arena *a) {
+    assert(l);
+    QueueVal *next = (QueueVal*)arena_calloc(sizeof(QueueVal), a);
+    next->val = val;
+    if (l->size == 0) {
+        l->head = next;
+        l->tail = next;
+        l->size = 1;
+        return;
+    }
+    QueueVal *cur = l->tail;
+    cur->next = next;
+    l->tail = next;
+    l->size++;
+}
+void *
+queue_peek(Queue *l) {
+    assert(l);
+    if (l->size == 0) {
+        return NULL;
+    }
+    QueueVal *cur = l->head;
+    return cur->val;
+}
+void *
+queue_pop(Queue *l) {
+    assert(l);
+    if (l->size == 0) {
+        return NULL;
+    }
+    QueueVal *cur = l->head;
+    l->head = cur->next;
+    l->size--;
+    return cur->val;
+}
+//
+// Map.
+//
 typedef u64 (HashFunc)(void *in);
 typedef bool (EqFunc)(void *a, void *b);
-typedef struct HashNode {
+typedef struct MapNode {
-    struct HashNode *child[4];
+    struct MapNode *child[4];
    void *key;
    void *val;
-} HashNode;
+} MapNode;
-typedef struct HashMap {
+typedef struct Map {
    HashFunc *hash_func;
    EqFunc *eq_func;
-    HashNode *root;
+    MapNode *root;
    Arena *storage;
-} HashMap;
+} Map;
-HashNode *
+MapNode *
-upsert(HashMap *m, void *key, Arena *a) {
+map_upsert(Map *m, void *key, Arena *a) {
    u64 h = m->hash_func(key);
-    HashNode **item = &m->root;
+    MapNode **item = &m->root;
    while (*item) {
        if (m->eq_func(key, (*item)->key)) {
            return *item;
@@ -356,15 +410,32 @@ upsert(HashMap *m, void *key, Arena *a) {
        h = (h << 2) | (h >> 62);
        item = &(*item)->child[h & 0x3];
    }
-    *item = (HashNode *)arena_calloc(sizeof(HashNode), a);
+    *item = (MapNode *)arena_calloc(sizeof(MapNode), a);
    (*item)->key = key;
    return *item;
 }
-HashNode *
+void
-lookup(HashMap *m, void *key) {
+map_insert(Map *m, void *key, void *val, Arena *a) {
    u64 h = m->hash_func(key);
-    HashNode **item = &m->root;
+    MapNode **item = &m->root;
+    while (*item) {
+        if (m->eq_func(key, (*item)->key)) {
+            (*item)->val = val;
+            return;
+        }
+        h = (h << 2) | (h >> 62);
+        item = &(*item)->child[h & 0x3];
+    }
+    *item = (MapNode *)arena_calloc(sizeof(MapNode), a);
+    (*item)->key = key;
+    (*item)->val = val;
+}
+MapNode *
+map_lookup(Map *m, void *key) {
+    u64 h = m->hash_func(key);
+    MapNode **item = &m->root;
    while (*item) {
        if (m->eq_func(key, (*item)->key)) {
            return *item;
@@ -375,34 +446,38 @@ lookup(HashMap *m, void *key) {
    return NULL;
 }
-// u64
+typedef struct MapIter {
-// hash(Str s) {
+    Queue queue;
-//     u64 h = 0x100;
+} MapIter;
-//     for (sz i = 0; i < s.size; i++) {
-//         h ^= s.mem[i];
+MapIter
-//         h *= 1111111111111111111u;
+map_iterator(Map map, Arena *a) {
-//     }
+    MapIter it = {0};
-//     return h;
+    queue_push(&it.queue, map.root, a);
-// }
+    return it;
+}
-// typedef struct StrMap {
-//     struct StrMap *child[4];
+MapNode *
-//     Str key;
+map_next(MapIter *it, Arena *a) {
-//     sz val;
+    assert(it);
-// } StrMap;
+    assert(a);
+    while (it->queue.head) {
-// StrMap *
+        MapNode *item = (MapNode *)queue_pop(&it->queue);
-// upsert(StrMap **m, Str key, Arena *a) {
+        for (sz i = 0; i < 4; i++) {
-//     for (u64 h = hash(key); *m; h <<= 2) {
+            MapNode *child = item->child[i];
-//         if (str_eq(key, (*m)->key)) {
+            if (child) {
-//             return *m;
+                queue_push(&it->queue, child, a);
-//         }
+            }
-//         m = &(*m)->child[h >> 62];
+        }
-//     }
+        return item;
-//     *m = (StrMap *)arena_calloc(sizeof(StrMap), a);
+    }
-//     (*m)->key = key;
+    return NULL;
-//     return *m;
+}
-// }
+//
+// Dynamic arrays.
+//
 typedef struct ArrayHeader {
    sz size;
author	Bad Diode <bd@badd10de.dev>	2024-06-12 17:12:38 +0200
committer	Bad Diode <bd@badd10de.dev>	2024-06-12 17:12:38 +0200
commit	94b95f76ddbc5552c7356753d07bf081a3ae3bb6 (patch)
tree	fe2df5e386f03b504642a8b21795fb6cead9350c
parent	872d0a536280550c7742f0ea805fdfefddd44d9f (diff)
download	mic-main.tar.gz mic-main.zip

diff --git a/src/app.c b/src/app.c index 3d28077..371c132 100644 --- a/src/app.c +++ b/src/app.c
@@ -2,6 +2,11 @@
2	#include "app.h"	2	#include "app.h"
3	#include "platform.h"	3	#include "platform.h"
4		4
		5	#include <stdio.h>
		6	#include <ctype.h>
		7	#define printstr(s) if (s) printf("%.*s", (int)(s)->size, (s)->mem);
		8	#define printstrln(s) if (s) printf("%.*s\n", (int)(s)->size, (s)->mem);
		9
5	static inline bool	10	static inline bool
6	app_init(AppState *s, PlatformAPI p) {	11	app_init(AppState *s, PlatformAPI p) {
7	p.log("INIT");	12	p.log("INIT");
@@ -53,10 +58,6 @@ profile_end(PlatformAPI p, char *name) {
53	}	58	}
54		59
55		60
56	#include <stdio.h>
57	#define printstr(s) printf("%.*s", (int)(s)->size, (s)->mem);
58	#define printstrln(s) printf("%.*s\n", (int)(s)->size, (s)->mem);
59
60	bool	61	bool
61	eq_func(void a, void b) {	62	eq_func(void a, void b) {
62	Str *x = a;	63	Str *x = a;
@@ -76,7 +77,7 @@ hash_func(void *x) {
76	}	77	}
77		78
78	void	79	void
79	print_node(HashNode *item) {	80	print_node(MapNode *item) {
80	if (!item) {	81	if (!item) {
81	return;	82	return;
82	}	83	}
@@ -85,7 +86,7 @@ print_node(HashNode *item) {
85	printstr((Str*)item->key);	86	printstr((Str*)item->key);
86	printf("\\n%ld\", shape=record]\n", (sz)item->val);	87	printf("\\n%ld\", shape=record]\n", (sz)item->val);
87	for (sz i = 0; i < 4; i++) {	88	for (sz i = 0; i < 4; i++) {
88	HashNode *child = item->child[i];	89	MapNode *child = item->child[i];
89	if (child) {	90	if (child) {
90	printstr((Str*)item->key);	91	printstr((Str*)item->key);
91	printf(" -> ");	92	printf(" -> ");
@@ -96,7 +97,7 @@ print_node(HashNode *item) {
96	}	97	}
97		98
98	void	99	void
99	print_map(HashMap m) {	100	print_map(Map m) {
100	if (m.root == NULL) {	101	if (m.root == NULL) {
101	return;	102	return;
102	}	103	}
@@ -105,16 +106,28 @@ print_map(HashMap m) {
105	printf("}\n");	106	printf("}\n");
106	}	107	}
107		108
		109	void
		110	iterate_map(Map map, Arena *scratch) {
		111	MapIter it = map_iterator(map, scratch);
		112	MapNode *item;
		113	while ((item = map_next(&it, scratch)) != NULL) {
		114	Str *key = item->key;
		115	printf("{ ");
		116	printstr(key);
		117	printf(", %ld }\n", (sz)item->val);
		118	}
		119	}
		120
108	// Find how many of the given strings are unique.	121	// Find how many of the given strings are unique.
109	sz	122	sz
110	unique(Str *strings, sz len, Arena scratch) {	123	unique(Str strings, sz len, Arena scratch) {
111	sz count = 0;	124	sz count = 0;
112	HashMap map = {	125	Map map = {
113	.eq_func = eq_func,	126	.eq_func = eq_func,
114	.hash_func = hash_func,	127	.hash_func = hash_func,
115	};	128	};
116	for (sz i = 0; i < len; i++) {	129	for (sz i = 0; i < len; i++) {
117	HashNode *item = upsert(&map, &strings[i], &scratch);	130	MapNode *item = map_upsert(&map, &strings[i], scratch);
118	sz cnt = (sz)item->val;	131	sz cnt = (sz)item->val;
119	item->val = (void*)(++cnt);	132	item->val = (void*)(++cnt);
120	if ((sz)item->val <= 1) {	133	if ((sz)item->val <= 1) {
@@ -122,12 +135,10 @@ unique(Str *strings, sz len, Arena scratch) {
122	}	135	}
123	}	136	}
124	// print_map(map);	137	// print_map(map);
		138	// iterate_map(map, scratch);
125	return count;	139	return count;
126	}	140	}
127		141
128	#include <stdio.h>
129	#include <ctype.h>
130
131	sz	142	sz
132	token_split(Str s) {	143	token_split(Str s) {
133	if (s.size) {	144	if (s.size) {
@@ -170,72 +181,56 @@ token_split(Str s) {
170	return splitter.size;	181	return splitter.size;
171	}	182	}
172	}	183	}
173
174	// splitter = cstr("digraph");
175	// if(str_eq((Str){s.mem, splitter.size}, splitter)) {
176	// return splitter.size;
177	// }
178	// splitter = cstr("node");
179	// if(str_eq((Str){s.mem, splitter.size}, splitter)) {
180	// return splitter.size;
181	// }
182	// splitter = cstr("STRICT");
183	// if(str_eq((Str){s.mem, splitter.size}, splitter)) {
184	// return splitter.size;
185	// }
186	// splitter = cstr("graph");
187	// if(str_eq((Str){s.mem, splitter.size}, splitter)) {
188	// return splitter.size;
189	// }
190	}	184	}
		185	// iterate_map(map, scratch);
191	return 0;	186	return 0;
192	}	187	}
193		188
		189	sz
		190	unique_tokenize(Str data, Arena *scratch) {
		191	(void)data;
		192	sz count = 0;
		193	Map map = {
		194	.eq_func = eq_func,
		195	.hash_func = hash_func,
		196	};
		197	Str strings[] = {
		198	cstr("a"),
		199	cstr("b"),
		200	cstr("c"),
		201	cstr("d"),
		202	cstr("e"),
		203	cstr("f"),
		204	cstr("g"),
		205	};
		206	for (sz i = 0; i < len(strings); i++) {
		207	map_insert(&map, &strings[i], (void*)i, scratch);
		208	}
		209	iterate_map(map, scratch);
		210	// print_map(map);
		211	return count;
		212	}
		213
194	static inline bool	214	static inline bool
195	app_step(AppState *s, PlatformAPI p) {	215	app_step(AppState *s, PlatformAPI p) {
196	// Passing an arena by value makes the operation self cleaning.	216	// Passing an arena by value makes the operation self cleaning.
197	Arena scratch = s->scratch;	217	Arena scratch = s->scratch;
198	// TODO: split a file into "words" or "tokens"	218	Queue q = {0};
199	// Str strings[] = {	219	queue_push(&q, &cstr("HI!"), &scratch);
200	// cstr("test"),	220	queue_push(&q, &cstr("HO!"), &scratch);
201	// cstr("test"),	221	queue_push(&q, &cstr("HU!"), &scratch);
202	// cstr("test"),	222	Str *val;
203	// cstr("toast"),	223	val = queue_peek(&q); printstrln(val);
204	// cstr("test"),	224	val = queue_pop(&q); printstrln(val);
205	// cstr("helllo"),	225	val = queue_pop(&q); printstrln(val);
206	// cstr("dummy"),	226	val = queue_pop(&q); printstrln(val);
207	// cstr("sasfdladsf"),	227	// Str file_name = cstr("WebstersEnglishDictionary.txt");
208	// cstr("yodog"),	228	Str file_name = cstr("./README.md");
209	// cstr("kazuya"),
210	// cstr("hello"),
211	// cstr("world"),
212	// cstr("what"),
213	// cstr("hello"),
214	// cstr("whot"),
215	// };
216	// sz u = unique(strings, len(strings), scratch);
217	// // return false;
218	// p.log("unique: %ld", u);
219	// u8 * p1 = arena_malloc(10, &scratch);
220	// u8 * p2 = arena_malloc(8, &scratch);
221	// u8 * p3 = arena_malloc(8, &scratch);
222	// p.log("scratch size: %ld", scratch.size);
223	// p.log("ptraddr1: 0x%x", p1);
224	// p.log("ptraddr2: 0x%x", p2);
225	// p.log("ptraddr3: 0x%x", p3);
226	// p.log("base: 0x%x", scratch.beg);
227	Str file_name = cstr("WebstersEnglishDictionary.txt");
228	// Str file_name = cstr("test.dot");
229	FileContents file_content;	229	FileContents file_content;
230	profile("reading_file") {	230	profile("reading_file") {
231	file_content = p.read_file(file_name, &scratch);	231	file_content = p.read_file(file_name, &scratch);
232	}	232	}
233	if (!file_content.err) {	233	if (!file_content.err) {
234	// p.log("file content: `%.*s` (size: %ld)\n"
235	// "%.*s",
236	// file_content.path.size, file_content.path.mem,
237	// file_content.data.size,
238	// MIN(50, file_content.data.size), file_content.data.mem);
239	Str data = file_content.data;	234	Str data = file_content.data;
240	profile("str_replace_all") {	235	profile("str_replace_all") {
241	str_replace_all(&data, cstr("\n"), cstr(" "));	236	str_replace_all(&data, cstr("\n"), cstr(" "));
@@ -243,37 +238,22 @@ app_step(AppState *s, PlatformAPI p) {
243	Str *tokens = NULL;	238	Str *tokens = NULL;
244	array_init(tokens, 256, &scratch);	239	array_init(tokens, 256, &scratch);
245	profile("create_tokens") {	240	profile("create_tokens") {
246	while (data.size > 0) {	241	while (data.size > 0) {
247	// // Str line = str_split(&data, cstr("\n")); printstrln(&line);	242	// Str token = str_split(&data, cstr(" "));
248	// // Str line = str_split(&data, cstr("\n")); printstrln(&line);	243	Str token = str_split_fn(&data, token_split);
249	// // Str token = str_split(&data, cstr(" "));	244	if (token.size > 0) {
250	Str token = str_split_fn(&data, token_split);	245	array_push(tokens, token, &scratch);
251	if (token.size > 0) {	246	}
252	// printstrln(&token);
253	// // printf("has_prefix: `app_`: %d ", str_has_prefix(token, cstr("app_")));
254	// // printf("has_suffix: `API`: %d ", str_has_suffix(token, cstr("API")));
255	// // printf("token_size: %03ld \| ", token.size); printstr(&token);
256	// // printf(" -> ");
257	// // token = str_remove_prefix(token, cstr("app_")); printstr(&token)
258	// // printf(" -> ");
259	// // token = str_remove_suffix(token, cstr("API")); printstr(&token)
260	// p.log("N: %ld", array_size(tokens));
261	array_push(tokens, token, &scratch);
262	// // printf("\n");
263	}	247	}
264	}	248	}
265	}
266	// for (sz i = 0; i < array_size(tokens); i++) {
267	// // printstrln(&tokens[i]);
268	// }
269	// for (sz i = 0; i < len(strings); i++) {
270	// array_push(tokens, strings[i], &scratch);
271	// }
272	sz u;	249	sz u;
273	profile("find unique") {	250	profile("find unique") {
274	u = unique(tokens, array_size(tokens), scratch);	251	u = unique(tokens, array_size(tokens), &scratch);
		252	}
		253	p.log("unique: %ld", u);
		254	profile("find unique (directly)") {
		255	u = unique_tokenize(file_content.data, &scratch);
275	}	256	}
276	// return false;
277	p.log("unique: %ld", u);	257	p.log("unique: %ld", u);
278	} else {	258	} else {
279	Str err_msg = err_str[file_content.err];	259	Str err_msg = err_str[file_content.err];
@@ -281,16 +261,16 @@ app_step(AppState *s, PlatformAPI p) {
281	err_msg.size, err_msg.mem,	261	err_msg.size, err_msg.mem,
282	file_name.size, file_name.mem);	262	file_name.size, file_name.mem);
283	}	263	}
284	// p.log("Used memory: scratch -> %lld/%lld KB, perm -> %lld/%lld KB",
285	// scratch.size / 1024,
286	// scratch.cap / 1024,
287	// s->perm.size / 1024,
288	// s->perm.cap / 1024);
289	p.log("Used memory: scratch -> %lld/%lld MB, perm -> %lld/%lld MB",	264	p.log("Used memory: scratch -> %lld/%lld MB, perm -> %lld/%lld MB",
290	scratch.size / 1024 / 1024,	265	scratch.size / 1024 / 1024,
291	scratch.cap / 1024 / 1024,	266	scratch.cap / 1024 / 1024,
292	s->perm.size / 1024 / 1024,	267	s->perm.size / 1024 / 1024,
293	s->perm.cap / 1024 / 1024);	268	s->perm.cap / 1024 / 1024);
		269	// p.log("Used memory: scratch -> %lld/%lld KB, perm -> %lld/%lld KB",
		270	// scratch.size / 1024,
		271	// scratch.cap / 1024,
		272	// s->perm.size / 1024,
		273	// s->perm.cap / 1024);
294	// p.log("Used memory: scratch -> %lld/%lld B, perm -> %lld/%lld B",	274	// p.log("Used memory: scratch -> %lld/%lld B, perm -> %lld/%lld B",
295	// scratch.size,	275	// scratch.size,
296	// scratch.cap,	276	// scratch.cap,


diff --git a/src/shorthand.h b/src/shorthand.h index 879b8ed..f70c792 100644 --- a/src/shorthand.h +++ b/src/shorthand.h
@@ -3,15 +3,10 @@
3		3
4	// TODO:	4	// TODO:
5	// - Add string operations.	5	// - Add string operations.
6	// - eq
7	// - sub	6	// - sub
8	// - contains	7	// - contains
9	// - remove_prefix
10	// - remove_suffix
11	// - find_first	8	// - find_first
12	// - find_last	9	// - find_last
13	// - pop_split
14	// - split
15	// - Add string buffer operations.	10	// - Add string buffer operations.
16	// - make	11	// - make
17	// - append	12	// - append
@@ -19,7 +14,6 @@
19	// - remove	14	// - remove
20	// - to_str	15	// - to_str
21	// - Add math operations for vectors and matrices.	16	// - Add math operations for vectors and matrices.
22	// - Add darray and hash_map.
23	// - Can we remove the PlatformAPI function pointers and just use extern	17	// - Can we remove the PlatformAPI function pointers and just use extern
24	// references?	18	// references?
25	// - Breakdown this file in the different library parts.	19	// - Breakdown this file in the different library parts.
@@ -277,7 +271,7 @@ arena_calloc(sz size, void *ctx) {
277		271
278	void	272	void
279	arena_free(void ptr, sz size, void ctx) {	273	arena_free(void ptr, sz size, void ctx) {
280	// Undo the latest allocation.	274	// Undo the latest allocation if possible.
281	Arena a = (Arena )ctx;	275	Arena a = (Arena )ctx;
282	sz padding = -size & (ARENA_ALIGNMENT - 1);	276	sz padding = -size & (ARENA_ALIGNMENT - 1);
283	size += padding;	277	size += padding;
@@ -288,6 +282,9 @@ arena_free(void ptr, sz size, void ctx) {
288		282
289	void *	283	void *
290	arena_realloc(void ptr, sz old_size, sz new_size, void ctx) {	284	arena_realloc(void ptr, sz old_size, sz new_size, void ctx) {
		285	// This function can avoid copying memory around if we could just extend the
		286	// latest allocation, otherwise a new malloc will be performed (keeping the
		287	// previous data alive!).
291	Arena a = (Arena )ctx;	288	Arena a = (Arena )ctx;
292	sz old_padding = -old_size & (ARENA_ALIGNMENT - 1);	289	sz old_padding = -old_size & (ARENA_ALIGNMENT - 1);
293	old_size += old_padding;	290	old_size += old_padding;
@@ -328,27 +325,84 @@ arena_reset(Arena *a) {
328	a->size = 0;	325	a->size = 0;
329	}	326	}
330		327
331	struct HashTable;	328	//
		329	// Queue.
		330	//
		331
		332	typedef struct QueueVal {
		333	struct QueueVal *next;
		334	void *val;
		335	} QueueVal;
		336
		337	typedef struct Queue {
		338	struct QueueVal *head;
		339	struct QueueVal *tail;
		340	sz size;
		341	} Queue;
		342
		343	void
		344	queue_push(Queue l, void val, Arena *a) {
		345	assert(l);
		346	QueueVal next = (QueueVal)arena_calloc(sizeof(QueueVal), a);
		347	next->val = val;
		348	if (l->size == 0) {
		349	l->head = next;
		350	l->tail = next;
		351	l->size = 1;
		352	return;
		353	}
		354	QueueVal *cur = l->tail;
		355	cur->next = next;
		356	l->tail = next;
		357	l->size++;
		358	}
		359
		360	void *
		361	queue_peek(Queue *l) {
		362	assert(l);
		363	if (l->size == 0) {
		364	return NULL;
		365	}
		366	QueueVal *cur = l->head;
		367	return cur->val;
		368	}
		369
		370	void *
		371	queue_pop(Queue *l) {
		372	assert(l);
		373	if (l->size == 0) {
		374	return NULL;
		375	}
		376	QueueVal *cur = l->head;
		377	l->head = cur->next;
		378	l->size--;
		379	return cur->val;
		380	}
		381
		382	//
		383	// Map.
		384	//
		385
332	typedef u64 (HashFunc)(void *in);	386	typedef u64 (HashFunc)(void *in);
333	typedef bool (EqFunc)(void a, void b);	387	typedef bool (EqFunc)(void a, void b);
334		388
335	typedef struct HashNode {	389	typedef struct MapNode {
336	struct HashNode *child[4];	390	struct MapNode *child[4];
337	void *key;	391	void *key;
338	void *val;	392	void *val;
339	} HashNode;	393	} MapNode;
340		394
341	typedef struct HashMap {	395	typedef struct Map {
342	HashFunc *hash_func;	396	HashFunc *hash_func;
343	EqFunc *eq_func;	397	EqFunc *eq_func;
344	HashNode *root;	398	MapNode *root;
345	Arena *storage;	399	Arena *storage;
346	} HashMap;	400	} Map;
347		401
348	HashNode *	402	MapNode *
349	upsert(HashMap m, void key, Arena *a) {	403	map_upsert(Map m, void key, Arena *a) {
350	u64 h = m->hash_func(key);	404	u64 h = m->hash_func(key);
351	HashNode **item = &m->root;	405	MapNode **item = &m->root;
352	while (*item) {	406	while (*item) {
353	if (m->eq_func(key, (*item)->key)) {	407	if (m->eq_func(key, (*item)->key)) {
354	return *item;	408	return *item;
@@ -356,15 +410,32 @@ upsert(HashMap m, void key, Arena *a) {
356	h = (h << 2) \| (h >> 62);	410	h = (h << 2) \| (h >> 62);
357	item = &(*item)->child[h & 0x3];	411	item = &(*item)->child[h & 0x3];
358	}	412	}
359	item = (HashNode )arena_calloc(sizeof(HashNode), a);	413	item = (MapNode )arena_calloc(sizeof(MapNode), a);
360	(*item)->key = key;	414	(*item)->key = key;
361	return *item;	415	return *item;
362	}	416	}
363		417
364	HashNode *	418	void
365	lookup(HashMap m, void key) {	419	map_insert(Map m, void key, void val, Arena a) {
366	u64 h = m->hash_func(key);	420	u64 h = m->hash_func(key);
367	HashNode **item = &m->root;	421	MapNode **item = &m->root;
		422	while (*item) {
		423	if (m->eq_func(key, (*item)->key)) {
		424	(*item)->val = val;
		425	return;
		426	}
		427	h = (h << 2) \| (h >> 62);
		428	item = &(*item)->child[h & 0x3];
		429	}
		430	item = (MapNode )arena_calloc(sizeof(MapNode), a);
		431	(*item)->key = key;
		432	(*item)->val = val;
		433	}
		434
		435	MapNode *
		436	map_lookup(Map m, void key) {
		437	u64 h = m->hash_func(key);
		438	MapNode **item = &m->root;
368	while (*item) {	439	while (*item) {
369	if (m->eq_func(key, (*item)->key)) {	440	if (m->eq_func(key, (*item)->key)) {
370	return *item;	441	return *item;
@@ -375,34 +446,38 @@ lookup(HashMap m, void key) {
375	return NULL;	446	return NULL;
376	}	447	}
377		448
378	// u64	449	typedef struct MapIter {
379	// hash(Str s) {	450	Queue queue;
380	// u64 h = 0x100;	451	} MapIter;
381	// for (sz i = 0; i < s.size; i++) {	452
382	// h ^= s.mem[i];	453	MapIter
383	// h *= 1111111111111111111u;	454	map_iterator(Map map, Arena *a) {
384	// }	455	MapIter it = {0};
385	// return h;	456	queue_push(&it.queue, map.root, a);
386	// }	457	return it;
387		458	}
388	// typedef struct StrMap {	459
389	// struct StrMap *child[4];	460	MapNode *
390	// Str key;	461	map_next(MapIter it, Arena a) {
391	// sz val;	462	assert(it);
392	// } StrMap;	463	assert(a);
393		464	while (it->queue.head) {
394	// StrMap *	465	MapNode item = (MapNode )queue_pop(&it->queue);
395	// upsert(StrMap *m, Str key, Arena a) {	466	for (sz i = 0; i < 4; i++) {
396	// for (u64 h = hash(key); *m; h <<= 2) {	467	MapNode *child = item->child[i];
397	// if (str_eq(key, (*m)->key)) {	468	if (child) {
398	// return *m;	469	queue_push(&it->queue, child, a);
399	// }	470	}
400	// m = &(*m)->child[h >> 62];	471	}
401	// }	472	return item;
402	// m = (StrMap )arena_calloc(sizeof(StrMap), a);	473	}
403	// (*m)->key = key;	474	return NULL;
404	// return *m;	475	}
405	// }	476
		477
		478	//
		479	// Dynamic arrays.
		480	//
406		481
407	typedef struct ArrayHeader {	482	typedef struct ArrayHeader {
408	sz size;	483	sz size;