From 413cb3b0c5c70d60eee212c72afed9b5c659b6d8 Mon Sep 17 00:00:00 2001 From: Martin Kagamino Lehoux Date: Mon, 21 Jul 2025 21:46:41 +0200 Subject: refactor: Vec on arena --- README.md | 6 +- json.c | 196 ++++++++++++++++++++++++++++++++++++++---------------------- json.h | 1 + string.c | 4 +- string.h | 3 +- test_json.c | 24 +++++--- vec.c | 10 +++- vec.h | 2 +- 8 files changed, 158 insertions(+), 88 deletions(-) diff --git a/README.md b/README.md index 7ee2af7..008e72e 100644 --- a/README.md +++ b/README.md @@ -3,13 +3,15 @@ ## TODO - Testing setup -- Vec push no need to reallocate vec, only items. Same for Str? Read about stack pointers in C - Vec_get not safe, I made a type mistake. And should be more efficient for loops - Fix tests in release -- Benchmark 1MB file +- Benchmark 100MB file + - json.loads: 526 ms ± 77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) +- Vec_new returns pointer - More modern include pragma (once) - File structure - Static functions for private? +- JSON float ## Resources diff --git a/json.c b/json.c index 05ea3fb..8a542f5 100644 --- a/json.c +++ b/json.c @@ -5,9 +5,52 @@ #include #include #include +#include +#include "json.h" #include "string.h" +JSONObject *JSONObject_new(Arena *a) { + JSONObject *object = new(a, JSONObject, 1); + object->len = 0; + object->keys = *Vec_new(a, Str, 2); + object->values = *Vec_new(a, JSON, 2); + return object; +} + +int JSON_fprint(FILE *w, JSON json) { + if (json.string != 0) + return Str_fprint(w, *json.string); + if (json.integer != 0) + return fprintf(w, "%d", *json.integer); + if (json.object != 0) { + fprintf(w, "{"); + for (size i = 0; i < json.object->len; i++) { + Str key = *Vec_get(&json.object->keys, Str, i); + Str_fprint(w, key); + fprintf(w, ": "); + JSON value = *Vec_get(&json.object->values, JSON, i); + JSON_fprint(w, value); + if (i < json.object->len - 1) + fprintf(w, ", "); + } + fprintf(w, "}"); + return 0; + } + if (json.array != 0) { + fprintf(w, "["); + for (size i = 0; i < json.array->len; i++) { + JSON value = *Vec_get(json.array, JSON, i); + JSON_fprint(w, value); + if (i < json.array->len - 1) + fprintf(w, ", "); + } + fprintf(w, "]"); + return 0; + } + return fprintf(w, "null"); +} + typedef struct { JSON *value; uptr pos; @@ -19,11 +62,11 @@ typedef struct { uptr pos; } parse_integer_result; -parse_integer_result parse_integer(Arena *a, byte *src, uptr pos) { +parse_integer_result parse_integer(Arena *a, byte *src, uptr start_pos) { byte ints[16]; int i = 0; - while (isdigit(src[pos + i])) { - int val = (src[pos + i] - '0'); + while (isdigit(src[start_pos + i])) { + int val = (src[start_pos + i] - '0'); ints[i] = val; i++; } @@ -31,15 +74,15 @@ parse_integer_result parse_integer(Arena *a, byte *src, uptr pos) { for (int j = 0; j < i; j++) { *result += ints[j] * pow(10, (i - j - 1)); } - return (parse_integer_result){result, pos + i}; + return (parse_integer_result){result, start_pos + i}; } -uptr absorb_whitespaces(byte *src, uptr pos) { - int i = 0; - while (isspace(src[pos + i])) { - i++; +uptr absorb_whitespaces(byte *src, uptr start_pos) { + uptr pos = start_pos; + while (isspace(src[pos])) { + pos++; } - return pos + i; + return pos; } typedef struct { @@ -47,25 +90,29 @@ typedef struct { uptr pos; } parse_array_result; -parse_array_result parse_array(Arena *a, byte *src, uptr pos) { - assert(src[pos] == '['); - pos++; - Vec items = Vec_new(a, JSON, 2); +parse_array_result parse_array(Arena *a, byte *src, uptr start_pos) { + assert(src[start_pos] == '['); + parse_array_result result = {0}; + result.pos = start_pos + 1; + result.items = Vec_new(a, JSON, 2); + if (src[result.pos] == ']') { + result.pos++; + return result; + } for (;;) { - pos = absorb_whitespaces(src, pos); - parse_any_result result = parse_any(a, src, pos); - Vec_push(a, &items, result.value); - pos = result.pos; - pos = absorb_whitespaces(src, pos); - if (src[pos] == ',') { - pos++; + result.pos = absorb_whitespaces(src, result.pos); + parse_any_result any_result = parse_any(a, src, result.pos); + Vec_push(a, result.items, any_result.value); + result.pos = absorb_whitespaces(src, any_result.pos); + if (src[result.pos] == ',') { + result.pos++; } else { break; } }; - assert(src[pos] == ']'); - - return (parse_array_result){&items, pos + 1}; + assert(src[result.pos] == ']'); + result.pos++; + return result; } typedef struct { @@ -73,17 +120,19 @@ typedef struct { uptr pos; } parse_string_result; -parse_string_result parse_string(Arena *a, byte *src, uptr pos) { - assert(src[pos] == '"'); - int i = 1; +parse_string_result parse_string(Arena *a, byte *src, uptr start_pos) { + assert(src[start_pos] == '"'); + parse_string_result result = {.pos = start_pos + 1}; - while (src[pos + i] != '"' && src[pos + i - 1] != '\\') { - i++; + while (src[result.pos] != '"' && src[result.pos - 1] != '\\') { + result.pos++; } - assert(src[pos + i] == '"'); - Str *s = Str_copy(a, &src[pos + 1], i - 1); + assert(src[result.pos] == '"'); + result.string = + Str_copy(a, &src[start_pos + 1], result.pos - start_pos - 1); + result.pos++; - return (parse_string_result){s, pos + i + 1}; + return result; } typedef struct { @@ -91,58 +140,59 @@ typedef struct { uptr pos; } parse_object_result; -parse_object_result parse_object(Arena *a, byte *src, uptr pos) { - assert(src[pos] == '{'); - JSONObject *object = new(a, JSONObject, 1); - object->len = 0; - object->keys = Vec_new(a, Str, 2); - object->values = Vec_new(a, JSON, 2); - pos = absorb_whitespaces(src, pos + 1); - if (src[pos] == '}') { - return (parse_object_result){object, pos + 1}; +parse_object_result parse_object(Arena *a, byte *src, uptr start_pos) { + assert(src[start_pos] == '{'); + parse_object_result result = {.pos = start_pos + 1}; + result.object = JSONObject_new(a); + start_pos = absorb_whitespaces(src, start_pos + 1); + if (src[start_pos] == '}') { + result.pos = start_pos + 1; + return result; } for (;;) { - assert(src[pos] == '"'); - parse_string_result str_result = parse_string(a, src, pos); + assert(src[start_pos] == '"'); + parse_string_result str_result = parse_string(a, src, start_pos); Str *key = str_result.string; - pos = absorb_whitespaces(src, str_result.pos); - assert(src[pos] == ':'); - pos = absorb_whitespaces(src, pos + 1); - parse_any_result any_result = parse_any(a, src, pos); - object->len++; - Vec_push(a, &object->keys, key); - Vec_push(a, &object->values, any_result.value); - pos = absorb_whitespaces(src, any_result.pos); - if (src[pos] != ',') { + start_pos = absorb_whitespaces(src, str_result.pos); + assert(src[start_pos] == ':'); + start_pos = absorb_whitespaces(src, start_pos + 1); + parse_any_result any_result = parse_any(a, src, start_pos); + result.object->len++; + Vec_push(a, &result.object->keys, key); + Vec_push(a, &result.object->values, any_result.value); + start_pos = absorb_whitespaces(src, any_result.pos); + if (src[start_pos] != ',') { break; } - pos = absorb_whitespaces(src, pos + 1); + start_pos = absorb_whitespaces(src, start_pos + 1); } - assert(src[pos] == '}'); - return (parse_object_result){object, pos + 1}; + assert(src[start_pos] == '}'); + result.pos = start_pos + 1; + return result; } -parse_any_result parse_any(Arena *a, byte *src, uptr pos) { - JSON *value = new(a, JSON, 1); - if (isdigit(src[pos])) { - parse_integer_result result = parse_integer(a, src, pos); - value->integer = result.value; - pos = result.pos; - } else if (src[pos] == '[') { - parse_array_result result = parse_array(a, src, pos); - value->array = result.items; - pos = result.pos; - } else if (src[pos] == '"') { - parse_string_result result = parse_string(a, src, pos); - value->string = result.string; - pos = result.pos; - } else if (src[pos] == '{') { - parse_object_result result = parse_object(a, src, pos); - value->object = result.object; - pos = result.pos; +parse_any_result parse_any(Arena *a, byte *src, uptr start_pos) { + parse_any_result result = {.pos = start_pos}; + result.value = new(a, JSON, 1); + if (isdigit(src[result.pos])) { + parse_integer_result int_result = parse_integer(a, src, result.pos); + result.value->integer = int_result.value; + result.pos = int_result.pos; + } else if (src[result.pos] == '[') { + parse_array_result array_result = parse_array(a, src, result.pos); + result.value->array = array_result.items; + result.pos = array_result.pos; + } else if (src[result.pos] == '"') { + parse_string_result string_result = parse_string(a, src, result.pos); + result.value->string = string_result.string; + result.pos = string_result.pos; + } else if (src[result.pos] == '{') { + parse_object_result object_result = parse_object(a, src, result.pos); + result.value->object = object_result.object; + result.pos = object_result.pos; } - return (parse_any_result){value, pos}; + return result; } JSON JSON_parse(Arena *a, byte *src) { diff --git a/json.h b/json.h index 13a3f11..5d5d703 100644 --- a/json.h +++ b/json.h @@ -16,6 +16,7 @@ typedef struct { JSONObject *object; } JSON; JSON *JSONObject_get(JSONObject *obj, Str key); +int JSON_fprint(FILE *w, JSON json); JSON JSON_parse(Arena *a, byte *src); JSON JSON_Int(Arena *a, int val); #endif diff --git a/string.c b/string.c index d174ed4..d788f58 100644 --- a/string.c +++ b/string.c @@ -29,4 +29,6 @@ Str *Str_copy(Arena *a, byte *data, size len) { return str; } -void Str_print(Str s) { printf("%.*s", (int)s.len, s.data); } +int Str_fprint(FILE *w, Str s) { + return fprintf(w, "%.*s", (int)s.len, s.data); +} diff --git a/string.h b/string.h index a984929..2785e99 100644 --- a/string.h +++ b/string.h @@ -1,5 +1,6 @@ #include #include +#include #include "memory.h" #include "types.h" @@ -15,5 +16,5 @@ typedef struct { int Str_equals(Str a, Str b); uint64_t Str_hash64(Str s); Str *Str_copy(Arena *a, byte *data, size len); -void Str_print(Str s); +int Str_fprint(FILE *w, Str s); #endif diff --git a/test_json.c b/test_json.c index 5807524..b268685 100644 --- a/test_json.c +++ b/test_json.c @@ -1,6 +1,5 @@ #include "json.h" #include "testing.h" -#include int test_json_integer() { Arena perm = Arena_new(128e3); @@ -30,7 +29,18 @@ int test_json_int_array() { t_assert(ints[1] == 2); t_assert(ints[2] == 3); t_assert(sum == 6); - t_assert_equal(Arena_get_used(perm), 344); + t_assert_equal(Arena_get_used(perm), 384); + + return 0; +} + +int test_json_empty_array() { + Arena perm = Arena_new(128e3); + + JSON json_empty_array = JSON_parse(&perm, "[]"); + + t_assert(json_empty_array.array->len == 0); + t_assert_equal(Arena_get_used(perm), 136); return 0; } @@ -40,7 +50,7 @@ int test_json_nested_array() { JSON doc = JSON_parse(&perm, "[[1,\"abc\"]]"); - t_assert_equal(Arena_get_used(perm), 283); + t_assert_equal(Arena_get_used(perm), 363); JSON sub_array = *Vec_get(doc.array, JSON, 0); JSON val_1 = *Vec_get(sub_array.array, JSON, 0); t_assert(*val_1.integer == 1); @@ -48,7 +58,7 @@ int test_json_nested_array() { Str str = *val_2.string; Str expected = S("abc"); t_assert(Str_equals(str, expected)); - t_assert_equal(Arena_get_used(perm), 283); + t_assert_equal(Arena_get_used(perm), 363); return 0; } @@ -71,7 +81,7 @@ int test_json_empty_object() { JSON doc = JSON_parse(&perm, "{}"); t_assert_equal(doc.object->len, 0); - t_assert_equal(Arena_get_used(perm), 216); + t_assert_equal(Arena_get_used(perm), 296); return 0; } @@ -81,11 +91,11 @@ int test_json_object() { JSON doc = JSON_parse(&perm, "{\"key\": \"value\"}"); - t_assert_equal(Arena_get_used(perm), 293); + t_assert_equal(Arena_get_used(perm), 373); t_assert_equal(doc.object->len, 1); t_assert(Str_equals(*Vec_get(&doc.object->keys, Str, 0), S("key"))); t_assert(Str_equals(*JSONObject_get(doc.object, S("key"))->string, - S("value"))) t_assert_equal(Arena_get_used(perm), 293); + S("value"))) t_assert_equal(Arena_get_used(perm), 373); return 0; } diff --git a/vec.c b/vec.c index e9df934..f555885 100644 --- a/vec.c +++ b/vec.c @@ -4,10 +4,14 @@ #include "types.h" #include "vec.h" -Vec _Vec_new(Arena *a, size tsize, size cap, int align) { +Vec *_Vec_new(Arena *a, size tsize, size cap, int align) { assert(cap > 0); - Vec v = {.size = tsize, .cap = cap, .len = 0, .align = align, .data = 0}; - v.data = alloc(a, cap, tsize, align); + Vec *v = new(a, Vec, 1); + v->size = tsize; + v->cap = cap; + v->align = align; + v->len = 0; + v->data = alloc(a, cap, tsize, align); return v; } diff --git a/vec.h b/vec.h index a9b4f92..c94b29e 100644 --- a/vec.h +++ b/vec.h @@ -14,7 +14,7 @@ typedef struct { int align; } Vec; #define Vec_new(a, T, cap) _Vec_new(a, sizeof(T), cap, _Alignof(T)) -Vec _Vec_new(Arena *a, size tsize, size cap, int align); +Vec *_Vec_new(Arena *a, size tsize, size cap, int align); void Vec_push(Arena *a, Vec *v, void *data); #define Vec_get(v, T, p) (T *)_Vec_get(v, p) void *_Vec_get(Vec *v, int pos); -- cgit v1.3