# HG changeset patch # User John Tsiombikas # Date 1420291745 -7200 # Node ID a71bd70c10141b230013263f3c3ab359366cba07 simple pack-file I/O library diff -r 000000000000 -r a71bd70c1014 .hgignore --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/.hgignore Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,4 @@ +\.o$ +\.swp$ +\.d$ +^libpackio.a$ diff -r 000000000000 -r a71bd70c1014 Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Makefile Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,24 @@ +PREFIX = /usr/local + +src = $(wildcard src/*.c) +obj = $(src:.c=.o) +dep = $(obj:.o=.d) +name = packio + +lib_a = lib$(name).a + +inc = -Iinclude + +CFLAGS = -pedantic -Wall -g $(pic) $(inc) + +$(lib_a): $(obj) + $(AR) rcs $@ $(obj) + +-include $(dep) + +%.d: %.c + @$(CPP) $(CFLAGS) $< -MM -MT $(@:.d=.o) >$@ + +.PHONY: clean +clean: + rm -f $(obj) $(dep) $(lib_a) diff -r 000000000000 -r a71bd70c1014 include/packio.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/include/packio.h Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,59 @@ +#ifndef PACKIO_H_ +#define PACKIO_H_ + +typedef struct pkio_file PKIO_FILE; +typedef struct pkio_dir PKIO_DIR; + +#define PKIO_MAX_NAME 256 +struct pkio_dirent { + char d_name[PKIO_MAX_NAME]; +}; + +struct pkio_stat { + unsigned int st_mode; + unsigned long st_size; +}; + +#ifdef __cplusplus +extern "C" { +#endif + +extern int pkio_errno; + +int pkio_fopen(const char *path); +int pkio_fclose(PKIO_FILE *fp); + +int pkio_fseek(PKIO_FILE *fp, long offset, int whence); +long pkio_ftell(PKIO_FILE *fp); +void pkio_rewind(PKIO_FILE *fp); + +size_t pkio_fread(void *buf, size_t size, size_t nitems, PKIO_FILE *fp); +size_t pkio_fwrite(void *buf, size_t size, size_t nitems, PKIO_FILE *fp); + +int pkio_fgetc(PKIO_FILE *fp); +int pkio_fputc(int c, PKIO_FILE *fp); + +char *pkio_fgets(char *buf, int size, PKIO_FILE *fp); +int pkio_fputs(char *buf, PKIO_FILE *fp); + +int pkio_fscanf(PKIO_FILE *fp, const char *fmt, ...); +int pkio_vfscanf(PKIO_FILE *fp, const char *fmt, va_list ap); +int pkio_fprintf(PKIO_FILE *fp, const char *fmt, ...); +int pkio_vfprintf(PKIO_FILE *fp, const char *fmt, va_list ap); + +void pkio_clearerr(PKIO_FILE *fp); +int pkio_feof(PKIO_FILE *fp); +int pkio_ferror(PKIO_FILE *fp); + +PKIO_DIR *pkio_opendir(const char *dirname); +int pkio_closedir(PKIO_DIR *dir); +struct pkio_dirent *pkio_readdir(PKIO_DIR *dir); +void pkio_rewinddir(PKIO_DIR *dir); + +int pkio_stat(const char *path, struct pkio_stat *buf); + +#ifdef __cplusplus +} +#endif + +#endif /* PACKIO_H_ */ diff -r 000000000000 -r a71bd70c1014 src/packio.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/packio.c Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,6 @@ +#include +#include "packio.h" + +int pkio_fopen(const char *path) +{ +} diff -r 000000000000 -r a71bd70c1014 src/pathmap.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/pathmap.c Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,62 @@ +#include +#include +#include +#include "pathmap.h" +#include "rbtree.h" + +static void map_entry_destructor(struct rbnode *node, void *data); + +static struct rbtree *map; + +int pkio_map(const char *from, const char *to) +{ + char *myfrom, *myto; + + if(!map) { + if(!(map = rb_create(RB_KEY_STRING))) { + fprintf(stderr, "packio: failed to create path mapping tree\n"); + return -1; + } + rb_set_delete_func(map, map_entry_destructor, 0); + } + + if(!(myfrom = malloc(strlen(from) + 1))) { + fprintf(stderr, "packio: failed to allocate mapping source string\n"); + return -1; + } + if(!(myto = malloc(strlen(to) + 1))) { + fprintf(stderr, "packio: failed to allocate mapping destination string\n"); + free(myto); + return -1; + } + strcpy(myfrom, from); + strcpy(myto, to); + + if(rb_insert(map, myfrom, myto) == -1) { + fprintf(stderr, "packio: failed to add path mapping\n"); + free(myfrom); + free(myto); + return -1; + } + return 0; +} + +const char *pkio_pathmap(const char *path) +{ + struct rbnode *node; + + if(!map) { + return path; + } + + if(!(node = rb_find(map, (void*)path))) { + return path; + } + return node->data; +} + +static void map_entry_destructor(struct rbnode *node, void *data) +{ + free(node->key); + free(node->data); +} diff -r 000000000000 -r a71bd70c1014 src/pathmap.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/pathmap.h Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,7 @@ +#ifndef PATH_MAP_H_ +#define PATH_MAP_H_ + +int pkio_map(const char *from, const char *to); +const char *pkio_pathmap(const char *path); + +#endif /* PATH_MAP_H_ */ diff -r 000000000000 -r a71bd70c1014 src/rbtree.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/rbtree.c Sat Jan 03 15:29:05 2015 +0200 @@ -0,0 +1,501 @@ +/* +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) +{ + rb->root = delete(rb, rb->root, key); + rb->root->red = 0; + return 0; +} + +int rb_deletei(struct rbtree *rb, int key) +{ + 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 -r 000000000000 -r a71bd70c1014 src/rbtree.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/rbtree.h Sat Jan 03 15:29:05 2015 +0200 @@ -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_ */