Mercurial > hg > ucx / changeset

     1.1 --- a/Makefile	Tue Oct 17 15:15:54 2017 +0200
     1.2 +++ b/Makefile	Tue Oct 17 16:15:41 2017 +0200
     1.3 @@ -45,10 +45,10 @@
     1.4  all: ucx test
     1.5  
     1.6  ucx: FORCE
     1.7 -	cd ucx; $(MAKE) CONF=$(CONF)
     1.8 +	cd src; $(MAKE) CONF=$(CONF)
     1.9  
    1.10  ucx-debug: FORCE
    1.11 -	cd ucx; $(MAKE) CONF=$(CONF) debug
    1.12 +	cd src; $(MAKE) CONF=$(CONF) debug
    1.13  	
    1.14  test: ucx FORCE
    1.15  	cd test; $(MAKE) CONF=$(CONF)
    1.16 @@ -67,7 +67,7 @@
    1.17  install: ucx $(DESTDIR)$(PREFIX)/lib $(DESTDIR)$(PREFIX)/include/ucx
    1.18  	cp ./build/release/libucx$(LIB_EXT) $(DESTDIR)$(PREFIX)/lib && \
    1.19  	cp ./build/release/libucx$(SO_EXT) $(DESTDIR)$(PREFIX)/lib && \
    1.20 -        cp ./ucx/*.h $(DESTDIR)$(PREFIX)/include/ucx
    1.21 +        cp ./src/ucx/*.h $(DESTDIR)$(PREFIX)/include/ucx
    1.22  
    1.23  uninstall:
    1.24  	$(RM) $(RMFLAGS) $(DESTDIR)$(PREFIX)/include/ucx &&\

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/Makefile	Tue Oct 17 16:15:41 2017 +0200
     2.3 @@ -0,0 +1,79 @@
     2.4 +#
     2.5 +# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     2.6 +#
     2.7 +# Copyright 2017 Olaf Wintermann. All rights reserved.
     2.8 +#
     2.9 +# Redistribution and use in source and binary forms, with or without
    2.10 +# modification, are permitted provided that the following conditions are met:
    2.11 +#
    2.12 +#   1. Redistributions of source code must retain the above copyright
    2.13 +#      notice, this list of conditions and the following disclaimer.
    2.14 +#
    2.15 +#   2. Redistributions in binary form must reproduce the above copyright
    2.16 +#      notice, this list of conditions and the following disclaimer in the
    2.17 +#      documentation and/or other materials provided with the distribution.
    2.18 +#
    2.19 +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    2.20 +# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    2.21 +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    2.22 +# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    2.23 +# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    2.24 +# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    2.25 +# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    2.26 +# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    2.27 +# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    2.28 +# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    2.29 +# POSSIBILITY OF SUCH DAMAGE.
    2.30 +#
    2.31 +
    2.32 +include ../$(CONF).mk
    2.33 +include ../cppcheck.mk
    2.34 +
    2.35 +# list of source files
    2.36 +SRC  = utils.c
    2.37 +SRC += list.c
    2.38 +SRC += map.c
    2.39 +SRC += avl.c
    2.40 +SRC += properties.c
    2.41 +SRC += mempool.c
    2.42 +SRC += string.c
    2.43 +SRC += test.c
    2.44 +SRC += allocator.c
    2.45 +SRC += logging.c
    2.46 +SRC += buffer.c
    2.47 +SRC += stack.c
    2.48 +
    2.49 +OBJ   = $(SRC:%.c=../build/release/ucx/%$(OBJ_EXT))
    2.50 +OBJ_D = $(SRC:%.c=../build/debug/ucx/%$(OBJ_EXT))
    2.51 +
    2.52 +all: ../build/release/ucx \
    2.53 +	../build/release/libucx$(LIB_EXT) ../build/release/libucx$(SO_EXT)
    2.54 +debug: ../build/debug/ucx \
    2.55 +	../build/debug/libucx$(LIB_EXT) ../build/debug/libucx$(SO_EXT)
    2.56 +
    2.57 +../build/release/libucx$(LIB_EXT): $(OBJ)
    2.58 +	$(AR) $(ARFLAGS) ../build/release/libucx$(LIB_EXT) $(OBJ)
    2.59 +
    2.60 +../build/release/libucx$(SO_EXT): $(OBJ)
    2.61 +	$(LD) $(SOLDFLAGS) -o ../build/release/libucx$(SO_EXT) $(OBJ)
    2.62 +
    2.63 +../build/release/ucx/%$(OBJ_EXT): %.c
    2.64 +	$(CC) $(CFLAGS) -I. -o $@ -c $<
    2.65 +
    2.66 +../build/release/ucx:
    2.67 +	$(MKDIR) $(MKDIRFLAGS) ../build/release/ucx
    2.68 +
    2.69 +../build/debug/libucx$(LIB_EXT): $(OBJ_D)
    2.70 +	$(AR) $(ARFLAGS) ../build/debug/libucx$(LIB_EXT) $(OBJ_D)
    2.71 +	
    2.72 +../build/debug/libucx$(SO_EXT): $(OBJ_D)
    2.73 +	$(LD) $(SOLDFLAGS) -o ../build/debug/libucx$(SO_EXT) $(OBJ_D)
    2.74 +
    2.75 +../build/debug/ucx/%$(OBJ_EXT): %.c
    2.76 +	$(CC) $(CFLAGS_D) -I. -o $@ -c $<
    2.77 +
    2.78 +../build/debug/ucx:
    2.79 +	$(MKDIR) $(MKDIRFLAGS) ../build/debug/ucx
    2.80 +
    2.81 +cppcheck: $(SRC)
    2.82 +	$(CPPCHECK) $(CPPCHECK_CONFIG) $(CPPCHECK_FLAGS) $+ 2>> ../$(CPPCHECK_LOG)

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/allocator.c	Tue Oct 17 16:15:41 2017 +0200
     3.3 @@ -0,0 +1,60 @@
     3.4 +/*
     3.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     3.6 + *
     3.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     3.8 + *
     3.9 + * Redistribution and use in source and binary forms, with or without
    3.10 + * modification, are permitted provided that the following conditions are met:
    3.11 + *
    3.12 + *   1. Redistributions of source code must retain the above copyright
    3.13 + *      notice, this list of conditions and the following disclaimer.
    3.14 + *
    3.15 + *   2. Redistributions in binary form must reproduce the above copyright
    3.16 + *      notice, this list of conditions and the following disclaimer in the
    3.17 + *      documentation and/or other materials provided with the distribution.
    3.18 + *
    3.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    3.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    3.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    3.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    3.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    3.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    3.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    3.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    3.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    3.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    3.29 + * POSSIBILITY OF SUCH DAMAGE.
    3.30 + */
    3.31 +
    3.32 +#include "ucx/allocator.h"
    3.33 +
    3.34 +#include <stdlib.h>
    3.35 +
    3.36 +UcxAllocator default_allocator = {
    3.37 +    NULL,
    3.38 +    ucx_default_malloc,
    3.39 +    ucx_default_calloc,
    3.40 +    ucx_default_realloc,
    3.41 +    ucx_default_free
    3.42 +};
    3.43 +
    3.44 +UcxAllocator *ucx_default_allocator() {
    3.45 +    UcxAllocator *allocator = &default_allocator;
    3.46 +    return allocator;
    3.47 +}
    3.48 +
    3.49 +void *ucx_default_malloc(void *ignore, size_t n) {
    3.50 +    return malloc(n);
    3.51 +}
    3.52 +
    3.53 +void *ucx_default_calloc(void *ignore, size_t n, size_t size) {
    3.54 +    return calloc(n, size);
    3.55 +}
    3.56 +
    3.57 +void *ucx_default_realloc(void *ignore, void *data, size_t n) {
    3.58 +    return realloc(data, n);
    3.59 +}
    3.60 +
    3.61 +void ucx_default_free(void *ignore, void *data) {
    3.62 +    free(data);
    3.63 +}

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/avl.c	Tue Oct 17 16:15:41 2017 +0200
     4.3 @@ -0,0 +1,356 @@
     4.4 +/*
     4.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     4.6 + *
     4.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     4.8 + *
     4.9 + * Redistribution and use in source and binary forms, with or without
    4.10 + * modification, are permitted provided that the following conditions are met:
    4.11 + *
    4.12 + *   1. Redistributions of source code must retain the above copyright
    4.13 + *      notice, this list of conditions and the following disclaimer.
    4.14 + *
    4.15 + *   2. Redistributions in binary form must reproduce the above copyright
    4.16 + *      notice, this list of conditions and the following disclaimer in the
    4.17 + *      documentation and/or other materials provided with the distribution.
    4.18 + *
    4.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    4.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    4.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    4.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    4.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    4.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    4.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    4.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    4.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    4.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    4.29 + * POSSIBILITY OF SUCH DAMAGE.
    4.30 + */
    4.31 +
    4.32 +#include "ucx/avl.h"
    4.33 +
    4.34 +#include <limits.h>
    4.35 +
    4.36 +#define ptrcast(ptr) ((void*)(ptr))
    4.37 +#define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree))
    4.38 +#define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode))
    4.39 +
    4.40 +static void ucx_avl_connect(UcxAVLTree *tree,
    4.41 +        UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) {
    4.42 +    if (child) {
    4.43 +        child->parent = node;
    4.44 +    }
    4.45 +    // if child is NULL, nullkey decides if left or right pointer is cleared
    4.46 +    if (tree->cmpfunc(
    4.47 +        ptrcast(child ? child->key : nullkey),
    4.48 +        ptrcast(node->key), tree->userdata) > 0) {
    4.49 +      node->right = child;
    4.50 +    } else {
    4.51 +      node->left = child;
    4.52 +    }
    4.53 +    size_t lh = node->left ? node->left->height : 0;
    4.54 +    size_t rh = node->right ? node->right->height : 0;
    4.55 +    node->height = 1 + (lh > rh ? lh : rh);
    4.56 +}
    4.57 +
    4.58 +#define avlheight(node) ((node) ? (node)->height : 0)
    4.59 +
    4.60 +static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) {
    4.61 +    UcxAVLNode *p = l0->parent;
    4.62 +    UcxAVLNode *l1 = l0->left;
    4.63 +    if (p) {
    4.64 +        ucx_avl_connect(tree, p, l1, 0);
    4.65 +    } else {
    4.66 +        l1->parent = NULL;
    4.67 +    }
    4.68 +    ucx_avl_connect(tree, l0, l1->right, l1->key);
    4.69 +    ucx_avl_connect(tree, l1, l0, 0);
    4.70 +    return l1;
    4.71 +}
    4.72 +
    4.73 +static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) {
    4.74 +    UcxAVLNode *p = l0->parent;
    4.75 +    UcxAVLNode *l1 = l0->right;
    4.76 +    if (p) {
    4.77 +        ucx_avl_connect(tree, p, l1, 0);
    4.78 +    } else {
    4.79 +        l1->parent = NULL;
    4.80 +    }
    4.81 +    ucx_avl_connect(tree, l0, l1->left, l1->key);
    4.82 +    ucx_avl_connect(tree, l1, l0, 0);
    4.83 +    return l1;
    4.84 +}
    4.85 +
    4.86 +static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) {
    4.87 +    int lh = avlheight(n->left);
    4.88 +    int rh = avlheight(n->right);
    4.89 +    n->height = 1 + (lh > rh ? lh : rh);
    4.90 +    
    4.91 +    if (lh - rh == 2) {
    4.92 +      UcxAVLNode *c = n->left;
    4.93 +      if (avlheight(c->right) - avlheight(c->left) == 1) {
    4.94 +        avl_rotleft(tree, c);
    4.95 +      }
    4.96 +      n = avl_rotright(tree, n);
    4.97 +    } else if (rh - lh == 2) {  
    4.98 +      UcxAVLNode *c = n->right;
    4.99 +      if (avlheight(c->left) - avlheight(c->right) == 1) {
   4.100 +        avl_rotright(tree, c);
   4.101 +      }
   4.102 +      n = avl_rotleft(tree, n);
   4.103 +    }
   4.104 +
   4.105 +    if (n->parent) {
   4.106 +      ucx_avl_balance(tree, n->parent);
   4.107 +    } else {
   4.108 +      tree->root = n;
   4.109 +    }
   4.110 +}
   4.111 +
   4.112 +UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) {
   4.113 +    return ucx_avl_new_a(cmpfunc, ucx_default_allocator());
   4.114 +}
   4.115 +
   4.116 +UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) {
   4.117 +    UcxAVLTree* tree = alloc_tree(allocator);
   4.118 +    if (tree) {
   4.119 +        tree->allocator = allocator;
   4.120 +        tree->cmpfunc = cmpfunc;
   4.121 +        tree->root = NULL;
   4.122 +        tree->userdata = NULL;
   4.123 +    }
   4.124 +    
   4.125 +    return tree;
   4.126 +}
   4.127 +
   4.128 +static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) {
   4.129 +    if (node) {
   4.130 +        ucx_avl_free_node(al, node->left);
   4.131 +        ucx_avl_free_node(al, node->right);
   4.132 +        alfree(al, node);
   4.133 +    }
   4.134 +}
   4.135 +
   4.136 +void ucx_avl_free(UcxAVLTree *tree) {
   4.137 +    UcxAllocator *al = tree->allocator;
   4.138 +    ucx_avl_free_node(al, tree->root);
   4.139 +    alfree(al, tree);
   4.140 +}
   4.141 +
   4.142 +UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {
   4.143 +    UcxAVLNode *n = tree->root;
   4.144 +    int cmpresult;
   4.145 +    while (n && (cmpresult = tree->cmpfunc(
   4.146 +            ptrcast(key), ptrcast(n->key), tree->userdata))) {
   4.147 +        n = cmpresult > 0 ? n->right : n->left;
   4.148 +    }
   4.149 +    return n;
   4.150 +}
   4.151 +
   4.152 +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
   4.153 +    UcxAVLNode *n = ucx_avl_get_node(tree, key);
   4.154 +    return n ? n->value : NULL;
   4.155 +}
   4.156 +
   4.157 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
   4.158 +        distance_func dfnc, int mode) {
   4.159 +    UcxAVLNode *n = tree->root;
   4.160 +    UcxAVLNode *closest = NULL;
   4.161 +
   4.162 +    intmax_t cmpresult;
   4.163 +    intmax_t closest_dist;
   4.164 +    closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
   4.165 +    
   4.166 +    while (n && (cmpresult = dfnc(
   4.167 +            ptrcast(key), ptrcast(n->key), tree->userdata))) {
   4.168 +        if (mode == UCX_AVL_FIND_CLOSEST) {
   4.169 +            intmax_t dist = cmpresult;
   4.170 +            if (dist < 0) dist *= -1;
   4.171 +            if (dist < closest_dist) {
   4.172 +                closest_dist = dist;
   4.173 +                closest = n;
   4.174 +            }
   4.175 +        } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
   4.176 +            if (cmpresult > closest_dist) {
   4.177 +                closest_dist = cmpresult;
   4.178 +                closest = n;
   4.179 +            }
   4.180 +        } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
   4.181 +            if (cmpresult < closest_dist) {
   4.182 +                closest_dist = cmpresult;
   4.183 +                closest = n;
   4.184 +            }
   4.185 +        }
   4.186 +        n = cmpresult > 0 ? n->right : n->left;
   4.187 +    }
   4.188 +    return n ? n : closest;
   4.189 +}
   4.190 +
   4.191 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
   4.192 +        distance_func dfnc, int mode) {
   4.193 +    UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
   4.194 +    return n ? n->value : NULL;
   4.195 +}
   4.196 +
   4.197 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
   4.198 +    return ucx_avl_put_s(tree, key, value, NULL);
   4.199 +}
   4.200 +
   4.201 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,
   4.202 +        void **oldvalue) {
   4.203 +    if (tree->root) {
   4.204 +        UcxAVLNode *n = tree->root;
   4.205 +        int cmpresult;
   4.206 +        while ((cmpresult = tree->cmpfunc(
   4.207 +                ptrcast(key), ptrcast(n->key), tree->userdata))) {
   4.208 +            UcxAVLNode *m = cmpresult > 0 ? n->right : n->left;
   4.209 +            if (m) {
   4.210 +                n = m;
   4.211 +            } else {
   4.212 +                break;
   4.213 +            }
   4.214 +        }
   4.215 +
   4.216 +        if (cmpresult) {
   4.217 +            UcxAVLNode* e = alloc_node(tree->allocator);
   4.218 +            if (e) {
   4.219 +                e->key = key; e->value = value; e->height = 1;
   4.220 +                e->parent = e->left = e->right = NULL;
   4.221 +                ucx_avl_connect(tree, n, e, 0);
   4.222 +                ucx_avl_balance(tree, n);
   4.223 +                return 0;
   4.224 +            } else {
   4.225 +                return 1;
   4.226 +            }
   4.227 +        } else {
   4.228 +            if (oldvalue) {
   4.229 +                *oldvalue = n->value;
   4.230 +            }
   4.231 +            n->value = value;
   4.232 +            return 0;
   4.233 +        }
   4.234 +    } else {
   4.235 +        tree->root = alloc_node(tree->allocator);
   4.236 +        if (tree->root) {
   4.237 +            tree->root->key = key; tree->root->value = value;
   4.238 +            tree->root->height = 1;
   4.239 +            tree->root->parent = tree->root->left = tree->root->right = NULL;
   4.240 +            
   4.241 +            if (oldvalue) {
   4.242 +                *oldvalue = NULL;
   4.243 +            }
   4.244 +            
   4.245 +            return 0;
   4.246 +        } else {
   4.247 +            return 1;
   4.248 +        }
   4.249 +    }
   4.250 +}
   4.251 +
   4.252 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
   4.253 +    return ucx_avl_remove_s(tree, key, NULL, NULL);
   4.254 +}
   4.255 +    
   4.256 +int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) {
   4.257 +    return ucx_avl_remove_s(tree, node->key, NULL, NULL);
   4.258 +}
   4.259 +
   4.260 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
   4.261 +        intptr_t *oldkey, void **oldvalue) {
   4.262 +    
   4.263 +    UcxAVLNode *n = tree->root;
   4.264 +    int cmpresult;
   4.265 +    while (n && (cmpresult = tree->cmpfunc(
   4.266 +            ptrcast(key), ptrcast(n->key), tree->userdata))) {
   4.267 +        n = cmpresult > 0 ? n->right : n->left;
   4.268 +    }
   4.269 +    if (n) {
   4.270 +        if (oldkey) {
   4.271 +            *oldkey = n->key;
   4.272 +        }
   4.273 +        if (oldvalue) {
   4.274 +            *oldvalue = n->value;
   4.275 +        }
   4.276 +        
   4.277 +        UcxAVLNode *p = n->parent;
   4.278 +        if (n->left && n->right) {
   4.279 +            UcxAVLNode *s = n->right;
   4.280 +            while (s->left) {
   4.281 +                s = s->left;
   4.282 +            }
   4.283 +            ucx_avl_connect(tree, s->parent, s->right, s->key);
   4.284 +            n->key = s->key; n->value = s->value;
   4.285 +            p = s->parent;
   4.286 +            alfree(tree->allocator, s);
   4.287 +        } else {
   4.288 +            if (p) {
   4.289 +                ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key);
   4.290 +            } else {
   4.291 +                tree->root = n->right ? n->right : n->left;
   4.292 +                if (tree->root) {
   4.293 +                    tree->root->parent = NULL;
   4.294 +                }
   4.295 +            }
   4.296 +            alfree(tree->allocator, n);
   4.297 +        }
   4.298 +
   4.299 +        if (p) {
   4.300 +            ucx_avl_balance(tree, p);
   4.301 +        }
   4.302 +        
   4.303 +        return 0;
   4.304 +    } else {
   4.305 +        return 1;
   4.306 +    }
   4.307 +}
   4.308 +
   4.309 +static size_t ucx_avl_countn(UcxAVLNode *node) {
   4.310 +    if (node) {
   4.311 +        return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right);
   4.312 +    } else {
   4.313 +        return 0;
   4.314 +    }
   4.315 +}
   4.316 +
   4.317 +size_t ucx_avl_count(UcxAVLTree *tree) {
   4.318 +    return ucx_avl_countn(tree->root);
   4.319 +}
   4.320 +
   4.321 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
   4.322 +    if (node->left) {
   4.323 +        UcxAVLNode* n = node->left;
   4.324 +        while (n->right) {
   4.325 +            n = n->right;
   4.326 +        }
   4.327 +        return n;
   4.328 +    } else {
   4.329 +        UcxAVLNode* n = node;
   4.330 +        while (n->parent) {
   4.331 +            if (n->parent->right == n) {
   4.332 +                return n->parent;
   4.333 +            } else {
   4.334 +                n = n->parent;
   4.335 +            }
   4.336 +        }
   4.337 +        return NULL;
   4.338 +    }
   4.339 +}
   4.340 +
   4.341 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
   4.342 +    if (node->right) {
   4.343 +        UcxAVLNode* n = node->right;
   4.344 +        while (n->left) {
   4.345 +            n = n->left;
   4.346 +        }
   4.347 +        return n;
   4.348 +    } else {
   4.349 +        UcxAVLNode* n = node;
   4.350 +        while (n->parent) {
   4.351 +            if (n->parent->left == n) {
   4.352 +                return n->parent;
   4.353 +            } else {
   4.354 +                n = n->parent;
   4.355 +            }
   4.356 +        }
   4.357 +        return NULL;
   4.358 +    }
   4.359 +}

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/buffer.c	Tue Oct 17 16:15:41 2017 +0200
     5.3 @@ -0,0 +1,236 @@
     5.4 +/*
     5.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     5.6 + *
     5.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     5.8 + *
     5.9 + * Redistribution and use in source and binary forms, with or without
    5.10 + * modification, are permitted provided that the following conditions are met:
    5.11 + *
    5.12 + *   1. Redistributions of source code must retain the above copyright
    5.13 + *      notice, this list of conditions and the following disclaimer.
    5.14 + *
    5.15 + *   2. Redistributions in binary form must reproduce the above copyright
    5.16 + *      notice, this list of conditions and the following disclaimer in the
    5.17 + *      documentation and/or other materials provided with the distribution.
    5.18 + *
    5.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    5.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    5.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    5.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    5.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    5.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    5.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    5.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    5.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    5.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    5.29 + * POSSIBILITY OF SUCH DAMAGE.
    5.30 + */
    5.31 +
    5.32 +#include "ucx/buffer.h"
    5.33 +
    5.34 +#include <stdarg.h>
    5.35 +#include <stdlib.h>
    5.36 +#include <string.h>
    5.37 +
    5.38 +UcxBuffer *ucx_buffer_new(void *space, size_t capacity, int flags) {
    5.39 +    UcxBuffer *buffer = (UcxBuffer*) malloc(sizeof(UcxBuffer));
    5.40 +    if (buffer) {
    5.41 +        buffer->flags = flags;
    5.42 +        if (!space) {
    5.43 +            buffer->space = (char*)malloc(capacity);
    5.44 +            if (!buffer->space) {
    5.45 +                free(buffer);
    5.46 +                return NULL;
    5.47 +            }
    5.48 +            memset(buffer->space, 0, capacity);
    5.49 +            buffer->flags |= UCX_BUFFER_AUTOFREE;
    5.50 +        } else {
    5.51 +            buffer->space = (char*)space;
    5.52 +        }
    5.53 +        buffer->capacity = capacity;
    5.54 +        buffer->size = 0;
    5.55 +
    5.56 +        buffer->pos = 0;
    5.57 +    }
    5.58 +
    5.59 +    return buffer;
    5.60 +}
    5.61 +
    5.62 +void ucx_buffer_free(UcxBuffer *buffer) {
    5.63 +    if ((buffer->flags & UCX_BUFFER_AUTOFREE) == UCX_BUFFER_AUTOFREE) {
    5.64 +        free(buffer->space);
    5.65 +    }
    5.66 +    free(buffer);
    5.67 +}
    5.68 +
    5.69 +UcxBuffer* ucx_buffer_extract(
    5.70 +        UcxBuffer *src, size_t start, size_t length, int flags) {
    5.71 +    if (src->size == 0 || length == 0 ||
    5.72 +        ((size_t)-1) - start < length || start+length > src->capacity)
    5.73 +    {
    5.74 +        return NULL;
    5.75 +    }
    5.76 +
    5.77 +    UcxBuffer *dst = (UcxBuffer*) malloc(sizeof(UcxBuffer));
    5.78 +    if (dst) {
    5.79 +        dst->space = (char*)malloc(length);
    5.80 +        if (!dst->space) {
    5.81 +            free(dst);
    5.82 +            return NULL;
    5.83 +        }
    5.84 +        dst->capacity = length;
    5.85 +        dst->size = length;
    5.86 +        dst->flags = flags | UCX_BUFFER_AUTOFREE;
    5.87 +        dst->pos = 0;
    5.88 +        memcpy(dst->space, src->space+start, length);
    5.89 +    }
    5.90 +    return dst;
    5.91 +}
    5.92 +
    5.93 +int ucx_buffer_seek(UcxBuffer *buffer, off_t offset, int whence) {
    5.94 +    size_t npos;
    5.95 +    switch (whence) {
    5.96 +    case SEEK_CUR:
    5.97 +        npos = buffer->pos;
    5.98 +        break;
    5.99 +    case SEEK_END:
   5.100 +        npos = buffer->size;
   5.101 +        break;
   5.102 +    case SEEK_SET:
   5.103 +        npos = 0;
   5.104 +        break;
   5.105 +    default:
   5.106 +        return -1;
   5.107 +    }
   5.108 +
   5.109 +    size_t opos = npos;
   5.110 +    npos += offset;
   5.111 +    
   5.112 +    if ((offset > 0 && npos < opos) || (offset < 0 && npos > opos)) {
   5.113 +        return -1;
   5.114 +    }
   5.115 +    
   5.116 +    if (npos >= buffer->size) {
   5.117 +        return -1;
   5.118 +    } else {
   5.119 +        buffer->pos = npos;
   5.120 +        return 0;
   5.121 +    }
   5.122 +
   5.123 +}
   5.124 +
   5.125 +int ucx_buffer_eof(UcxBuffer *buffer) {
   5.126 +    return buffer->pos >= buffer->size;
   5.127 +}
   5.128 +
   5.129 +int ucx_buffer_extend(UcxBuffer *buffer, size_t len) {
   5.130 +    size_t newcap = buffer->capacity;
   5.131 +    
   5.132 +    if (buffer->capacity + len < buffer->capacity) {
   5.133 +        return -1;
   5.134 +    }
   5.135 +    
   5.136 +    while (buffer->capacity + len > newcap) {
   5.137 +        newcap <<= 1;
   5.138 +        if (newcap < buffer->capacity) {
   5.139 +            return -1;
   5.140 +        }
   5.141 +    }
   5.142 +    
   5.143 +    char *newspace = (char*)realloc(buffer->space, newcap);
   5.144 +    if (newspace) {
   5.145 +        memset(newspace+buffer->size, 0, newcap-buffer->size);
   5.146 +        buffer->space = newspace;
   5.147 +        buffer->capacity = newcap;
   5.148 +    } else {
   5.149 +        return -1;
   5.150 +    }
   5.151 +    
   5.152 +    return 0;
   5.153 +}
   5.154 +
   5.155 +size_t ucx_buffer_write(const void *ptr, size_t size, size_t nitems,
   5.156 +        UcxBuffer *buffer) {
   5.157 +    size_t len = size * nitems;
   5.158 +    size_t required = buffer->pos + len;
   5.159 +    if (buffer->pos > required) {
   5.160 +        return 0;
   5.161 +    }
   5.162 +    
   5.163 +    if (required > buffer->capacity) {
   5.164 +        if ((buffer->flags & UCX_BUFFER_AUTOEXTEND) == UCX_BUFFER_AUTOEXTEND) {
   5.165 +            if (ucx_buffer_extend(buffer, required - buffer->capacity)) {
   5.166 +                return 0;
   5.167 +            }
   5.168 +        } else {
   5.169 +            len = buffer->capacity - buffer->pos;
   5.170 +            if (size > 1) {
   5.171 +                len -= len%size;
   5.172 +            }
   5.173 +        }
   5.174 +    }
   5.175 +    
   5.176 +    if (len == 0) {
   5.177 +        return len;
   5.178 +    }
   5.179 +    
   5.180 +    memcpy(buffer->space + buffer->pos, ptr, len);
   5.181 +    buffer->pos += len;
   5.182 +    if(buffer->pos > buffer->size) {
   5.183 +        buffer->size = buffer->pos;
   5.184 +    }
   5.185 +    
   5.186 +    return len / size;
   5.187 +}
   5.188 +
   5.189 +size_t ucx_buffer_read(void *ptr, size_t size, size_t nitems,
   5.190 +        UcxBuffer *buffer) {
   5.191 +    size_t len = size * nitems;
   5.192 +    if (buffer->pos + len > buffer->size) {
   5.193 +        len = buffer->size - buffer->pos;
   5.194 +        if (size > 1) len -= len%size;
   5.195 +    }
   5.196 +    
   5.197 +    if (len <= 0) {
   5.198 +        return len;
   5.199 +    }
   5.200 +    
   5.201 +    memcpy(ptr, buffer->space + buffer->pos, len);
   5.202 +    buffer->pos += len;
   5.203 +    
   5.204 +    return len / size;
   5.205 +}
   5.206 +
   5.207 +int ucx_buffer_putc(UcxBuffer *buffer, int c) {
   5.208 +    if(buffer->pos >= buffer->capacity) {
   5.209 +        if ((buffer->flags & UCX_BUFFER_AUTOEXTEND) == UCX_BUFFER_AUTOEXTEND) {
   5.210 +            if(ucx_buffer_extend(buffer, 1)) {
   5.211 +                return EOF;
   5.212 +            }
   5.213 +        } else {
   5.214 +            return EOF;
   5.215 +        }
   5.216 +    }
   5.217 +    
   5.218 +    c &= 0xFF;
   5.219 +    buffer->space[buffer->pos] = (char) c;
   5.220 +    buffer->pos++;
   5.221 +    if(buffer->pos > buffer->size) {
   5.222 +        buffer->size = buffer->pos;
   5.223 +    }
   5.224 +    return c;
   5.225 +}
   5.226 +
   5.227 +int ucx_buffer_getc(UcxBuffer *buffer) {
   5.228 +    if (ucx_buffer_eof(buffer)) {
   5.229 +        return EOF;
   5.230 +    } else {
   5.231 +        int c = buffer->space[buffer->pos];
   5.232 +        buffer->pos++;
   5.233 +        return c;
   5.234 +    }
   5.235 +}
   5.236 +
   5.237 +size_t ucx_buffer_puts(UcxBuffer *buffer, char *str) {
   5.238 +    return ucx_buffer_write((const void*)str, 1, strlen(str), buffer);
   5.239 +}

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/src/list.c	Tue Oct 17 16:15:41 2017 +0200
     6.3 @@ -0,0 +1,370 @@
     6.4 +/*
     6.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     6.6 + *
     6.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     6.8 + *
     6.9 + * Redistribution and use in source and binary forms, with or without
    6.10 + * modification, are permitted provided that the following conditions are met:
    6.11 + *
    6.12 + *   1. Redistributions of source code must retain the above copyright
    6.13 + *      notice, this list of conditions and the following disclaimer.
    6.14 + *
    6.15 + *   2. Redistributions in binary form must reproduce the above copyright
    6.16 + *      notice, this list of conditions and the following disclaimer in the
    6.17 + *      documentation and/or other materials provided with the distribution.
    6.18 + *
    6.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    6.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    6.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    6.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    6.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    6.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    6.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    6.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    6.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    6.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    6.29 + * POSSIBILITY OF SUCH DAMAGE.
    6.30 + */
    6.31 +
    6.32 +#include "ucx/list.h"
    6.33 +
    6.34 +UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
    6.35 +    return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
    6.36 +}
    6.37 +
    6.38 +UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l,
    6.39 +        copy_func fnc, void *data) {
    6.40 +    UcxList *ret = NULL;
    6.41 +    while (l) {
    6.42 +        if (fnc) {
    6.43 +            ret = ucx_list_append_a(alloc, ret, fnc(l->data, data));
    6.44 +        } else {
    6.45 +            ret = ucx_list_append_a(alloc, ret, l->data);
    6.46 +        }
    6.47 +        l = l->next;
    6.48 +    }
    6.49 +    return ret;
    6.50 +}
    6.51 +
    6.52 +int ucx_list_equals(const UcxList *l1, const UcxList *l2,
    6.53 +        cmp_func fnc, void* data) {
    6.54 +    if (l1 == l2) return 1;
    6.55 +    
    6.56 +    while (l1 != NULL && l2 != NULL) {
    6.57 +        if (fnc == NULL) {
    6.58 +            if (l1->data != l2->data) return 0;
    6.59 +        } else {
    6.60 +            if (fnc(l1->data, l2->data, data) != 0) return 0;
    6.61 +        }
    6.62 +        l1 = l1->next;
    6.63 +        l2 = l2->next;
    6.64 +    }
    6.65 +    
    6.66 +    return (l1 == NULL && l2 == NULL);
    6.67 +}
    6.68 +
    6.69 +void ucx_list_free(UcxList *l) {
    6.70 +    ucx_list_free_a(ucx_default_allocator(), l);
    6.71 +}
    6.72 +
    6.73 +void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) {
    6.74 +    UcxList *e = l, *f;
    6.75 +    while (e != NULL) {
    6.76 +        f = e;
    6.77 +        e = e->next;
    6.78 +        alfree(alloc, f);
    6.79 +    }
    6.80 +}
    6.81 +
    6.82 +void ucx_list_free_content(UcxList* list, ucx_destructor destr) {
    6.83 +    while (list != NULL) {
    6.84 +        destr(list->data);
    6.85 +        list = list->next;
    6.86 +    }
    6.87 +}
    6.88 +
    6.89 +UcxList *ucx_list_append(UcxList *l, void *data)  {
    6.90 +    return ucx_list_append_a(ucx_default_allocator(), l, data);
    6.91 +}
    6.92 +
    6.93 +UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data)  {
    6.94 +    UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
    6.95 +    if (!nl) {
    6.96 +        return NULL;
    6.97 +    }
    6.98 +    
    6.99 +    nl->data = data;
   6.100 +    nl->next = NULL;
   6.101 +    if (l) {
   6.102 +        UcxList *t = ucx_list_last(l);
   6.103 +        t->next = nl;
   6.104 +        nl->prev = t;
   6.105 +        return l;
   6.106 +    } else {
   6.107 +        nl->prev = NULL;
   6.108 +        return nl;
   6.109 +    }
   6.110 +}
   6.111 +
   6.112 +UcxList *ucx_list_append_once(UcxList *l, void *data,
   6.113 +        cmp_func cmpfnc, void *cmpdata) {
   6.114 +    return ucx_list_append_once_a(ucx_default_allocator(), l,
   6.115 +            data, cmpfnc, cmpdata);
   6.116 +}
   6.117 +
   6.118 +UcxList *ucx_list_append_once_a(UcxAllocator *alloc, UcxList *l, void *data,
   6.119 +        cmp_func cmpfnc, void *cmpdata) {
   6.120 +
   6.121 +    UcxList *last = NULL;
   6.122 +    {
   6.123 +        UcxList *e = l;
   6.124 +        while (e) {
   6.125 +            if (cmpfnc(e->data, data, cmpdata) == 0) {
   6.126 +                return l;
   6.127 +            }
   6.128 +            last = e;
   6.129 +            e = e->next;
   6.130 +        }
   6.131 +    }
   6.132 +    
   6.133 +    UcxList *nl = ucx_list_append_a(alloc, NULL, data);
   6.134 +    if (!nl) {
   6.135 +        return NULL;
   6.136 +    }
   6.137 +
   6.138 +    if (last == NULL) {
   6.139 +        return nl;
   6.140 +    } else {
   6.141 +        nl->prev = last;
   6.142 +        last->next = nl;
   6.143 +        return l;
   6.144 +    }
   6.145 +}
   6.146 +
   6.147 +UcxList *ucx_list_prepend(UcxList *l, void *data) {
   6.148 +    return ucx_list_prepend_a(ucx_default_allocator(), l, data);
   6.149 +}
   6.150 +
   6.151 +UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {
   6.152 +    UcxList *nl = ucx_list_append_a(alloc, NULL, data);
   6.153 +    if (!nl) {
   6.154 +        return NULL;
   6.155 +    }
   6.156 +    l = ucx_list_first(l);
   6.157 +    
   6.158 +    if (l) {
   6.159 +        nl->next = l;
   6.160 +        l->prev = nl;
   6.161 +    }
   6.162 +    return nl;
   6.163 +}
   6.164 +
   6.165 +UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
   6.166 +    if (l1) {
   6.167 +        UcxList *last = ucx_list_last(l1);
   6.168 +        last->next = l2;
   6.169 +        if (l2) {
   6.170 +            l2->prev = last;
   6.171 +        }
   6.172 +        return l1;
   6.173 +    } else {
   6.174 +        return l2;
   6.175 +    }
   6.176 +}
   6.177 +
   6.178 +UcxList *ucx_list_last(const UcxList *l) {
   6.179 +    if (l == NULL) return NULL;
   6.180 +    
   6.181 +    const UcxList *e = l;
   6.182 +    while (e->next != NULL) {
   6.183 +        e = e->next;
   6.184 +    }
   6.185 +    return (UcxList*)e;
   6.186 +}
   6.187 +
   6.188 +ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {
   6.189 +    ssize_t index = 0;
   6.190 +    while (list) {
   6.191 +        if (list == elem) {
   6.192 +            return index;
   6.193 +        }
   6.194 +        list = list->next;
   6.195 +        index++;
   6.196 +    }
   6.197 +    return -1;
   6.198 +}
   6.199 +
   6.200 +UcxList *ucx_list_get(const UcxList *l, size_t index) {
   6.201 +    if (l == NULL) return NULL;
   6.202 +
   6.203 +    const UcxList *e = l;
   6.204 +    while (e->next && index > 0) {
   6.205 +        e = e->next;
   6.206 +        index--;
   6.207 +    }
   6.208 +    
   6.209 +    return (UcxList*)(index == 0 ? e : NULL);
   6.210 +}
   6.211 +
   6.212 +ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
   6.213 +    ssize_t index = 0;
   6.214 +    UCX_FOREACH(e, l) {
   6.215 +        if (fnc) {
   6.216 +            if (fnc(elem, e->data, cmpdata) == 0) {
   6.217 +                return index;
   6.218 +            }
   6.219 +        } else {
   6.220 +            if (elem == e->data) {
   6.221 +                return index;
   6.222 +            }
   6.223 +        }
   6.224 +        index++;
   6.225 +    }
   6.226 +    return -1;
   6.227 +}
   6.228 +
   6.229 +int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
   6.230 +    return ucx_list_find(l, elem, fnc, cmpdata) > -1;
   6.231 +}
   6.232 +
   6.233 +size_t ucx_list_size(const UcxList *l) {
   6.234 +    if (l == NULL) return 0;
   6.235 +    
   6.236 +    const UcxList *e = l;
   6.237 +    size_t s = 1;
   6.238 +    while (e->next != NULL) {
   6.239 +        e = e->next;
   6.240 +        s++;
   6.241 +    }
   6.242 +
   6.243 +    return s;
   6.244 +}
   6.245 +
   6.246 +static UcxList *ucx_list_sort_merge(int length,
   6.247 +        UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
   6.248 +        cmp_func fnc, void* data) {
   6.249 +
   6.250 +    UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
   6.251 +    UcxList *rc, *lc;
   6.252 +
   6.253 +    lc = ls; rc = le;
   6.254 +    int n = 0;
   6.255 +    while (lc && lc != le && rc != re) {
   6.256 +        if (fnc(lc->data, rc->data, data) <= 0) {
   6.257 +            sorted[n] = lc;
   6.258 +            lc = lc->next;
   6.259 +        } else {
   6.260 +            sorted[n] = rc;
   6.261 +            rc = rc->next;
   6.262 +        }
   6.263 +        n++;
   6.264 +    }
   6.265 +    while (lc && lc != le) {
   6.266 +        sorted[n] = lc;
   6.267 +        lc = lc->next;
   6.268 +        n++;
   6.269 +    }
   6.270 +    while (rc && rc != re) {
   6.271 +        sorted[n] = rc;
   6.272 +        rc = rc->next;
   6.273 +        n++;
   6.274 +    }
   6.275 +
   6.276 +    // Update pointer
   6.277 +    sorted[0]->prev = NULL;
   6.278 +    for (int i = 0 ; i < length-1 ; i++) {
   6.279 +        sorted[i]->next = sorted[i+1];
   6.280 +        sorted[i+1]->prev = sorted[i];
   6.281 +    }
   6.282 +    sorted[length-1]->next = NULL;
   6.283 +
   6.284 +    UcxList *ret = sorted[0];
   6.285 +    free(sorted);
   6.286 +    return ret;
   6.287 +}
   6.288 +
   6.289 +UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
   6.290 +    if (l == NULL) {
   6.291 +        return NULL;
   6.292 +    }
   6.293 +
   6.294 +    UcxList *lc;
   6.295 +    int ln = 1;
   6.296 +
   6.297 +    UcxList *restrict ls = l, *restrict le, *restrict re;
   6.298 +    
   6.299 +    // check how many elements are already sorted
   6.300 +    lc = ls;
   6.301 +    while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
   6.302 +        lc = lc->next;
   6.303 +        ln++;
   6.304 +    }
   6.305 +    le = lc->next;
   6.306 +
   6.307 +    if (le == NULL) {
   6.308 +        return l; // this list is already sorted :)
   6.309 +    } else {
   6.310 +        UcxList *rc;
   6.311 +        int rn = 1;
   6.312 +        rc = le;
   6.313 +        // skip already sorted elements
   6.314 +        while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
   6.315 +            rc = rc->next;
   6.316 +            rn++;
   6.317 +        }
   6.318 +        re = rc->next;
   6.319 +
   6.320 +        // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
   6.321 +        UcxList *sorted = ucx_list_sort_merge(ln+rn,
   6.322 +                ls, le, re,
   6.323 +                fnc, data);
   6.324 +        
   6.325 +        // Something left? Sort it!
   6.326 +        size_t remainder_length = ucx_list_size(re);
   6.327 +        if (remainder_length > 0) {
   6.328 +            UcxList *remainder = ucx_list_sort(re, fnc, data);
   6.329 +
   6.330 +            // merge sorted list with (also sorted) remainder
   6.331 +            l = ucx_list_sort_merge(ln+rn+remainder_length,
   6.332 +                    sorted, remainder, NULL, fnc, data);
   6.333 +        } else {
   6.334 +            // no remainder - we've got our sorted list
   6.335 +            l = sorted;
   6.336 +        }
   6.337 +
   6.338 +        return l;
   6.339 +    }
   6.340 +}
   6.341 +
   6.342 +UcxList *ucx_list_first(const UcxList *l) {
   6.343 +    if (!l) {
   6.344 +        return NULL;
   6.345 +    }
   6.346 +    
   6.347 +    const UcxList *e = l;
   6.348 +    while (e->prev) {
   6.349 +        e = e->prev;
   6.350 +    }
   6.351 +    return (UcxList *)e;
   6.352 +}
   6.353 +
   6.354 +UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
   6.355 +    return ucx_list_remove_a(ucx_default_allocator(), l, e);
   6.356 +}
   6.357 +    
   6.358 +UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
   6.359 +    if (l == e) {
   6.360 +        l = e->next;
   6.361 +    }
   6.362 +    
   6.363 +    if (e->next) {
   6.364 +        e->next->prev = e->prev;
   6.365 +    }
   6.366 +    
   6.367 +    if (e->prev) {
   6.368 +        e->prev->next = e->next;
   6.369 +    }
   6.370 +    
   6.371 +    alfree(alloc, e);
   6.372 +    return l;
   6.373 +}

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/src/logging.c	Tue Oct 17 16:15:41 2017 +0200
     7.3 @@ -0,0 +1,106 @@
     7.4 +/*
     7.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     7.6 + *
     7.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     7.8 + *
     7.9 + * Redistribution and use in source and binary forms, with or without
    7.10 + * modification, are permitted provided that the following conditions are met:
    7.11 + *
    7.12 + *   1. Redistributions of source code must retain the above copyright
    7.13 + *      notice, this list of conditions and the following disclaimer.
    7.14 + *
    7.15 + *   2. Redistributions in binary form must reproduce the above copyright
    7.16 + *      notice, this list of conditions and the following disclaimer in the
    7.17 + *      documentation and/or other materials provided with the distribution.
    7.18 + *
    7.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    7.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    7.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    7.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    7.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    7.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    7.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    7.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    7.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    7.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    7.29 + * POSSIBILITY OF SUCH DAMAGE.
    7.30 + */
    7.31 +
    7.32 +#include "ucx/logging.h"
    7.33 +
    7.34 +#include <stdlib.h>
    7.35 +#include <string.h>
    7.36 +#include <stdarg.h>
    7.37 +#include <time.h>
    7.38 +
    7.39 +UcxLogger *ucx_logger_new(void *stream, unsigned int level, unsigned int mask) {
    7.40 +    UcxLogger *logger = (UcxLogger*) malloc(sizeof(UcxLogger));
    7.41 +    if (logger != NULL) {
    7.42 +        logger->stream = stream;
    7.43 +        logger->writer = (write_func)fwrite;
    7.44 +        logger->dateformat = (char*) "%F %T %z ";
    7.45 +        logger->level = level;
    7.46 +        logger->mask = mask;
    7.47 +        logger->levels = ucx_map_new(8);
    7.48 +        
    7.49 +        unsigned int l;
    7.50 +        l = UCX_LOGGER_ERROR;
    7.51 +        ucx_map_int_put(logger->levels, l, (void*) "[ERROR]");
    7.52 +        l = UCX_LOGGER_WARN;
    7.53 +        ucx_map_int_put(logger->levels, l, (void*) "[WARNING]");
    7.54 +        l = UCX_LOGGER_INFO;
    7.55 +        ucx_map_int_put(logger->levels, l, (void*) "[INFO]");
    7.56 +        l = UCX_LOGGER_TRACE;
    7.57 +        ucx_map_int_put(logger->levels, l, (void*) "[TRACE]");
    7.58 +    }
    7.59 +
    7.60 +    return logger;
    7.61 +}
    7.62 +
    7.63 +void ucx_logger_free(UcxLogger *logger) {
    7.64 +    ucx_map_free(logger->levels);
    7.65 +    free(logger);
    7.66 +}
    7.67 +
    7.68 +// estimated max. message length (documented)
    7.69 +#define UCX_LOGGER_MSGMAX 4096
    7.70 +
    7.71 +void ucx_logger_logf(UcxLogger *logger, unsigned int level, const char* file,
    7.72 +        const unsigned int line, const char *format, ...) {
    7.73 +    if (level <= logger->level) {
    7.74 +        char msg[UCX_LOGGER_MSGMAX];
    7.75 +        char *text;
    7.76 +        size_t k = 0;
    7.77 +        size_t n;
    7.78 +        
    7.79 +        if ((logger->mask & UCX_LOGGER_LEVEL) > 0) {
    7.80 +            text = (char*) ucx_map_int_get(logger->levels, level);
    7.81 +            n = strlen(text);
    7.82 +            n = n > 256 ? 256 : n;
    7.83 +            memcpy(msg+k, text, n);
    7.84 +            k += n;
    7.85 +            msg[k++] = ' ';
    7.86 +        }
    7.87 +        if ((logger->mask & UCX_LOGGER_TIMESTAMP) > 0) {
    7.88 +            time_t now = time(NULL);
    7.89 +            k += strftime(msg+k, 128, logger->dateformat, localtime(&now));
    7.90 +        }
    7.91 +        if ((logger->mask & UCX_LOGGER_SOURCE) > 0) {
    7.92 +            n = strlen(file);
    7.93 +            memcpy(msg+k, file, n);
    7.94 +            k += n;
    7.95 +            k += sprintf(msg+k, ":%u ", line);
    7.96 +        }
    7.97 +        
    7.98 +        msg[k++] = '-'; msg[k++] = ' ';
    7.99 +        
   7.100 +        va_list args;
   7.101 +        va_start (args, format);
   7.102 +        k += vsnprintf(msg+k, UCX_LOGGER_MSGMAX-k-1, format, args);
   7.103 +        va_end (args);        
   7.104 +        
   7.105 +        msg[k++] = '\n';
   7.106 +        
   7.107 +        logger->writer(msg, 1, k, logger->stream);
   7.108 +    }
   7.109 +}

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/src/map.c	Tue Oct 17 16:15:41 2017 +0200
     8.3 @@ -0,0 +1,328 @@
     8.4 +/*
     8.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     8.6 + *
     8.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     8.8 + *
     8.9 + * Redistribution and use in source and binary forms, with or without
    8.10 + * modification, are permitted provided that the following conditions are met:
    8.11 + *
    8.12 + *   1. Redistributions of source code must retain the above copyright
    8.13 + *      notice, this list of conditions and the following disclaimer.
    8.14 + *
    8.15 + *   2. Redistributions in binary form must reproduce the above copyright
    8.16 + *      notice, this list of conditions and the following disclaimer in the
    8.17 + *      documentation and/or other materials provided with the distribution.
    8.18 + *
    8.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    8.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    8.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    8.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    8.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    8.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    8.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    8.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    8.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    8.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    8.29 + * POSSIBILITY OF SUCH DAMAGE.
    8.30 + */
    8.31 +
    8.32 +#include "ucx/map.h"
    8.33 +
    8.34 +#include <stdlib.h>
    8.35 +#include <string.h>
    8.36 +
    8.37 +UcxMap *ucx_map_new(size_t size) {
    8.38 +    return ucx_map_new_a(NULL, size);
    8.39 +}
    8.40 +
    8.41 +UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) {
    8.42 +    if(size == 0) {
    8.43 +        size = 16;
    8.44 +    }
    8.45 +       
    8.46 +    if(!allocator) {
    8.47 +        allocator = ucx_default_allocator();
    8.48 +    }
    8.49 +    
    8.50 +    UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap));
    8.51 +    if (!map) {
    8.52 +        return NULL;
    8.53 +    }
    8.54 +    
    8.55 +    map->allocator = allocator;
    8.56 +    map->map = (UcxMapElement**)alcalloc(
    8.57 +            allocator, size, sizeof(UcxMapElement*));
    8.58 +    if(map->map == NULL) {
    8.59 +        alfree(allocator, map);
    8.60 +        return NULL;
    8.61 +    }
    8.62 +    map->size = size;
    8.63 +    map->count = 0;
    8.64 +
    8.65 +    return map;
    8.66 +}
    8.67 +
    8.68 +static void ucx_map_free_elmlist_contents(UcxMap *map) {
    8.69 +    for (size_t n = 0 ; n < map->size ; n++) {
    8.70 +        UcxMapElement *elem = map->map[n];
    8.71 +        if (elem != NULL) {
    8.72 +            do {
    8.73 +                UcxMapElement *next = elem->next;
    8.74 +                alfree(map->allocator, elem->key.data);
    8.75 +                alfree(map->allocator, elem);
    8.76 +                elem = next;
    8.77 +            } while (elem != NULL);
    8.78 +        }
    8.79 +    }
    8.80 +}
    8.81 +
    8.82 +void ucx_map_free(UcxMap *map) {
    8.83 +    ucx_map_free_elmlist_contents(map);
    8.84 +    alfree(map->allocator, map->map);
    8.85 +    alfree(map->allocator, map);
    8.86 +}
    8.87 +
    8.88 +void ucx_map_free_content(UcxMap *map, ucx_destructor destr) {
    8.89 +    UcxMapIterator iter = ucx_map_iterator(map);
    8.90 +    void *val;
    8.91 +    UCX_MAP_FOREACH(key, val, iter) {
    8.92 +        destr(val);
    8.93 +    }
    8.94 +}
    8.95 +
    8.96 +void ucx_map_clear(UcxMap *map) {
    8.97 +    if (map->count == 0) {
    8.98 +        return; // nothing to do
    8.99 +    }
   8.100 +    ucx_map_free_elmlist_contents(map);
   8.101 +    memset(map->map, 0, map->size*sizeof(UcxMapElement*));
   8.102 +    map->count = 0;
   8.103 +}
   8.104 +
   8.105 +int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,
   8.106 +        copy_func fnc, void *data) {
   8.107 +    UcxMapIterator i = ucx_map_iterator(from);
   8.108 +    void *value;
   8.109 +    UCX_MAP_FOREACH(key, value, i) {
   8.110 +        if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) {
   8.111 +            return 1;
   8.112 +        }
   8.113 +    }
   8.114 +    return 0;
   8.115 +}
   8.116 +
   8.117 +UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {
   8.118 +    size_t bs = (map->count * 5) >> 1;
   8.119 +    UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);
   8.120 +    if (!newmap) {
   8.121 +        return NULL;
   8.122 +    }
   8.123 +    ucx_map_copy(map, newmap, fnc, data);
   8.124 +    return newmap;
   8.125 +}
   8.126 +
   8.127 +int ucx_map_rehash(UcxMap *map) {
   8.128 +    size_t load = (map->size * 3) >> 2;
   8.129 +    if (map->count > load) {
   8.130 +        UcxMap oldmap;
   8.131 +        oldmap.map = map->map;
   8.132 +        oldmap.size = map->size;
   8.133 +        oldmap.count = map->count;
   8.134 +        oldmap.allocator = map->allocator;
   8.135 +        
   8.136 +        map->size = (map->count * 5) >> 1;
   8.137 +        map->map = (UcxMapElement**)alcalloc(
   8.138 +                map->allocator, map->size, sizeof(UcxMapElement*));
   8.139 +        if (!map->map) {
   8.140 +            *map = oldmap;
   8.141 +            return 1;
   8.142 +        }
   8.143 +        map->count = 0;
   8.144 +        ucx_map_copy(&oldmap, map, NULL, NULL);
   8.145 +        
   8.146 +        /* free the UcxMapElement list of oldmap */
   8.147 +        ucx_map_free_elmlist_contents(&oldmap);
   8.148 +        alfree(map->allocator, oldmap.map);
   8.149 +    }
   8.150 +    return 0;
   8.151 +}
   8.152 +
   8.153 +int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
   8.154 +    UcxAllocator *allocator = map->allocator;
   8.155 +    
   8.156 +    if (key.hash == 0) {
   8.157 +        key.hash = ucx_hash((char*)key.data, key.len);
   8.158 +    }
   8.159 +
   8.160 +    size_t slot = key.hash%map->size;
   8.161 +    UcxMapElement *restrict elm = map->map[slot];
   8.162 +    UcxMapElement *restrict prev = NULL;
   8.163 +
   8.164 +    while (elm && elm->key.hash < key.hash) {
   8.165 +        prev = elm;
   8.166 +        elm = elm->next;
   8.167 +    }
   8.168 +    
   8.169 +    if (!elm || elm->key.hash != key.hash) {
   8.170 +        UcxMapElement *e = (UcxMapElement*)almalloc(
   8.171 +                allocator, sizeof(UcxMapElement));
   8.172 +        if (!e) {
   8.173 +            return -1;
   8.174 +        }
   8.175 +        e->key.data = NULL;
   8.176 +        if (prev) {
   8.177 +            prev->next = e;
   8.178 +        } else {
   8.179 +            map->map[slot] = e;
   8.180 +        }
   8.181 +        e->next = elm;
   8.182 +        elm = e;
   8.183 +    }
   8.184 +    
   8.185 +    if (!elm->key.data) {
   8.186 +        void *kd = almalloc(allocator, key.len);
   8.187 +        if (!kd) {
   8.188 +            return -1;
   8.189 +        }
   8.190 +        memcpy(kd, key.data, key.len);
   8.191 +        key.data = kd;
   8.192 +        elm->key = key;
   8.193 +        map->count++;
   8.194 +    }
   8.195 +    elm->data = data;
   8.196 +
   8.197 +    return 0;
   8.198 +}
   8.199 +
   8.200 +void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {
   8.201 +    if(key.hash == 0) {
   8.202 +        key.hash = ucx_hash((char*)key.data, key.len);
   8.203 +    }
   8.204 +    
   8.205 +    size_t slot = key.hash%map->size;
   8.206 +    UcxMapElement *restrict elm = map->map[slot];
   8.207 +    UcxMapElement *restrict pelm = NULL;
   8.208 +    while (elm && elm->key.hash <= key.hash) {
   8.209 +        if(elm->key.hash == key.hash) {
   8.210 +            int n = (key.len > elm->key.len) ? elm->key.len : key.len;
   8.211 +            if (memcmp(elm->key.data, key.data, n) == 0) {
   8.212 +                void *data = elm->data;
   8.213 +                if (remove) {
   8.214 +                    if (pelm) {
   8.215 +                        pelm->next = elm->next;
   8.216 +                    } else {
   8.217 +                        map->map[slot] = elm->next;
   8.218 +                    }
   8.219 +                    alfree(map->allocator, elm->key.data);
   8.220 +                    alfree(map->allocator, elm);
   8.221 +                    map->count--;
   8.222 +                }
   8.223 +
   8.224 +                return data;
   8.225 +            }
   8.226 +        }
   8.227 +        pelm = elm;
   8.228 +        elm = pelm->next;
   8.229 +    }
   8.230 +
   8.231 +    return NULL;
   8.232 +}
   8.233 +
   8.234 +void *ucx_map_get(UcxMap *map, UcxKey key) {
   8.235 +    return ucx_map_get_and_remove(map, key, 0);
   8.236 +}
   8.237 +
   8.238 +void *ucx_map_remove(UcxMap *map, UcxKey key) {
   8.239 +    return ucx_map_get_and_remove(map, key, 1);
   8.240 +}
   8.241 +
   8.242 +UcxKey ucx_key(void *data, size_t len) {
   8.243 +    UcxKey key;
   8.244 +    key.data = data;
   8.245 +    key.len = len;
   8.246 +    key.hash = ucx_hash((const char*) data, len);
   8.247 +    return key;
   8.248 +}
   8.249 +
   8.250 +
   8.251 +int ucx_hash(const char *data, size_t len) {
   8.252 +    /* murmur hash 2 */
   8.253 +
   8.254 +    int m = 0x5bd1e995;
   8.255 +    int r = 24;
   8.256 +
   8.257 +    int h = 25 ^ len;
   8.258 +
   8.259 +    int i = 0;
   8.260 +    while (len >= 4) {
   8.261 +        int k = data[i + 0] & 0xFF;
   8.262 +        k |= (data[i + 1] & 0xFF) << 8;
   8.263 +        k |= (data[i + 2] & 0xFF) << 16;
   8.264 +        k |= (data[i + 3] & 0xFF) << 24;
   8.265 +
   8.266 +        k *= m;
   8.267 +        k ^= k >> r;
   8.268 +        k *= m;
   8.269 +
   8.270 +        h *= m;
   8.271 +        h ^= k;
   8.272 +
   8.273 +        i += 4;
   8.274 +        len -= 4;
   8.275 +    }
   8.276 +
   8.277 +    switch (len) {
   8.278 +        case 3: h ^= (data[i + 2] & 0xFF) << 16;
   8.279 +        /* no break */
   8.280 +        case 2: h ^= (data[i + 1] & 0xFF) << 8;
   8.281 +        /* no break */
   8.282 +        case 1: h ^= (data[i + 0] & 0xFF); h *= m;
   8.283 +        /* no break */
   8.284 +    }
   8.285 +
   8.286 +    h ^= h >> 13;
   8.287 +    h *= m;
   8.288 +    h ^= h >> 15;
   8.289 +
   8.290 +    return h;
   8.291 +}
   8.292 +
   8.293 +UcxMapIterator ucx_map_iterator(UcxMap *map) {
   8.294 +    UcxMapIterator i;
   8.295 +    i.map = map;
   8.296 +    i.cur = NULL;
   8.297 +    i.index = 0;
   8.298 +    return i;
   8.299 +}
   8.300 +
   8.301 +int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) {
   8.302 +    UcxMapElement *e = i->cur;
   8.303 +    
   8.304 +    if (e) {
   8.305 +        e = e->next;
   8.306 +    } else {
   8.307 +        e = i->map->map[0];
   8.308 +    }
   8.309 +    
   8.310 +    while (i->index < i->map->size) {
   8.311 +        if (e) {
   8.312 +            if (e->data) {
   8.313 +                i->cur = e;
   8.314 +                *elm = e->data;
   8.315 +                *key = e->key;
   8.316 +                return 1;
   8.317 +            }
   8.318 +
   8.319 +            e = e->next;
   8.320 +        } else {
   8.321 +            i->index++;
   8.322 +            
   8.323 +            if (i->index < i->map->size) {
   8.324 +                e = i->map->map[i->index];
   8.325 +            }
   8.326 +        }
   8.327 +    }
   8.328 +    
   8.329 +    return 0;
   8.330 +}
   8.331 +

     9.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.2 +++ b/src/mempool.c	Tue Oct 17 16:15:41 2017 +0200
     9.3 @@ -0,0 +1,211 @@
     9.4 +/*
     9.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     9.6 + *
     9.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
     9.8 + *
     9.9 + * Redistribution and use in source and binary forms, with or without
    9.10 + * modification, are permitted provided that the following conditions are met:
    9.11 + *
    9.12 + *   1. Redistributions of source code must retain the above copyright
    9.13 + *      notice, this list of conditions and the following disclaimer.
    9.14 + *
    9.15 + *   2. Redistributions in binary form must reproduce the above copyright
    9.16 + *      notice, this list of conditions and the following disclaimer in the
    9.17 + *      documentation and/or other materials provided with the distribution.
    9.18 + *
    9.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    9.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    9.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    9.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    9.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    9.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    9.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    9.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    9.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    9.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    9.29 + * POSSIBILITY OF SUCH DAMAGE.
    9.30 + */
    9.31 +
    9.32 +#include "ucx/mempool.h"
    9.33 +
    9.34 +#include <stdlib.h>
    9.35 +#include <string.h>
    9.36 +#include <stdio.h>
    9.37 +#ifdef __cplusplus
    9.38 +#define __STDC_FORMAT_MACROS
    9.39 +#endif
    9.40 +#include <inttypes.h>
    9.41 +
    9.42 +/** Capsule for destructible memory chunks. */
    9.43 +typedef struct {
    9.44 +    /** The destructor for the memory chunk. */
    9.45 +    ucx_destructor destructor;
    9.46 +    /**
    9.47 +     * First byte of the memory chunk.
    9.48 +     * Note, that the address <code>&amp;c</code> is also the address
    9.49 +     * of the whole memory chunk.
    9.50 +     */
    9.51 +    char c;
    9.52 +} ucx_memchunk;
    9.53 +
    9.54 +/** Capsule for data and its destructor. */
    9.55 +typedef struct {
    9.56 +    /** The destructor for the data. */
    9.57 +    ucx_destructor destructor;
    9.58 +    /** A pointer to the data. */
    9.59 +    void           *ptr;
    9.60 +} ucx_regdestr;
    9.61 +
    9.62 +UCX_EXTERN void ucx_mempool_shared_destr(void* ptr) {
    9.63 +    ucx_regdestr *rd = (ucx_regdestr*)ptr;
    9.64 +    rd->destructor(rd->ptr);
    9.65 +}
    9.66 +
    9.67 +UcxMempool *ucx_mempool_new(size_t n) {
    9.68 +    UcxMempool *pool = (UcxMempool*)malloc(sizeof(UcxMempool));
    9.69 +    if (!pool) {
    9.70 +        return NULL;
    9.71 +    }
    9.72 +    
    9.73 +    pool->data = (void**) malloc(n * sizeof(void*));
    9.74 +    if (pool->data == NULL) {
    9.75 +        free(pool);
    9.76 +        return NULL;
    9.77 +    }
    9.78 +    
    9.79 +    pool->ndata = 0;
    9.80 +    pool->size = n;
    9.81 +    
    9.82 +    UcxAllocator *allocator = (UcxAllocator*)malloc(sizeof(UcxAllocator));
    9.83 +    if(!allocator) {
    9.84 +        free(pool->data);
    9.85 +        free(pool);
    9.86 +        return NULL;
    9.87 +    }
    9.88 +    allocator->malloc = (ucx_allocator_malloc)ucx_mempool_malloc;
    9.89 +    allocator->calloc = (ucx_allocator_calloc)ucx_mempool_calloc;
    9.90 +    allocator->realloc = (ucx_allocator_realloc)ucx_mempool_realloc;
    9.91 +    allocator->free = (ucx_allocator_free)ucx_mempool_free;
    9.92 +    allocator->pool = pool;
    9.93 +    pool->allocator = allocator;
    9.94 +    
    9.95 +    return pool;
    9.96 +}
    9.97 +
    9.98 +int ucx_mempool_chcap(UcxMempool *pool, size_t newcap) {
    9.99 +    if (newcap < pool->ndata) {
   9.100 +        return 1;
   9.101 +    }
   9.102 +    
   9.103 +    void **data = (void**) realloc(pool->data, newcap*sizeof(void*));
   9.104 +    if (data) {
   9.105 +        pool->data = data; 
   9.106 +        pool->size = newcap;
   9.107 +        return 0;
   9.108 +    } else {
   9.109 +        return 1;
   9.110 +    }
   9.111 +}
   9.112 +
   9.113 +void *ucx_mempool_malloc(UcxMempool *pool, size_t n) {
   9.114 +    if (pool->ndata >= pool->size) {
   9.115 +        size_t newcap = pool->size*2;
   9.116 +        if (newcap < pool->size || ucx_mempool_chcap(pool, newcap)) {
   9.117 +            return NULL;
   9.118 +        }
   9.119 +    }
   9.120 +
   9.121 +    void *p = malloc(sizeof(ucx_destructor) + n);
   9.122 +    ucx_memchunk *mem = (ucx_memchunk*)p;
   9.123 +    if (!mem) {
   9.124 +        return NULL;
   9.125 +    }
   9.126 +
   9.127 +    mem->destructor = NULL;
   9.128 +    pool->data[pool->ndata] = mem;
   9.129 +    pool->ndata++;
   9.130 +
   9.131 +    return &(mem->c);
   9.132 +}
   9.133 +
   9.134 +void *ucx_mempool_calloc(UcxMempool *pool, size_t nelem, size_t elsize) {
   9.135 +    void *ptr = ucx_mempool_malloc(pool, nelem*elsize);
   9.136 +    if (!ptr) {
   9.137 +        return NULL;
   9.138 +    }
   9.139 +    memset(ptr, 0, nelem * elsize);
   9.140 +    return ptr;
   9.141 +}
   9.142 +
   9.143 +void *ucx_mempool_realloc(UcxMempool *pool, void *ptr, size_t n) {
   9.144 +    char *mem = ((char*)ptr) - sizeof(ucx_destructor);
   9.145 +    char *newm = (char*) realloc(mem, n + sizeof(ucx_destructor));
   9.146 +    if (!newm) {
   9.147 +        return NULL;
   9.148 +    }
   9.149 +    if (mem != newm) {
   9.150 +        for(size_t i=0 ; i < pool->ndata ; i++) {
   9.151 +            if(pool->data[i] == mem) {
   9.152 +                pool->data[i] = newm;
   9.153 +                return newm + sizeof(ucx_destructor);
   9.154 +            }
   9.155 +        }
   9.156 +        fprintf(stderr, "FATAL: 0x%08" PRIxPTR" not in mpool 0x%08" PRIxPTR"\n",
   9.157 +          (intptr_t)ptr, (intptr_t)pool);
   9.158 +        abort();
   9.159 +    } else {
   9.160 +        return newm + sizeof(ucx_destructor);
   9.161 +    }
   9.162 +}
   9.163 +
   9.164 +void ucx_mempool_free(UcxMempool *pool, void *ptr) {
   9.165 +    ucx_memchunk *chunk = (ucx_memchunk*)((char*)ptr-sizeof(ucx_destructor));
   9.166 +    for(size_t i=0 ; i<pool->ndata ; i++) {
   9.167 +        if(chunk == pool->data[i]) {
   9.168 +            if(chunk->destructor != NULL) {
   9.169 +                chunk->destructor(&(chunk->c));
   9.170 +            }
   9.171 +            free(chunk);
   9.172 +            size_t last_index = pool->ndata - 1;
   9.173 +            if(i != last_index) {
   9.174 +                pool->data[i] = pool->data[last_index];
   9.175 +                pool->data[last_index] = NULL;
   9.176 +            }
   9.177 +            pool->ndata--;
   9.178 +            return;
   9.179 +        }
   9.180 +    }
   9.181 +    fprintf(stderr, "FATAL: 0x%08" PRIxPTR" not in mpool 0x%08" PRIxPTR"\n",
   9.182 +            (intptr_t)ptr, (intptr_t)pool);
   9.183 +    abort();
   9.184 +}
   9.185 +
   9.186 +void ucx_mempool_destroy(UcxMempool *pool) {
   9.187 +    ucx_memchunk *chunk;
   9.188 +    for(size_t i=0 ; i<pool->ndata ; i++) {
   9.189 +        chunk = (ucx_memchunk*) pool->data[i];
   9.190 +        if(chunk) {
   9.191 +            if(chunk->destructor) {
   9.192 +                chunk->destructor(&(chunk->c));
   9.193 +            }
   9.194 +            free(chunk);
   9.195 +        }
   9.196 +    }
   9.197 +    free(pool->data);
   9.198 +    free(pool->allocator);
   9.199 +    free(pool);
   9.200 +}
   9.201 +
   9.202 +void ucx_mempool_set_destr(void *ptr, ucx_destructor func) {
   9.203 +    *(ucx_destructor*)((char*)ptr-sizeof(ucx_destructor)) = func;
   9.204 +}
   9.205 +
   9.206 +void ucx_mempool_reg_destr(UcxMempool *pool, void *ptr, ucx_destructor destr) {
   9.207 +    ucx_regdestr *rd = (ucx_regdestr*)ucx_mempool_malloc(
   9.208 +            pool,
   9.209 +            sizeof(ucx_regdestr));
   9.210 +    rd->destructor = destr;
   9.211 +    rd->ptr = ptr;
   9.212 +    ucx_mempool_set_destr(rd, ucx_mempool_shared_destr);
   9.213 +}
   9.214 +

    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/src/properties.c	Tue Oct 17 16:15:41 2017 +0200
    10.3 @@ -0,0 +1,264 @@
    10.4 +/*
    10.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    10.6 + *
    10.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    10.8 + *
    10.9 + * Redistribution and use in source and binary forms, with or without
   10.10 + * modification, are permitted provided that the following conditions are met:
   10.11 + *
   10.12 + *   1. Redistributions of source code must retain the above copyright
   10.13 + *      notice, this list of conditions and the following disclaimer.
   10.14 + *
   10.15 + *   2. Redistributions in binary form must reproduce the above copyright
   10.16 + *      notice, this list of conditions and the following disclaimer in the
   10.17 + *      documentation and/or other materials provided with the distribution.
   10.18 + *
   10.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   10.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   10.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   10.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   10.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   10.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   10.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   10.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   10.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   10.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   10.29 + * POSSIBILITY OF SUCH DAMAGE.
   10.30 + */
   10.31 +
   10.32 +#include "ucx/properties.h"
   10.33 +
   10.34 +#include <stdio.h>
   10.35 +#include <stdlib.h>
   10.36 +#include <string.h>
   10.37 +
   10.38 +UcxProperties *ucx_properties_new() {
   10.39 +    UcxProperties *parser = (UcxProperties*)malloc(
   10.40 +            sizeof(UcxProperties));
   10.41 +    if(!parser) {
   10.42 +        return NULL;
   10.43 +    }
   10.44 +    
   10.45 +    parser->buffer = NULL;
   10.46 +    parser->buflen = 0;
   10.47 +    parser->pos = 0;
   10.48 +    parser->tmp = NULL;
   10.49 +    parser->tmplen = 0;
   10.50 +    parser->tmpcap = 0;
   10.51 +    parser->error = 0;
   10.52 +    parser->delimiter = '=';
   10.53 +    parser->comment1 = '#';
   10.54 +    parser->comment2 = 0;
   10.55 +    parser->comment3 = 0;   
   10.56 +    
   10.57 +    return parser;
   10.58 +}
   10.59 +
   10.60 +void ucx_properties_free(UcxProperties *parser) {
   10.61 +    if(parser->tmp) {
   10.62 +        free(parser->tmp);
   10.63 +    }
   10.64 +    free(parser);
   10.65 +}
   10.66 +
   10.67 +void ucx_properties_fill(UcxProperties *parser, char *buf, size_t len) {
   10.68 +    parser->buffer = buf;
   10.69 +    parser->buflen = len;
   10.70 +    parser->pos = 0;
   10.71 +}
   10.72 +
   10.73 +static void parser_tmp_append(UcxProperties *parser, char *buf, size_t len) {
   10.74 +    if(parser->tmpcap - parser->tmplen < len) {
   10.75 +        size_t newcap = parser->tmpcap + len + 64;
   10.76 +        parser->tmp = (char*)realloc(parser->tmp, newcap);
   10.77 +        parser->tmpcap = newcap;
   10.78 +    }
   10.79 +    memcpy(parser->tmp + parser->tmplen, buf, len);
   10.80 +    parser->tmplen += len;
   10.81 +}
   10.82 +
   10.83 +int ucx_properties_next(UcxProperties *parser, sstr_t *name, sstr_t *value)  {   
   10.84 +    if(parser->tmplen > 0) {
   10.85 +        char *buf = parser->buffer + parser->pos;
   10.86 +        size_t len = parser->buflen - parser->pos;
   10.87 +        sstr_t str = sstrn(buf, len);
   10.88 +        sstr_t nl = sstrchr(str, '\n');
   10.89 +        if(nl.ptr) {
   10.90 +            size_t newlen = (size_t)(nl.ptr - buf) + 1;
   10.91 +            parser_tmp_append(parser, buf, newlen);
   10.92 +            // the tmp buffer contains exactly one line now
   10.93 +            
   10.94 +            char *orig_buf = parser->buffer;
   10.95 +            size_t orig_len = parser->buflen;
   10.96 +            
   10.97 +            parser->buffer = parser->tmp;
   10.98 +            parser->buflen = parser->tmplen;
   10.99 +            parser->pos = 0;    
  10.100 +            parser->tmp = NULL;
  10.101 +            parser->tmpcap = 0;
  10.102 +            parser->tmplen = 0;
  10.103 +            // run ucx_properties_next with the tmp buffer as main buffer
  10.104 +            int ret = ucx_properties_next(parser, name, value);
  10.105 +            
  10.106 +            // restore original buffer
  10.107 +            parser->tmp = parser->buffer;
  10.108 +            parser->buffer = orig_buf;
  10.109 +            parser->buflen = orig_len;
  10.110 +            parser->pos = newlen;
  10.111 +            
  10.112 +            /*
  10.113 +             * if ret == 0 the tmp buffer contained just space or a comment
  10.114 +             * we parse again with the original buffer to get a name/value
  10.115 +             * or a new tmp buffer
  10.116 +             */
  10.117 +            return ret ? ret : ucx_properties_next(parser, name, value);
  10.118 +        } else {
  10.119 +            parser_tmp_append(parser, buf, len);
  10.120 +            return 0;
  10.121 +        }
  10.122 +    } else if(parser->tmp) {
  10.123 +        free(parser->tmp);
  10.124 +        parser->tmp = NULL;
  10.125 +    }
  10.126 +    
  10.127 +    char comment1 = parser->comment1;
  10.128 +    char comment2 = parser->comment2;
  10.129 +    char comment3 = parser->comment3;
  10.130 +    char delimiter = parser->delimiter;
  10.131 +    
  10.132 +    // get one line and parse it
  10.133 +    while(parser->pos < parser->buflen) {
  10.134 +        char *buf = parser->buffer + parser->pos;
  10.135 +        size_t len = parser->buflen - parser->pos;
  10.136 +        
  10.137 +        /*
  10.138 +         * First we check if we have at least one line. We also get indices of
  10.139 +         * delimiter and comment chars
  10.140 +         */
  10.141 +        size_t delimiter_index = 0;
  10.142 +        size_t comment_index = 0;
  10.143 +        int has_comment = 0;
  10.144 +
  10.145 +        size_t i = 0;
  10.146 +        char c = 0;
  10.147 +        for(;i<len;i++) {
  10.148 +            c = buf[i];
  10.149 +            if(c == comment1 || c == comment2 || c == comment3) {
  10.150 +                if(comment_index == 0) {
  10.151 +                    comment_index = i;
  10.152 +                    has_comment = 1;
  10.153 +                }
  10.154 +            } else if(c == delimiter) {
  10.155 +                if(delimiter_index == 0 && !has_comment) {
  10.156 +                    delimiter_index = i;
  10.157 +                }
  10.158 +            } else if(c == '\n') {
  10.159 +                break;
  10.160 +            }
  10.161 +        }
  10.162 +
  10.163 +        if(c != '\n') {
  10.164 +            // we don't have enough data for a line
  10.165 +            // store remaining bytes in temporary buffer for next round
  10.166 +            parser->tmpcap = len + 128;
  10.167 +            parser->tmp = (char*)malloc(parser->tmpcap);
  10.168 +            parser->tmplen = len;
  10.169 +            memcpy(parser->tmp, buf, len);
  10.170 +            return 0;
  10.171 +        }
  10.172 +        
  10.173 +        sstr_t line = has_comment ? sstrn(buf, comment_index) : sstrn(buf, i);
  10.174 +        // check line
  10.175 +        if(delimiter_index == 0) {
  10.176 +            line = sstrtrim(line);
  10.177 +            if(line.length != 0) {
  10.178 +                parser->error = 1;
  10.179 +            }
  10.180 +        } else {
  10.181 +            sstr_t n = sstrn(buf, delimiter_index);
  10.182 +            sstr_t v = sstrn(
  10.183 +                    buf + delimiter_index + 1,
  10.184 +                    line.length - delimiter_index - 1); 
  10.185 +            n = sstrtrim(n);
  10.186 +            v = sstrtrim(v);
  10.187 +            if(n.length != 0 || v.length != 0) {
  10.188 +                *name = n;
  10.189 +                *value = v;
  10.190 +                parser->pos += i + 1;
  10.191 +                return 1;
  10.192 +            } else {
  10.193 +                parser->error = 1;
  10.194 +            }
  10.195 +        }
  10.196 +        
  10.197 +        parser->pos += i + 1;
  10.198 +    }
  10.199 +    
  10.200 +    return 0;
  10.201 +}
  10.202 +
  10.203 +int ucx_properties2map(UcxProperties *parser, UcxMap *map) {
  10.204 +    sstr_t name;
  10.205 +    sstr_t value;
  10.206 +    while(ucx_properties_next(parser, &name, &value)) {
  10.207 +        value = sstrdup_a(map->allocator, value);
  10.208 +        if(!value.ptr) {
  10.209 +            return 1;
  10.210 +        }
  10.211 +        if(ucx_map_sstr_put(map, name, value.ptr)) {
  10.212 +            alfree(map->allocator, value.ptr);
  10.213 +            return 1;
  10.214 +        }
  10.215 +    }
  10.216 +    if (parser->error) {
  10.217 +        return parser->error;
  10.218 +    } else {
  10.219 +        return 0;
  10.220 +    }
  10.221 +}
  10.222 +
  10.223 +// buffer size is documented - change doc, when you change bufsize!
  10.224 +#define UCX_PROPLOAD_BUFSIZE  1024
  10.225 +int ucx_properties_load(UcxMap *map, FILE *file) {
  10.226 +    UcxProperties *parser = ucx_properties_new();
  10.227 +    if(!(parser && map && file)) {
  10.228 +        return 1;
  10.229 +    }
  10.230 +    
  10.231 +    int error = 0;
  10.232 +    size_t r;
  10.233 +    char buf[UCX_PROPLOAD_BUFSIZE];
  10.234 +    while((r = fread(buf, 1, UCX_PROPLOAD_BUFSIZE, file)) != 0) {
  10.235 +        ucx_properties_fill(parser, buf, r);
  10.236 +        error = ucx_properties2map(parser, map);
  10.237 +        if (error) {
  10.238 +            break;
  10.239 +        }
  10.240 +    }
  10.241 +    ucx_properties_free(parser);
  10.242 +    return error;
  10.243 +}
  10.244 +
  10.245 +int ucx_properties_store(UcxMap *map, FILE *file) {
  10.246 +    UcxMapIterator iter = ucx_map_iterator(map);
  10.247 +    void *v;
  10.248 +    sstr_t value;
  10.249 +    size_t written;
  10.250 +
  10.251 +    UCX_MAP_FOREACH(k, v, iter) {
  10.252 +        value = sstr((char*)v);
  10.253 +
  10.254 +        written = 0;
  10.255 +        written += fwrite(k.data, 1, k.len, file);
  10.256 +        written += fwrite(" = ", 1, 3, file);
  10.257 +        written += fwrite(value.ptr, 1, value.length, file);
  10.258 +        written += fwrite("\n", 1, 1, file);
  10.259 +
  10.260 +        if (written != k.len + value.length + 4) {
  10.261 +            return 1;
  10.262 +        }
  10.263 +    }
  10.264 +
  10.265 +    return 0;
  10.266 +}
  10.267 +

    11.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    11.2 +++ b/src/stack.c	Tue Oct 17 16:15:41 2017 +0200
    11.3 @@ -0,0 +1,144 @@
    11.4 +/*
    11.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    11.6 + *
    11.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    11.8 + *
    11.9 + * Redistribution and use in source and binary forms, with or without
   11.10 + * modification, are permitted provided that the following conditions are met:
   11.11 + *
   11.12 + *   1. Redistributions of source code must retain the above copyright
   11.13 + *      notice, this list of conditions and the following disclaimer.
   11.14 + *
   11.15 + *   2. Redistributions in binary form must reproduce the above copyright
   11.16 + *      notice, this list of conditions and the following disclaimer in the
   11.17 + *      documentation and/or other materials provided with the distribution.
   11.18 + *
   11.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   11.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   11.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   11.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   11.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   11.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   11.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   11.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   11.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   11.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   11.29 + * POSSIBILITY OF SUCH DAMAGE.
   11.30 + */
   11.31 +
   11.32 +#include "ucx/stack.h"
   11.33 +
   11.34 +#include <string.h>
   11.35 +
   11.36 +static size_t ucx_stack_align(size_t n) {
   11.37 +    int align = n % sizeof(void*);
   11.38 +    if (align) {
   11.39 +        n += sizeof(void*) - align;
   11.40 +    }
   11.41 +    return n;
   11.42 +}
   11.43 +
   11.44 +void ucx_stack_init(UcxStack *stack, char* space, size_t size) {
   11.45 +    stack->size = size - size % sizeof(void*);
   11.46 +    stack->space = space;
   11.47 +    stack->top = NULL;
   11.48 +    
   11.49 +    stack->allocator.pool = stack;
   11.50 +    stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc;
   11.51 +    stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc;
   11.52 +    stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc;
   11.53 +    stack->allocator.free = (ucx_allocator_free) ucx_stack_free;
   11.54 +}
   11.55 +
   11.56 +void *ucx_stack_malloc(UcxStack *stack, size_t n) {
   11.57 +
   11.58 +    if (ucx_stack_avail(stack) < ucx_stack_align(n)) {
   11.59 +        return NULL;
   11.60 +    } else {
   11.61 +        char *prev = stack->top;
   11.62 +        if (stack->top) {
   11.63 +            stack->top += ucx_stack_align(ucx_stack_topsize(stack));
   11.64 +        } else {
   11.65 +            stack->top = stack->space;
   11.66 +        }
   11.67 +        
   11.68 +        ((struct ucx_stack_metadata*)stack->top)->prev = prev;
   11.69 +        ((struct ucx_stack_metadata*)stack->top)->size = n;
   11.70 +        stack->top += sizeof(struct ucx_stack_metadata);
   11.71 +        
   11.72 +        return stack->top;
   11.73 +    }
   11.74 +}
   11.75 +
   11.76 +void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) {
   11.77 +    void *mem = ucx_stack_malloc(stack, nelem*elsize);
   11.78 +    memset(mem, 0, nelem*elsize);
   11.79 +    return mem;
   11.80 +}
   11.81 +
   11.82 +void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) {
   11.83 +    if (ptr == stack->top) {
   11.84 +        if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) {
   11.85 +            return NULL;
   11.86 +        } else {
   11.87 +            ((struct ucx_stack_metadata*)stack->top - 1)->size = n;
   11.88 +            return ptr;
   11.89 +        }
   11.90 +    } else {
   11.91 +        if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) <
   11.92 +                ucx_stack_align(n)) {
   11.93 +            void *nptr = ucx_stack_malloc(stack, n);
   11.94 +            if (nptr) {
   11.95 +                memcpy(nptr, ptr, n);
   11.96 +                ucx_stack_free(stack, ptr);
   11.97 +                
   11.98 +                return nptr;
   11.99 +            } else {
  11.100 +                return NULL;
  11.101 +            }
  11.102 +        } else {
  11.103 +            ((struct ucx_stack_metadata*)ptr - 1)->size = n;
  11.104 +            return ptr;
  11.105 +        }
  11.106 +    }
  11.107 +}
  11.108 +
  11.109 +void ucx_stack_free(UcxStack *stack, void *ptr) {
  11.110 +    if (ptr == stack->top) {
  11.111 +        stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev;
  11.112 +    } else {
  11.113 +        struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)(
  11.114 +            (char*)ptr +
  11.115 +            ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size)
  11.116 +        );
  11.117 +        next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev;
  11.118 +    }
  11.119 +}
  11.120 +
  11.121 +void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) {
  11.122 +    if (ucx_stack_empty(stack)) {
  11.123 +        return;
  11.124 +    }
  11.125 +    
  11.126 +    size_t len = ucx_stack_topsize(stack);
  11.127 +    if (len > n) {
  11.128 +        len = n;
  11.129 +    }
  11.130 +    
  11.131 +    memcpy(dest, stack->top, len);
  11.132 +    
  11.133 +    ucx_stack_free(stack, stack->top);
  11.134 +}
  11.135 +
  11.136 +size_t ucx_stack_avail(UcxStack *stack) {
  11.137 +    size_t avail = ((stack->top ? (stack->size
  11.138 +                    - (stack->top - stack->space)
  11.139 +                    - ucx_stack_align(ucx_stack_topsize(stack)))
  11.140 +                    : stack->size));
  11.141 +    
  11.142 +    if (avail > sizeof(struct ucx_stack_metadata)) {
  11.143 +        return avail - sizeof(struct ucx_stack_metadata);
  11.144 +    } else {
  11.145 +        return 0;
  11.146 +    }
  11.147 +}

    12.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    12.2 +++ b/src/string.c	Tue Oct 17 16:15:41 2017 +0200
    12.3 @@ -0,0 +1,463 @@
    12.4 +/*
    12.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    12.6 + *
    12.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    12.8 + *
    12.9 + * Redistribution and use in source and binary forms, with or without
   12.10 + * modification, are permitted provided that the following conditions are met:
   12.11 + *
   12.12 + *   1. Redistributions of source code must retain the above copyright
   12.13 + *      notice, this list of conditions and the following disclaimer.
   12.14 + *
   12.15 + *   2. Redistributions in binary form must reproduce the above copyright
   12.16 + *      notice, this list of conditions and the following disclaimer in the
   12.17 + *      documentation and/or other materials provided with the distribution.
   12.18 + *
   12.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   12.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   12.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   12.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   12.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   12.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   12.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   12.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   12.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   12.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   12.29 + * POSSIBILITY OF SUCH DAMAGE.
   12.30 + */
   12.31 +
   12.32 +#include "ucx/string.h"
   12.33 +
   12.34 +#include "ucx/allocator.h"
   12.35 +
   12.36 +#include <stdlib.h>
   12.37 +#include <string.h>
   12.38 +#include <stdarg.h>
   12.39 +#include <stdint.h>
   12.40 +#include <ctype.h>
   12.41 +
   12.42 +sstr_t sstr(char *cstring) {
   12.43 +    sstr_t string;
   12.44 +    string.ptr = cstring;
   12.45 +    string.length = strlen(cstring);
   12.46 +    return string;
   12.47 +}
   12.48 +
   12.49 +sstr_t sstrn(char *cstring, size_t length) {
   12.50 +    sstr_t string;
   12.51 +    string.ptr = cstring;
   12.52 +    string.length = length;
   12.53 +    return string;
   12.54 +}
   12.55 +
   12.56 +size_t sstrnlen(size_t n, sstr_t s, ...) {
   12.57 +    va_list ap;
   12.58 +    size_t size = s.length;
   12.59 +    va_start(ap, s);
   12.60 +
   12.61 +    for (size_t i = 1 ; i < n ; i++) {
   12.62 +        sstr_t str = va_arg(ap, sstr_t);
   12.63 +        size += str.length;
   12.64 +    }
   12.65 +    va_end(ap);
   12.66 +
   12.67 +    return size;
   12.68 +}
   12.69 +
   12.70 +static sstr_t sstrvcat_a(
   12.71 +        UcxAllocator *a,
   12.72 +        size_t count,
   12.73 +        sstr_t s1,
   12.74 +        sstr_t s2,
   12.75 +        va_list ap) {
   12.76 +    sstr_t str;
   12.77 +    str.ptr = NULL;
   12.78 +    str.length = 0;
   12.79 +    if(count < 2) {
   12.80 +        return str;
   12.81 +    }
   12.82 +    
   12.83 +    sstr_t *strings = (sstr_t*) calloc(count, sizeof(sstr_t));
   12.84 +    if(!strings) {
   12.85 +        return str;
   12.86 +    }
   12.87 +    
   12.88 +    // get all args and overall length
   12.89 +    strings[0] = s1;
   12.90 +    strings[1] = s2;
   12.91 +    size_t strlen = s1.length + s2.length;
   12.92 +    for (size_t i=2;i<count;i++) {
   12.93 +        sstr_t s = va_arg (ap, sstr_t);
   12.94 +        strings[i] = s;
   12.95 +        strlen += s.length;
   12.96 +    }
   12.97 +    
   12.98 +    // create new string
   12.99 +    str.ptr = (char*) almalloc(a, strlen + 1);
  12.100 +    str.length = strlen;
  12.101 +    if(!str.ptr) {
  12.102 +        free(strings);
  12.103 +        str.length = 0;
  12.104 +        return str;
  12.105 +    }
  12.106 +    
  12.107 +    // concatenate strings
  12.108 +    size_t pos = 0;
  12.109 +    for (size_t i=0;i<count;i++) {
  12.110 +        sstr_t s = strings[i];
  12.111 +        memcpy(str.ptr + pos, s.ptr, s.length);
  12.112 +        pos += s.length;
  12.113 +    }
  12.114 +    
  12.115 +    str.ptr[str.length] = '\0';
  12.116 +    
  12.117 +    free(strings);
  12.118 +    
  12.119 +    return str;
  12.120 +}
  12.121 +
  12.122 +sstr_t sstrcat(size_t count, sstr_t s1, sstr_t s2, ...) {
  12.123 +    va_list ap;
  12.124 +    va_start(ap, s2);
  12.125 +    sstr_t s = sstrvcat_a(ucx_default_allocator(), count, s1, s2, ap);
  12.126 +    va_end(ap);
  12.127 +    return s;
  12.128 +}
  12.129 +
  12.130 +sstr_t sstrcat_a(UcxAllocator *a, size_t count, sstr_t s1, sstr_t s2, ...) {
  12.131 +    va_list ap;
  12.132 +    va_start(ap, s2);
  12.133 +    sstr_t s = sstrvcat_a(a, count, s1, s2, ap);
  12.134 +    va_end(ap);
  12.135 +    return s;
  12.136 +}
  12.137 +
  12.138 +sstr_t sstrsubs(sstr_t s, size_t start) {
  12.139 +    return sstrsubsl (s, start, s.length-start);
  12.140 +}
  12.141 +
  12.142 +sstr_t sstrsubsl(sstr_t s, size_t start, size_t length) {
  12.143 +    sstr_t new_sstr;
  12.144 +    if (start >= s.length) {
  12.145 +        new_sstr.ptr = NULL;
  12.146 +        new_sstr.length = 0;
  12.147 +    } else {
  12.148 +        if (length > s.length-start) {
  12.149 +            length = s.length-start;
  12.150 +        }
  12.151 +        new_sstr.ptr = &s.ptr[start];
  12.152 +        new_sstr.length = length;
  12.153 +    }
  12.154 +    return new_sstr;
  12.155 +}
  12.156 +
  12.157 +sstr_t sstrchr(sstr_t s, int c) {
  12.158 +    for(size_t i=0;i<s.length;i++) {
  12.159 +        if(s.ptr[i] == c) {
  12.160 +            return sstrsubs(s, i);
  12.161 +        }
  12.162 +    }
  12.163 +    sstr_t n;
  12.164 +    n.ptr = NULL;
  12.165 +    n.length = 0;
  12.166 +    return n;
  12.167 +}
  12.168 +
  12.169 +sstr_t sstrrchr(sstr_t s, int c) {
  12.170 +    if (s.length > 0) {
  12.171 +        for(size_t i=s.length;i>0;i--) {
  12.172 +            if(s.ptr[i-1] == c) {
  12.173 +                return sstrsubs(s, i-1);
  12.174 +            }
  12.175 +        }
  12.176 +    }
  12.177 +    sstr_t n;
  12.178 +    n.ptr = NULL;
  12.179 +    n.length = 0;
  12.180 +    return n;
  12.181 +}
  12.182 +
  12.183 +#define ptable_r(dest, useheap, ptable, index) (dest = useheap ? \
  12.184 +    ((size_t*)ptable)[index] : (size_t) ((uint8_t*)ptable)[index])
  12.185 +
  12.186 +#define ptable_w(useheap, ptable, index, src) do {\
  12.187 +    if (!useheap) ((uint8_t*)ptable)[index] = (uint8_t) src;\
  12.188 +    else ((size_t*)ptable)[index] = src;\
  12.189 +    } while (0);
  12.190 +
  12.191 +sstr_t sstrstr(sstr_t string, sstr_t match) {
  12.192 +    if (match.length == 0) {
  12.193 +        return string;
  12.194 +    }
  12.195 +    
  12.196 +    /* prepare default return value in case of no match */
  12.197 +    sstr_t result = sstrn(NULL, 0);
  12.198 +    
  12.199 +    /*
  12.200 +     * IMPORTANT:
  12.201 +     * our prefix table contains the prefix length PLUS ONE
  12.202 +     * this is our decision, because we want to use the full range of size_t
  12.203 +     * the original algorithm needs a (-1) at one single place
  12.204 +     * and we want to avoid that
  12.205 +     */
  12.206 +    
  12.207 +    /* static prefix table */
  12.208 +    static uint8_t s_prefix_table[256];
  12.209 +    
  12.210 +    /* check pattern length and use appropriate prefix table */
  12.211 +    /* if the pattern exceeds static prefix table, allocate on the heap */
  12.212 +    register int useheap = match.length > 255;
  12.213 +    register void* ptable = useheap ?
  12.214 +        calloc(match.length+1, sizeof(size_t)): s_prefix_table;
  12.215 +    
  12.216 +    /* keep counter in registers */
  12.217 +    register size_t i, j;
  12.218 +    
  12.219 +    /* fill prefix table */
  12.220 +    i = 0; j = 0;
  12.221 +    ptable_w(useheap, ptable, i, j);
  12.222 +    while (i < match.length) {
  12.223 +        while (j >= 1 && match.ptr[j-1] != match.ptr[i]) {
  12.224 +            ptable_r(j, useheap, ptable, j-1);
  12.225 +        }
  12.226 +        i++; j++;
  12.227 +        ptable_w(useheap, ptable, i, j);
  12.228 +    }
  12.229 +
  12.230 +    /* search */
  12.231 +    i = 0; j = 1;
  12.232 +    while (i < string.length) {
  12.233 +        while (j >= 1 && string.ptr[i] != match.ptr[j-1]) {
  12.234 +            ptable_r(j, useheap, ptable, j-1);
  12.235 +        }
  12.236 +        i++; j++;
  12.237 +        if (j-1 == match.length) {
  12.238 +            size_t start = i - match.length;
  12.239 +            result.ptr = string.ptr + start;
  12.240 +            result.length = string.length - start;
  12.241 +            break;
  12.242 +        }
  12.243 +    }
  12.244 +
  12.245 +    /* if prefix table was allocated on the heap, free it */
  12.246 +    if (ptable != s_prefix_table) {
  12.247 +        free(ptable);
  12.248 +    }
  12.249 +    
  12.250 +    return result;
  12.251 +}
  12.252 +
  12.253 +#undef ptable_r
  12.254 +#undef ptable_w
  12.255 +
  12.256 +sstr_t* sstrsplit(sstr_t s, sstr_t d, ssize_t *n) {
  12.257 +    return sstrsplit_a(ucx_default_allocator(), s, d, n);
  12.258 +}
  12.259 +
  12.260 +sstr_t* sstrsplit_a(UcxAllocator *allocator, sstr_t s, sstr_t d, ssize_t *n) {
  12.261 +    if (s.length == 0 || d.length == 0) {
  12.262 +        *n = -1;
  12.263 +        return NULL;
  12.264 +    }
  12.265 +    
  12.266 +    /* special cases: delimiter is at least as large as the string */
  12.267 +    if (d.length >= s.length) {
  12.268 +        /* exact match */
  12.269 +        if (sstrcmp(s, d) == 0) {
  12.270 +            *n = 0;
  12.271 +            return NULL;
  12.272 +        } else /* no match possible */ {
  12.273 +            *n = 1;
  12.274 +            sstr_t *result = (sstr_t*) almalloc(allocator, sizeof(sstr_t));
  12.275 +            *result = sstrdup_a(allocator, s);
  12.276 +            return result;
  12.277 +        }
  12.278 +    }
  12.279 +    
  12.280 +    ssize_t nmax = *n;
  12.281 +    size_t arrlen = 16;
  12.282 +    sstr_t* result = (sstr_t*) almalloc(allocator, arrlen*sizeof(sstr_t));
  12.283 +
  12.284 +    if (result) {
  12.285 +        sstr_t curpos = s;
  12.286 +        ssize_t j = 1;
  12.287 +        while (1) {
  12.288 +            sstr_t match;
  12.289 +            /* optimize for one byte delimiters */
  12.290 +            if (d.length == 1) {
  12.291 +                match = curpos;
  12.292 +                for (size_t i = 0 ; i < curpos.length ; i++) {
  12.293 +                    if (curpos.ptr[i] == *(d.ptr)) {
  12.294 +                        match.ptr = curpos.ptr + i;
  12.295 +                        break;
  12.296 +                    }
  12.297 +                    match.length--;
  12.298 +                }
  12.299 +            } else {
  12.300 +                match = sstrstr(curpos, d);
  12.301 +            }
  12.302 +            if (match.length > 0) {
  12.303 +                /* is this our last try? */
  12.304 +                if (nmax == 0 || j < nmax) {
  12.305 +                    /* copy the current string to the array */
  12.306 +                    sstr_t item = sstrn(curpos.ptr, match.ptr - curpos.ptr);
  12.307 +                    result[j-1] = sstrdup_a(allocator, item);
  12.308 +                    size_t processed = item.length + d.length;
  12.309 +                    curpos.ptr += processed;
  12.310 +                    curpos.length -= processed;
  12.311 +
  12.312 +                    /* allocate memory for the next string */
  12.313 +                    j++;
  12.314 +                    if (j > arrlen) {
  12.315 +                        arrlen *= 2;
  12.316 +                        sstr_t* reallocated = (sstr_t*) alrealloc(
  12.317 +                                allocator, result, arrlen*sizeof(sstr_t));
  12.318 +                        if (reallocated) {
  12.319 +                            result = reallocated;
  12.320 +                        } else {
  12.321 +                            for (ssize_t i = 0 ; i < j-1 ; i++) {
  12.322 +                                alfree(allocator, result[i].ptr);
  12.323 +                            }
  12.324 +                            alfree(allocator, result);
  12.325 +                            *n = -2;
  12.326 +                            return NULL;
  12.327 +                        }
  12.328 +                    }
  12.329 +                } else {
  12.330 +                    /* nmax reached, copy the _full_ remaining string */
  12.331 +                    result[j-1] = sstrdup_a(allocator, curpos);
  12.332 +                    break;
  12.333 +                }
  12.334 +            } else {
  12.335 +                /* no more matches, copy last string */
  12.336 +                result[j-1] = sstrdup_a(allocator, curpos);
  12.337 +                break;
  12.338 +            }
  12.339 +        }
  12.340 +        *n = j;
  12.341 +    } else {
  12.342 +        *n = -2;
  12.343 +    }
  12.344 +
  12.345 +    return result;
  12.346 +}
  12.347 +
  12.348 +int sstrcmp(sstr_t s1, sstr_t s2) {
  12.349 +    if (s1.length == s2.length) {
  12.350 +        return memcmp(s1.ptr, s2.ptr, s1.length);
  12.351 +    } else if (s1.length > s2.length) {
  12.352 +        return 1;
  12.353 +    } else {
  12.354 +        return -1;
  12.355 +    }
  12.356 +}
  12.357 +
  12.358 +int sstrcasecmp(sstr_t s1, sstr_t s2) {
  12.359 +    if (s1.length == s2.length) {
  12.360 +#ifdef _WIN32
  12.361 +        return _strnicmp(s1.ptr, s2.ptr, s1.length);
  12.362 +#else
  12.363 +        return strncasecmp(s1.ptr, s2.ptr, s1.length);
  12.364 +#endif
  12.365 +    } else if (s1.length > s2.length) {
  12.366 +        return 1;
  12.367 +    } else {
  12.368 +        return -1;
  12.369 +    }
  12.370 +}
  12.371 +
  12.372 +sstr_t sstrdup(sstr_t s) {
  12.373 +    return sstrdup_a(ucx_default_allocator(), s);
  12.374 +}
  12.375 +
  12.376 +sstr_t sstrdup_a(UcxAllocator *allocator, sstr_t s) {
  12.377 +    sstr_t newstring;
  12.378 +    newstring.ptr = (char*)almalloc(allocator, s.length + 1);
  12.379 +    if (newstring.ptr) {
  12.380 +        newstring.length = s.length;
  12.381 +        newstring.ptr[newstring.length] = 0;
  12.382 +        
  12.383 +        memcpy(newstring.ptr, s.ptr, s.length);
  12.384 +    } else {
  12.385 +        newstring.length = 0;
  12.386 +    }
  12.387 +    
  12.388 +    return newstring;
  12.389 +}
  12.390 +
  12.391 +sstr_t sstrtrim(sstr_t string) {
  12.392 +    sstr_t newstr = string;
  12.393 +    
  12.394 +    while (newstr.length > 0 && isspace(*newstr.ptr)) {
  12.395 +        newstr.ptr++;
  12.396 +        newstr.length--;
  12.397 +    }
  12.398 +    while (newstr.length > 0 && isspace(newstr.ptr[newstr.length-1])) {
  12.399 +        newstr.length--;
  12.400 +    }
  12.401 +    
  12.402 +    return newstr;
  12.403 +}
  12.404 +
  12.405 +int sstrprefix(sstr_t string, sstr_t prefix) {
  12.406 +    if (string.length == 0) {
  12.407 +        return prefix.length == 0;
  12.408 +    }
  12.409 +    if (prefix.length == 0) {
  12.410 +        return 1;
  12.411 +    }
  12.412 +    
  12.413 +    if (prefix.length > string.length) {
  12.414 +        return 0;
  12.415 +    } else {
  12.416 +        return memcmp(string.ptr, prefix.ptr, prefix.length) == 0;
  12.417 +    }
  12.418 +}
  12.419 +
  12.420 +int sstrsuffix(sstr_t string, sstr_t suffix) {
  12.421 +    if (string.length == 0) {
  12.422 +        return suffix.length == 0;
  12.423 +    }
  12.424 +    if (suffix.length == 0) {
  12.425 +        return 1;
  12.426 +    }
  12.427 +    
  12.428 +    if (suffix.length > string.length) {
  12.429 +        return 0;
  12.430 +    } else {
  12.431 +        return memcmp(string.ptr+string.length-suffix.length,
  12.432 +            suffix.ptr, suffix.length) == 0;
  12.433 +    }
  12.434 +}
  12.435 +
  12.436 +sstr_t sstrlower(sstr_t string) {
  12.437 +    sstr_t ret = sstrdup(string);
  12.438 +    for (size_t i = 0; i < ret.length ; i++) {
  12.439 +        ret.ptr[i] = tolower(ret.ptr[i]);
  12.440 +    }
  12.441 +    return ret;
  12.442 +}
  12.443 +
  12.444 +sstr_t sstrlower_a(UcxAllocator *allocator, sstr_t string) {
  12.445 +    sstr_t ret = sstrdup_a(allocator, string);
  12.446 +    for (size_t i = 0; i < ret.length ; i++) {
  12.447 +        ret.ptr[i] = tolower(ret.ptr[i]);
  12.448 +    }
  12.449 +    return ret;
  12.450 +}
  12.451 +
  12.452 +sstr_t sstrupper(sstr_t string) {
  12.453 +    sstr_t ret = sstrdup(string);
  12.454 +    for (size_t i = 0; i < ret.length ; i++) {
  12.455 +        ret.ptr[i] = toupper(ret.ptr[i]);
  12.456 +    }
  12.457 +    return ret;
  12.458 +}
  12.459 +
  12.460 +sstr_t sstrupper_a(UcxAllocator *allocator, sstr_t string) {
  12.461 +    sstr_t ret = sstrdup_a(allocator, string);
  12.462 +    for (size_t i = 0; i < ret.length ; i++) {
  12.463 +        ret.ptr[i] = toupper(ret.ptr[i]);
  12.464 +    }
  12.465 +    return ret;
  12.466 +}

    13.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    13.2 +++ b/src/test.c	Tue Oct 17 16:15:41 2017 +0200
    13.3 @@ -0,0 +1,91 @@
    13.4 +/*
    13.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    13.6 + *
    13.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    13.8 + *
    13.9 + * Redistribution and use in source and binary forms, with or without
   13.10 + * modification, are permitted provided that the following conditions are met:
   13.11 + *
   13.12 + *   1. Redistributions of source code must retain the above copyright
   13.13 + *      notice, this list of conditions and the following disclaimer.
   13.14 + *
   13.15 + *   2. Redistributions in binary form must reproduce the above copyright
   13.16 + *      notice, this list of conditions and the following disclaimer in the
   13.17 + *      documentation and/or other materials provided with the distribution.
   13.18 + *
   13.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   13.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   13.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   13.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   13.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   13.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   13.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   13.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   13.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   13.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   13.29 + * POSSIBILITY OF SUCH DAMAGE.
   13.30 + */
   13.31 +
   13.32 +#include "ucx/test.h"
   13.33 +
   13.34 +UcxTestSuite* ucx_test_suite_new() {
   13.35 +    UcxTestSuite* suite = (UcxTestSuite*) malloc(sizeof(UcxTestSuite));
   13.36 +    if (suite != NULL) {
   13.37 +        suite->success = 0;
   13.38 +        suite->failure = 0;
   13.39 +        suite->tests = NULL;
   13.40 +    }
   13.41 +
   13.42 +    return suite;
   13.43 +}
   13.44 +
   13.45 +void ucx_test_suite_free(UcxTestSuite* suite) {
   13.46 +    UcxTestList *l = suite->tests;
   13.47 +    while (l != NULL) {
   13.48 +        UcxTestList *e = l;
   13.49 +        l = l->next;
   13.50 +        free(e);
   13.51 +    }
   13.52 +    free(suite);
   13.53 +}
   13.54 +
   13.55 +int ucx_test_register(UcxTestSuite* suite, UcxTest test) {
   13.56 +    if (suite->tests) {
   13.57 +        UcxTestList *newelem = (UcxTestList*) malloc(sizeof(UcxTestList));
   13.58 +        if (newelem) {
   13.59 +            newelem->test = test;
   13.60 +            newelem->next = NULL;
   13.61 +            
   13.62 +            UcxTestList *last = suite->tests;
   13.63 +            while (last->next) {
   13.64 +                last = last->next;
   13.65 +            }
   13.66 +            last->next = newelem;
   13.67 +            
   13.68 +            return EXIT_SUCCESS;
   13.69 +        } else {
   13.70 +            return EXIT_FAILURE;
   13.71 +        }
   13.72 +    } else {
   13.73 +        suite->tests = (UcxTestList*) malloc(sizeof(UcxTestList));
   13.74 +        if (suite->tests) {
   13.75 +            suite->tests->test = test;
   13.76 +            suite->tests->next = NULL;
   13.77 +            
   13.78 +            return EXIT_SUCCESS;
   13.79 +        } else {
   13.80 +            return EXIT_FAILURE;
   13.81 +        }
   13.82 +    }
   13.83 +}
   13.84 +
   13.85 +void ucx_test_run(UcxTestSuite* suite, FILE* output) {
   13.86 +    suite->success = 0;
   13.87 +    suite->failure = 0;
   13.88 +    for (UcxTestList* elem = suite->tests ; elem ; elem = elem->next) {
   13.89 +        elem->test(suite, output);
   13.90 +    }
   13.91 +    fwrite("\nAll test completed.\n", 1, 21, output);
   13.92 +    fprintf(output, "  Total:   %u\n  Success: %u\n  Failure: %u\n",
   13.93 +            suite->success+suite->failure, suite->success, suite->failure);
   13.94 +}

    14.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    14.2 +++ b/src/ucx.c	Tue Oct 17 16:15:41 2017 +0200
    14.3 @@ -0,0 +1,37 @@
    14.4 +/**
    14.5 + * @mainpage UAP Common Extensions
    14.6 + * Library with common and useful functions, macros and data structures.
    14.7 + * <p>
    14.8 + * Latest available source:<br/>
    14.9 + * <a href="https://develop.uap-core.de/hg/ucx">
   14.10 + * https://develop.uap-core.de/hg/ucx</a>
   14.11 + * </p>
   14.12 + * 
   14.13 + * <h2>LICENCE</h2>
   14.14 + * 
   14.15 + * Copyright 2017 Olaf Wintermann. All rights reserved.
   14.16 + *
   14.17 + * Redistribution and use in source and binary forms, with or without
   14.18 + * modification, are permitted provided that the following conditions are met:
   14.19 + *
   14.20 + *   1. Redistributions of source code must retain the above copyright
   14.21 + *      notice, this list of conditions and the following disclaimer.
   14.22 + *
   14.23 + *   2. Redistributions in binary form must reproduce the above copyright
   14.24 + *      notice, this list of conditions and the following disclaimer in the
   14.25 + *      documentation and/or other materials provided with the distribution.
   14.26 + *
   14.27 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   14.28 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   14.29 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   14.30 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   14.31 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   14.32 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   14.33 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   14.34 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   14.35 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   14.36 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   14.37 + * POSSIBILITY OF SUCH DAMAGE.
   14.38 + */
   14.39 +
   14.40 +#include "ucx/ucx.h"

    15.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    15.2 +++ b/src/ucx/allocator.h	Tue Oct 17 16:15:41 2017 +0200
    15.3 @@ -0,0 +1,206 @@
    15.4 +/*
    15.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    15.6 + *
    15.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    15.8 + *
    15.9 + * Redistribution and use in source and binary forms, with or without
   15.10 + * modification, are permitted provided that the following conditions are met:
   15.11 + *
   15.12 + *   1. Redistributions of source code must retain the above copyright
   15.13 + *      notice, this list of conditions and the following disclaimer.
   15.14 + *
   15.15 + *   2. Redistributions in binary form must reproduce the above copyright
   15.16 + *      notice, this list of conditions and the following disclaimer in the
   15.17 + *      documentation and/or other materials provided with the distribution.
   15.18 + *
   15.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   15.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   15.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   15.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   15.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   15.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   15.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   15.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   15.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   15.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   15.29 + * POSSIBILITY OF SUCH DAMAGE.
   15.30 + */
   15.31 +/**
   15.32 + * Allocator for custom memory management.
   15.33 + * 
   15.34 + * A UCX allocator consists of a pointer to the memory area / pool and four
   15.35 + * function pointers to memory management functions operating on this memory
   15.36 + * area / pool. These functions shall behave equivalent to the standard libc
   15.37 + * functions <code>malloc(), calloc(), realloc()</code> and <code>free()</code>.
   15.38 + * 
   15.39 + * The signature of the memory management functions is based on the signature
   15.40 + * of the respective libc function but each of them takes the pointer to the
   15.41 + * memory area / pool as first argument.
   15.42 + * 
   15.43 + * As the pointer to the memory area / pool can be arbitrarily chosen, any data
   15.44 + * can be provided to the memory management functions. A UcxMempool is just
   15.45 + * one example.
   15.46 + * 
   15.47 + * @see mempool.h
   15.48 + * @see UcxMap
   15.49 + * 
   15.50 + * @file   allocator.h
   15.51 + * @author Mike Becker
   15.52 + * @author Olaf Wintermann
   15.53 + */
   15.54 +
   15.55 +#ifndef UCX_ALLOCATOR_H
   15.56 +#define	UCX_ALLOCATOR_H
   15.57 +
   15.58 +#include <ucx/ucx.h>
   15.59 +
   15.60 +#ifdef	__cplusplus
   15.61 +extern "C" {
   15.62 +#endif
   15.63 +
   15.64 +/**
   15.65 + * A function pointer to the allocators <code>malloc()</code> function.
   15.66 + * @see UcxAllocator
   15.67 + */
   15.68 +typedef void*(*ucx_allocator_malloc)(void *pool, size_t n);
   15.69 +
   15.70 +/**
   15.71 + * A function pointer to the allocators <code>calloc()</code> function.
   15.72 + * @see UcxAllocator
   15.73 + */
   15.74 +typedef void*(*ucx_allocator_calloc)(void *pool, size_t n, size_t size);
   15.75 +
   15.76 +/**
   15.77 + * A function pointer to the allocators <code>realloc()</code> function.
   15.78 + * @see UcxAllocator
   15.79 + */
   15.80 +typedef void*(*ucx_allocator_realloc)(void *pool, void *data, size_t n);
   15.81 +
   15.82 +/**
   15.83 + * A function pointer to the allocators <code>free()</code> function.
   15.84 + * @see UcxAllocator
   15.85 + */
   15.86 +typedef void(*ucx_allocator_free)(void *pool, void *data);
   15.87 +
   15.88 +/**
   15.89 + * UCX allocator data structure containing memory management functions.
   15.90 + */
   15.91 +typedef struct {
   15.92 +    /** Pointer to an area of memory or a complex memory pool.
   15.93 +     * This pointer will be passed to any memory management function as first
   15.94 +     * argument.
   15.95 +     */
   15.96 +    void *pool;
   15.97 +    /**
   15.98 +     * The <code>malloc()</code> function for this allocator.
   15.99 +     */
  15.100 +    ucx_allocator_malloc  malloc;
  15.101 +    /**
  15.102 +     * The <code>calloc()</code> function for this allocator.
  15.103 +     */
  15.104 +    ucx_allocator_calloc  calloc;
  15.105 +    /**
  15.106 +     * The <code>realloc()</code> function for this allocator.
  15.107 +     */
  15.108 +    ucx_allocator_realloc realloc;
  15.109 +    /**
  15.110 +     * The <code>free()</code> function for this allocator.
  15.111 +     */
  15.112 +    ucx_allocator_free    free;
  15.113 +} UcxAllocator;
  15.114 +
  15.115 +/**
  15.116 + * Returns a pointer to the default allocator.
  15.117 + * 
  15.118 + * The default allocator contains wrappers to the standard libc memory
  15.119 + * management functions. Use this function to get a pointer to a globally
  15.120 + * available allocator. You may also define an own UcxAllocator by assigning
  15.121 + * #UCX_ALLOCATOR_DEFAULT to a variable and pass the address of this variable
  15.122 + * to any function that takes a UcxAllocator as argument. Note that using
  15.123 + * this function is the recommended way of passing a default allocator, thus
  15.124 + * it never runs out of scope.
  15.125 + * 
  15.126 + * @return a pointer to the default allocator
  15.127 + * 
  15.128 + * @see UCX_ALLOCATOR_DEFAULT
  15.129 + */
  15.130 +UcxAllocator *ucx_default_allocator();
  15.131 +
  15.132 +/**
  15.133 + * A wrapper for the standard libc <code>malloc()</code> function.
  15.134 + * @param ignore ignored (may be used by allocators for pooled memory)
  15.135 + * @param n argument passed to <code>malloc()</code>
  15.136 + * @return return value of <code>malloc()</code>
  15.137 + */
  15.138 +void *ucx_default_malloc(void *ignore, size_t n);
  15.139 +/**
  15.140 + * A wrapper for the standard libc <code>calloc()</code> function.
  15.141 + * @param ignore ignored (may be used by allocators for pooled memory)
  15.142 + * @param n argument passed to <code>calloc()</code>
  15.143 + * @param size  argument passed to <code>calloc()</code>
  15.144 + * @return return value of <code>calloc()</code>
  15.145 + */
  15.146 +void *ucx_default_calloc(void *ignore, size_t n, size_t size);
  15.147 +/**
  15.148 + * A wrapper for the standard libc <code>realloc()</code> function.
  15.149 + * @param ignore ignored (may be used by allocators for pooled memory)
  15.150 + * @param data argumend passed to <code>realloc()</code>
  15.151 + * @param n argument passed to <code>realloc()</code>
  15.152 + * @return return value of <code>realloc()</code>
  15.153 + */
  15.154 +void *ucx_default_realloc(void *ignore, void *data, size_t n);
  15.155 +/**
  15.156 + * A wrapper for the standard libc <code>free()</code> function.
  15.157 + * @param ignore ignored (may be used by allocators for pooled memory)
  15.158 + * @param data argument passed to <code>free()</code>
  15.159 + */
  15.160 +void ucx_default_free(void *ignore, void *data);
  15.161 +
  15.162 +/**
  15.163 + * Shorthand for calling an allocators malloc function.
  15.164 + * @param allocator the allocator to use
  15.165 + * @param n size of space to allocate
  15.166 + * @return a pointer to the allocated memory area
  15.167 + */
  15.168 +#define almalloc(allocator, n) ((allocator)->malloc((allocator)->pool, n))
  15.169 +
  15.170 +/**
  15.171 + * Shorthand for calling an allocators calloc function.
  15.172 + * @param allocator the allocator to use
  15.173 + * @param n the count of elements the space should be allocated for
  15.174 + * @param size the size of each element
  15.175 + * @return a pointer to the allocated memory area
  15.176 + */
  15.177 +#define alcalloc(allocator, n, size) \
  15.178 +        ((allocator)->calloc((allocator)->pool, n, size))
  15.179 +
  15.180 +/**
  15.181 + * Shorthand for calling an allocators realloc function.
  15.182 + * @param allocator the allocator to use
  15.183 + * @param ptr the pointer to the memory area that shall be reallocated
  15.184 + * @param n the new size of the allocated memory area
  15.185 + * @return a pointer to the reallocated memory area
  15.186 + */
  15.187 +#define alrealloc(allocator, ptr, n) \
  15.188 +        ((allocator)->realloc((allocator)->pool, ptr, n))
  15.189 +
  15.190 +/**
  15.191 + * Shorthand for calling an allocators free function.
  15.192 + * @param allocator the allocator to use
  15.193 + * @param ptr the pointer to the memory area that shall be freed
  15.194 + */
  15.195 +#define alfree(allocator, ptr) ((allocator)->free((allocator)->pool, ptr))
  15.196 +
  15.197 +/**
  15.198 + * Convenient macro for a default allocator <code>struct</code> definition.
  15.199 + */
  15.200 +#define UCX_ALLOCATOR_DEFAULT {NULL, \
  15.201 +        ucx_default_malloc, ucx_default_calloc, ucx_default_realloc, \
  15.202 +        ucx_default_free }
  15.203 +
  15.204 +#ifdef	__cplusplus
  15.205 +}
  15.206 +#endif
  15.207 +
  15.208 +#endif	/* UCX_ALLOCATOR_H */
  15.209 +

    16.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    16.2 +++ b/src/ucx/avl.h	Tue Oct 17 16:15:41 2017 +0200
    16.3 @@ -0,0 +1,327 @@
    16.4 +/*
    16.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    16.6 + *
    16.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    16.8 + *
    16.9 + * Redistribution and use in source and binary forms, with or without
   16.10 + * modification, are permitted provided that the following conditions are met:
   16.11 + *
   16.12 + *   1. Redistributions of source code must retain the above copyright
   16.13 + *      notice, this list of conditions and the following disclaimer.
   16.14 + *
   16.15 + *   2. Redistributions in binary form must reproduce the above copyright
   16.16 + *      notice, this list of conditions and the following disclaimer in the
   16.17 + *      documentation and/or other materials provided with the distribution.
   16.18 + *
   16.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   16.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   16.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   16.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   16.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   16.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   16.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   16.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   16.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   16.29 + * POSSIBILITY OF SUCH DAMAGE.
   16.30 + */
   16.31 +
   16.32 +
   16.33 +/**
   16.34 + * @file avl.h
   16.35 + * 
   16.36 + * AVL tree implementation.
   16.37 + * 
   16.38 + * This binary search tree implementation allows average O(1) insertion and
   16.39 + * removal of elements (excluding binary search time).
   16.40 + * 
   16.41 + * @author Mike Becker
   16.42 + * @author Olaf Wintermann
   16.43 + */
   16.44 +
   16.45 +#ifndef UCX_AVL_H
   16.46 +#define UCX_AVL_H
   16.47 +
   16.48 +#include <ucx/ucx.h>
   16.49 +#include <ucx/allocator.h>
   16.50 +#include <inttypes.h>
   16.51 +
   16.52 +#ifdef	__cplusplus
   16.53 +extern "C" {
   16.54 +#endif
   16.55 +
   16.56 +/**
   16.57 + * UCX AVL Node type.
   16.58 + * 
   16.59 + * @see UcxAVLNode
   16.60 + */
   16.61 +typedef struct UcxAVLNode UcxAVLNode;
   16.62 +
   16.63 +/**
   16.64 + * UCX AVL Node.
   16.65 + */
   16.66 +struct UcxAVLNode {
   16.67 +    /**
   16.68 +     * The key for this node.
   16.69 +     */
   16.70 +    intptr_t key;
   16.71 +    /**
   16.72 +     * Data contained by this node.
   16.73 +     */
   16.74 +    void *value;
   16.75 +    /**
   16.76 +     * The height of this (sub)-tree.
   16.77 +     */
   16.78 +    size_t height;
   16.79 +    /**
   16.80 +     * Parent node.
   16.81 +     */
   16.82 +    UcxAVLNode *parent;
   16.83 +    /**
   16.84 +     * Root node of left subtree.
   16.85 +     */
   16.86 +    UcxAVLNode *left;
   16.87 +    /**
   16.88 +     * Root node of right subtree.
   16.89 +     */
   16.90 +    UcxAVLNode *right;
   16.91 +};
   16.92 +
   16.93 +/**
   16.94 + * UCX AVL Tree.
   16.95 + */
   16.96 +typedef struct {
   16.97 +    /**
   16.98 +     * The UcxAllocator that shall be used to manage the memory for node data.
   16.99 +     */
  16.100 +    UcxAllocator *allocator;
  16.101 +    /**
  16.102 +     * Root node of the tree.
  16.103 +     */
  16.104 +    UcxAVLNode *root;
  16.105 +    /**
  16.106 +     * Compare function that shall be used to compare the UcxAVLNode keys.
  16.107 +     * @see UcxAVLNode.key
  16.108 +     */
  16.109 +    cmp_func cmpfunc;
  16.110 +    /**
  16.111 +     * Custom user data.
  16.112 +     * This data will also be provided to the cmpfunc.
  16.113 +     */
  16.114 +    void *userdata;
  16.115 +} UcxAVLTree;
  16.116 +
  16.117 +/**
  16.118 + * Initializes a new UcxAVLTree with a default allocator.
  16.119 + * 
  16.120 + * @param cmpfunc the compare function that shall be used
  16.121 + * @return a new UcxAVLTree object
  16.122 + * @see ucx_avl_new_a()
  16.123 + */
  16.124 +UcxAVLTree *ucx_avl_new(cmp_func cmpfunc);
  16.125 +
  16.126 +/**
  16.127 + * Initializes a new UcxAVLTree with the specified allocator.
  16.128 + * 
  16.129 + * The cmpfunc should be capable of comparing two keys within this AVL tree.
  16.130 + * So if you want to use null terminated strings as keys, you could use the
  16.131 + * ucx_strcmp() function here.
  16.132 + * 
  16.133 + * @param cmpfunc the compare function that shall be used
  16.134 + * @param allocator the UcxAllocator that shall be used
  16.135 + * @return a new UcxAVLTree object
  16.136 + */
  16.137 +UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
  16.138 +
  16.139 +/**
  16.140 + * Destroys a UcxAVLTree.
  16.141 + * @param tree the tree to destroy
  16.142 + */
  16.143 +void ucx_avl_free(UcxAVLTree *tree);
  16.144 +
  16.145 +/**
  16.146 + * Macro for initializing a new UcxAVLTree with the default allocator and a
  16.147 + * ucx_ptrcmp() compare function.
  16.148 + * 
  16.149 + * @return a new default UcxAVLTree object
  16.150 + */
  16.151 +#define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
  16.152 +
  16.153 +/**
  16.154 + * Gets the node from the tree, that is associated with the specified key.
  16.155 + * @param tree the UcxAVLTree
  16.156 + * @param key the key
  16.157 + * @return the node (or <code>NULL</code>, if the key is not present)
  16.158 + */
  16.159 +UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key);
  16.160 +
  16.161 +/**
  16.162 + * Gets the value from the tree, that is associated with the specified key.
  16.163 + * @param tree the UcxAVLTree
  16.164 + * @param key the key
  16.165 + * @return the value (or <code>NULL</code>, if the key is not present)
  16.166 + */
  16.167 +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
  16.168 +
  16.169 +/**
  16.170 + * A mode for #ucx_avl_find_node() with the same behavior as
  16.171 + * #ucx_avl_get_node().
  16.172 + */
  16.173 +#define UCX_AVL_FIND_EXACT         0
  16.174 +/**
  16.175 + * A mode for #ucx_avl_find_node() finding the node whose key is at least
  16.176 + * as large as the specified key.
  16.177 + */
  16.178 +#define UCX_AVL_FIND_LOWER_BOUNDED 1
  16.179 +/**
  16.180 + * A mode for #ucx_avl_find_node() finding the node whose key is at most
  16.181 + * as large as the specified key.
  16.182 + */
  16.183 +#define UCX_AVL_FIND_UPPER_BOUNDED 2
  16.184 +/**
  16.185 + * A mode for #ucx_avl_find_node() finding the node with a key that is as close
  16.186 + * to the specified key as possible. If the key is present, the behavior is
  16.187 + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
  16.188 + * empty trees.
  16.189 + */
  16.190 +#define UCX_AVL_FIND_CLOSEST       3
  16.191 +
  16.192 +/**
  16.193 + * Finds a node within the tree. The following modes are supported:
  16.194 + * <ul>
  16.195 + * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li>
  16.196 + * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least
  16.197 + * as large as the specified key</li>
  16.198 + * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most
  16.199 + * as large as the specified key</li>
  16.200 + * <li>#UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to
  16.201 + * the specified key as possible. If the key is present, the behavior is
  16.202 + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
  16.203 + * empty trees.</li> 
  16.204 + * </ul>
  16.205 + * 
  16.206 + * The distance function provided MUST agree with the compare function of
  16.207 + * the AVL tree.
  16.208 + * 
  16.209 + * @param tree the UcxAVLTree
  16.210 + * @param key the key
  16.211 + * @param dfnc the distance function
  16.212 + * @param mode the find mode
  16.213 + * @return the node (or <code>NULL</code>, if no node can be found)
  16.214 + */
  16.215 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
  16.216 +        distance_func dfnc, int mode);
  16.217 +
  16.218 +/**
  16.219 + * Finds a value within the tree.
  16.220 + * See #ucx_avl_find_node() for details.
  16.221 + * 
  16.222 + * @param tree the UcxAVLTree
  16.223 + * @param key the key
  16.224 + * @param dfnc the distance function
  16.225 + * @param mode the find mode
  16.226 + * @return the value (or <code>NULL</code>, if no value can be found)
  16.227 + */
  16.228 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
  16.229 +        distance_func dfnc, int mode);
  16.230 +
  16.231 +/**
  16.232 + * Puts a key/value pair into the tree.
  16.233 + * 
  16.234 + * Attention: use this function only, if a possible old value does not need
  16.235 + * to be preserved.
  16.236 + * 
  16.237 + * @param tree the UcxAVLTree
  16.238 + * @param key the key
  16.239 + * @param value the new value
  16.240 + * @return zero, if and only if the operation succeeded
  16.241 + */
  16.242 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
  16.243 +
  16.244 +/**
  16.245 + * Puts a key/value pair into the tree.
  16.246 + * 
  16.247 + * This is a secure function which saves the old value to the variable pointed
  16.248 + * at by oldvalue.
  16.249 + * 
  16.250 + * @param tree the UcxAVLTree
  16.251 + * @param key the key
  16.252 + * @param value the new value
  16.253 + * @param oldvalue optional: a pointer to the location where a possible old
  16.254 + * value shall be stored
  16.255 + * @return zero, if and only if the operation succeeded
  16.256 + */
  16.257 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
  16.258 +
  16.259 +/**
  16.260 + * Removes a node from the AVL tree.
  16.261 + * 
  16.262 + * Note: the specified node is logically removed. The tree implementation
  16.263 + * decides which memory area is freed. In most cases the here provided node
  16.264 + * is freed, so its further use is generally undefined.
  16.265 + * 
  16.266 + * @param tree the UcxAVLTree
  16.267 + * @param node the node to remove
  16.268 + * @return zero, if and only if an element has been removed
  16.269 + */
  16.270 +int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node);
  16.271 +
  16.272 +/**
  16.273 + * Removes an element from the AVL tree.
  16.274 + * 
  16.275 + * @param tree the UcxAVLTree
  16.276 + * @param key the key
  16.277 + * @return zero, if and only if an element has been removed
  16.278 + */
  16.279 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
  16.280 +
  16.281 +/**
  16.282 + * Removes an element from the AVL tree.
  16.283 + * 
  16.284 + * This is a secure function which saves the old key and value data from node
  16.285 + * to the variables at the location of oldkey and oldvalue (if specified), so
  16.286 + * they can be freed afterwards (if necessary).
  16.287 + * 
  16.288 + * Note: the returned key in oldkey is possibly not the same as the provided
  16.289 + * key for the lookup (in terms of memory location).
  16.290 + * 
  16.291 + * @param tree the UcxAVLTree
  16.292 + * @param key the key of the element to remove
  16.293 + * @param oldkey optional: a pointer to the location where the old key shall be
  16.294 + * stored
  16.295 + * @param oldvalue optional: a pointer to the location where the old value
  16.296 + * shall be stored
  16.297 + * @return zero, if and only if an element has been removed
  16.298 + */
  16.299 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
  16.300 +        intptr_t *oldkey, void **oldvalue);
  16.301 +
  16.302 +/**
  16.303 + * Counts the nodes in the specified UcxAVLTree.
  16.304 + * @param tree the AVL tree
  16.305 + * @return the node count
  16.306 + */
  16.307 +size_t ucx_avl_count(UcxAVLTree *tree);
  16.308 +
  16.309 +/**
  16.310 + * Finds the in-order predecessor of the given node.
  16.311 + * @param node an AVL node
  16.312 + * @return the in-order predecessor of the given node, or <code>NULL</code> if
  16.313 + * the given node is the in-order minimum
  16.314 + */
  16.315 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node);
  16.316 +
  16.317 +/**
  16.318 + * Finds the in-order successor of the given node.
  16.319 + * @param node an AVL node
  16.320 + * @return the in-order successor of the given node, or <code>NULL</code> if
  16.321 + * the given node is the in-order maximum
  16.322 + */
  16.323 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node);
  16.324 +
  16.325 +#ifdef	__cplusplus
  16.326 +}
  16.327 +#endif
  16.328 +
  16.329 +#endif	/* UCX_AVL_H */
  16.330 +

    17.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    17.2 +++ b/src/ucx/buffer.h	Tue Oct 17 16:15:41 2017 +0200
    17.3 @@ -0,0 +1,270 @@
    17.4 +/*
    17.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    17.6 + *
    17.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    17.8 + *
    17.9 + * Redistribution and use in source and binary forms, with or without
   17.10 + * modification, are permitted provided that the following conditions are met:
   17.11 + *
   17.12 + *   1. Redistributions of source code must retain the above copyright
   17.13 + *      notice, this list of conditions and the following disclaimer.
   17.14 + *
   17.15 + *   2. Redistributions in binary form must reproduce the above copyright
   17.16 + *      notice, this list of conditions and the following disclaimer in the
   17.17 + *      documentation and/or other materials provided with the distribution.
   17.18 + *
   17.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   17.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   17.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   17.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   17.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   17.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   17.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   17.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   17.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   17.29 + * POSSIBILITY OF SUCH DAMAGE.
   17.30 + */
   17.31 +
   17.32 +/**
   17.33 + * @file buffer.h
   17.34 + * 
   17.35 + * Advanced buffer implementation.
   17.36 + * 
   17.37 + * Instances of UcxBuffer can be used to read from or to write to like one
   17.38 + * would do with a stream. This allows the use of ucx_stream_copy() to copy
   17.39 + * contents from one buffer to another.
   17.40 + * 
   17.41 + * Some features for convenient use of the buffer
   17.42 + * can be enabled. See the documentation of the macro constants for more
   17.43 + * information.
   17.44 + * 
   17.45 + * @author Mike Becker
   17.46 + * @author Olaf Wintermann
   17.47 + */
   17.48 +
   17.49 +#ifndef UCX_BUFFER_H
   17.50 +#define	UCX_BUFFER_H
   17.51 +
   17.52 +#include <ucx/ucx.h>
   17.53 +#include <sys/types.h>
   17.54 +#include <stdio.h>
   17.55 +
   17.56 +#ifdef	__cplusplus
   17.57 +extern "C" {
   17.58 +#endif
   17.59 +
   17.60 +/**
   17.61 + * No buffer features enabled (all flags cleared).
   17.62 + */
   17.63 +#define UCX_BUFFER_DEFAULT      0x00
   17.64 +
   17.65 +/**
   17.66 + * If this flag is enabled, the buffer will automatically free its contents.
   17.67 + */
   17.68 +#define UCX_BUFFER_AUTOFREE     0x01
   17.69 +
   17.70 +/**
   17.71 + * If this flag is enabled, the buffer will automatically extends its capacity.
   17.72 + */
   17.73 +#define UCX_BUFFER_AUTOEXTEND   0x02
   17.74 +
   17.75 +/** UCX Buffer. */
   17.76 +typedef struct {
   17.77 +    /** A pointer to the buffer contents. */
   17.78 +    char *space;
   17.79 +    /** Current position of the buffer. */
   17.80 +    size_t pos;
   17.81 +    /** Current capacity (i.e. maximum size) of the buffer. */
   17.82 +    size_t capacity;
   17.83 +    /** Current size of the buffer content. */
   17.84 +    size_t size;
   17.85 +    /**
   17.86 +     * Flag register for buffer features.
   17.87 +     * @see #UCX_BUFFER_DEFAULT
   17.88 +     * @see #UCX_BUFFER_AUTOFREE
   17.89 +     * @see #UCX_BUFFER_AUTOEXTEND
   17.90 +     */
   17.91 +    int flags;
   17.92 +} UcxBuffer;
   17.93 +
   17.94 +/**
   17.95 + * Creates a new buffer.
   17.96 + * 
   17.97 + * <b>Note:</b> you may provide <code>NULL</code> as argument for
   17.98 + * <code>space</code>. Then this function will allocate the space and enforce
   17.99 + * the #UCX_BUFFER_AUTOFREE flag.
  17.100 + * 
  17.101 + * @param space pointer to the memory area, or <code>NULL</code> to allocate
  17.102 + * new memory
  17.103 + * @param capacity the capacity of the buffer
  17.104 + * @param flags buffer features (see UcxBuffer.flags)
  17.105 + * @return the new buffer
  17.106 + */
  17.107 +UcxBuffer *ucx_buffer_new(void *space, size_t capacity, int flags);
  17.108 +
  17.109 +/**
  17.110 + * Destroys a buffer.
  17.111 + * 
  17.112 + * If the #UCX_BUFFER_AUTOFREE feature is enabled, the contents of the buffer
  17.113 + * are also freed.
  17.114 + * 
  17.115 + * @param buffer the buffer to destroy
  17.116 + */
  17.117 +void ucx_buffer_free(UcxBuffer* buffer);
  17.118 +
  17.119 +/**
  17.120 + * Creates a new buffer and fills it with extracted content from another buffer.
  17.121 + * 
  17.122 + * <b>Note:</b> the #UCX_BUFFER_AUTOFREE feature is enforced for the new buffer.
  17.123 + * 
  17.124 + * @param src the source buffer
  17.125 + * @param start the start position of extraction
  17.126 + * @param length the count of bytes to extract (must not be zero)
  17.127 + * @param flags feature mask for the new buffer
  17.128 + * @return a new buffer containing the extraction
  17.129 + */
  17.130 +UcxBuffer* ucx_buffer_extract(UcxBuffer *src,
  17.131 +        size_t start, size_t length, int flags);
  17.132 +
  17.133 +/**
  17.134 + * A shorthand macro for the full extraction of the buffer.
  17.135 + * 
  17.136 + * @param src the source buffer
  17.137 + * @param flags feature mask for the new buffer
  17.138 + * @return a new buffer with the extracted content
  17.139 + */
  17.140 +#define ucx_buffer_clone(src,flags) \
  17.141 +    ucx_buffer_extract(src, 0, (src)->capacity, flags)
  17.142 +
  17.143 +/**
  17.144 + * Moves the position of the buffer.
  17.145 + * 
  17.146 + * The new position is relative to the <code>whence</code> argument.
  17.147 + *
  17.148 + * SEEK_SET marks the start of the buffer.
  17.149 + * SEEK_CUR marks the current position.
  17.150 + * SEEK_END marks the end of the buffer.
  17.151 + * 
  17.152 + * With an offset of zero, this function sets the buffer position to zero
  17.153 + * (SEEK_SET), the buffer size (SEEK_END) or leaves the buffer position
  17.154 + * unchanged (SEEK_CUR).
  17.155 + * 
  17.156 + * @param buffer
  17.157 + * @param offset position offset relative to <code>whence</code>
  17.158 + * @param whence one of SEEK_SET, SEEK_CUR or SEEK_END
  17.159 + * @return 0 on success, non-zero if the position is invalid
  17.160 + *
  17.161 + */
  17.162 +int ucx_buffer_seek(UcxBuffer *buffer, off_t offset, int whence);
  17.163 +
  17.164 +/**
  17.165 + * Clears the buffer by resetting the position and deleting the data.
  17.166 + * 
  17.167 + * The data is deleted by a zeroing it with call to <code>memset()</code>.
  17.168 + * 
  17.169 + * @param buffer the buffer to be cleared
  17.170 + */
  17.171 +#define ucx_buffer_clear(buffer) memset(buffer->space, 0, buffer->size); \
  17.172 +        buffer->size = 0; buffer->pos = 0;
  17.173 +
  17.174 +/**
  17.175 + * Tests, if the buffer position has exceeded the buffer capacity.
  17.176 + * 
  17.177 + * @param buffer the buffer to test
  17.178 + * @return non-zero, if the current buffer position has exceeded the last
  17.179 + * available byte of the buffer.
  17.180 + */
  17.181 +int ucx_buffer_eof(UcxBuffer *buffer);
  17.182 +
  17.183 +
  17.184 +/**
  17.185 + * Extends the capacity of the buffer.
  17.186 + * 
  17.187 + * <b>Note:</b> The buffer capacity increased by a power of two. I.e.
  17.188 + * the buffer capacity is doubled, as long as it would not hold the current
  17.189 + * content plus the additional required bytes.
  17.190 + * 
  17.191 + * <b>Attention:</b> the argument provided is the number of <i>additional</i>
  17.192 + * bytes the buffer shall hold. It is <b>NOT</b> the total number of bytes the
  17.193 + * buffer shall hold.
  17.194 + * 
  17.195 + * @param buffer the buffer to extend
  17.196 + * @param additional_bytes the number of additional bytes the buffer shall
  17.197 + * <i>at least</i> hold
  17.198 + * @return 0 on success or a non-zero value on failure
  17.199 + */
  17.200 +int ucx_buffer_extend(UcxBuffer *buffer, size_t additional_bytes);
  17.201 +
  17.202 +/**
  17.203 + * Writes data to a UcxBuffer.
  17.204 + * 
  17.205 + * The position of the buffer is increased by the number of bytes written.
  17.206 + * 
  17.207 + * @param ptr a pointer to the memory area containing the bytes to be written
  17.208 + * @param size the length of one element
  17.209 + * @param nitems the element count
  17.210 + * @param buffer the UcxBuffer to write to
  17.211 + * @return the total count of bytes written
  17.212 + */
  17.213 +size_t ucx_buffer_write(const void *ptr, size_t size, size_t nitems,
  17.214 +        UcxBuffer *buffer);
  17.215 +
  17.216 +/**
  17.217 + * Reads data from a UcxBuffer.
  17.218 + * 
  17.219 + * The position of the buffer is increased by the number of bytes read.
  17.220 + * 
  17.221 + * @param ptr a pointer to the memory area where to store the read data
  17.222 + * @param size the length of one element
  17.223 + * @param nitems the element count
  17.224 + * @param buffer the UcxBuffer to read from
  17.225 + * @return the total number of elements read
  17.226 + */
  17.227 +size_t ucx_buffer_read(void *ptr, size_t size, size_t nitems,
  17.228 +        UcxBuffer *buffer);
  17.229 +
  17.230 +/**
  17.231 + * Writes a character to a buffer.
  17.232 + * 
  17.233 + * The least significant byte of the argument is written to the buffer. If the
  17.234 + * end of the buffer is reached and #UCX_BUFFER_AUTOEXTEND feature is enabled,
  17.235 + * the buffer capacity is extended by ucx_buffer_extend(). If the feature is
  17.236 + * disabled or buffer extension fails, <code>EOF</code> is returned.
  17.237 + * 
  17.238 + * On successful write the position of the buffer is increased.
  17.239 + * 
  17.240 + * @param buffer the buffer to write to
  17.241 + * @param c the character to write as <code>int</code> value
  17.242 + * @return the byte that has bean written as <code>int</code> value or
  17.243 + * <code>EOF</code> when the end of the stream is reached and automatic
  17.244 + * extension is not enabled or not possible
  17.245 + */
  17.246 +int ucx_buffer_putc(UcxBuffer *buffer, int c);
  17.247 +
  17.248 +/**
  17.249 + * Gets a character from a buffer.
  17.250 + * 
  17.251 + * The current position of the buffer is increased after a successful read.
  17.252 + * 
  17.253 + * @param buffer the buffer to read from
  17.254 + * @return the character as <code>int</code> value or <code>EOF</code>, if the
  17.255 + * end of the buffer is reached
  17.256 + */
  17.257 +int ucx_buffer_getc(UcxBuffer *buffer);
  17.258 +
  17.259 +/**
  17.260 + * Writes a string to a buffer.
  17.261 + * 
  17.262 + * @param buffer the buffer
  17.263 + * @param str the string
  17.264 + * @return the number of bytes written
  17.265 + */
  17.266 +size_t ucx_buffer_puts(UcxBuffer *buffer, char *str);
  17.267 +
  17.268 +#ifdef	__cplusplus
  17.269 +}
  17.270 +#endif
  17.271 +
  17.272 +#endif	/* UCX_BUFFER_H */
  17.273 +

    18.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    18.2 +++ b/src/ucx/list.h	Tue Oct 17 16:15:41 2017 +0200
    18.3 @@ -0,0 +1,428 @@
    18.4 +/*
    18.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
    18.6 + *
    18.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
    18.8 + *
    18.9 + * Redistribution and use in source and binary forms, with or without
   18.10 + * modification, are permitted provided that the following conditions are met:
   18.11 + *
   18.12 + *   1. Redistributions of source code must retain the above copyright
   18.13 + *      notice, this list of conditions and the following disclaimer.
   18.14 + *
   18.15 + *   2. Redistributions in binary form must reproduce the above copyright
   18.16 + *      notice, this list of conditions and the following disclaimer in the
   18.17 + *      documentation and/or other materials provided with the distribution.
   18.18 + *
   18.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   18.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   18.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
   18.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   18.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   18.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   18.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   18.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   18.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   18.29 + * POSSIBILITY OF SUCH DAMAGE.
   18.30 + */
   18.31 +/**
   18.32 + * Doubly linked list implementation.
   18.33 + * 
   18.34 + * @file   list.h
   18.35 + * @author Mike Becker
   18.36 + * @author Olaf Wintermann
   18.37 + */
   18.38 +
   18.39 +#ifndef UCX_LIST_H
   18.40 +#define	UCX_LIST_H
   18.41 +
   18.42 +#include <ucx/ucx.h>
   18.43 +#include <ucx/allocator.h>
   18.44 +
   18.45 +#ifdef	__cplusplus
   18.46 +extern "C" {
   18.47 +#endif
   18.48 +
   18.49 +/**
   18.50 + * Loop statement for UCX lists.
   18.51 + * 
   18.52 + * The first argument is the name of the iteration variable. The scope of
   18.53 + * this variable is limited to the <code>UCX_FOREACH</code> statement.
   18.54 + * 
   18.55 + * The second argument is a pointer to the list. In most cases this will be the
   18.56 + * pointer to the first element of the list, but it may also be an arbitrary
   18.57 + * element of the list. The iteration will then start with that element.
   18.58 + * 
   18.59 + * @param list The first element of the list
   18.60 + * @param elem The variable name of the element
   18.61 + */
   18.62 +#define UCX_FOREACH(elem,list) \
   18.63 +        for (UcxList* elem = list ; elem != NULL ; elem = elem->next)
   18.64 +
   18.65 +/**
   18.66 + * UCX list type.
   18.67 + * @see UcxList
   18.68 + */
   18.69 +typedef struct UcxList UcxList;
   18.70 +
   18.71 +/**
   18.72 + * UCX list structure.
   18.73 + */
   18.74 +struct UcxList {
   18.75 +    /**
   18.76 +     * List element payload.
   18.77 +     */
   18.78 +    void    *data;
   18.79 +    /**
   18.80 +     * Pointer to the next list element or <code>NULL</code>, if this is the
   18.81 +     * last element.
   18.82 +     */
   18.83 +    UcxList *next;
   18.84 +    /**
   18.85 +     * Pointer to the previous list element or <code>NULL</code>, if this is
   18.86 +     * the first element.
   18.87 +     */
   18.88 +    UcxList *prev;
   18.89 +};
   18.90 +
   18.91 +/**
   18.92 + * Creates an element-wise copy of a list.
   18.93 + * 
   18.94 + * This function clones the specified list by creating new list elements and
   18.95 + * copying the data with the specified copy_func(). If no copy_func() is
   18.96 + * specified, a shallow copy is created and the new list will reference the
   18.97 + * same data as the source list.
   18.98 + * 
   18.99 + * @param list the list to copy
  18.100 + * @param cpyfnc a pointer to the function that shall copy an element (may be
  18.101 + * <code>NULL</code>)
  18.102 + * @param data additional data for the copy_func()
  18.103 + * @return a pointer to the copy
  18.104 + */
  18.105 +UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data);
  18.106 +
  18.107 +/**
  18.108 + * Creates an element-wise copy of a list using a UcxAllocator.
  18.109 + * 
  18.110 + * See ucx_list_clone() for details.
  18.111 + * 
  18.112 + * You might want to pass the allocator via the <code>data</code> parameter,
  18.113 + * to access it within the copy function for making deep copies.
  18.114 + * 
  18.115 + * @param allocator the allocator to use
  18.116 + * @param list the list to copy
  18.117 + * @param cpyfnc a pointer to the function that shall copy an element (may be
  18.118 + * <code>NULL</code>)
  18.119 + * @param data additional data for the copy_func()
  18.120 + * @return a pointer to the copy
  18.121 + * @see ucx_list_clone()
  18.122 + */
  18.123 +UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list,
  18.124 +        copy_func cpyfnc, void* data);
  18.125 +
  18.126 +/**
  18.127 + * Compares two UCX lists element-wise by using a compare function.
  18.128 + * 
  18.129 + * Each element of the two specified lists are compared by using the specified
  18.130 + * compare function and the additional data. The type and content of this
  18.131 + * additional data depends on the cmp_func() used.
  18.132 + * 
  18.133 + * If the list pointers denote elements within a list, the lists are compared
  18.134 + * starting with the denoted elements. Thus any previous elements are not taken
  18.135 + * into account. This might be useful to check, if certain list tails match
  18.136 + * each other.
  18.137 + * 
  18.138 + * @param list1 the first list
  18.139 + * @param list2 the second list
  18.140 + * @param cmpfnc the compare function
  18.141 + * @param data additional data for the compare function
  18.142 + * @return 1, if and only if the two lists equal element-wise, 0 otherwise
  18.143 + */
  18.144 +int ucx_list_equals(const UcxList *list1, const UcxList *list2,
  18.145 +        cmp_func cmpfnc, void* data);
  18.146 +
  18.147 +/**
  18.148 + * Destroys the entire list.
  18.149 + * 
  18.150 + * The members of the list are not automatically freed, so ensure they are
  18.151 + * otherwise referenced or destroyed by ucx_list_free_contents().
  18.152 + * Otherwise, a memory leak is likely to occur.
  18.153 + * 
  18.154 + * <b>Caution:</b> the argument <b>MUST</b> denote an entire list (i.e. a call
  18.155 + * to ucx_list_first() on the argument must return the argument itself)
  18.156 + * 
  18.157 + * @param list the list to free
  18.158 + * @see ucx_list_free_contents()
  18.159 + */
  18.160 +void ucx_list_free(UcxList *list);
  18.161 +
  18.162 +/**
  18.163 + * Destroys the entire list using a UcxAllocator.
  18.164 + * 
  18.165 + * See ucx_list_free() for details.
  18.166 + * 
  18.167 + * @param allocator the allocator to use
  18.168 + * @param list the list to free
  18.169 + * @see ucx_list_free()
  18.170 + */
  18.171 +void ucx_list_free_a(UcxAllocator *allocator, UcxList *list);
  18.172 +
  18.173 +/**
  18.174 + * Destroys the contents of the specified list by calling the specified
  18.175 + * destructor on each of them.
  18.176 + * 
  18.177 + * Note, that the contents are not usable afterwards and the list should be
  18.178 + * destroyed with ucx_list_free().
  18.179 + * 
  18.180 + * @param list the list for which the contents shall be freed
  18.181 + * @param destr the destructor function (e.g. stdlib free())
  18.182 + * @see ucx_list_free()
  18.183 + */
  18.184 +void ucx_list_free_content(UcxList* list, ucx_destructor destr);
  18.185 +
  18.186 +
  18.187 +/**
  18.188 + * Inserts an element at the end of the list.
  18.189 + * 
  18.190 + * This is generally an O(n) operation, as the end of the list is retrieved with
  18.191 + * ucx_list_last().
  18.192 + * 
  18.193 + * @param list the list where to append the data, or <code>NULL</code> to
  18.194 + * create a new list
  18.195 + * @param data the data to insert
  18.196 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
  18.197 + * the newly created list otherwise
  18.198 + */
  18.199 +UcxList *ucx_list_append(UcxList *list, void *data);
  18.200 +
  18.201 +/**
  18.202 + * Inserts an element at the end of the list using a UcxAllocator.
  18.203 + * 
  18.204 + * See ucx_list_append() for details.
  18.205 + * 
  18.206 + * @param allocator the allocator to use
  18.207 + * @param list the list where to append the data, or <code>NULL</code> to
  18.208 + * create a new list
  18.209 + * @param data the data to insert
  18.210 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
  18.211 + * the newly created list otherwise
  18.212 + * @see ucx_list_append()
  18.213 + */
  18.214 +UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data);
  18.215 +
  18.216 +/**
  18.217 + * Inserts an element at the end of the list, if it is not present in the list.
  18.218 + * 
  18.219 + * 
  18.220 + * @param list the list where to append the data, or <code>NULL</code> to
  18.221 + * create a new list
  18.222 + * @param data the data to insert
  18.223 + * @param cmpfnc the compare function
  18.224 + * @param cmpdata additional data for the compare function
  18.225 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
  18.226 + * the newly created list otherwise
  18.227 + * @see ucx_list_append()
  18.228 + */
  18.229 +UcxList *ucx_list_append_once(UcxList *list, void *data,
  18.230 +        cmp_func cmpfnc, void *cmpdata);
  18.231 +
  18.232 +/**
  18.233 + * Inserts an element at the end of the list, if it is not present in the list,
  18.234 + * using a UcxAllocator.
  18.235 + * 
  18.236 + * See ucx_list_append() for details.
  18.237 + * 
  18.238 + * @param allocator the allocator to use
  18.239 + * @param list the list where to append the data, or <code>NULL</code> to
  18.240 + * create a new list
  18.241 + * @param data the data to insert
  18.242 + * @param cmpfnc the compare function
  18.243 + * @param cmpdata additional data for the compare function
  18.244 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
  18.245 + * the newly created list otherwise
  18.246 + * @see ucx_list_append_a()
  18.247 + */
  18.248 +UcxList *ucx_list_append_once_a(UcxAllocator *allocator,
  18.249 +        UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata);
  18.250 +
  18.251 +/**
  18.252 + * Inserts an element at the beginning of the list.
  18.253 + * 
  18.254 + * You <i>should</i> overwrite the old list pointer by calling
  18.255 + * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may
  18.256 + * also perform successive calls of ucx_list_prepend() on the same list pointer,
  18.257 + * as this function always searchs for the head of the list with
  18.258 + * ucx_list_first().
  18.259 + * 
  18.260 + * @param list the list where to insert the data or <code>NULL</code> to create
  18.261 + * a new list
  18.262 + * @param data the data to insert
  18.263 + * @return a pointer to the new list head
  18.264 + */
  18.265 +UcxList *ucx_list_prepend(UcxList *list, void *data);
  18.266 +
  18.267 +/**
  18.268 + * Inserts an element at the beginning of the list using a UcxAllocator.
  18.269 + * 
  18.270 + * See ucx_list_prepend() for details.
  18.271 + * 
  18.272 + * @param allocator the allocator to use
  18.273 + * @param list the list where to insert the data or <code>NULL</code> to create
  18.274 + * a new list
  18.275 + * @param data the data to insert
  18.276 + * @return a pointer to the new list head
  18.277 + * @see ucx_list_prepend()
  18.278 + */
  18.279 +UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data);
  18.280 +
  18.281 +/**
  18.282 + * Concatenates two lists.
  18.283 + * 
  18.284 + * Either of the two arguments may be <code>NULL</code>.
  18.285 + * 
  18.286 + * This function modifies the references to the next/previous element of
  18.287 + * the last/first element of <code>list1</code>/<code>
  18.288 + * list2</code>.
  18.289 + * 
  18.290 + * @param list1 first list
  18.291 + * @param list2 second list
  18.292 + * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is
  18.293 + * returned, otherwise <code>list1</code> is returned
  18.294 + */
  18.295 +UcxList *ucx_list_concat(UcxList *list1, UcxList *list2);
  18.296 +
  18.297 +/**
  18.298 + * Returns the first element of a list.
  18.299 + * 
  18.300 + * If the argument is the list pointer, it is directly returned. Otherwise
  18.301 + * this function traverses to the first element of the list and returns the
  18.302 + * list pointer.
  18.303 + * 
  18.304 + * @param elem one element of the list
  18.305 + * @return the first element of the list, the specified element is a member of
  18.306 + */
  18.307 +UcxList *ucx_list_first(const UcxList *elem);
  18.308 +
  18.309 +/**
  18.310 + * Returns the last element of a list.
  18.311 + * 
  18.312 + * If the argument has no successor, it is the last element and therefore
  18.313 + * directly returned. Otherwise this function traverses to the last element of
  18.314 + * the list and returns it.
  18.315 + * 
  18.316 + * @param elem one element of the list
  18.317 + * @return the last element of the list, the specified element is a member of
  18.318 + */
  18.319 +UcxList *ucx_list_last(const UcxList *elem);
  18.320 +
  18.321 +/**
  18.322 + * Returns the list element at the specified index.
  18.323 + * 
  18.324 + * @param list the list to retrieve the element from
  18.325 + * @param index index of the element to return
  18.326 + * @return the element at the specified index or <code>NULL</code>, if the
  18.327 + * index is greater than the list size
  18.328 + */
  18.329 +UcxList *ucx_list_get(const UcxList *list, size_t index);
  18.330 +
  18.331 +/**
  18.332 + * Returns the index of an element.
  18.333 + * 
  18.334 + * @param list the list where to search for the element
  18.335 + * @param elem the element to find
  18.336 + * @return the index of the element or -1 if the list does not contain the
  18.337 + * element
  18.338 + */
  18.339 +ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem);
  18.340 +
  18.341 +/**
  18.342 + * Returns the element count of the list.
  18.343 + * 
  18.344 + * @param list the list whose elements are counted
  18.345 + * @return the element count
  18.346 + */
  18.347 +size_t ucx_list_size(const UcxList *list);
  18.348 +
  18.349 +/**
  18.350 + * Returns the index of an element containing the specified data.
  18.351 + *
  18.352 + * This function uses a cmp_func() to compare the data of each list element
  18.353 + * with the specified data. If no cmp_func is provided, the pointers are
  18.354 + * compared.
  18.355 + * 
  18.356 + * If the list contains the data more than once, the index of the first
  18.357 + * occurrence is returned.
  18.358 + *  
  18.359 + * @param list the list where to search for the data
  18.360 + * @param elem the element data
  18.361 + * @param cmpfnc the compare function
  18.362 + * @param data additional data for the compare function
  18.363 + * @return the index of the element containing the specified data or -1 if the
  18.364 + * data is not found in this list
  18.365 + */
  18.366 +ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
  18.367 +
  18.368 +/**
  18.369 + * Checks, if a list contains a specific element.
  18.370 + * 
  18.371 + * An element is found, if ucx_list_find() returns a value greater than -1.
  18.372 + * 
  18.373 + * @param list the list where to search for the data
  18.374 + * @param elem the element data
  18.375 + * @param cmpfnc the compare function
  18.376 + * @param data additional data for the compare function
  18.377 + * @return 1, if and only if the list contains the specified element data
  18.378 + * @see ucx_list_find()
  18.379 + */
  18.380 +int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
  18.381 +
  18.382 +/**
  18.383 + * Sorts a UcxList with natural merge sort.
  18.384 + * 
  18.385 + * This function uses O(n) additional temporary memory for merge operations
  18.386 + * that is automatically freed after each merge.
  18.387 + * 
  18.388 + * As the head of the list might change, you <b>MUST</b> call this function
  18.389 + * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>.
  18.390 + * 
  18.391 + * @param list the list to sort
  18.392 + * @param cmpfnc the function that shall be used to compare the element data
  18.393 + * @param data additional data for the cmp_func()
  18.394 + * @return the sorted list
  18.395 + */
  18.396 +UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data);
  18.397 +
  18.398 +/**
  18.399 + * Removes an element from the list.
  18.400 + * 
  18.401 + * If the first element is removed, the list pointer changes. So it is
  18.402 + * <i>highly recommended</i> to <i>always</i> update the pointer by calling
  18.403 + * <code>mylist = ucx_list_remove(mylist, myelem);</code>.
  18.404 + * 
  18.405 + * @param list the list from which the element shall be removed
  18.406 + * @param element the element to remove
  18.407 + * @return returns the updated list pointer or <code>NULL</code>, if the list
  18.408 + * is now empty
  18.409 + */
  18.410 +UcxList *ucx_list_remove(UcxList *list, UcxList *element);
  18.411 +
  18.412 +/**
  18.413 + * Removes an element from the list using a UcxAllocator.
  18.414 + * 
  18.415 + * See ucx_list_remove() for details.
  18.416 + * 
  18.417 + * @param allocator the allocator to use
  18.418 + * @param list the list from which the element shall be removed
  18.419 + * @param element the element to remove
  18.420 + * @return returns the updated list pointer or <code>NULL</code>, if the list
  18.421 + * @see ucx_list_remove()
  18.422 + */
  18.423 +UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
  18.424 +        UcxList *element);
  18.425 +
  18.426 +#ifdef	__cplusplus
  18.427 +}
  18.428 +#endif
  18.429 +
  18.430 +#endif	/* UCX_LIST_H */
  18.431 +