# HG changeset patch # User John Tsiombikas # Date 1334525198 -10800 # Node ID 8d7233ff61d35f99ffb16a12cd4c9179c65b88c4 # Parent b266386d19ceeb6d72188e59404087b711d09deb# Parent 2c0baa1fd4190e9ebf5048f0cf86b95448eced06 merged fixes with rbshell diff -r b266386d19ce -r 8d7233ff61d3 .hgignore --- a/.hgignore Mon Apr 16 00:25:05 2012 +0300 +++ b/.hgignore Mon Apr 16 00:26:38 2012 +0300 @@ -4,3 +4,4 @@ ^Makefile$ rbtree\.a$ rbtree\.so +^test/.*test$ diff -r b266386d19ce -r 8d7233ff61d3 src/rbtree.c --- a/src/rbtree.c Mon Apr 16 00:25:05 2012 +0300 +++ b/src/rbtree.c Mon Apr 16 00:26:38 2012 +0300 @@ -261,7 +261,9 @@ del_tree(node->left, delfunc, cls); del_tree(node->right, delfunc, cls); - delfunc(node, cls); + if(delfunc) { + delfunc(node, cls); + } free(node); } diff -r b266386d19ce -r 8d7233ff61d3 src/rbtree.h --- a/src/rbtree.h Mon Apr 16 00:25:05 2012 +0300 +++ b/src/rbtree.h Mon Apr 16 00:26:38 2012 +0300 @@ -36,6 +36,7 @@ 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); diff -r b266386d19ce -r 8d7233ff61d3 test/rbshell/Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/rbshell/Makefile Mon Apr 16 00:26:38 2012 +0300 @@ -0,0 +1,14 @@ +src = $(wildcard *.c) +obj = $(src:.c=.o) +bin = test + +CC = gcc +CFLAGS = -pedantic -Wall -g -I../../src -I/usr/local/include +LDFLAGS = -L../.. -L/usr/local/lib -lrbtree + +$(bin): $(obj) + $(CC) -o $@ $(obj) $(LDFLAGS) + +.PHONY: clean +clean: + rm -f $(obj) $(bin) diff -r b266386d19ce -r 8d7233ff61d3 test/rbshell/sym.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/rbshell/sym.c Mon Apr 16 00:26:38 2012 +0300 @@ -0,0 +1,73 @@ +#include +#include +#include +#include "sym.h" +#include "rbtree.h" + +struct symbol { + char *name; + int id, arity; +}; + +static void del_func(struct rbnode *node, void *cls); + +struct rbtree *symbols; + +int init_sym(void) +{ + if(!(symbols = rb_create(RB_KEY_STRING))) { + fprintf(stderr, "failed to create symbol table\n"); + return -1; + } + rb_set_delete_func(symbols, del_func, 0); + return 0; +} + +void destroy_sym(void) +{ + rb_free(symbols); +} + +int add_sym(const char *name, int id, int arity) +{ + struct symbol *sym; + + if(!(sym = malloc(sizeof *sym)) || !(sym->name = malloc(strlen(name) + 1))) { + perror("failed to allocate symbol"); + free(sym); + return -1; + } + strcpy(sym->name, name); + sym->id = id; + sym->arity = arity; + + return rb_insert(symbols, sym->name, sym); +} + +int sym_lookup(const char *str) +{ + struct rbnode *node; + + if(!(node = rb_find(symbols, (char*)str))) { + fprintf(stderr, "undefined symbol: %s\n", str); + return -1; + } + return ((struct symbol*)node->data)->id; +} + +int sym_arity(const char *str) +{ + struct rbnode *node; + + if(!(node = rb_find(symbols, (char*)str))) { + fprintf(stderr, "undefined symbol: %s\n", str); + return -1; + } + return ((struct symbol*)node->data)->arity; +} + +static void del_func(struct rbnode *node, void *cls) +{ + free(((struct symbol*)node->data)->name); + free(node->data); +} diff -r b266386d19ce -r 8d7233ff61d3 test/rbshell/sym.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/rbshell/sym.h Mon Apr 16 00:26:38 2012 +0300 @@ -0,0 +1,12 @@ +#ifndef SYM_H_ +#define SYM_H_ + +int init_sym(void); +void destroy_sym(void); + +int add_sym(const char *name, int id, int arity); + +int sym_lookup(const char *str); +int sym_arity(const char *str); + +#endif /* SYM_H_ */ diff -r b266386d19ce -r 8d7233ff61d3 test/rbshell/test.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/rbshell/test.c Mon Apr 16 00:26:38 2012 +0300 @@ -0,0 +1,214 @@ +#include +#include +#include +#include +#include "rbtree.h" +#include "sym.h" + +#define SEP " \t\r\n,\"\'" + +/* commands */ +enum { + CMD_CREATE, + CMD_DESTROY, + CMD_CLEAR, + CMD_COPY, + CMD_SIZE, + CMD_INSERT, + CMD_DELETE, + CMD_FIND, + CMD_PRINT, + + MAX_CMD +}; + +int runcmd(int cmd, int argc, char **argv); + +#define NUM_TREES 8 +struct rbtree *trees[NUM_TREES]; + + +int main(void) +{ + char buf[512]; + + /* init symbol table */ + if(init_sym() == -1) { + return 1; + } + add_sym("create", CMD_CREATE, 0); + add_sym("destroy", CMD_DESTROY, 1); + add_sym("clear", CMD_CLEAR, 1); + add_sym("copy", CMD_COPY, 2); + add_sym("size", CMD_SIZE, 1); + add_sym("insert", CMD_INSERT, 2); + add_sym("delete", CMD_DELETE, 2); + add_sym("find", CMD_FIND, 2); + add_sym("print", CMD_PRINT, 1); + + for(;;) { + int argc = 0; + char *argv[8]; + int cmd_id, cmd_arity; + + printf("rbshell> "); + fflush(stdout); + + if(!fgets(buf, sizeof buf, stdin)) { + putchar('\n'); + break; + } + + if(!(argv[argc] = strtok(buf, SEP)) || argv[argc][0] == '#') { + return 0; /* empty / comment */ + } + argc++; + + if((cmd_id = sym_lookup(argv[0])) == -1) { + continue; + } + cmd_arity = sym_arity(argv[0]); + + while((argv[argc] = strtok(0, SEP))) { + argc++; + if(argc >= sizeof argv / sizeof *argv) { + break; + } + } + + if(argc - 1 != cmd_arity) { + fprintf(stderr, "too many (%d) arguments for %s, expected %d\n", argc - 1, argv[0], cmd_arity); + continue; + } + + runcmd(cmd_id, argc, argv); + } + + destroy_sym(); + return 0; +} + +#define CHECKINT(i) \ + if(!isdigit(argv[i][0])) { \ + fprintf(stderr, "expected number, got: %s\n", argv[i]); \ + return -1; \ + } + +#define CHECKVALID(idx) \ + if((idx) < 0 || (idx) >= NUM_TREES || !trees[idx]) { \ + fprintf(stderr, "invalid tree specified: %d\n", idx); \ + return -1; \ + } + + +int runcmd(int cmd, int argc, char **argv) +{ + int i, idx, idx2, n; + struct rbnode *node; + + switch(cmd) { + case CMD_CREATE: + for(i=0; i %d\n", idx, idx2); + break; + + case CMD_SIZE: + CHECKINT(1); + idx = atoi(argv[1]); + CHECKVALID(idx); + + printf("tree size: %d\n", rb_size(trees[idx])); + break; + + case CMD_INSERT: + CHECKINT(1); + CHECKINT(2); + idx = atoi(argv[1]); + CHECKVALID(idx); + + n = atoi(argv[2]); + rb_inserti(trees[idx], n, 0); + printf("inserted: %d\n", n); + break; + + case CMD_DELETE: + case CMD_FIND: + CHECKINT(1); + CHECKINT(2); + idx = atoi(argv[1]); + CHECKVALID(idx); + n = atoi(argv[2]); + + if(!rb_findi(trees[idx], n)) { + fprintf(stderr, "%d not found\n", n); + } else { + if(cmd == CMD_DELETE) { + rb_deletei(trees[idx], n); + printf("deleted %d\n", n); + } else { + printf("found %d\n", n); + } + } + break; + + case CMD_PRINT: + CHECKINT(1); + idx = atoi(argv[1]); + CHECKVALID(idx); + + rb_begin(trees[idx]); + while((node = rb_next(trees[idx]))) { + printf("%d ", rb_node_keyi(node)); + } + putchar('\n'); + break; + + default: + /* can't happen */ + break; + } + return 0; +}