summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/format.h13
-rw-r--r--lib/hashtable.c109
-rw-r--r--lib/hashtable.d2
-rw-r--r--lib/hashtable.h34
-rw-r--r--lib/jove.h15
-rw-r--r--lib/kpanic.c15
-rw-r--r--lib/kpanic.d1
-rw-r--r--lib/linkedlist.c34
-rw-r--r--lib/linkedlist.d1
-rw-r--r--lib/linkedlist.h26
-rw-r--r--lib/ltostr.c26
-rw-r--r--lib/ltostr.d1
-rw-r--r--lib/mem.c52
-rw-r--r--lib/mem.d1
-rw-r--r--lib/sfmt.c112
-rw-r--r--lib/sfmt.d1
-rw-r--r--lib/string.c16
-rw-r--r--lib/string.d1
-rw-r--r--lib/string.h18
-rw-r--r--lib/toupper.c26
-rw-r--r--lib/toupper.d1
21 files changed, 505 insertions, 0 deletions
diff --git a/lib/format.h b/lib/format.h
new file mode 100644
index 0000000..5a2b75c
--- /dev/null
+++ b/lib/format.h
@@ -0,0 +1,13 @@
+#ifndef JOVE_LIB_FORMAT_H
+#define JOVE_LIB_FORMAT_H 1
+
+#include <stddef.h>
+#include <stdbool.h>
+
+size_t ltostr(char *s, size_t limit, unsigned long l, bool sgn, int radix);
+
+char *sfmt(char *s, size_t limit, const char *fmt, ...);
+#include <stdarg.h>
+char *svfmt(char *s, size_t limit, const char *fmt, va_list ap);
+
+#endif
diff --git a/lib/hashtable.c b/lib/hashtable.c
new file mode 100644
index 0000000..17f1e74
--- /dev/null
+++ b/lib/hashtable.c
@@ -0,0 +1,109 @@
+#include "hashtable.h"
+#include "string.h"
+#include "mem/memory.h"
+
+static size_t
+s_hash_function_mul(const void *data, size_t len)
+{
+ size_t hash = 1;
+ const char *cdata = (const char*)data;
+ for(size_t i = 0; i < len; i++) {
+ hash *= ((size_t)cdata[i]) + 1;
+ }
+ return hash;
+}
+
+static size_t
+s_hash_function_mul_s(const void *data, size_t _)
+{
+ return s_hash_function_mul(data, strlen(data));
+}
+
+void
+_hashtable_new(struct HashTable *table, size_t obj_size, size_t key_size)
+{
+ *table = (struct HashTable){
+ .buckets = NULL,
+ .bucket_count = 0,
+ .bucket_capacity = 2,
+ .obj_size = obj_size,
+ .key_size = key_size,
+ .hash_function = s_hash_function_mul
+ };
+ table->buckets = mem_alloc(sizeof(struct SLinkedList) * 2);
+}
+
+void
+_hashtable_news(struct HashTable *table, size_t obj_size)
+{
+ *table = (struct HashTable){
+ .buckets = NULL,
+ .bucket_count = 0,
+ .bucket_capacity = 2,
+ .obj_size = obj_size,
+ .key_size = -1,
+ .hash_function = s_hash_function_mul_s
+ };
+ table->buckets = mem_alloc(sizeof(struct SLinkedList) * 2);
+}
+
+void
+hashtable_insert(struct HashTable *table, const void *key, void *data)
+{
+ size_t hash = table->hash_function(key, table->key_size);
+ if(table->bucket_capacity == table->bucket_count) {
+ struct SLinkedList *old_buckets = table->buckets;
+ size_t old_buckets_count = table->bucket_count;
+
+ table->bucket_capacity *= 2;
+ table->bucket_count = 0;
+ table->buckets = mem_alloc(sizeof(struct SLinkedList) * table->bucket_capacity);
+ for(size_t i = 0; i < old_buckets_count; i++) {
+ for(struct SLLNode *node = old_buckets[i].head; node != NULL; node = node->next) {
+ struct HashTableValue *value = (struct HashTableValue*)(&node->data);
+ hashtable_insert(table, value->key, value->value);
+ mem_free(node);
+ }
+ }
+ }
+
+ size_t index = hash % table->bucket_capacity;
+ struct SLinkedList *bucket = &table->buckets[index];
+ struct SLLNode *node = mem_alloc(sizeof(struct SLLNode) + sizeof(struct HashTableValue) + table->obj_size);
+ struct HashTableValue *value = (struct HashTableValue*)(node->data);
+
+ value->key = key;
+ memcpy(value->value, data, table->obj_size);
+
+ table->bucket_count++;
+ if(bucket->count == 0) {
+ sll_new(bucket, table->obj_size);
+ sll_push(bucket, node);
+ return;
+ }
+ for(struct SLLNode *onode = bucket->head; onode != NULL; onode = onode->next)
+ {
+ struct HashTableValue *ovalue = (struct HashTableValue*)onode->data;
+ size_t keylen = table->key_size > 0 ? table->key_size : strlen((const char*)key) + 1;
+ if(memcmp(ovalue->key, value->key, keylen) == 0) {
+ memcpy(ovalue->value, value->value, table->obj_size);
+ return;
+ }
+ }
+ sll_push(bucket, node);
+}
+
+void*
+_hashtable_get(struct HashTable *table, const void *key)
+{
+ size_t hash = table->hash_function(key, table->key_size);
+ size_t index = hash % table->bucket_capacity;
+ struct SLinkedList *bucket = &table->buckets[index];
+ for(struct SLLNode *node = bucket->head; node != NULL; node = node->next)
+ {
+ struct HashTableValue *value = (struct HashTableValue*)node->data;
+ size_t keylen = table->key_size > 0 ? table->key_size : strlen((const char*)value->key);
+ if(memcmp(key, value->key, keylen) == 0) return value->value;
+ }
+ return NULL;
+}
diff --git a/lib/hashtable.d b/lib/hashtable.d
new file mode 100644
index 0000000..791f457
--- /dev/null
+++ b/lib/hashtable.d
@@ -0,0 +1,2 @@
+lib/hashtable.o: lib/hashtable.c lib/hashtable.h lib/linkedlist.h \
+ lib/string.h mem/memory.h mem/slab.h
diff --git a/lib/hashtable.h b/lib/hashtable.h
new file mode 100644
index 0000000..fe6f5c3
--- /dev/null
+++ b/lib/hashtable.h
@@ -0,0 +1,34 @@
+#ifndef JOVE_LIB_HASHTABLE_H
+#define JOVE_LIB_HASHTABLE_H 1
+
+#include <stddef.h>
+#include <stdint.h>
+#include "linkedlist.h"
+
+struct HashTableValue
+{
+ const void *key;
+ char value[];
+};
+
+struct HashTable {
+ struct SLinkedList *buckets;
+ size_t bucket_count;
+ size_t bucket_capacity;
+
+ size_t obj_size;
+ int key_size;
+ size_t (*hash_function)(const void*, size_t);
+};
+
+void _hashtable_new(struct HashTable *table, size_t obj_size, size_t key_size);
+#define hashtable_new(table, type, keytype) _hashtable_new(table, sizeof(type), sizeof(keytype))
+
+void _hashtable_news(struct HashTable *table, size_t obj_size);
+#define hashtable_news(table, type) _hashtable_news(table, sizeof(type))
+
+void hashtable_insert(struct HashTable *table, const void *key, void *data);
+void *_hashtable_get(struct HashTable *table, const void *key);
+#define hashtable_get(table, key, type) (type*)_hashtable_get(table, key)
+
+#endif
diff --git a/lib/jove.h b/lib/jove.h
new file mode 100644
index 0000000..4aa60ed
--- /dev/null
+++ b/lib/jove.h
@@ -0,0 +1,15 @@
+#ifndef JOVE_LIB_JOVE_H
+#define JOVE_LIB_JOVE_H 1
+
+#define ALWAYS_INLINE inline __attribute__((always_inline))
+#define PAGEALIGN __attribute__((aligned(0x1000)))
+
+//#define LOG2(n) (__builtin_clz(n) ^ 31)
+
+extern void *_kernel_start;
+extern void *_kernel_end;
+
+__attribute__((noreturn)) void _kpanic(const char *file, int line, const char *fmt, ...);
+#define kpanic(...) _kpanic(__FILE__, __LINE__, __VA_ARGS__)
+
+#endif
diff --git a/lib/kpanic.c b/lib/kpanic.c
new file mode 100644
index 0000000..97e42eb
--- /dev/null
+++ b/lib/kpanic.c
@@ -0,0 +1,15 @@
+#include "jove.h"
+#include "io/log.h"
+
+#include <stdarg.h>
+
+__attribute__((noreturn))
+void _kpanic(const char *file, int line, const char *fmt, ...)
+{
+ va_list ap;
+ va_start(ap, fmt);
+ klogf("!!! PANIC !!!\n%s:%i\n", file, line);
+ kvlogf(fmt, ap);
+ va_end(ap);
+ for(;;) __asm__ volatile("hlt");
+}
diff --git a/lib/kpanic.d b/lib/kpanic.d
new file mode 100644
index 0000000..bf4ed9e
--- /dev/null
+++ b/lib/kpanic.d
@@ -0,0 +1 @@
+lib/kpanic.o: lib/kpanic.c lib/jove.h io/log.h
diff --git a/lib/linkedlist.c b/lib/linkedlist.c
new file mode 100644
index 0000000..6cc6403
--- /dev/null
+++ b/lib/linkedlist.c
@@ -0,0 +1,34 @@
+#include "linkedlist.h"
+
+void
+sll_new(struct SLinkedList *list, size_t obj_size)
+{
+ list->obj_size = obj_size;
+ list->count = 0;
+ list->head = list->tail = NULL;
+};
+
+void
+sll_push(struct SLinkedList *list, void *data)
+{
+ struct SLLNode *node = (struct SLLNode*)data;
+ if(list->tail != NULL) {
+ list->tail->next = node;
+ }
+ if(list->head == NULL)
+ list->head = node;
+ list->tail = node;
+ list->count++;
+}
+
+void*
+sll_get(struct SLinkedList *list, size_t index)
+{
+ struct SLLNode *node = list->head;
+ if(node == NULL) return NULL;
+ if(index > list->count) return list->tail;
+ for(size_t i = 0; i < index; i++) {
+ node = node->next;
+ }
+ return node;
+}
diff --git a/lib/linkedlist.d b/lib/linkedlist.d
new file mode 100644
index 0000000..a06a9df
--- /dev/null
+++ b/lib/linkedlist.d
@@ -0,0 +1 @@
+lib/linkedlist.o: lib/linkedlist.c lib/linkedlist.h
diff --git a/lib/linkedlist.h b/lib/linkedlist.h
new file mode 100644
index 0000000..26c148e
--- /dev/null
+++ b/lib/linkedlist.h
@@ -0,0 +1,26 @@
+#ifndef JOVE_LIB_LINKEDLIST_H
+#define JOVE_LIB_LINKEDLIST_H 1
+
+#include <stdint.h>
+#include <stddef.h>
+
+struct SLLNode {
+ struct SLLNode *next;
+ char data[];
+};
+
+/*Singly Linked List*/
+struct SLinkedList
+{
+ struct SLLNode *head;
+ struct SLLNode *tail;
+
+ size_t obj_size;
+ size_t count;
+};
+
+void sll_new(struct SLinkedList *list, size_t obj_size);
+void sll_push(struct SLinkedList *list, void *node);
+void *sll_get(struct SLinkedList *list, size_t index);
+
+#endif
diff --git a/lib/ltostr.c b/lib/ltostr.c
new file mode 100644
index 0000000..e28be31
--- /dev/null
+++ b/lib/ltostr.c
@@ -0,0 +1,26 @@
+#include "format.h"
+
+size_t
+ltostr(char *s, size_t limit, unsigned long l, bool sgn, int radix)
+{
+ size_t si = 0;
+ size_t digits = 0;
+ if((long)l < 0 && sgn) {
+ l = -((long)l);
+ s[0] = '-';
+ }
+ for(unsigned long lv = l; lv != 0; lv /= radix)
+ digits++;
+ digits = digits > limit ? limit : digits;
+
+ if(digits-- == 0)
+ s[si++] = '0';
+ for(unsigned long lv = l; lv != 0; lv /= radix)
+ {
+ if(si >= limit) return si;
+ int digit = lv % radix;
+ s[(digits - si)] = (digit >= 10 ? (digit + 'a' - 10) : digit + '0');
+ si++;
+ }
+ return si;
+}
diff --git a/lib/ltostr.d b/lib/ltostr.d
new file mode 100644
index 0000000..fecc225
--- /dev/null
+++ b/lib/ltostr.d
@@ -0,0 +1 @@
+lib/ltostr.o: lib/ltostr.c lib/format.h
diff --git a/lib/mem.c b/lib/mem.c
new file mode 100644
index 0000000..b60fbbd
--- /dev/null
+++ b/lib/mem.c
@@ -0,0 +1,52 @@
+#include "string.h"
+#include "mem/memory.h"
+
+void*
+memset(void *dest, int c, size_t n)
+{
+ char *destc = (char*)dest;
+ for(size_t i = 0; i < n; i++)
+ destc[i] = c;
+ return dest;
+}
+
+void*
+memcpy(void *dest, const void *src, size_t n)
+{
+ char *destc = (char*)dest;
+ const char *srcc = (const char*)src;
+ for(size_t i = 0; i < n; i++)
+ destc[i] = srcc[i];
+ return dest;
+}
+
+void*
+memmove(void *dest, const void *src, size_t n)
+{
+ char *destc = (char*)dest;
+ const char *srcc = (const char*)src;
+ if(destc + n < srcc) return memcpy(dest, src, n);
+ char buffer[n];
+ memcpy(buffer, src, n);
+ return memcpy(destc, buffer, n);
+}
+
+int
+memcmp(const void *a, const void *b, size_t n)
+{
+ const char *ac = (const char*)a;
+ const char *bc = (const char*)b;
+ for(size_t i = 0; i < n; i++) {
+ if(ac[i] != bc[i]) return ac[i] - bc[i];
+ }
+ return 0;
+}
+
+char*
+strdup(const char *s)
+{
+ size_t slen = strlen(s);
+ char *ret = mem_alloc(slen);
+ memcpy(ret, s, slen);
+ return ret;
+}
diff --git a/lib/mem.d b/lib/mem.d
new file mode 100644
index 0000000..232ecd5
--- /dev/null
+++ b/lib/mem.d
@@ -0,0 +1 @@
+lib/mem.o: lib/mem.c lib/string.h mem/memory.h mem/slab.h
diff --git a/lib/sfmt.c b/lib/sfmt.c
new file mode 100644
index 0000000..f903cbf
--- /dev/null
+++ b/lib/sfmt.c
@@ -0,0 +1,112 @@
+#include "string.h"
+#include "format.h"
+
+char*
+sfmt(char *s, size_t limit, const char *fmt, ...)
+{
+ va_list ap;
+ va_start(ap, fmt);
+
+ s = svfmt(s, limit, fmt, ap);
+
+ va_end(ap);
+ return s;
+}
+
+char*
+svfmt(char *s, size_t limit, const char *fmt, va_list ap)
+{
+
+ size_t fmtlen = strlen(fmt);
+ size_t si = 0;
+ for(size_t fmti = 0; fmti < fmtlen; fmti++)
+ {
+ if(si >= limit) break;
+ if(fmt[fmti] != '%') {
+ s[si++] = fmt[fmti];
+ continue;
+ }
+ // TODO: Format flags
+ fmti++;
+
+ bool alt = false;
+ bool zpad = false;
+ for(;;fmti++){
+ if(fmt[fmti] == '#') { alt = true; continue; }
+ if(fmt[fmti] == '0') { zpad = true; continue; }
+ break;
+ }
+ int fwidth = 0;
+ if(fmt[fmti] >= '1' && fmt[fmti] <= '9')
+ {
+ for(;fmt[fmti] >= '0' && fmt[fmti] <= '9';fmti++) {
+ fwidth *= 10;
+ fwidth += fmt[fmti] - '0';
+ }
+ }
+ int precision = 0;
+ if(fmt[fmti] == '.')
+ {
+ fmti++;
+ for(;fmt[fmti] >= '0' && fmt[fmti] <= '9';fmti++) {
+ precision *= 10;
+ precision += fmt[fmti] - '0';
+ }
+ }
+
+ bool sgn = true;
+ bool upper = false;
+ int radix = 10;
+ switch(fmt[fmti])
+ {
+ case '%':
+ s[si++] = '%';
+ break;
+ case 'b':
+ radix = 2;
+ case 'X':
+ upper = true;
+ case 'x':
+ if(radix == 10)
+ radix = 16;
+ case 'o':
+ if(radix == 10)
+ radix = 8;
+ case 'u':
+ sgn = false;
+ case 'i': {
+ if((radix == 8 || radix == 16) && alt) {
+ s[si++] = '0';
+ if(radix == 16) {
+ s[si++] = 'x';
+ }
+ if(radix == 2) {
+ s[si++] = 'b';
+ }
+ }
+ size_t osi = si;
+ size_t nlen = ltostr(&s[si], limit - si, va_arg(ap, long), sgn, radix);
+ if(upper) sntoupper(&s[si], nlen);
+ si += nlen;
+
+ int lpad = fwidth - (int)nlen;
+ if(lpad > 0)
+ {
+ if(lpad + osi >= limit) lpad = (limit - osi - 1);
+ memmove(&s[osi + lpad], &s[osi], nlen);
+ memset(&s[osi], zpad ? '0' : ' ', lpad);
+ si += lpad;
+ }
+ } break;
+ case 's': {
+ const char *str = va_arg(ap, char*);
+ size_t slen = strlen(str);
+ size_t wlen = slen > limit - si ? limit - si : slen;
+ for(size_t i = 0; i < wlen; i++)
+ s[si++] = str[i];
+ } break;
+ }
+ }
+ s[si] = 0;
+ return s;
+}
diff --git a/lib/sfmt.d b/lib/sfmt.d
new file mode 100644
index 0000000..f462cea
--- /dev/null
+++ b/lib/sfmt.d
@@ -0,0 +1 @@
+lib/sfmt.o: lib/sfmt.c lib/string.h lib/format.h
diff --git a/lib/string.c b/lib/string.c
new file mode 100644
index 0000000..4bb1bad
--- /dev/null
+++ b/lib/string.c
@@ -0,0 +1,16 @@
+#include "string.h"
+
+size_t strlen(const char *s) {
+ size_t l = 0;
+ for(; *s != 0; s++, l++);
+ return l;
+}
+
+int strcmp(const char *a, const char *b)
+{
+ size_t i = 0;
+ for(; a[i] != 0 && b[i] != 0; i++) {
+ if(a[i] != b[i]) return a[i] - b[i];
+ }
+ return a[i] - b[i];
+}
diff --git a/lib/string.d b/lib/string.d
new file mode 100644
index 0000000..dae7158
--- /dev/null
+++ b/lib/string.d
@@ -0,0 +1 @@
+lib/string.o: lib/string.c lib/string.h
diff --git a/lib/string.h b/lib/string.h
new file mode 100644
index 0000000..a91ec94
--- /dev/null
+++ b/lib/string.h
@@ -0,0 +1,18 @@
+#ifndef JOVE_LIB_STRING_H
+#define JOVE_LIB_STRING_H 1
+
+#include <stddef.h>
+
+int toupper(int c);
+char *stoupper(char *s);
+char *sntoupper(char *s, size_t limit);
+
+size_t strlen(const char *s);
+
+void *memset(void *dest, int c, size_t n);
+void *memcpy(void *dest, const void *src, size_t n);
+void *memmove(void *dest, const void *src, size_t n);
+int memcmp(const void *a, const void *b, size_t n);
+int strcmp(const char *a, const char *b);
+
+#endif
diff --git a/lib/toupper.c b/lib/toupper.c
new file mode 100644
index 0000000..807eb38
--- /dev/null
+++ b/lib/toupper.c
@@ -0,0 +1,26 @@
+#include "string.h"
+
+int
+toupper(int c)
+{
+ if(c >= 'a' && c <= 'z')
+ c -= ('a' - 'A');
+ return c;
+}
+
+char*
+stoupper(char *s)
+{
+ char *o = s;
+ for(; *s != 0; s++)
+ *s = toupper(*s);
+ return o;
+}
+
+char*
+sntoupper(char *s, size_t limit)
+{
+ for(size_t i = 0; i < limit; i++)
+ s[i] = toupper(s[i]);
+ return s;
+}
diff --git a/lib/toupper.d b/lib/toupper.d
new file mode 100644
index 0000000..72e73f9
--- /dev/null
+++ b/lib/toupper.d
@@ -0,0 +1 @@
+lib/toupper.o: lib/toupper.c lib/string.h
generated by cgit v1.2.1 (git 2.18.0) at 2024-07-04 23:07:32 +0000