diff options
| -rw-r--r-- | alisp.h | 56 | ||||
| -rw-r--r-- | build.sh | 2 | ||||
| -rw-r--r-- | constructor.c | 4 | ||||
| -rw-r--r-- | ivec.c | 76 | ||||
| -rw-r--r-- | symtable.c | 28 | ||||
| -rw-r--r-- | tag.c | 6 | ||||
| -rw-r--r-- | vec.c | 51 |
7 files changed, 92 insertions, 131 deletions
@@ -15,6 +15,9 @@ #ifndef ALISP_H #define ALISP_H +#include <assert.h> +#include <stdalign.h> +#include <stddef.h> #include <stdint.h> /// The bare fucking minimum @@ -46,53 +49,46 @@ typedef struct sv_t sv_copy(sv_t); -/// Good ol' Dynamic Arrays +/// Dynamic arrays + +#define VEC_INLINE_CAPACITY 32 +#define VEC_MULT 2 + typedef struct Vector { u64 size, capacity; - void *data; + u8 is_inlined; + union + { + void *ptr; + alignas(max_align_t) u8 inlined[VEC_INLINE_CAPACITY]; + }; } vec_t; -#define VEC_MULT 2 -#define VEC_DEFAULT_CAPACITY 8 +static_assert(sizeof(vec_t) == 64, "vec_t has to be 64 bytes"); +#define VEC_GET(V, T) ((T *)vec_data(V)) + +void vec_init(vec_t *, u64); void vec_free(vec_t *); +void *vec_data(vec_t *); void vec_ensure_free(vec_t *, u64); void vec_append(vec_t *, void *, u64); void vec_clone(vec_t *, vec_t *); -/// Inlined Dynamic arrays -typedef struct InlineVector -{ - u64 size, capacity; - u8 bytes[]; -} ivec_t; - -#define IVEC_GET(P) (((ivec_t *)(P)) - 1) -#define IVEC_SIZE(P) (IVEC_GET(P)->size) -#define IVEC_CAP(P) (IVEC_GET(P)->capacity) -#define IVEC_MULT 2 - -void ivec_make(void **, u64); -void ivec_free(void **); -void ivec_ensure_free(void **, u64); -void ivec_append_byte(void **, u8); -void ivec_append(void **, void *, u64); -void ivec_clone(void **, void **); - /// Symbol table typedef struct { - u64 count; // How many strings? - u64 capacity; // How many entry buckets? - sv_t *entries; // this is actually a vector on the inside lol + u64 count; // How many strings? + u64 capacity; // How many entry buckets? + vec_t entries; } sym_table_t; -#define SYM_TABLE_INIT_SIZE 1024 +#define SYM_TABLE_INIT_SIZE (1 << 10) u64 djb2(sv_t string); void sym_table_init(sym_table_t *); -sv_t *sym_table_find(sym_table_t *, sv_t); +char *sym_table_find(sym_table_t *, sv_t); void sym_table_cleanup(sym_table_t *); /// Basic defintions for a Lisp @@ -123,7 +119,7 @@ lisp_t *intern(sys_t *, sv_t); lisp_t *cons(sys_t *, lisp_t *, lisp_t *); i64 as_int(lisp_t *); -sv_t *as_sym(lisp_t *); +char *as_sym(lisp_t *); cons_t *as_cons(lisp_t *); vec_t *as_vec(lisp_t *); @@ -168,7 +164,7 @@ enum Mask tag_t get_tag(lisp_t *); lisp_t *tag_int(i64); -lisp_t *tag_sym(sv_t *); +lisp_t *tag_sym(char *); lisp_t *tag_cons(cons_t *); lisp_t *tag_vec(vec_t *); @@ -1,7 +1,7 @@ #!/usr/bin/env sh CFLAGS="-Wall -Wextra -std=c11 -ggdb -fsanitize=address -fsanitize=undefined" -SRC="vec.c ivec.c symtable.c tag.c constructor.c sys.c main.c" +SRC="vec.c symtable.c tag.c constructor.c sys.c main.c" OUT="alisp.out" set -xe diff --git a/constructor.c b/constructor.c index 910ed2a..9db0330 100644 --- a/constructor.c +++ b/constructor.c @@ -35,7 +35,7 @@ lisp_t *cons(sys_t *sys, lisp_t *car, lisp_t *cdr) lisp_t *make_vec(sys_t *sys, u64 capacity) { vec_t *vec = calloc(1, sizeof(*vec)); - vec_ensure_free(vec, MAX(capacity, VEC_DEFAULT_CAPACITY)); + vec_init(vec, capacity); lisp_t *ptr = tag_vec(vec); sys_register(sys, ptr); return ptr; @@ -43,6 +43,6 @@ lisp_t *make_vec(sys_t *sys, u64 capacity) lisp_t *intern(sys_t *sys, sv_t sv) { - sv_t *str = sym_table_find(&sys->symtable, sv); + char *str = sym_table_find(&sys->symtable, sv); return tag_sym(str); } @@ -1,76 +0,0 @@ -/* Copyright (C) 2025 Aryadev Chavali - - * This program is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS - * FOR A PARTICULAR PURPOSE. See the Unlicense for details. - - * You may distribute and modify this code under the terms of the Unlicense, - * which you should have received a copy of along with this program. If not, - * please go to <https://unlicense.org/>. - - * Created: 2025-08-19 - * Description: Inline Vector implementation - */ - -#include <malloc.h> -#include <string.h> - -#include "./alisp.h" - -void ivec_make(void **ptr, u64 size) -{ - if (!ptr) - return; - ivec_t *ivector = calloc(1, sizeof(*ivector) + size); - ivector->size = 0; - ivector->capacity = size; - *ptr = (ivector + 1); -} - -void ivec_free(void **data) -{ - if (!data || !*data) - return; - free(IVEC_GET(*data)); - *data = NULL; -} - -void ivec_ensure_free(void **ptr, u64 space) -{ - if (!ptr || !*ptr) - return; - ivec_t *ivec = IVEC_GET(*ptr); - if (ivec->capacity - ivec->size < space) - { - void *new_ivec = NULL; - ivec_make(&new_ivec, MAX(ivec->capacity * IVEC_MULT, ivec->size + space)); - IVEC_SIZE(new_ivec) = ivec->size; - memcpy(new_ivec, *ptr, ivec->size); - ivec_free(ptr); - *ptr = new_ivec; - } -} - -void ivec_append_byte(void **ptr, u8 byte) -{ - ivec_ensure_free(ptr, 1); - ivec_t *ivec = IVEC_GET(*ptr); - ivec->bytes[ivec->size++] = byte; -} - -void ivec_append(void **ptr, void *data, u64 size) -{ - ivec_ensure_free(ptr, size); - ivec_t *ivec = IVEC_GET(*ptr); - memcpy(*ptr + ivec->size, data, size); - ivec->size += size; -} - -void ivec_clone(void **dest, void **src) -{ - if (!dest || !src || !*src) - return; - ivec_make(dest, IVEC_SIZE(*src)); - memcpy(*dest, *src, IVEC_SIZE(*src)); - IVEC_SIZE(*dest) = IVEC_SIZE(*src); -} @@ -29,39 +29,43 @@ void sym_table_init(sym_table_t *table) { table->capacity = MAX(table->capacity, SYM_TABLE_INIT_SIZE); table->count = 0; - ivec_make((void **)&table->entries, - table->capacity * sizeof(*table->entries)); + vec_init(&table->entries, table->capacity * sizeof(sv_t)); } -sv_t *sym_table_find(sym_table_t *table, sv_t sv) +char *sym_table_find(sym_table_t *table, sv_t sv) { // WIP: Deal with resizing this when table->count > table->size / 2 u64 index = djb2(sv) & (table->capacity - 1); - for (sv_t comp = table->entries[index]; comp.data; index += 1, - index = index & (table->capacity - 1), comp = table->entries[index]) + for (sv_t comp = VEC_GET(&table->entries, sv_t)[index]; comp.data; index += 1, + index = index & (table->capacity - 1), + comp = VEC_GET(&table->entries, sv_t)[index]) // Is it present in the table? if (sv.size == comp.size && strncmp(sv.data, comp.data, sv.size) == 0) break; // we couldn't find it in our linear search (worst case scenario) - if (!table->entries[index].data) + if (!VEC_GET(&table->entries, sv_t)[index].data) { - sv_t newsv = sv_copy(sv); - table->entries[index] = newsv; + sv_t newsv = sv_copy(sv); + VEC_GET(&table->entries, sv_t)[index] = newsv; ++table->count; } - return table->entries + index; + return VEC_GET(&table->entries, sv_t)[index].data; } void sym_table_cleanup(sym_table_t *table) { // kill the data + sv_t current = {0}; for (u64 i = 0; i < table->capacity; ++i) - if (table->entries[i].data) - free(table->entries[i].data); + { + current = VEC_GET(&table->entries, sv_t)[i]; + if (current.data) + free(current.data); + } // kill the container - ivec_free((void **)&table->entries); + vec_free(&table->entries); memset(table, 0, sizeof(*table)); } @@ -22,7 +22,7 @@ lisp_t *tag_int(i64 i) return TAG((u64)i, INT); } -lisp_t *tag_sym(sv_t *str) +lisp_t *tag_sym(char *str) { return TAG((u64)str, SYM); } @@ -57,10 +57,10 @@ i64 as_int(lisp_t *obj) ; } -sv_t *as_sym(lisp_t *obj) +char *as_sym(lisp_t *obj) { assert(IS_TAG(obj, SYM)); - return (sv_t *)UNTAG(obj, SYM); + return (char *)UNTAG(obj, SYM); } cons_t *as_cons(lisp_t *obj) @@ -18,15 +18,39 @@ #include "./alisp.h" +void vec_init(vec_t *vec, u64 size) +{ + memset(vec, 0, sizeof(*vec)); + if (!vec) + return; + else if (size <= VEC_INLINE_CAPACITY) + { + vec->is_inlined = 1; + vec->capacity = VEC_INLINE_CAPACITY; + vec->ptr = NULL; + } + else + { + vec->is_inlined = 0; + vec->capacity = size; + vec->ptr = calloc(1, vec->capacity); + } +} + void vec_free(vec_t *vec) { if (!vec) return; - if (vec->data) - free(vec->data); + if (!vec->is_inlined && vec->ptr) + free(vec->ptr); memset(vec, 0, sizeof(*vec)); } +void *vec_data(vec_t *vec) +{ + return vec->is_inlined ? vec->inlined : vec->ptr; +} + void vec_ensure_free(vec_t *vec, u64 size) { if (!vec) @@ -34,7 +58,21 @@ void vec_ensure_free(vec_t *vec, u64 size) if (vec->capacity - vec->size < size) { vec->capacity = MAX(vec->capacity * VEC_MULT, vec->size + size); - vec->data = realloc(vec->data, vec->capacity); + if (vec->is_inlined) + { + // If we're inlined, we need to allocate on the heap now. So let's copy + // vec->inlined over to vec->ptr, then turn off inlining. + + // We need to do a two-way swap since vec->ptr and vec->inlined are taking + // up the same space. + u8 buffer[VEC_INLINE_CAPACITY]; + memcpy(buffer, vec->inlined, vec->size); + vec->ptr = calloc(1, vec->capacity); + memcpy(vec->ptr, buffer, vec->size); + vec->is_inlined = 0; + } + else + vec->ptr = realloc(vec->ptr, vec->capacity); } } @@ -43,7 +81,7 @@ void vec_append(vec_t *vec, void *ptr, u64 size) if (!vec) return; vec_ensure_free(vec, size); - memcpy(vec->data + vec->size, ptr, size); + memcpy(vec_data(vec) + vec->size, ptr, size); vec->size += size; } @@ -51,7 +89,6 @@ void vec_clone(vec_t *dest, vec_t *src) { if (!src || !dest) return; - dest = src; - dest->data = calloc(1, dest->capacity); - memcpy(dest->data, src->data, src->size); + vec_init(dest, src->capacity); + memcpy(vec_data(dest), vec_data(src), src->size); } |