diff options
| -rw-r--r-- | Makefile | 31 | ||||
| -rw-r--r-- | src/btree.h | 43 | ||||
| -rw-r--r-- | src/btree_naive.c | 58 | ||||
| -rw-r--r-- | src/main.c | 40 |
4 files changed, 172 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..e340023 --- /dev/null +++ b/Makefile @@ -0,0 +1,31 @@ +CC = gcc +LFLAGS = +FLAGS = -ansi -Wall -Wextra -pedantic +OUT = btree-test +SRC :=$(wildcard src/*.c) +OBJ :=$(addprefix obj/,$(notdir $(SRC:.c=.o))) + +.PHONY: clean + +test: debug + ./$(OUT) + +gdb: debug + gdb -q -ex r $(OUT) + +debug: DEFS += -g3 -DDEBUG +debug: obj build + +build: $(OUT) + +$(OUT): $(OBJ) + $(CC) $(DEFS) $(FLAGS) $(LFLAGS) -o $(OUT) $(OBJ) + +obj/%.o: src/%.c + $(CC) $(DEFS) $(FLAGS) -c -o $@ $< + +obj: + mkdir -p $@ + +clean: + rm -rf $(OUT) obj diff --git a/src/btree.h b/src/btree.h new file mode 100644 index 0000000..95acf22 --- /dev/null +++ b/src/btree.h @@ -0,0 +1,43 @@ +#ifndef BTREE_H +#define BTREE_H + +#include <stddef.h> + +#define BTREE_DEGREE_DEFAULT 4 + +#define BTREE_SIZE_MIN 8 +#define BTREE_SIZE_MAX 4096 + +#define BTREE_CMP_LT ( -1 ) +#define BTREE_CMP_EQ ( 0 ) +#define BTREE_CMP_GT ( 1 ) + +struct btree; + +/* elem_size: the size of the elements, typically `sizeof(struct <your struct>)` + * t: degree of the btree, if you're in doubt, use `BTREE_SIZE_DEFAULT` + * cmp: comparison function, in order to support any operations on the tree. + * + * This function just calls `btree_new_with_allocator` with `free` and `malloc` + * as initializers. + */ +struct btree *btree_new(size_t elem_size, + size_t t, + int(*cmp)(const void *a, const void *b)); + +/* Same as `btree_new`, except that it actually initializes a btree, but with + * the given allocators. + */ +struct btree *btree_new_with_allocator(size_t elem_size, + size_t t, + int(*cmp)(const void *a, const void *b), + void *(*alloc)(size_t), + void (*dealloc)(void*)); + +void btree_free(struct btree *btree); + +void *btree_search(struct btree *btree, void *elem); +void *btree_insert(struct btree *btree, void *elem); +void *btree_delete(struct btree *btree, void *elem); + +#endif diff --git a/src/btree_naive.c b/src/btree_naive.c new file mode 100644 index 0000000..bc881f1 --- /dev/null +++ b/src/btree_naive.c @@ -0,0 +1,58 @@ +#include "btree.h" + +#include <stdlib.h> +#include <stdbool.h> + +typedef unsigned char byte; + +struct node { + size_t n; /* number of items */ + bool leaf; + byte *items; + struct node *children; +}; + +struct btree { + /* Memory stuffs */ + void *(*alloc)(size_t); + void (*dealloc)(void*); + + /* Size stuffs */ + size_t elem_size; + size_t degree; + + /* comparison */ + int (*cmp)(const void *a, const void *b); +}; + +struct btree *btree_new(size_t elem_size, + size_t t, + int(*cmp)(const void *a, const void *b)) { + return btree_new_with_allocator(elem_size, t, cmp, malloc, free); +} + +struct btree *btree_new_with_allocator(size_t elem_size, + size_t t, + int(*cmp)(const void *a, const void *b), + void *(*alloc)(size_t), + void (*dealloc)(void*)) { + struct btree *new_tree = malloc(sizeof(struct btree)); + + new_tree->alloc = alloc; + new_tree->dealloc = dealloc; + + new_tree->elem_size = elem_size; + new_tree->degree = t; + + new_tree->cmp = cmp; +} + +void btree_free(struct btree *btree) { + /*btree->dealloc(btree->root);*/ + free(btree); + btree = NULL; +} + +void *btree_search(struct btree *btree, void *elem) {} +void *btree_insert(struct btree *btree, void *elem) {} +void *btree_delete(struct btree *btree, void *elem) {} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..7e460c8 --- /dev/null +++ b/src/main.c @@ -0,0 +1,40 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "btree.h" + +enum gender { + gender_male, + gender_female, + gender_other +}; + +struct userdat { + const char *name; + unsigned short age; + enum gender gender; +}; + +int userdat_cmp(const void *a, const void *b) { + const struct userdat *ua = a; + const struct userdat *ub = b; + + if (ua->age == ub->age) { + if (ua->gender > ub->gender) { return BTREE_CMP_GT; } + else if (ua->gender < ub->gender) { return BTREE_CMP_LT; } + { return BTREE_CMP_EQ; } + + } else if (ua->age > ub->age) { + return BTREE_CMP_GT; + } return BTREE_CMP_LT; +} + +int main() { + struct btree *tree = btree_new(sizeof(struct userdat), + BTREE_DEGREE_DEFAULT, + &userdat_cmp); + + btree_free(tree); + + return 0; +} |