From ace65b453151845bc361f21f3e5b651c35f9f126 Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Wed, 22 May 2024 13:00:41 -0400 Subject: massive refactor for mp and organization --- klib/buddymap.c | 170 +++++++++++++++++++++++++ klib/buddymap.h | 35 ++++++ klib/format.h | 13 ++ klib/hash.h | 18 +++ klib/kpanic.c | 16 +++ klib/linkedlist.c | 34 +++++ klib/linkedlist.h | 26 ++++ klib/ltostr.c | 26 ++++ klib/mem.c | 52 ++++++++ klib/rbtree.c | 361 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ klib/rbtree.h | 48 ++++++++ klib/sfmt.c | 115 +++++++++++++++++ klib/spinlock.h | 27 ++++ klib/string.c | 16 +++ klib/toupper.c | 26 ++++ 15 files changed, 983 insertions(+) create mode 100644 klib/buddymap.c create mode 100644 klib/buddymap.h create mode 100644 klib/format.h create mode 100644 klib/hash.h create mode 100644 klib/kpanic.c create mode 100644 klib/linkedlist.c create mode 100644 klib/linkedlist.h create mode 100644 klib/ltostr.c create mode 100644 klib/mem.c create mode 100644 klib/rbtree.c create mode 100644 klib/rbtree.h create mode 100644 klib/sfmt.c create mode 100644 klib/spinlock.h create mode 100644 klib/string.c create mode 100644 klib/toupper.c (limited to 'klib') diff --git a/klib/buddymap.c b/klib/buddymap.c new file mode 100644 index 0000000..62cecf1 --- /dev/null +++ b/klib/buddymap.c @@ -0,0 +1,170 @@ +#include "buddymap.h" +#include "jove.h" +#include "print.h" + +#define BLOCK_AT_LAYER(blocks, l, i) blocks[l][i / BUDDY_BLOCK_BITS] +#define BLOCK_BITMASK(i) (1ULL << (i % BUDDY_BLOCK_BITS)) +#define LOG2(v) (31 - __builtin_clz(v)) + +bool +buddy_bit_test(struct BuddyMap *map, size_t l, size_t i) +{ + return (BLOCK_AT_LAYER(map->blocks, l, i) & BLOCK_BITMASK(i)) > 0; +} + +void +buddy_bit_mark(struct BuddyMap *map, size_t l, size_t i) +{ + size_t wi = i << l; + size_t bits = 1ULL << l; + for(size_t wl = 0; wl < map->orders; wl++) { + if(bits == 0) { + if(buddy_bit_test(map, wl - 1, (wi << 1) + 1)) bits = 1; + } + for(size_t bit = 0; bit < bits; bit++) { + size_t rbit = bit + wi; + if(l == 0 && !buddy_bit_test(map, 0, rbit)) map->free--; + BLOCK_AT_LAYER(map->blocks, wl, rbit) |= BLOCK_BITMASK(rbit); + } + bits >>= 1; + wi >>= 1; + } +} + +void +buddy_bit_free(struct BuddyMap *map, size_t l, size_t i) +{ + size_t wi = i << l; + size_t bits = 1ULL << l; + for(size_t wl = 0; wl < map->orders; wl++) { + if(bits == 0) bits = 1; + for(size_t bit = 0; bit < bits; bit++) { + size_t rbit = bit + wi; + if(l == 0 && buddy_bit_test(map, 0, rbit)) map->free++; + BLOCK_AT_LAYER(map->blocks, wl, rbit) &= ~BLOCK_BITMASK(rbit); + } + bits >>= 1; + wi >>= 1; + } +} + +static void +s_buddy_op_range( + struct BuddyMap *map, + size_t l, + size_t start, + size_t end, + void (*op)(struct BuddyMap*, size_t, size_t)) +{ + size_t layerw = 1ULL << l; + size_t start_off = start % layerw; + size_t end_off = end % layerw; + + size_t start_real = start + (start_off > 0 ? (layerw - start_off) : 0); + size_t end_real = end - end_off; + + if(start_real != start) s_buddy_op_range(map, l - 1, start, start_real, op); + if(end_real != end) s_buddy_op_range(map, l - 1, end_real, end, op); + + size_t start_bit = start_real >> l; + size_t end_bit = end_real >> l; + if(start_bit == end_bit || end_bit < start_bit) return; + for(size_t bit = start_bit; bit < end_bit; bit++) + op(map, l, bit); +} + +static size_t +s_buddy_layer_bestfit(struct BuddyMap *map, size_t length) +{ + if(length == 1) return 0; + size_t length_log2 = LOG2(length); + if(length_log2 > map->orders) length_log2 = map->orders - 1; + return length_log2; +} + +void +buddy_mark_range(struct BuddyMap *map, size_t start, size_t end) +{ + size_t l = s_buddy_layer_bestfit(map, end - start); + s_buddy_op_range(map, l, start, end, buddy_bit_mark); +} +void +buddy_free_range(struct BuddyMap *map, size_t start, size_t end) +{ + size_t l = s_buddy_layer_bestfit(map, end - start); + s_buddy_op_range(map, l, start, end, buddy_bit_free); +} + +static intmax_t +s_buddy_top_firstfree(struct BuddyMap *map) +{ + size_t layer = map->orders - 1; + size_t layer_bits = map->bits >> layer; + size_t layer_blocks = layer_bits / BUDDY_BLOCK_BITS; + for(size_t i = 0; i < layer_blocks; i++) { + if(map->blocks[layer][i] == (uintptr_t)-1) continue; + for(size_t j = 0; j < BUDDY_BLOCK_BITS; j++) { + size_t bit = (i * BUDDY_BLOCK_BITS) + j; + if(buddy_bit_test(map, layer, bit)) continue; + return bit; + } + } + return -1; +} + +static intmax_t +s_buddy_top_alloc_contig(struct BuddyMap *map, size_t length) +{ + size_t layer = map->orders - 1; + size_t layer_bits = map->bits >> layer; + + size_t contig_base = 0; + size_t contig_bits = 0; + for(size_t i = 0; i < layer_bits; i++) { + if(buddy_bit_test(map, layer, i)) { + contig_base = i + 1; + contig_bits = 0; + continue; + } + if(++contig_bits == length) { + return contig_base; + } + } + return -1; +} + +intmax_t +buddy_alloc(struct BuddyMap *map, size_t length) +{ + size_t layer = s_buddy_layer_bestfit(map, length); + size_t layerw = 1ULL << layer; + size_t allocw = length / layerw; + + if(allocw == 0) allocw = 1; + if(allocw > 1) + return s_buddy_top_alloc_contig(map, length); + + intmax_t alloci = s_buddy_top_firstfree(map); + if(alloci < 0) { + klogf("Top layer is full!\n"); + return -1; + } + + for(int wlayer = map->orders - 2; wlayer > layer; wlayer--) { + alloci <<= 1; + if(buddy_bit_test(map, wlayer, alloci)) { + alloci++; + } + } + alloci <<= 1; + if(buddy_bit_test(map, layer, alloci)) alloci++; + + s_buddy_op_range(map, layer, alloci, alloci + length, buddy_bit_mark); + return alloci; +} + +void +buddy_free(struct BuddyMap *map, size_t i, size_t length) +{ + buddy_free_range(map, i, i + length); +} diff --git a/klib/buddymap.h b/klib/buddymap.h new file mode 100644 index 0000000..1af8dfb --- /dev/null +++ b/klib/buddymap.h @@ -0,0 +1,35 @@ +#ifndef JOVE_LIB_BUDDYMAP_H +#define JOVE_LIB_BUDDYMAP_H 1 + +#include +#include +#include + +#define BUDDY_BLOCK_BYTES sizeof(intmax_t) +#define BUDDY_BLOCK_BITS (BUDDY_BLOCK_BYTES * 8) + +#define BUDDY_BITS_FOR(range) (range * 2) +#define BUDDY_BLOCKS_FOR(range) (BUDDY_BITS_FOR(range) / BUDDY_BLOCK_BITS) + +struct BuddyMap +{ + size_t orders; + size_t bits; + size_t free; + uintmax_t **blocks; +}; + +#define BUDDY_BIT_PARTIAL 0 +#define BUDDY_BIT_FULL 1 + +bool buddy_bit_test(struct BuddyMap *map, size_t l, size_t i); +void buddy_bit_mark(struct BuddyMap *map, size_t l, size_t i); +void buddy_bit_free(struct BuddyMap *map, size_t l, size_t i); + +void buddy_mark_range(struct BuddyMap *map, size_t start, size_t end); +void buddy_free_range(struct BuddyMap *map, size_t start, size_t end); + +intmax_t buddy_alloc(struct BuddyMap *map, size_t length); +void buddy_free(struct BuddyMap *map, size_t i, size_t length); + +#endif diff --git a/klib/format.h b/klib/format.h new file mode 100644 index 0000000..5a2b75c --- /dev/null +++ b/klib/format.h @@ -0,0 +1,13 @@ +#ifndef JOVE_LIB_FORMAT_H +#define JOVE_LIB_FORMAT_H 1 + +#include +#include + +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 +char *svfmt(char *s, size_t limit, const char *fmt, va_list ap); + +#endif diff --git a/klib/hash.h b/klib/hash.h new file mode 100644 index 0000000..03b0f3a --- /dev/null +++ b/klib/hash.h @@ -0,0 +1,18 @@ +#ifndef JOVE_LIB_HASH_H +#define JOVE_LIB_HASH_H 1 + +#include + +static intmax_t +string_hash(const char *str) +{ + /* Hash function courtesy of the following website: + * http://www.cse.yorku.ca/~oz/hash.html*/ + intmax_t r = 5381; + while (*str) { + r = (r * 33) ^ *(str++); + } + return r; +} + +#endif diff --git a/klib/kpanic.c b/klib/kpanic.c new file mode 100644 index 0000000..2918711 --- /dev/null +++ b/klib/kpanic.c @@ -0,0 +1,16 @@ +#include "jove.h" +#include "print.h" + +#include +#include + +__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); + _plogvf(NULL, NULL, 0, PRINT_LOG, fmt, ap); + va_end(ap); + for(;;) __asm__ volatile("hlt"); +} diff --git a/klib/linkedlist.c b/klib/linkedlist.c new file mode 100644 index 0000000..6cc6403 --- /dev/null +++ b/klib/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/klib/linkedlist.h b/klib/linkedlist.h new file mode 100644 index 0000000..26c148e --- /dev/null +++ b/klib/linkedlist.h @@ -0,0 +1,26 @@ +#ifndef JOVE_LIB_LINKEDLIST_H +#define JOVE_LIB_LINKEDLIST_H 1 + +#include +#include + +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/klib/ltostr.c b/klib/ltostr.c new file mode 100644 index 0000000..e28be31 --- /dev/null +++ b/klib/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/klib/mem.c b/klib/mem.c new file mode 100644 index 0000000..cf9e2aa --- /dev/null +++ b/klib/mem.c @@ -0,0 +1,52 @@ +#include "string.h" +#include "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 = kmalloc(slen); + memcpy(ret, s, slen); + return ret; +} diff --git a/klib/rbtree.c b/klib/rbtree.c new file mode 100644 index 0000000..2920384 --- /dev/null +++ b/klib/rbtree.c @@ -0,0 +1,361 @@ +#include "rbtree.h" +#include "assert.h" +#include "string.h" + +#define BLACK 0 +#define RED 1 + +#define LEFT 0 +#define left children[LEFT] + +#define RIGHT 1 +#define right children[RIGHT] + +#define CHILD_DIR(c) (c->parent->children[LEFT] == c ? LEFT : RIGHT) + +/**Given a root and a direction, rotate the subtree such that the order of the + * elements are unchanged. + * The opposite direction child of the given root is treated as the pivot point + * The dir-most child of the pivot becomes the opposite dir child of the root. + * The pivot becomes the root and vice-versa. + * @param tree to do rotation on. + * @param root of rotation. + * @param dir to rotate by. + * @return new root node.*/ +rbnode_t* +s_node_rotate(rbtree_t *tree, rbnode_t *root, bool dir) +{ + assert(root != NULL); + rbnode_t *gparent = root->parent; + rbnode_t *sibling = root->children[1-dir]; + rbnode_t *child = NULL; + + assert(sibling != NULL); + child = sibling->children[dir]; + + /* Opposite child of root is dir-most child of sibling.*/ + root->children[1-dir] = child; + if(child != NULL) child->parent = root; + + /* Child of sibling is the root.*/ + sibling->children[ dir] = root; + root->parent = sibling; + + /* Parent of sibling is the grandparent. */ + sibling->parent = gparent; + if(gparent != NULL) + gparent->children[CHILD_DIR(root)] = sibling; + else + tree->root = sibling; + + return sibling; +} + +/**Search the rbtree for a node that matches the key. + * If no such node is found, returns NULL. + * @param tree to search through. + * @param key to search for. + * @return found node.*/ +rbnode_t* +s_find(rbtree_t *tree, intmax_t key) +{ + rbnode_t *node = tree->root; + while(node != NULL && node->key != key) { + node = node->children[node->key > key]; + } + return node; +} + +rbnode_t* +s_closest(rbtree_t *tree, intmax_t key) +{ + rbnode_t *node = tree->root; + while(node != NULL && node->key != key) { + rbnode_t *child = node->children[node->key > key]; + if(child == NULL) return node; + node = child; + } + return node; +} + +/**Find the left-most node for this subtree. + * @param node root of the subtree to search through. + * @return left-most node.*/ +rbnode_t* +s_node_min(rbnode_t *node) +{ + while(node->left != NULL) node = node->left; + return node; +} + +/**Find the successor for the specified node. + * The successor is defined as the left-most node of the right sub-tree. + * (the smallest node larger than the root) + * @param node to search for. + * @return the successor.*/ +rbnode_t* +s_node_successor(rbnode_t *node) +{ + if(node->right != NULL) + return s_node_min(node->right); + /* If the node has no left child (meaning that the node is larger than it's + * parents), we cycle up through the RHS of the parent tree (such that each + * parent is smaller than the child) until we reach a point by which the + * child node is smaller than the parent.*/ + rbnode_t *parent = node->parent; + while(parent != NULL && node == parent->right) { + node = parent; + parent = node->parent; + } + return parent; +} + +/**Copy the data from one node onto another, keeping parent and child relations. + * @prarm tree for metadata purposes. + * @param dest destination node. + * @param src source node.*/ +void +s_node_copy_value(rbtree_t *tree, rbnode_t *dest, rbnode_t *src) +{ + dest->key = src->key; + memcpy(dest->data, src->data, tree->objw); +} + +/**Perform tree adjustments after insertion to rebalance the rbtree. + * @param tree to rebalance. + * @param node that was inserted. + * @param parent of the node. + * @param dir that the node was inserted in.*/ +void +s_node_insert_fix( + rbtree_t *tree, + rbnode_t *node, + rbnode_t *parent, + bool dir) +{ + rbnode_t *gparent; + rbnode_t *uncle; + while((parent = node->parent) != NULL) { + if(parent->color == BLACK) return; /* Tree is valid. no fixes needed.*/ + /*Parent is known to be red.*/ + if((gparent = parent->parent) == NULL) { + /*Parent is red and the root. We can just fix it and return.*/ + parent->color = BLACK; + return; + } + /* Parent is red and has a parent. + * We now need to fix the parent.*/ + dir = CHILD_DIR(parent); + uncle = gparent->children[1-dir]; + if(uncle == NULL || uncle->color == BLACK) { + /* Parent is red, but uncle (opposite child of gparent) is black. + * We need to rotate the gparent node such that the parent takes + * its place. However, if the current node is an inner child of + * gparent, we need to rotate N into P.*/ + if(node == parent->children[1-dir]) { + /* Node is an inner child. We need to rotate N and P first.*/ + s_node_rotate(tree, parent, dir); + node = parent; + parent = gparent->children[dir]; + } + /* N is not an inner child, we can rotate the tree properly.*/ + s_node_rotate(tree, gparent, 1-dir); + parent->color = BLACK; + gparent->color = RED; + return; + } + } +} + +/**Insert a node into the rbtree on the parent and direction given. + * @param tree to insert into. + * @param node to insert. + * @param parent node to insert onto. + * @param dir direction to insert node.*/ +void +s_node_insert(rbtree_t *tree, rbnode_t *node, rbnode_t *parent, bool dir) +{ + node->color = RED; + node->left = NULL; + node->right = NULL; + node->parent = parent; + if(parent == NULL) { + tree->root = node; + return; + } + parent->children[dir] = node; + s_node_insert_fix(tree, node, parent, dir); +} + +void +s_node_remove_fixup(rbtree_t *tree, rbnode_t *node) +{ + bool dir; + rbnode_t *parent = node->parent; + rbnode_t *sibling; + rbnode_t *cnephew; + rbnode_t *dnephew; + + dir = CHILD_DIR(node); + parent->children[dir] = NULL; + while((parent = node->parent) != NULL) + { + dir = CHILD_DIR(node); + sibling = parent->children[1-dir]; + cnephew = parent->children[ dir]; + dnephew = parent->children[1-dir]; + if(sibling->color == RED) + goto case3; + if(dnephew != NULL && dnephew->color == RED) + goto case6; + if(cnephew != NULL && cnephew->color == RED) + goto case5; + if(parent->color == RED) + goto case4; + + /* The parent, both nephews, and sibling are black. We need to paint + * the sibling black and move up a level.*/ + sibling->color = RED; + node = parent; + } + return; + +case3: + /* The sibling is red, which means both nephews and the parent are black. + * We rotate the subtree so that the parent moves to become the siblings + * left child. The tree is then repainted.*/ + s_node_rotate(tree, parent, dir); + parent->color = RED; + sibling->color = BLACK; + /* Now we are working on the sibling subtree.*/ + sibling = cnephew; + dnephew = sibling->children[1-dir]; + if(dnephew != NULL && dnephew->color == BLACK) + goto case6; + cnephew = sibling->children[dir]; + if(cnephew != NULL && cnephew->color == RED) + goto case5; + +case4: + sibling->color = RED; + parent->color = BLACK; + return; + +case5: + s_node_rotate(tree, sibling, 1-dir); + sibling->color = RED; + cnephew->color = BLACK; + dnephew = sibling; + sibling = cnephew; + +case6: + s_node_rotate(tree, parent, dir); + sibling->color = parent->color; + parent->color = BLACK; + dnephew->color = BLACK; +} + +void +s_node_remove(rbtree_t *tree, rbnode_t *node) +{ + rbnode_t *parent = node->parent; + if(node->left != NULL && node->right != NULL) { + /* Node is a full tree. We can replace the node with it's successor to + * keep the balance. + * Needs to recurse if the successor has a right-most child, which is + * dealt with in the next case.*/ + rbnode_t *successor = s_node_successor(node); + s_node_copy_value(tree, node, successor); + s_node_remove(tree, successor); + return; + } else if(node->left == NULL && node->right == NULL) { + if(parent == NULL) { + tree->root = NULL; + kfree(node); + return; + } + if(node->color == RED) { + parent->children[CHILD_DIR(node)] = NULL; + kfree(node); + return; + } + s_node_remove_fixup(tree, node); + } else { + /* Node has a single child. Because the child must be red as per spec, + * and this node must be black, we can simply replace the node + * with it's child and color it black.*/ + rbnode_t *child = node->left == NULL ? node->right : node->left; + memcpy(node, child, sizeof(rbnode_t) + tree->objw); + node->parent = parent; + node->color = BLACK; + kfree(child); + return; + } +} + +void +__rbtree_new(rbtree_t *tree, size_t objw) +{ + *tree = (rbtree_t) { + .root = NULL, + .objw = objw, + }; +} + +void* +rbtree_find(rbtree_t *tree, intmax_t key) +{ + rbnode_t *found = s_find(tree, key); + if(found == NULL) return NULL; + return found->data; +} + +rbnode_t* +s_node_new(rbtree_t *tree, intmax_t key, void *data) +{ + rbnode_t *node = kmalloc(sizeof(rbnode_t) + tree->objw); + if(data != NULL) memcpy(node->data, data, tree->objw); + node->key = key; + return node; +} + +void* +rbtree_insert(rbtree_t *tree, intmax_t key, void *data) +{ + assert(tree != NULL); + + rbnode_t *node = s_closest(tree, key); + if(node != NULL && node->key == key) { + memcpy(node->data, data, tree->objw); + } else if(node != NULL) { + rbnode_t *child = s_node_new(tree, key, data); + s_node_insert(tree, child, node, node->key > key); + return child->data; + } else { + node = s_node_new(tree, key, data); + node->parent = NULL; + node->children[0] = node->children[1] = NULL; + node->color = BLACK; + tree->root = node; + } + return node->data; +} + +void *rbtree_reserve(rbtree_t *tree, intmax_t key) +{ + assert(tree != NULL); + + rbnode_t *node = s_closest(tree, key); + if(node != NULL && node->key == key) { + return node->data; + } else if(node != NULL) { + rbnode_t *child = s_node_new(tree, key, NULL); + s_node_insert(tree, child, node, node->key > key); + return child->data; + } else { + node = s_node_new(tree, key, NULL); + tree->root = node; + } + return node->data; +} + diff --git a/klib/rbtree.h b/klib/rbtree.h new file mode 100644 index 0000000..4376713 --- /dev/null +++ b/klib/rbtree.h @@ -0,0 +1,48 @@ +#ifndef JOVE_LIB_RBTREE_H +#define JOVE_LIB_RBTREE_H 1 + +#include +#include +#include +#include "memory.h" + +typedef struct rbnode +{ + struct rbnode *parent; + struct rbnode *children[2]; + intmax_t key; + bool color; + char data[]; +} rbnode_t; + +typedef struct rbtree +{ + rbnode_t *root; + size_t objw; +} rbtree_t; + +/**Instantiate a new tree based on the given type. + * @param tree to instantiate into. + * @param type to instantiate for.*/ +#define rbtree_new(tree, type) __rbtree_new(tree, sizeof(type)) +void __rbtree_new(rbtree_t *tree, size_t objw); + +/**Find the data corresponding to the key in the tree. + * usage: rbtree_find(type)(tree, key); + * @param tree to search through. + * @param key to search for. + * @return */ +void *rbtree_find(rbtree_t *tree, intmax_t key); + +/**Insert a value into the given tree using the given key. + * If the key is already present within the tree, the existing data is + * overwritten. + * @param tree to insert into. + * @param key to insert. + * @param value to insert. + * @return pointer to inserted data. + * */ +void *rbtree_insert(rbtree_t *tree, intmax_t key, void *value); +void *rbtree_reserve(rbtree_t *tree, intmax_t key); + +#endif diff --git a/klib/sfmt.c b/klib/sfmt.c new file mode 100644 index 0000000..519fbf4 --- /dev/null +++ b/klib/sfmt.c @@ -0,0 +1,115 @@ +#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 'p': + radix = 16; + alt = true; + case 'b': + if(radix == 10) 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/klib/spinlock.h b/klib/spinlock.h new file mode 100644 index 0000000..75af28a --- /dev/null +++ b/klib/spinlock.h @@ -0,0 +1,27 @@ +#ifndef JOVE_LIB_SPINLOCK_H +#define JOVE_LIB_SPINLOCK_H 1 + +#include + +typedef struct Spinlock +{ + atomic_flag flg; + + const char *locker_file; + const char *locker_func; + int locker_line; +} spinlock_t; + +#define spinlock_acquire(lock) \ + while(atomic_flag_test_and_set_explicit(&lock.flg, memory_order_acquire)) \ + __builtin_ia32_pause(); \ + lock.locker_file = __FILE__; \ + lock.locker_func = __FUNCTION__; \ + lock.locker_line = __LINE__ + +#define spinlock_release(lock) \ + atomic_flag_clear_explicit(&lock.flg, memory_order_release); \ + lock.locker_file = lock.locker_func = NULL; \ + lock.locker_line = -1 + +#endif diff --git a/klib/string.c b/klib/string.c new file mode 100644 index 0000000..4bb1bad --- /dev/null +++ b/klib/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/klib/toupper.c b/klib/toupper.c new file mode 100644 index 0000000..807eb38 --- /dev/null +++ b/klib/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; +} -- cgit v1.2.1