From 8001fafbf699a4048046d4393377e3ec83480b95 Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Sat, 17 Feb 2018 03:13:07 +0200 Subject: [PATCH] writing obj loader --- src/dynarr.c | 12 ++ src/dynarr.h | 66 ++++++-- src/infcubes.c | 5 + src/mesh.c | 5 - src/meshload.c | 278 +++++++++++++++++++++++++++++++ src/rbtree.c | 503 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/rbtree.h | 78 +++++++++ src/vmath.h | 3 + 8 files changed, 933 insertions(+), 17 deletions(-) create mode 100644 src/meshload.c create mode 100644 src/rbtree.c create mode 100644 src/rbtree.h diff --git a/src/dynarr.c b/src/dynarr.c index f3e9c47..09a5e45 100644 --- a/src/dynarr.c +++ b/src/dynarr.c @@ -70,6 +70,11 @@ int dynarr_size(void *da) } +void *dynarr_clear(void *da) +{ + return dynarr_resize(da, 0); +} + /* stack semantics */ void *dynarr_push(void *da, void *item) { @@ -126,3 +131,10 @@ void *dynarr_pop(void *da) return da; } + +void *dynarr_finalize(void *da) +{ + struct arrdesc *desc = DESC(da); + memmove(desc, da, desc->bufsz); + return desc; +} diff --git a/src/dynarr.h b/src/dynarr.h index e528305..8690b5a 100644 --- a/src/dynarr.h +++ b/src/dynarr.h @@ -5,18 +5,6 @@ #ifndef DYNARR_H_ #define DYNARR_H_ -void *dynarr_alloc(int elem, int szelem); -void dynarr_free(void *da); -void *dynarr_resize(void *da, int elem); - -int dynarr_empty(void *da); -int dynarr_size(void *da); - -/* stack semantics */ -void *dynarr_push(void *da, void *item); -void *dynarr_pop(void *da); - - /* usage example: * ------------- * int *arr = dynarr_alloc(0, sizeof *arr); @@ -34,5 +22,59 @@ void *dynarr_pop(void *da); * dynarr_free(arr); */ +void *dynarr_alloc(int elem, int szelem); +void dynarr_free(void *da); +void *dynarr_resize(void *da, int elem); + +/* dynarr_empty returns non-zero if the array is empty + * Complexity: O(1) */ +int dynarr_empty(void *da); +/* dynarr_size returns the number of elements in the array + * Complexity: O(1) */ +int dynarr_size(void *da); + +void *dynarr_clear(void *da); + +/* stack semantics */ +void *dynarr_push(void *da, void *item); +void *dynarr_pop(void *da); + +/* Finalize the array. No more resizing is possible after this call. + * Use free() instead of dynarr_free() to deallocate a finalized array. + * Returns pointer to the finalized array. + * dynarr_finalize can't fail. + * Complexity: O(n) + */ +void *dynarr_finalize(void *da); + +/* helper macros */ +#define DYNARR_RESIZE(da, n) \ + do { (da) = dynarr_resize((da), (n)); } while(0) +#define DYNARR_CLEAR(da) \ + do { (da) = dynarr_clear(da); } while(0) +#define DYNARR_PUSH(da, item) \ + do { (da) = dynarr_push((da), (item)); } while(0) +#define DYNARR_POP(da) \ + do { (da) = dynarr_pop(da); } while(0) + +/* utility macros to push characters to a string. assumes and maintains + * the invariant that the last element is always a zero + */ +#define DYNARR_STRPUSH(da, c) \ + do { \ + char cnull = 0, ch = (char)(c); \ + (da) = dynarr_pop(da); \ + (da) = dynarr_push((da), &ch); \ + (da) = dynarr_push((da), &cnull); \ + } while(0) + +#define DYNARR_STRPOP(da) \ + do { \ + char cnull = 0; \ + (da) = dynarr_pop(da); \ + (da) = dynarr_pop(da); \ + (da) = dynarr_push((da), &cnull); \ + } while(0) + #endif /* DYNARR_H_ */ diff --git a/src/infcubes.c b/src/infcubes.c index 4da85c6..36225f9 100644 --- a/src/infcubes.c +++ b/src/infcubes.c @@ -51,9 +51,14 @@ static int init(void) } convimg_rgb24_rgb16(tex_outer.pixels, (unsigned char*)tex_outer.pixels, tex_outer.width, tex_outer.height); + /* if(gen_cube_mesh(&mesh_cube, 1.0f, 3) == -1) { return -1; } + */ + if(load_mesh(&mesh_cube, "data/bevelbox.obj") == -1) { + return -1; + } return 0; } diff --git a/src/mesh.c b/src/mesh.c index 9e31840..c4c8a87 100644 --- a/src/mesh.c +++ b/src/mesh.c @@ -5,11 +5,6 @@ #include "mesh.h" #include "3dgfx.h" -int load_mesh(struct g3d_mesh *mesh, const char *fname) -{ - return -1; /* TODO */ -} - static struct { struct g3d_vertex *varr; const float *xform; diff --git a/src/meshload.c b/src/meshload.c new file mode 100644 index 0000000..61cf128 --- /dev/null +++ b/src/meshload.c @@ -0,0 +1,278 @@ +#include +#include +#include +#include "mesh.h" +#include "dynarr.h" +#include "rbtree.h" +#include "vmath.h" +#include "3dgfx.h" + + +struct facevertex { + int vidx, tidx, nidx; + int myidx; +}; + +static char *clean_line(char *s); +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn); +static int cmp_facevert(const void *ap, const void *bp); +static void free_rbnode_key(struct rbnode *n, void *cls); + + +int load_mesh(struct g3d_mesh *mesh, const char *fname) +{ + int i, line_num = 0, result = -1; + int found_quad = 0; + FILE *fp; + char buf[256]; + vec3_t *varr = 0, *narr = 0; + vec2_t *tarr = 0; + struct rbtree *rbtree; + + if(!(fp = fopen(fname, "rb"))) { + fprintf(stderr, "load_mesh: failed to open file: %s\n", fname); + return -1; + } + + if(!(rbtree = rb_create(cmp_facevert))) { + fprintf(stderr, "load_mesh: failed to create facevertex binary search tree\n"); + goto err; + } + rb_set_delete_func(rbtree, free_rbnode_key, 0); + + if(!(mesh->varr = dynarr_alloc(0, sizeof *mesh->varr)) || + !(mesh->iarr = dynarr_alloc(0, sizeof *mesh->iarr))) { + fprintf(stderr, "load_mesh: failed to allocate resizable mesh arrays\n"); + goto err; + } + if(!(varr = dynarr_alloc(0, sizeof *varr)) || + !(narr = dynarr_alloc(0, sizeof *narr)) || + !(tarr = dynarr_alloc(0, sizeof *tarr))) { + fprintf(stderr, "load_mesh: failed to allocate resizable vertex array\n"); + goto err; + } + + while(fgets(buf, sizeof buf, fp)) { + char *line = clean_line(buf); + ++line_num; + + if(!*line) continue; + + switch(line[0]) { + case 'v': + if(isspace(line[1])) { + /* vertex */ + vec3_t v; + if(sscanf(line + 2, "%f %f %f", &v.x, &v.y, &v.z) != 3) { + fprintf(stderr, "%s:%d: invalid vertex definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(varr = dynarr_push(varr, &v))) { + fprintf(stderr, "load_mesh: failed to resize vertex buffer\n"); + goto err; + } + + } else if(line[1] == 't' && isspace(line[2])) { + /* texcoord */ + vec2_t tc; + if(sscanf(line + 3, "%f %f", &tc.x, &tc.y) != 2) { + fprintf(stderr, "%s:%d: invalid texcoord definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(tarr = dynarr_push(tarr, &tc))) { + fprintf(stderr, "load_mesh: failed to resize texcoord buffer\n"); + goto err; + } + + } else if(line[1] == 'n' && isspace(line[2])) { + /* normal */ + vec3_t norm; + if(sscanf(line + 3, "%f %f %f", &norm.x, &norm.y, &norm.z) != 3) { + fprintf(stderr, "%s:%d: invalid normal definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(narr = dynarr_push(narr, &norm))) { + fprintf(stderr, "load_mesh: failed to resize normal buffer\n"); + goto err; + } + } + break; + + case 'f': + if(isspace(line[1])) { + /* face */ + char *ptr = line + 2; + struct facevertex fv; + struct rbnode *node; + int vsz = dynarr_size(varr); + int tsz = dynarr_size(tarr); + int nsz = dynarr_size(narr); + + for(i=0; i<4; i++) { + if(!(ptr = parse_face_vert(ptr, &fv, vsz, tsz, nsz))) { + if(i < 3 || found_quad) { + fprintf(stderr, "%s:%d: invalid face definition: \"%s\"\n", fname, line_num, line); + goto err; + } else { + break; + } + } + + if((node = rb_find(rbtree, &fv))) { + uint16_t idx = (int)(intptr_t)node->data; + if(!(mesh->iarr = dynarr_push(mesh->iarr, &idx))) { + fprintf(stderr, "load_mesh: failed to resize index array\n"); + goto err; + } + } else { + uint16_t idx = dynarr_size(mesh->varr); + struct g3d_vertex v; + struct facevertex *newfv; + + v.x = varr[fv.vidx].x; + v.y = varr[fv.vidx].y; + v.z = varr[fv.vidx].z; + v.w = 1.0f; + if(fv.tidx >= 0) { + v.u = tarr[fv.tidx].x; + v.v = tarr[fv.tidx].y; + } else { + v.u = v.x; + v.v = v.y; + } + if(fv.nidx >= 0) { + v.nx = narr[fv.nidx].x; + v.ny = narr[fv.nidx].y; + v.nz = narr[fv.nidx].z; + } else { + v.nx = v.ny = 0.0f; + v.nz = 1.0f; + } + v.r = v.g = v.b = v.a = 255; + + if(!(mesh->varr = dynarr_push(mesh->varr, &v))) { + fprintf(stderr, "load_mesh: failed to resize combined vertex array\n"); + goto err; + } + if(!(mesh->iarr = dynarr_push(mesh->iarr, &idx))) { + fprintf(stderr, "load_mesh: failed to resize index array\n"); + goto err; + } + + if((newfv = malloc(sizeof *newfv))) { + *newfv = fv; + } + if(!newfv || rb_insert(rbtree, newfv, &idx) == -1) { + fprintf(stderr, "load_mesh: failed to insert facevertex to the binary search tree\n"); + goto err; + } + } + } + if(i >= 3) found_quad = 1; + } + break; + + default: + break; + } + } + + mesh->prim = found_quad ? G3D_QUADS : G3D_TRIANGLES; + mesh->vcount = dynarr_size(mesh->varr); + mesh->icount = dynarr_size(mesh->iarr); + mesh->varr = dynarr_finalize(mesh->varr); + mesh->iarr = dynarr_finalize(mesh->iarr); + result = 0; /* success */ + + printf("loaded %s mesh: %s: %d vertices, %d faces\n", found_quad ? "quad" : "triangle", + fname, mesh->vcount, mesh->icount / mesh->prim); + +err: + if(fp) fclose(fp); + dynarr_free(varr); + dynarr_free(narr); + dynarr_free(tarr); + if(result == -1) { + dynarr_free(mesh->varr); + dynarr_free(mesh->iarr); + } + rb_free(rbtree); + return result; +} + +static char *clean_line(char *s) +{ + char *end; + + while(*s && isspace(*s)) ++s; + if(!*s) return 0; + + end = s; + while(*end && *end != '#') ++end; + *end = 0; + + while(end > s && isspace(*end)) --end; + *end = 0; + + return s; +} + +static char *parse_idx(char *ptr, int *idx, int arrsz) +{ + char *endp; + int val = strtol(ptr, &endp, 10); + if(endp == ptr) return 0; + + if(val < 0) { /* convert negative indices */ + *idx = arrsz + val; + } else { + *idx = val - 1; /* indices in obj are 1-based */ + } + return endp; +} + +/* possible face-vertex definitions: + * 1. vertex + * 2. vertex/texcoord + * 3. vertex//normal + * 4. vertex/texcoord/normal + */ +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn) +{ + if(!(ptr = parse_idx(ptr, &fv->vidx, numv))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + + if(*++ptr == '/') { /* no texcoord */ + fv->tidx = -1; + ++ptr; + } else { + if(!(ptr = parse_idx(ptr, &fv->tidx, numt))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + ++ptr; + } + + if(!(ptr = parse_idx(ptr, &fv->nidx, numn))) + return 0; + return (!*ptr || isspace(*ptr)) ? ptr : 0; +} + +static int cmp_facevert(const void *ap, const void *bp) +{ + const struct facevertex *a = ap; + const struct facevertex *b = bp; + + if(a->vidx == b->vidx) { + if(a->tidx == b->tidx) { + return a->nidx - b->nidx; + } + return a->tidx - b->tidx; + } + return a->vidx - b->vidx; +} + +static void free_rbnode_key(struct rbnode *n, void *cls) +{ + free(n->key); +} diff --git a/src/rbtree.c b/src/rbtree.c new file mode 100644 index 0000000..e595885 --- /dev/null +++ b/src/rbtree.c @@ -0,0 +1,503 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. + */ +#include +#include +#include +#include +#include "rbtree.h" + +#define INT2PTR(x) ((void*)(intptr_t)(x)) +#define PTR2INT(x) ((int)(intptr_t)(x)) + +struct rbtree { + struct rbnode *root; + + rb_alloc_func_t alloc; + rb_free_func_t free; + + rb_cmp_func_t cmp; + rb_del_func_t del; + void *del_cls; + + struct rbnode *rstack, *iter; +}; + +static int cmpaddr(const void *ap, const void *bp); +static int cmpint(const void *ap, const void *bp); + +static int count_nodes(struct rbnode *node); +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls); +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data); +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key); +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/ +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls); + +struct rbtree *rb_create(rb_cmp_func_t cmp_func) +{ + struct rbtree *rb; + + if(!(rb = malloc(sizeof *rb))) { + return 0; + } + if(rb_init(rb, cmp_func) == -1) { + free(rb); + return 0; + } + return rb; +} + +void rb_free(struct rbtree *rb) +{ + rb_destroy(rb); + free(rb); +} + + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func) +{ + memset(rb, 0, sizeof *rb); + + if(!cmp_func) { + rb->cmp = cmpaddr; + } else if(cmp_func == RB_KEY_INT) { + rb->cmp = cmpint; + } else if(cmp_func == RB_KEY_STRING) { + rb->cmp = (rb_cmp_func_t)strcmp; + } else { + rb->cmp = cmp_func; + } + + rb->alloc = malloc; + rb->free = free; + return 0; +} + +void rb_destroy(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); +} + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free) +{ + rb->alloc = alloc; + rb->free = free; +} + + +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func) +{ + rb->cmp = func; +} + +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls) +{ + rb->del = func; + rb->del_cls = cls; +} + + +void rb_clear(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); + rb->root = 0; +} + +int rb_copy(struct rbtree *dest, struct rbtree *src) +{ + struct rbnode *node; + + rb_clear(dest); + rb_begin(src); + while((node = rb_next(src))) { + if(rb_insert(dest, node->key, node->data) == -1) { + return -1; + } + } + return 0; +} + +int rb_size(struct rbtree *rb) +{ + return count_nodes(rb->root); +} + +int rb_insert(struct rbtree *rb, void *key, void *data) +{ + rb->root = insert(rb, rb->root, key, data); + rb->root->red = 0; + return 0; +} + +int rb_inserti(struct rbtree *rb, int key, void *data) +{ + rb->root = insert(rb, rb->root, INT2PTR(key), data); + rb->root->red = 0; + return 0; +} + + +int rb_delete(struct rbtree *rb, void *key) +{ + if((rb->root = delete(rb, rb->root, key))) { + rb->root->red = 0; + } + return 0; +} + +int rb_deletei(struct rbtree *rb, int key) +{ + if((rb->root = delete(rb, rb->root, INT2PTR(key)))) { + rb->root->red = 0; + } + return 0; +} + + +struct rbnode *rb_find(struct rbtree *rb, void *key) +{ + struct rbnode *node = rb->root; + + while(node) { + int cmp = rb->cmp(key, node->key); + if(cmp == 0) { + return node; + } + node = cmp < 0 ? node->left : node->right; + } + return 0; +} + +struct rbnode *rb_findi(struct rbtree *rb, int key) +{ + return rb_find(rb, INT2PTR(key)); +} + + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls) +{ + traverse(rb->root, func, cls); +} + + +struct rbnode *rb_root(struct rbtree *rb) +{ + return rb->root; +} + +void rb_begin(struct rbtree *rb) +{ + rb->rstack = 0; + rb->iter = rb->root; +} + +#define push(sp, x) ((x)->next = (sp), (sp) = (x)) +#define pop(sp) ((sp) = (sp)->next) +#define top(sp) (sp) + +struct rbnode *rb_next(struct rbtree *rb) +{ + struct rbnode *res = 0; + + while(rb->rstack || rb->iter) { + if(rb->iter) { + push(rb->rstack, rb->iter); + rb->iter = rb->iter->left; + } else { + rb->iter = top(rb->rstack); + pop(rb->rstack); + res = rb->iter; + rb->iter = rb->iter->right; + break; + } + } + return res; +} + +void *rb_node_key(struct rbnode *node) +{ + return node ? node->key : 0; +} + +int rb_node_keyi(struct rbnode *node) +{ + return node ? PTR2INT(node->key) : 0; +} + +void *rb_node_data(struct rbnode *node) +{ + return node ? node->data : 0; +} + +static int cmpaddr(const void *ap, const void *bp) +{ + return ap < bp ? -1 : (ap > bp ? 1 : 0); +} + +static int cmpint(const void *ap, const void *bp) +{ + return PTR2INT(ap) - PTR2INT(bp); +} + + +/* ---- left-leaning 2-3 red-black implementation ---- */ + +/* helper prototypes */ +static int is_red(struct rbnode *tree); +static void color_flip(struct rbnode *tree); +static struct rbnode *rot_left(struct rbnode *a); +static struct rbnode *rot_right(struct rbnode *a); +static struct rbnode *find_min(struct rbnode *tree); +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree); +/*static struct rbnode *move_red_right(struct rbnode *tree);*/ +static struct rbnode *move_red_left(struct rbnode *tree); +static struct rbnode *fix_up(struct rbnode *tree); + +static int count_nodes(struct rbnode *node) +{ + if(!node) + return 0; + + return 1 + count_nodes(node->left) + count_nodes(node->right); +} + +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls) +{ + if(!node) + return; + + del_tree(node->left, delfunc, cls); + del_tree(node->right, delfunc, cls); + + if(delfunc) { + delfunc(node, cls); + } + free(node); +} + +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data) +{ + int cmp; + + if(!tree) { + struct rbnode *node = rb->alloc(sizeof *node); + node->red = 1; + node->key = key; + node->data = data; + node->left = node->right = 0; + return node; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + tree->left = insert(rb, tree->left, key, data); + } else if(cmp > 0) { + tree->right = insert(rb, tree->right, key, data); + } else { + tree->data = data; + } + + /* fix right-leaning reds */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* fix two reds in a row */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + + /* if 4-node, split it by color inversion */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + + return tree; +} + +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key) +{ + int cmp; + + if(!tree) { + return 0; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = delete(rb, tree->left, key); + } else { + /* need reds on the right */ + if(is_red(tree->left)) { + tree = rot_right(tree); + } + + /* found it at the bottom (XXX what certifies left is null?) */ + if(cmp == 0 && !tree->right) { + if(rb->del) { + rb->del(tree, rb->del_cls); + } + rb->free(tree); + return 0; + } + + if(!is_red(tree->right) && !is_red(tree->right->left)) { + tree = move_red_left(tree); + } + + if(key == tree->key) { + struct rbnode *rmin = find_min(tree->right); + tree->key = rmin->key; + tree->data = rmin->data; + tree->right = del_min(rb, tree->right); + } else { + tree->right = delete(rb, tree->right, key); + } + } + + return fix_up(tree); +} + +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key) +{ + int cmp; + + if(!node) + return 0; + + if((cmp = rb->cmp(key, node->key)) == 0) { + return node; + } + return find(rb, cmp < 0 ? node->left : node->right, key); +}*/ + +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls) +{ + if(!node) + return; + + traverse(node->left, func, cls); + func(node, cls); + traverse(node->right, func, cls); +} + +/* helpers */ + +static int is_red(struct rbnode *tree) +{ + return tree && tree->red; +} + +static void color_flip(struct rbnode *tree) +{ + tree->red = !tree->red; + tree->left->red = !tree->left->red; + tree->right->red = !tree->right->red; +} + +static struct rbnode *rot_left(struct rbnode *a) +{ + struct rbnode *b = a->right; + a->right = b->left; + b->left = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *rot_right(struct rbnode *a) +{ + struct rbnode *b = a->left; + a->left = b->right; + b->right = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *find_min(struct rbnode *tree) +{ + if(!tree) + return 0; + + while(tree->left) { + tree = tree->left; + } + return tree; +} + +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree) +{ + if(!tree->left) { + if(rb->del) { + rb->del(tree->left, rb->del_cls); + } + rb->free(tree->left); + return 0; + } + + /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */ + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = del_min(rb, tree->left); + + /* fix right-reds, red-reds, and split 4-nodes on the way up */ + return fix_up(tree); +} + +#if 0 +/* push a red link on this node to the right */ +static struct rbnode *move_red_right(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the right */ + color_flip(tree); + + /* if after the flip we've got a red-red situation to the left, fix it */ + if(is_red(tree->left->left)) { + tree = rot_right(tree); + color_flip(tree); + } + return tree; +} +#endif + +/* push a red link on this node to the left */ +static struct rbnode *move_red_left(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the left */ + color_flip(tree); + + /* if after the flip we've got a red-red on the right-left, fix it */ + if(is_red(tree->right->left)) { + tree->right = rot_right(tree->right); + tree = rot_left(tree); + color_flip(tree); + } + return tree; +} + +static struct rbnode *fix_up(struct rbnode *tree) +{ + /* fix right-leaning */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* change invalid red-red pairs into a proper 4-node */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + /* split 4-nodes */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + return tree; +} diff --git a/src/rbtree.h b/src/rbtree.h new file mode 100644 index 0000000..8688c7f --- /dev/null +++ b/src/rbtree.h @@ -0,0 +1,78 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. + */ +#ifndef RBTREE_H_ +#define RBTREE_H_ + +struct rbtree; + + +struct rbnode { + void *key, *data; + int red; + struct rbnode *left, *right; + struct rbnode *next; /* for iterator stack */ +}; + + +typedef void *(*rb_alloc_func_t)(size_t); +typedef void (*rb_free_func_t)(void*); + +typedef int (*rb_cmp_func_t)(const void*, const void*); +typedef void (*rb_del_func_t)(struct rbnode*, void*); + +#define RB_KEY_ADDR (rb_cmp_func_t)(0) +#define RB_KEY_INT (rb_cmp_func_t)(1) +#define RB_KEY_STRING (rb_cmp_func_t)(3) + + +#ifdef __cplusplus +extern "C" { +#endif + +struct rbtree *rb_create(rb_cmp_func_t cmp_func); +void rb_free(struct rbtree *rb); + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); +void rb_destroy(struct rbtree *rb); + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); +/* TODO add user deep copy function */ + +void rb_clear(struct rbtree *rb); +int rb_copy(struct rbtree *dest, struct rbtree *src); + +int rb_size(struct rbtree *rb); + +int rb_insert(struct rbtree *rb, void *key, void *data); +int rb_inserti(struct rbtree *rb, int key, void *data); + +int rb_delete(struct rbtree *rb, void *key); +int rb_deletei(struct rbtree *rb, int key); + +struct rbnode *rb_find(struct rbtree *rb, void *key); +struct rbnode *rb_findi(struct rbtree *rb, int key); + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); + +struct rbnode *rb_root(struct rbtree *rb); + +void rb_begin(struct rbtree *rb); +struct rbnode *rb_next(struct rbtree *rb); + +void *rb_node_key(struct rbnode *node); +int rb_node_keyi(struct rbnode *node); +void *rb_node_data(struct rbnode *node); + +#ifdef __cplusplus +} +#endif + + +#endif /* RBTREE_H_ */ diff --git a/src/vmath.h b/src/vmath.h index d8c6be2..7e35cc8 100644 --- a/src/vmath.h +++ b/src/vmath.h @@ -1,6 +1,8 @@ #ifndef VMATH_H_ #define VMATH_H_ +#include + #ifdef __GNUC__ #define INLINE __inline @@ -11,6 +13,7 @@ #define INLINE #endif +typedef struct { float x, y; } vec2_t; typedef struct { float x, y, z; } vec3_t; typedef struct { float x, y, z, w; } vec4_t; -- 1.7.10.4