aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore2
-rwxr-xr-xbuild.sh8
-rw-r--r--include/binop_type.h2
-rw-r--r--include/std/buffer.h3
-rw-r--r--include/std/defs.h3
-rw-r--r--include/std/hash.h8
-rw-r--r--include/std/hash_map.h38
-rw-r--r--include/std/mem.h1
-rw-r--r--include/std/scoped_allocator.h4
-rw-r--r--include/std/thread.h1
-rw-r--r--src/ast.c30
-rw-r--r--src/compiler.c1
-rw-r--r--src/main.c27
-rw-r--r--src/std/buffer.c7
-rw-r--r--src/std/hash.c14
-rw-r--r--src/std/hash_map.c191
-rw-r--r--src/std/mem.c6
-rw-r--r--src/std/thread.c4
-rw-r--r--src/tokenizer.c2
-rw-r--r--tests/main.c61
20 files changed, 372 insertions, 41 deletions
diff --git a/.gitignore b/.gitignore
index c551744..06e9210 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,5 @@
.vscode/
.gdb_history
amalgam
+test
+libamalgam.so
diff --git a/build.sh b/build.sh
index b3dfc9f..5ca2ea6 100755
--- a/build.sh
+++ b/build.sh
@@ -21,4 +21,10 @@ CFLAGS+="-Wall -Wextra -Werror -g -O0 -DDEBUG -std=c89 -pedantic -D_GNU_SOURCE"
LIBS+="-pthread"
set -x
-time "$CC" $source_files $CFLAGS $LIBS -o amalgam
+time "$CC" $source_files $CFLAGS $LIBS -shared -fpic -o libamalgam.so
+set +x
+if [ -z "$NO_TEST" ]; then
+ source_files_tests=$(readlink -f $(find "$this_script_dir/tests" -name "*.c"))
+ set -x
+ time "$CC" $source_files_tests $CFLAGS $LIBS -o test "$this_script_dir/libamalgam.so"
+fi \ No newline at end of file
diff --git a/include/binop_type.h b/include/binop_type.h
index d04f9d7..e747102 100644
--- a/include/binop_type.h
+++ b/include/binop_type.h
@@ -9,4 +9,4 @@ typedef enum {
BINOP_DOT
} BinopType;
-#endif \ No newline at end of file
+#endif
diff --git a/include/std/buffer.h b/include/std/buffer.h
index a60def9..688f18a 100644
--- a/include/std/buffer.h
+++ b/include/std/buffer.h
@@ -16,7 +16,8 @@ typedef struct {
struct ScopedAllocator;
CHECK_RESULT int buffer_init(Buffer *self, struct ScopedAllocator *allocator);
-CHECK_RESULT int buffer_append(Buffer *self, void *data, usize size);
+/* @data can be NULL */
+CHECK_RESULT int buffer_append(Buffer *self, const void *data, usize size);
void* buffer_get(Buffer *self, usize index, usize type_size);
CHECK_RESULT int buffer_pop(Buffer *self, void *data, usize size);
void* buffer_start(Buffer *self);
diff --git a/include/std/defs.h b/include/std/defs.h
index 653bf73..ee049d4 100644
--- a/include/std/defs.h
+++ b/include/std/defs.h
@@ -4,4 +4,7 @@
typedef struct amal_thread amal_thread;
typedef struct amal_mutex amal_mutex;
+typedef struct ScopedAllocatorNode ScopedAllocatorNode;
+typedef struct ScopedAllocator ScopedAllocator;
+
#endif
diff --git a/include/std/hash.h b/include/std/hash.h
new file mode 100644
index 0000000..f7a807d
--- /dev/null
+++ b/include/std/hash.h
@@ -0,0 +1,8 @@
+#ifndef AMALGAM_HASH_H
+#define AMALGAM_HASH_H
+
+#include "types.h"
+
+usize amal_hash_string(const u8 *data, usize size);
+
+#endif
diff --git a/include/std/hash_map.h b/include/std/hash_map.h
new file mode 100644
index 0000000..c36ecc4
--- /dev/null
+++ b/include/std/hash_map.h
@@ -0,0 +1,38 @@
+#ifndef AMALGAM_HASH_MAP_H
+#define AMALGAM_HASH_MAP_H
+
+#include "defs.h"
+#include "misc.h"
+#include "types.h"
+#include "buffer.h"
+#include "buffer_view.h"
+
+typedef struct HashMap HashMap;
+
+typedef int(*HashMapCompare)(const void *a, const void *b);
+typedef usize(*HashMapHash)(const u8 *data, usize size);
+
+struct HashMap {
+ ScopedAllocator *allocator; /* borrowed */
+ Buffer/*HashMapBucket*/ buckets;
+ usize type_size;
+ usize num_elements;
+ HashMapCompare compare_func;
+ HashMapHash hash_func;
+};
+
+CHECK_RESULT int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size, HashMapCompare compare_func, HashMapHash hash_func);
+/*
+Not thread-safe.
+Expected @value size to be @self->type_size.
+*/
+CHECK_RESULT int hash_map_insert(HashMap *self, BufferView key, void *value);
+/*
+Thread-safe unless @hash_map_insert is used in another thread at the same time.
+Expected @value size to be @self->type_size.
+*/
+CHECK_RESULT bool hash_map_get(HashMap *self, BufferView key, void *value);
+
+int hash_compare_string(const void *a, const void *b);
+
+#endif
diff --git a/include/std/mem.h b/include/std/mem.h
index 8d91a5a..ddd2b31 100644
--- a/include/std/mem.h
+++ b/include/std/mem.h
@@ -5,6 +5,7 @@
#include "misc.h"
void am_memcpy(void *dest, const void *src, usize size);
+int am_memcmp(const void *lhs, const void *rhs, usize size);
bool am_memeql(const void *lhs, const void *rhs, usize size);
void am_memset(void *dest, int value, usize size);
diff --git a/include/std/scoped_allocator.h b/include/std/scoped_allocator.h
index ad6e2dd..0de4f04 100644
--- a/include/std/scoped_allocator.h
+++ b/include/std/scoped_allocator.h
@@ -1,13 +1,11 @@
#ifndef AMALGAM_SCOPED_ALLOCATOR_H
#define AMALGAM_SCOPED_ALLOCATOR_H
+#include "defs.h"
#include "misc.h"
#include "types.h"
#include "buffer.h"
-typedef struct ScopedAllocatorNode ScopedAllocatorNode;
-typedef struct ScopedAllocator ScopedAllocator;
-
struct ScopedAllocatorNode {
char *data;
usize size;
diff --git a/include/std/thread.h b/include/std/thread.h
index 972ce3a..915d6a9 100644
--- a/include/std/thread.h
+++ b/include/std/thread.h
@@ -38,6 +38,7 @@ CHECK_RESULT int amal_thread_detach(amal_thread *self);
CHECK_RESULT int amal_thread_join(amal_thread *self, void **result);
void amal_mutex_init(amal_mutex *self);
+void amal_mutex_deinit(amal_mutex *self);
CHECK_RESULT int amal_mutex_lock(amal_mutex *self, const char *lock_identifier);
CHECK_RESULT int amal_mutex_unlock(amal_mutex *self);
void amal_mutex_tryunlock(amal_mutex *self);
diff --git a/src/ast.c b/src/ast.c
index 1db114a..c28b314 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -1,4 +1,8 @@
#include "../include/ast.h"
+#include "../include/std/log.h"
+#include <assert.h>
+
+static void ast_resolve(Ast *self);
Ast ast_none() {
Ast ast;
@@ -51,6 +55,26 @@ int scope_init(Scope *self, ScopedAllocator *allocator) {
}
void scope_resolve(Scope *self) {
- /* TODO: Implement. Also use longjmp to jump back to compiler on error */
- (void)self;
-} \ No newline at end of file
+ Ast *ast;
+ Ast *ast_end;
+ ast = buffer_start(&self->ast_objects);
+ ast_end = buffer_end(&self->ast_objects);
+ for(; ast != ast_end; ++ast) {
+ ast_resolve(ast);
+ }
+}
+
+static void lhs_resolve(LhsExpr *self) {
+ amal_log_debug("Lhs resolve var name: %.*s", self->var_name.size, self->var_name.data);
+}
+
+void ast_resolve(Ast *self) {
+ switch(self->type) {
+ case AST_LHS:
+ lhs_resolve(self->value.lhs_expr);
+ break;
+ default:
+ assert(bool_false && "ast_resolve not implemented for type");
+ break;
+ }
+}
diff --git a/src/compiler.c b/src/compiler.c
index e44ba6a..bcb36c3 100644
--- a/src/compiler.c
+++ b/src/compiler.c
@@ -70,6 +70,7 @@ int amal_compiler_deinit(amal_compiler *self) {
result = r;
}
+ amal_mutex_deinit(&self->mutex);
scoped_allocator_deinit(&self->allocator);
scoped_allocator_deinit(&self->main_thread_allocator);
return result;
diff --git a/src/main.c b/src/main.c
deleted file mode 100644
index c016892..0000000
--- a/src/main.c
+++ /dev/null
@@ -1,27 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include "../include/compiler.h"
-
-int main() {
- amal_compiler compiler;
- int result;
- const char *filepath;
- filepath = "tests/main.amal";
-
- result = amal_compiler_init(&compiler);
- if(result != AMAL_COMPILER_OK) {
- fprintf(stderr, "Failed to initialize compiler, error code: %d\n", result);
- return 1;
- }
-
- result = amal_compiler_load_file(&compiler, create_buffer_view(filepath, strlen(filepath)));
- if(result != AMAL_COMPILER_OK) {
- fprintf(stderr, "Failed to load file, error code: %d\n", result);
- return 1;
- }
-
-#ifdef DEBUG
- return amal_compiler_deinit(&compiler);
-#endif
- return 0;
-}
diff --git a/src/std/buffer.c b/src/std/buffer.c
index 1fdcfd4..e631153 100644
--- a/src/std/buffer.c
+++ b/src/std/buffer.c
@@ -39,9 +39,10 @@ static CHECK_RESULT int buffer_ensure_capacity(Buffer *self, usize new_capacity)
return BUFFER_OK;
}
-int buffer_append(Buffer *self, void *data, usize size) {
+int buffer_append(Buffer *self, const void *data, usize size) {
return_if_error(buffer_ensure_capacity(self, self->size + size));
- am_memcpy(self->data + self->size, data, size);
+ if(data)
+ am_memcpy(self->data + self->size, data, size);
self->size += size;
return BUFFER_OK;
}
@@ -72,4 +73,4 @@ void *buffer_end(Buffer *self) {
usize __buffer_get_size(Buffer *self, usize type_size) {
assert(type_size != 0);
return self->size / type_size;
-} \ No newline at end of file
+}
diff --git a/src/std/hash.c b/src/std/hash.c
new file mode 100644
index 0000000..603149a
--- /dev/null
+++ b/src/std/hash.c
@@ -0,0 +1,14 @@
+#include "../../include/std/hash.h"
+
+usize amal_hash_string(const u8 *data, usize size) {
+ usize result;
+ result = 0xdec05eba;
+
+ while(size) {
+ result ^= *data;
+ ++data;
+ --size;
+ }
+
+ return result;
+}
diff --git a/src/std/hash_map.c b/src/std/hash_map.c
new file mode 100644
index 0000000..1ffca90
--- /dev/null
+++ b/src/std/hash_map.c
@@ -0,0 +1,191 @@
+#include "../../include/std/hash_map.h"
+#include "../../include/std/scoped_allocator.h"
+#include "../../include/std/mem.h"
+#include <assert.h>
+
+/*
+Basic hash map implementation. TODO: Improve performance
+*/
+
+#define HASH_MAP_INITIAL_SIZE 16
+
+typedef struct HashMapBucketNode HashMapBucketNode;
+
+typedef struct {
+ HashMapBucketNode *start;
+} HashMapBucket;
+
+static void bucket_node_set_next(HashMapBucketNode *self, HashMapBucketNode *next) {
+ am_memcpy(self, &next, sizeof(next));
+}
+
+static HashMapBucketNode* bucket_node_get_next(HashMapBucketNode *self) {
+ HashMapBucketNode *next;
+ am_memcpy(&next, self, sizeof(HashMapBucketNode*));
+ return next;
+}
+
+static void bucket_node_set_key(HashMapBucketNode *self, BufferView key) {
+ u32 key_size;
+ key_size = (u32)key.size;
+ am_memcpy((char*)self + sizeof(HashMapBucketNode*), &key_size, sizeof(u32));
+ am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(u32), key.data, key_size);
+}
+
+static BufferView bucket_node_get_key(HashMapBucketNode *self) {
+ BufferView key;
+ u32 key_size;
+ am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(u32));
+ key.size = key_size;
+ key.data = (char*)self + sizeof(HashMapBucketNode*) + sizeof(u32);
+ return key;
+}
+
+static void bucket_node_set_value(HashMapBucketNode *self, void *value, usize type_size) {
+ u32 key_size;
+ am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(key_size));
+ am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(u32) + key_size, value, type_size);
+}
+
+static void* bucket_node_get_value(HashMapBucketNode *self) {
+ u32 key_size;
+ void *value;
+ am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(key_size));
+ value = (char*)self + sizeof(HashMapBucketNode*) + sizeof(u32) + key_size;
+ return value;
+}
+
+int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size,
+ HashMapCompare compare_func, HashMapHash hash_func) {
+ assert(compare_func);
+ assert(hash_func);
+ self->allocator = allocator;
+ self->type_size = type_size;
+ self->num_elements = 0;
+ self->compare_func = compare_func;
+ self->hash_func = hash_func;
+ return_if_error(buffer_init(&self->buckets, self->allocator));
+ assert(self->buckets.size == 0);
+ return_if_error(buffer_append(&self->buckets, NULL, sizeof(HashMapBucket) * HASH_MAP_INITIAL_SIZE));
+ am_memset(self->buckets.data, 0, self->buckets.size);
+ return 0;
+}
+
+static CHECK_RESULT int hash_map_bucket_add(HashMap *self, HashMapBucket *bucket, BufferView key, void *value) {
+ HashMapBucketNode *new_bucket_node;
+ return_if_error(scoped_allocator_alloc(self->allocator,
+ sizeof(HashMapBucketNode*) + sizeof(u32) + key.size + self->type_size,
+ (void**)&new_bucket_node));
+ bucket_node_set_next(new_bucket_node, bucket->start);
+ bucket_node_set_key(new_bucket_node, key);
+ bucket_node_set_value(new_bucket_node, value, self->type_size);
+ bucket->start = new_bucket_node;
+ return 0;
+}
+
+static void hash_map_reorder_buckets(HashMap *self, usize end_index) {
+ HashMapBucket *bucket;
+ HashMapBucket *bucket_end;
+ usize bucket_size;
+ usize index;
+
+ bucket = (HashMapBucket*)self->buckets.data;
+ bucket_end = ((HashMapBucket*)self->buckets.data) + end_index;
+ bucket_size = buffer_get_size(&self->buckets, HashMapBucket);
+ index = 0;
+
+ for(; bucket != bucket_end; ++bucket, ++index) {
+ HashMapBucketNode *prev_bucket_node;
+ HashMapBucketNode *bucket_node;
+ prev_bucket_node = NULL;
+ for(bucket_node = bucket->start; bucket_node; bucket_node_get_next(bucket_node)) {
+ BufferView bucket_key;
+ usize bucket_index;
+
+ /* Node between current and previous has been removed, chain previous and current */
+ if(prev_bucket_node && !bucket_node_get_next(prev_bucket_node))
+ bucket_node_set_next(prev_bucket_node, bucket_node);
+
+ bucket_key = bucket_node_get_key(bucket_node);
+ bucket_index = self->hash_func((const u8*)bucket_key.data, bucket_key.size) % bucket_size;
+ if(bucket_index != index) {
+ /* Add node to new bucket */
+ HashMapBucket *new_bucket;
+ new_bucket = ((HashMapBucket*)self->buckets.data) + bucket_index;
+ bucket_node_set_next(bucket_node, new_bucket->start);
+ new_bucket->start = bucket_node;
+ /* Mark bucket node to be removed from previous bucket */
+ bucket_node_set_next(prev_bucket_node, NULL);
+ } else {
+ prev_bucket_node = bucket_node;
+ }
+ }
+ }
+}
+
+static CHECK_RESULT int hash_map_increase_buckets(HashMap *self) {
+ usize prev_size;
+ usize bytes_to_append;
+ prev_size = buffer_get_size(&self->buckets, HashMapBucket);
+ bytes_to_append = prev_size * 1.5;
+ return_if_error(buffer_append(&self->buckets, NULL, bytes_to_append));
+ am_memset(self->buckets.data + prev_size, 0, prev_size + bytes_to_append);
+ hash_map_reorder_buckets(self, prev_size);
+ return 0;
+}
+
+int hash_map_insert(HashMap *self, BufferView key, void *value) {
+ usize bucket_index;
+ usize bucket_size;
+ HashMapBucket *bucket;
+
+ bucket_size = buffer_get_size(&self->buckets, HashMapBucket);
+ if(self->num_elements == bucket_size) {
+ return_if_error(hash_map_increase_buckets(self));
+ bucket_size = buffer_get_size(&self->buckets, HashMapBucket);
+ }
+
+ bucket_index = self->hash_func((const u8*)key.data, key.size) % bucket_size;
+ bucket = ((HashMapBucket*)self->buckets.data) + bucket_index;
+ return_if_error(hash_map_bucket_add(self, bucket, key, value));
+ ++self->num_elements;
+ return 0;
+}
+
+bool hash_map_get(HashMap *self, BufferView key, void *value) {
+ usize bucket_size;
+ usize bucket_index;
+ HashMapBucket *bucket;
+ HashMapBucketNode *bucket_node;
+
+ bucket_size = buffer_get_size(&self->buckets, HashMapBucket);
+ bucket_index = self->hash_func((const u8*)key.data, key.size) % bucket_size;
+
+ bucket = ((HashMapBucket*)self->buckets.data) + bucket_index;
+ for(bucket_node = bucket->start; bucket_node; bucket_node_get_next(bucket_node)) {
+ BufferView bucket_key;
+ bucket_key = bucket_node_get_key(bucket_node);
+ bucket_index = self->hash_func((const u8*)bucket_key.data, bucket_key.size) % bucket_size;
+ bucket_index %= bucket_size;
+ if(self->compare_func(value, bucket_node_get_value(bucket_node)) == 0)
+ return bool_true;
+ }
+
+ return bool_false;
+}
+
+#define MIN(a, b) ((a) < (b) ? (a) : (b))
+
+int hash_compare_string(const void *a, const void *b) {
+ const BufferView *lhs;
+ const BufferView *rhs;
+ int mem_diff;
+
+ lhs = a;
+ rhs = b;
+ mem_diff = am_memcmp(lhs->data, rhs->data, MIN(lhs->size, rhs->size));
+ if(mem_diff == 0)
+ return (int)lhs->size - (int)rhs->size;
+ else
+ return mem_diff;
+}
diff --git a/src/std/mem.c b/src/std/mem.c
index ec7520c..f406176 100644
--- a/src/std/mem.c
+++ b/src/std/mem.c
@@ -5,8 +5,12 @@ void am_memcpy(void *dest, const void *src, usize size) {
memcpy(dest, src, size);
}
+int am_memcmp(const void *lhs, const void *rhs, usize size) {
+ return memcmp(lhs, rhs, size);
+}
+
bool am_memeql(const void *lhs, const void *rhs, usize size) {
- return memcmp(lhs, rhs, size) == 0;
+ return am_memcmp(lhs, rhs, size) == 0;
}
void am_memset(void *dest, int value, usize size) {
diff --git a/src/std/thread.c b/src/std/thread.c
index c8dba9a..64a7f1b 100644
--- a/src/std/thread.c
+++ b/src/std/thread.c
@@ -89,6 +89,10 @@ void amal_mutex_init(amal_mutex *self) {
self->lock_identifier = NULL;
}
+void amal_mutex_deinit(amal_mutex *self) {
+ pthread_mutex_destroy(&self->mutex);
+}
+
static long amal_process_get_id() {
return getpid();
}
diff --git a/src/tokenizer.c b/src/tokenizer.c
index 152aec4..04e9d27 100644
--- a/src/tokenizer.c
+++ b/src/tokenizer.c
@@ -558,4 +558,4 @@ TokenizerError tokenizer_create_error(Tokenizer *tokenizer, const char *err_str)
result.index = tokenizer->prev_index;
result.str = err_str;
return result;
-} \ No newline at end of file
+}
diff --git a/tests/main.c b/tests/main.c
new file mode 100644
index 0000000..881866e
--- /dev/null
+++ b/tests/main.c
@@ -0,0 +1,61 @@
+#include <stdio.h>
+#include <string.h>
+#include "../include/compiler.h"
+#include "../include/std/hash_map.h"
+#include "../include/std/hash.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+#define REQUIRE_EQ_INT(expected, actual) do{\
+ if((expected) != (actual)) {\
+ fprintf(stderr, "%s:%d: Assert failed (%s vs %s).\nExpected %d, got %d.\n", __FILE__, __LINE__, #expected, #actual, (expected), (actual));\
+ exit(1);\
+ }\
+}while(0)
+
+static CHECK_RESULT int test_hash_map() {
+ ScopedAllocator scoped_allocator;
+ HashMap hash_map;
+ int value;
+ bool has_key;
+
+ return_if_error(scoped_allocator_init(&scoped_allocator));
+ cleanup_if_error(hash_map_init(&hash_map, &scoped_allocator, sizeof(int), hash_compare_string, amal_hash_string));
+
+ value = 34;
+ return_if_error(hash_map_insert(&hash_map, create_buffer_view("hello", 5), &value));
+ return_if_error(hash_map_insert(&hash_map, create_buffer_view("hellp", 5), &value));
+ has_key = hash_map_get(&hash_map, create_buffer_view("hello", 5), &value);
+ if(!has_key) {
+ fprintf(stderr, "Missing value for key \"hello\" in hash map\n");
+ exit(1);
+ }
+ REQUIRE_EQ_INT(34, value);
+
+ cleanup:
+ scoped_allocator_deinit(&scoped_allocator);
+ return 0;
+}
+
+int main() {
+ amal_compiler compiler;
+ int result;
+ const char *filepath;
+ filepath = "tests/main.amal";
+
+ return_if_error(test_hash_map());
+
+ result = amal_compiler_init(&compiler);
+ if(result != AMAL_COMPILER_OK) {
+ fprintf(stderr, "Failed to initialize compiler, error code: %d\n", result);
+ return 1;
+ }
+
+ result = amal_compiler_load_file(&compiler, create_buffer_view(filepath, strlen(filepath)));
+ if(result != AMAL_COMPILER_OK) {
+ fprintf(stderr, "Failed to load file, error code: %d\n", result);
+ return 1;
+ }
+
+ return amal_compiler_deinit(&compiler);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 14:03:11 +0000