From 06a83976694c970fcf42bfdfc91832e780ca4747 Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Thu, 28 Feb 2019 21:16:27 +0200 Subject: [PATCH] mesh loading --- Makefile | 10 +- src/cmesh.c | 68 ++++++++ src/cmesh.h | 9 + src/gamescr.c | 10 ++ src/meshload.c | 125 ++++---------- src/rbtree.c | 505 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/rbtree.h | 78 +++++++++ src/screen.c | 32 ++-- src/screen.h | 2 +- 9 files changed, 729 insertions(+), 110 deletions(-) create mode 100644 src/rbtree.c create mode 100644 src/rbtree.h diff --git a/Makefile b/Makefile index 3b1335d..94ecd85 100644 --- a/Makefile +++ b/Makefile @@ -4,7 +4,11 @@ dep = $(obj:.o=.d) bin = vrtris -CFLAGS = -pedantic -Wall -g `pkg-config --cflags sdl2` +warn = -pedantic -Wall -Wno-pointer-to-int-cast -Wno-int-to-pointer-cast +dbg = -g +opt = -O0 + +CFLAGS = $(warn) $(dbg) $(opt) `pkg-config --cflags sdl2` LDFLAGS = $(libsys) $(libgl) `pkg-config --libs sdl2` -ldrawtext -lgoatvr \ -limago -lm @@ -29,6 +33,10 @@ $(bin): $(obj) -include $(dep) +%.d: %.c + @echo depfile $@ + @$(CPP) $(CFLAGS) $< -MM -MT $(@:.d=.o) >$@ + .PHONY: cross cross: $(MAKE) CC=i686-w64-mingw32-gcc sys=mingw diff --git a/src/cmesh.c b/src/cmesh.c index 4d74251..3190576 100644 --- a/src/cmesh.c +++ b/src/cmesh.c @@ -366,6 +366,64 @@ int cmesh_attrib_count(struct cmesh *cm, int attr) return cmesh_has_attrib(cm, attr) ? cm->nverts : 0; } +int cmesh_push_attrib(struct cmesh *cm, int attr, float *v) +{ + float *vptr; + int i; + int cursz = dynarr_size(cm->vattr[attr].data); + int newsz = cursz + cm->vattr[attr].nelem; + + if(!(vptr = dynarr_resize(cm->vattr[attr].data, newsz))) { + return -1; + } + cm->vattr[attr].data = vptr; + vptr += cursz; + for(i=0; ivattr[attr].nelem; i++) { + *vptr++ = *v++; + } + cm->vattr[attr].vbo_valid = 0; + return 0; +} + +int cmesh_push_attrib1f(struct cmesh *cm, int attr, float x) +{ + float v[4]; + v[0] = x; + v[1] = v[2] = 0.0f; + v[3] = 1.0f; + return cmesh_push_attrib(cm, attr, v); +} + +int cmesh_push_attrib2f(struct cmesh *cm, int attr, float x, float y) +{ + float v[4]; + v[0] = x; + v[1] = y; + v[2] = 0.0f; + v[3] = 1.0f; + return cmesh_push_attrib(cm, attr, v); +} + +int cmesh_push_attrib3f(struct cmesh *cm, int attr, float x, float y, float z) +{ + float v[4]; + v[0] = x; + v[1] = y; + v[2] = z; + v[3] = 1.0f; + return cmesh_push_attrib(cm, attr, v); +} + +int cmesh_push_attrib4f(struct cmesh *cm, int attr, float x, float y, float z, float w) +{ + float v[4]; + v[0] = x; + v[1] = y; + v[2] = z; + v[3] = w; + return cmesh_push_attrib(cm, attr, v); +} + /* indices can be 0, in which case only memory is allocated * returns pointer to the index array */ @@ -435,6 +493,16 @@ int cmesh_index_count(struct cmesh *cm) return cm->nfaces * 3; } +int cmesh_push_index(struct cmesh *cm, unsigned int idx) +{ + unsigned int *iptr; + if(!(iptr = dynarr_push(cm->idata, &idx))) { + return -1; + } + cm->idata = iptr; + return 0; +} + int cmesh_poly_count(struct cmesh *cm) { if(cm->nfaces) { diff --git a/src/cmesh.h b/src/cmesh.h index a73cd20..8745c2b 100644 --- a/src/cmesh.h +++ b/src/cmesh.h @@ -51,6 +51,11 @@ const float *cmesh_attrib_ro(struct cmesh *cm, int attr); /* doesn't invalidate float *cmesh_attrib_at(struct cmesh *cm, int attr, int idx); const float *cmesh_attrib_at_ro(struct cmesh *cm, int attr, int idx); int cmesh_attrib_count(struct cmesh *cm, int attr); +int cmesh_push_attrib(struct cmesh *cm, int attr, float *v); +int cmesh_push_attrib1f(struct cmesh *cm, int attr, float x); +int cmesh_push_attrib2f(struct cmesh *cm, int attr, float x, float y); +int cmesh_push_attrib3f(struct cmesh *cm, int attr, float x, float y, float z); +int cmesh_push_attrib4f(struct cmesh *cm, int attr, float x, float y, float z, float w); /* indices can be 0, in which case only memory is allocated * returns pointer to the index array @@ -59,6 +64,7 @@ unsigned int *cmesh_set_index(struct cmesh *cm, int num, const unsigned int *ind unsigned int *cmesh_index(struct cmesh *cm); /* invalidates IBO */ const unsigned int *cmesh_index_ro(struct cmesh *cm); /* doesn't invalidate */ int cmesh_index_count(struct cmesh *cm); +int cmesh_push_index(struct cmesh *cm, unsigned int idx); int cmesh_poly_count(struct cmesh *cm); @@ -109,6 +115,9 @@ void cmesh_texcoord_gen_plane(struct cmesh *cm, cgm_vec3 *norm, cgm_vec3 *tang); void cmesh_texcoord_gen_box(struct cmesh *cm); void cmesh_texcoord_gen_cylinder(struct cmesh *cm); + +int cmesh_load(struct cmesh *cm, const char *fname); + int cmesh_dump(struct cmesh *cm, const char *fname); int cmesh_dump_file(struct cmesh *cm, FILE *fp); int cmesh_dump_obj(struct cmesh *cm, const char *fname); diff --git a/src/gamescr.c b/src/gamescr.c index de314ae..52db999 100644 --- a/src/gamescr.c +++ b/src/gamescr.c @@ -1,4 +1,5 @@ #include "screen.h" +#include "cmesh.h" static int init(void); static void cleanup(void); @@ -29,14 +30,23 @@ struct game_screen game_screen = { wheel }; +static struct cmesh *blkmesh; static int init(void) { + if(!(blkmesh = cmesh_alloc())) { + return -1; + } + if(cmesh_load(blkmesh, "data/noisecube.obj") == -1) { + fprintf(stderr, "failed to load block model\n"); + return -1; + } return 0; } static void cleanup(void) { + cmesh_free(blkmesh); } static void start(void) diff --git a/src/meshload.c b/src/meshload.c index f9ee26f..ef596a1 100644 --- a/src/meshload.c +++ b/src/meshload.c @@ -1,12 +1,10 @@ -#if 0 #include #include #include #include -#include "mesh.h" +#include "cmesh.h" #include "dynarr.h" #include "rbtree.h" -#include "util.h" struct vertex_pos_color { float x, y, z; @@ -29,19 +27,19 @@ static void free_rbnode_key(struct rbnode *n, void *cls); * to the same triplet if it has been encountered before. That index is * appended to the index buffer. * - * If a particular triplet has not been encountered before, a new g3d_vertex is + * If a particular triplet has not been encountered before, a new vertex is * appended to the vertex buffer. The index of this new vertex is appended to * the index buffer, and also inserted into the tree for future searches. */ -int load_mesh(struct g3d_mesh *mesh, const char *fname) +int cmesh_load(struct cmesh *mesh, const char *fname) { int i, line_num = 0, result = -1; int found_quad = 0; FILE *fp = 0; char buf[256]; struct vertex_pos_color *varr = 0; - vec3_t *narr = 0; - vec2_t *tarr = 0; + cgm_vec3 *narr = 0; + cgm_vec2 *tarr = 0; struct rbtree *rbtree = 0; if(!(fp = fopen(fname, "rb"))) { @@ -55,11 +53,6 @@ int load_mesh(struct g3d_mesh *mesh, const char *fname) } 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))) { @@ -102,7 +95,7 @@ int load_mesh(struct g3d_mesh *mesh, const char *fname) } else if(line[1] == 't' && isspace(line[2])) { /* texcoord */ - vec2_t tc; + cgm_vec2 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; @@ -114,7 +107,7 @@ int load_mesh(struct g3d_mesh *mesh, const char *fname) } else if(line[1] == 'n' && isspace(line[2])) { /* normal */ - vec3_t norm; + cgm_vec3 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; @@ -147,53 +140,41 @@ int load_mesh(struct g3d_mesh *mesh, const char *fname) } if((node = rb_find(rbtree, &fv))) { - uint16_t idx = (int)(intptr_t)node->data; - if(!(mesh->iarr = dynarr_push(mesh->iarr, &idx))) { + unsigned int idx = (unsigned int)node->data; + if(cmesh_push_index(mesh, idx) == -1) { fprintf(stderr, "load_mesh: failed to resize index array\n"); goto err; } } else { - uint16_t newidx = dynarr_size(mesh->varr); - struct g3d_vertex v; + unsigned int newidx = cmesh_attrib_count(mesh, CMESH_ATTR_VERTEX); struct facevertex *newfv; + struct vertex_pos_color *vptr = varr + fv.vidx; + float tu, tv; - v.x = varr[fv.vidx].x; - v.y = varr[fv.vidx].y; - v.z = varr[fv.vidx].z; - v.w = 1.0f; - v.r = cround64(varr[fv.vidx].r * 255.0); - v.g = cround64(varr[fv.vidx].g * 255.0); - v.b = cround64(varr[fv.vidx].b * 255.0); - v.a = cround64(varr[fv.vidx].a * 255.0); - 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; + if(cmesh_push_attrib3f(mesh, CMESH_ATTR_VERTEX, vptr->x, vptr->y, vptr->z) == -1) { + fprintf(stderr, "load_mesh: failed to resize vertex array\n"); + goto err; } - - if(!(mesh->varr = dynarr_push(mesh->varr, &v))) { - fprintf(stderr, "load_mesh: failed to resize combined vertex array\n"); + if(cmesh_push_attrib(mesh, CMESH_ATTR_COLOR, &vptr->r) == -1) { + fprintf(stderr, "load_mesh: failed to resize color array\n"); goto err; } - if(!(mesh->iarr = dynarr_push(mesh->iarr, &newidx))) { - fprintf(stderr, "load_mesh: failed to resize index array\n"); + if(fv.tidx >= 0) { + tu = tarr[fv.tidx].x; + tv = tarr[fv.tidx].y; + } else { + tu = vptr->x; + tv = vptr->y; + } + if(cmesh_push_attrib2f(mesh, CMESH_ATTR_TEXCOORD, tu, tv) == -1) { + fprintf(stderr, "load_mesh: failed to resize texcoord array\n"); goto err; } if((newfv = malloc(sizeof *newfv))) { *newfv = fv; } - if(!newfv || rb_insert(rbtree, newfv, (void*)(intptr_t)newidx) == -1) { + if(!newfv || rb_insert(rbtree, newfv, (void*)newidx) == -1) { fprintf(stderr, "load_mesh: failed to insert facevertex to the binary search tree\n"); goto err; } @@ -208,69 +189,20 @@ int load_mesh(struct g3d_mesh *mesh, const char *fname) } } - 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); + fname, cmesh_attrib_count(mesh, CMESH_ATTR_VERTEX), cmesh_poly_count(mesh)); 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; } -int save_mesh(struct g3d_mesh *mesh, const char *fname) -{ - int i, fvcount; - FILE *fp; - - if(!(fp = fopen(fname, "wb"))) { - fprintf(stderr, "save_mesh: failed to open %s for writing\n", fname); - return -1; - } - fprintf(fp, "# Wavefront OBJ file shoved in your FACE by Mindlapse. Deal with it\n"); - - for(i=0; ivcount; i++) { - struct g3d_vertex *v = mesh->varr + i; - fprintf(fp, "v %f %f %f %f %f %f %f\n", v->x, v->y, v->z, v->r / 255.0f, v->g / 255.0f, - v->b / 255.0f, v->a / 255.0f); - } - for(i=0; ivcount; i++) { - fprintf(fp, "vn %f %f %f\n", mesh->varr[i].nx, mesh->varr[i].ny, mesh->varr[i].nz); - } - for(i=0; ivcount; i++) { - fprintf(fp, "vt %f %f\n", mesh->varr[i].u, mesh->varr[i].v); - } - - fvcount = mesh->prim; - for(i=0; iicount; i++) { - int idx = mesh->iarr[i] + 1; - - if(fvcount == mesh->prim) { - fprintf(fp, "\nf"); - fvcount = 0; - } - fprintf(fp, " %d/%d/%d", idx, idx, idx); - ++fvcount; - } - fprintf(fp, "\n"); - - fclose(fp); - return 0; -} - static char *clean_line(char *s) { char *end; @@ -347,4 +279,3 @@ static void free_rbnode_key(struct rbnode *n, void *cls) { free(n->key); } -#endif /* 0 */ diff --git a/src/rbtree.c b/src/rbtree.c new file mode 100644 index 0000000..829b511 --- /dev/null +++ b/src/rbtree.c @@ -0,0 +1,505 @@ +/* +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) +{ + if(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/screen.c b/src/screen.c index 9b80cf5..7242a3f 100644 --- a/src/screen.c +++ b/src/screen.c @@ -1,6 +1,7 @@ #include #include "screen.h" #include "opt.h" +#include "logger.h" /* defined in their respective screen source files */ struct game_screen main_menu_screen; @@ -9,8 +10,6 @@ struct game_screen game_screen; static struct game_screen *screens[16]; static int num_screens; -static struct game_screen *stack; - int init_screens(void) { int i = 0; @@ -20,14 +19,15 @@ int init_screens(void) screens[i++] = &game_screen; num_screens = i; - stack = screens[0]; + screen = screens[0]; + screen->next = 0; for(i=0; iinit() == -1) { return -1; } if(opt.start_scr && strcmp(screens[i]->name, opt.start_scr) == 0) { - stack = screens[i]; + screen = screens[i]; } } return 0; @@ -44,27 +44,37 @@ void cleanup_screens(void) void reshape_screens(int x, int y) { - struct game_screen *s = stack; + struct game_screen *s = screen; while(s) { s->reshape(x, y); s = s->next; } } -void push_screen(struct game_screen *s) +int push_screen(struct game_screen *s) { - s->next = stack; - stack = s; + struct game_screen *it = screen; + while(it && it != s) { + it = it->next; + } + if(it == s) { + error_log("attempting to push screen %s more than once!\n", s->name); + return -1; + } + + s->next = screen; + screen = s; s->start(); + return 0; } int pop_screen(void) { struct game_screen *s; - if(!stack->next) return -1; - s = stack; - stack = stack->next; + if(!screen->next) return -1; + s = screen; + screen = screen->next; s->stop(); return 0; } diff --git a/src/screen.h b/src/screen.h index 95cf4df..9aca41d 100644 --- a/src/screen.h +++ b/src/screen.h @@ -32,7 +32,7 @@ int init_screens(void); void cleanup_screens(void); void reshape_screens(int x, int y); -void push_screen(struct game_screen *s); +int push_screen(struct game_screen *s); int pop_screen(void); #endif /* SCREEN_H_ */ -- 1.7.10.4