# HG changeset patch # User Olaf Wintermann # Date 1433271443 -7200 # Node ID 649eb328674a7d80f49aa125152a6cdf3cd760ce # Parent 7072a2b4ae35452c4a9d9cc40e53853241da4673 implemented minimal executor features and added missing ucx files diff -r 7072a2b4ae35 -r 649eb328674a libidav/davqlexec.c --- a/libidav/davqlexec.c Tue Jun 02 10:07:20 2015 +0200 +++ b/libidav/davqlexec.c Tue Jun 02 20:57:23 2015 +0200 @@ -33,17 +33,19 @@ #include #include "davqlexec.h" #include "utils.h" +#include "methods.h" +#include "session.h" -DavQLResult* dav_statement_exec(DavSession *sn, DavQLStatement *st, ...) { +DavResult* dav_statement_exec(DavSession *sn, DavQLStatement *st, ...) { va_list ap; va_start(ap, st); - DavQLResult *result = dav_statement_execv(sn, st, ap); + DavResult *result = dav_statement_execv(sn, st, ap); va_end(ap); return result; } -DavQLResult* dav_statement_execv(DavSession *sn, DavQLStatement *st, va_list ap) { - DavQLResult *result = dav_session_malloc(sn, sizeof(DavQLResult)); +DavResult* dav_statement_execv(DavSession *sn, DavQLStatement *st, va_list ap) { + DavResult *result = dav_session_malloc(sn, sizeof(DavResult)); result->result = NULL; result->status = 1; @@ -57,7 +59,7 @@ sstr_t path = dav_format_string(sn->mp->allocator, st->path, ap, &error); if(st->type == DAVQL_SELECT) { - dav_exec_get(sn, st, path.ptr, ap); + *result = dav_exec_select(sn, st, path.ptr, ap); } else { // TODO } @@ -126,23 +128,128 @@ return sstrdup_a(a, sstrn(buf->space, buf->size)); } -void dav_exec_get(DavSession *sn, DavQLStatement *st, char* path, va_list ap) { - // execute a davql get statement +/* + * execute a davql select statement + */ +DavResult dav_exec_select(DavSession *sn, DavQLStatement *st, char* path, va_list ap) { UcxMempool *mp = ucx_mempool_new(128); // TODO: get property list + UcxBuffer *rqbuf = create_allprop_propfind_request(); - UcxBuffer *bcode = dav_compile_expr(mp->allocator, st->where, ap); + UcxBuffer *where = dav_compile_expr(sn->context, mp->allocator, st->where, ap); + + DavResource *selroot = dav_resource_new(sn, path); + DavResult result; + result.result = selroot; + result.status = 0; + - //print_bytecode(bcode); + UcxList *stack = NULL; // stack with DavResource* elements + // initialize the stack with the requested resource + DavQLRes *r = ucx_mempool_malloc(mp, sizeof(DavQLRes)); + r->resource = selroot; + r->depth = 0; + stack = ucx_list_prepend(stack, r); + + // reuseable response buffer + UcxBuffer *rpbuf = ucx_buffer_new(NULL, 4096, UCX_BUFFER_AUTOEXTEND); - DavResource *res = dav_resource_new(sn, "/test.txt"); - dav_set_property_ns(res, "DAV:", "string", "value"); - dav_set_property_ns(res, "DAV:", "integer", "1337"); - res->lastmodified = 100; + // do a propfind request for each resource on the stack + while(stack) { + DavQLRes *sr = stack->data; // get first element from the stack + stack = ucx_list_remove(stack, stack); // remove first element + DavResource *root = sr->resource; + + util_set_url(sn, dav_resource_get_href(sr->resource)); + CURLcode ret = do_propfind_request(sn->handle, rqbuf, rpbuf); + int http_status = 0; + curl_easy_getinfo (sn->handle, CURLINFO_RESPONSE_CODE, &http_status); + + if(ret == CURLE_OK && http_status == 207) { + // propfind request successful, now parse the response + char *url = "http://url/"; + PropfindParser *parser = create_propfind_parser(rpbuf, url); + ResponseTag response; + int r; + while((r = get_propfind_response(parser, &response)) != 0) { + if(r == -1) { + // error + result.status = -1; + // TODO: free resources + break; + } + + // the propfind multistatus response contains responses + // for the requsted resource and all childs + // determine if the response is a child or not + if(hrefeq(sn, root->href, response.href)) { + // response is the currently requested resource + // and not a child + + // add properties + add_properties(root, &response); + + if(root == selroot) { + // The current root is the root of the select query. + // In this case we have to check the where clause. + // If root is not selroot, the where clause was + // already checked for the resource before it was + // added to the stack. + DavQLStackObj where_result; + if(!dav_exec_expr(where, root, &where_result)) { + if(where_result.data.integer != 0) { + continue; + } + } else { + result.status = -1; + } + dav_resource_free_all(selroot); + ucx_list_free(stack); + break; + } + } else { + DavResource *child = response2resource( + sn, + &response, + root->path); + // check where clause + DavQLStackObj where_result; + if(!dav_exec_expr(where, child, &where_result)) { + if(where_result.data.integer != 0) { + resource_add_child(root, child); + if(child->iscollection && + (st->depth < 0 || st->depth > sr->depth+1)) + { + DavQLRes *rs = ucx_mempool_malloc( + mp, + sizeof(DavQLRes)); + rs->resource = child; + rs->depth = sr->depth + 1; + stack = ucx_list_prepend(stack, rs); + } + } else { + dav_resource_free(child); + } + } + } + } + + } else { + dav_session_set_error(sn, ret, http_status); + result.status = -1; + dav_resource_free_all(selroot); + break; + } + + // reset response buffer + ucx_buffer_seek(rpbuf, SEEK_SET, 0); + } - DavQLStackObj result; - dav_exec_expr(bcode, res, &result); + ucx_mempool_destroy(mp); + + result.result = selroot; + return result; } static int count_func_args(DavQLExpression *expr) { @@ -159,21 +266,7 @@ return count; } -static int identifier2propname(UcxAllocator *a, sstr_t id, DavPropName *propname) { - ssize_t count; - sstr_t *s = sstrsplit_a(a, id, S(":"), &count); - if(count == 2) { - sstr_t ns = s[0]; - sstr_t name = s[1]; - propname->ns = ns.ptr; - propname->name = name.ptr; - return 0; - } else { - return 1; - } -} - -static int add_cmd(UcxAllocator *a, UcxBuffer *bcode, DavQLExpression *expr, va_list ap) { +static int add_cmd(DavContext *ctx, UcxAllocator *a, UcxBuffer *bcode, DavQLExpression *expr, va_list ap) { if(!expr) { return 0; } @@ -219,7 +312,17 @@ cmd.type = DAVQL_CMD_RES_IDENTIFIER; if(propertyname.length > 0) { cmd.type = DAVQL_CMD_PROP_IDENTIFIER; - if(identifier2propname(a, src, &cmd.data.property)) { + char *ns; + char *name; + dav_get_property_namespace( + ctx, + sstrdup_a(a, src).ptr, + &ns, + &name); + if(ns && name) { + cmd.data.property.ns = ns; + cmd.data.property.name = name; + } else { // error return -1; } @@ -253,27 +356,29 @@ break; } case DAVQL_UNARY: { - numcmd += add_cmd(a, bcode, expr->left, ap); + numcmd += add_cmd(ctx, a, bcode, expr->left, ap); switch(expr->op) { case DAVQL_ADD: { - cmd.type = DAVQL_CMD_OP_UNARY_ADD; + // noop + numcmd = 0; break; } case DAVQL_SUB: { cmd.type = DAVQL_CMD_OP_UNARY_SUB; + ucx_buffer_write(&cmd, sizeof(cmd), 1, bcode); break; } case DAVQL_NEG: { cmd.type = DAVQL_CMD_OP_UNARY_NEG; + ucx_buffer_write(&cmd, sizeof(cmd), 1, bcode); break; } } - ucx_buffer_write(&cmd, sizeof(cmd), 1, bcode); break; } case DAVQL_BINARY: { - numcmd += add_cmd(a, bcode, expr->left, ap); - numcmd += add_cmd(a, bcode, expr->right, ap); + numcmd += add_cmd(ctx, a, bcode, expr->left, ap); + numcmd += add_cmd(ctx, a, bcode, expr->right, ap); switch(expr->op) { case DAVQL_ADD: { cmd.type = DAVQL_CMD_OP_BINARY_ADD; @@ -309,13 +414,13 @@ } case DAVQL_LOGICAL: { if(expr->left && expr->right && expr->op != DAVQL_LOR) { - numcmd += add_cmd(a, bcode, expr->left, ap); - numcmd += add_cmd(a, bcode, expr->right, ap); + numcmd += add_cmd(ctx, a, bcode, expr->left, ap); + numcmd += add_cmd(ctx, a, bcode, expr->right, ap); } switch(expr->op) { case DAVQL_NOT: { - numcmd += add_cmd(a, bcode, expr->left, ap); + numcmd += add_cmd(ctx, a, bcode, expr->left, ap); cmd.type = DAVQL_CMD_OP_LOGICAL_NOT; ucx_buffer_write(&cmd, sizeof(cmd), 1, bcode); break; @@ -326,13 +431,13 @@ break; } case DAVQL_LOR: { - int nleft = add_cmd(a, bcode, expr->left, ap); + int nleft = add_cmd(ctx, a, bcode, expr->left, ap); cmd.type = DAVQL_CMD_OP_LOGICAL_OR_L; DavQLCmd *or_l = (DavQLCmd*)(bcode->space + bcode->pos); ucx_buffer_write(&cmd, sizeof(cmd), 1, bcode); - int nright = add_cmd(a, bcode, expr->right, ap); + int nright = add_cmd(ctx, a, bcode, expr->right, ap); or_l->data.integer = nright + 1; cmd.type = DAVQL_CMD_OP_LOGICAL_OR; @@ -393,7 +498,7 @@ case DAVQL_FUNCCALL: { switch(expr->op) { case DAVQL_CALL: { - int nright = add_cmd(a, bcode, expr->right, ap); + int nright = add_cmd(ctx, a, bcode, expr->right, ap); // TODO: count args DavQLExpression *funcid = expr->left; if(!funcid && funcid->type != DAVQL_IDENTIFIER) { @@ -417,8 +522,8 @@ } case DAVQL_ARGLIST: { numcmd = 0; - numcmd += add_cmd(a, bcode, expr->left, ap); - numcmd += add_cmd(a, bcode, expr->right, ap); + numcmd += add_cmd(ctx, a, bcode, expr->left, ap); + numcmd += add_cmd(ctx, a, bcode, expr->right, ap); break; } } @@ -428,13 +533,13 @@ return numcmd; } -UcxBuffer* dav_compile_expr(UcxAllocator *a, DavQLExpression *lexpr, va_list ap) { +UcxBuffer* dav_compile_expr(DavContext *ctx, UcxAllocator *a, DavQLExpression *lexpr, va_list ap) { UcxBuffer *bcode = ucx_buffer_new(NULL, 512, UCX_BUFFER_AUTOEXTEND); if(!bcode) { return NULL; } - if(add_cmd(a, bcode, lexpr, ap) <= 0) { + if(add_cmd(ctx, a, bcode, lexpr, ap) <= 0) { ucx_buffer_free(bcode); return NULL; } @@ -678,15 +783,15 @@ } } - for(int i=0;idocument = xmlReadMemory(response->space, response->size, url, NULL, 0); + parser->current = NULL; + if(parser->document) { + xmlNode *xml_root = xmlDocGetRootElement(parser->document); + if(xml_root) { + xmlNode *node = xml_root->children; + while(node) { + // find first response tag + if(node->type == XML_ELEMENT_NODE) { + if(xstreq(node->name, "response")) { + parser->current = node; + break; + } + } + node = node->next; + } + return parser; + } else { + xmlFreeDoc(parser->document); + } + } + free(parser); + return NULL; +} + +int get_propfind_response(PropfindParser *parser, ResponseTag *result) { + if(parser->current == NULL) { + return 0; + } + + char *href = NULL; + int iscollection = 0; + UcxList *properties = NULL; // xmlNode list + char *crypto_name = NULL; // name set by crypto-name property + char *crypto_key = NULL; + + xmlNode *node = parser->current->children; + while(node) { + if(node->type == XML_ELEMENT_NODE) { + if(xstreq(node->name, "href")) { + xmlNode *href_node = node->children; + if(href_node->type != XML_TEXT_NODE) { + // error + return -1; + } + href = (char*)href_node->content; + } else if(xstreq(node->name, "propstat")) { + xmlNode *n = node->children; + xmlNode *prop_node = NULL; + int ok = 0; + // get the status code + while(n) { + if(n->type == XML_ELEMENT_NODE) { + if(xstreq(n->name, "prop")) { + prop_node = n; + } else if(xstreq(n->name, "status")) { + xmlNode *status_node = n->children; + if(status_node->type != XML_TEXT_NODE) { + // error + return -1; + } + sstr_t status_str = sstr((char*)status_node->content); + if(status_str.length < 13) { + // error + return -1; + } + status_str = sstrsubsl(status_str, 9, 3); + if(!sstrcmp(status_str, S("200"))) { + ok = 1; + } + } + } + n = n->next; + } + // if status is ok, get all properties + if(ok) { + n = prop_node->children; + while(n) { + if(n->type == XML_ELEMENT_NODE) { + properties = ucx_list_append(properties, n); + if(xstreq(n->name, "resourcetype")) { + xmlNode *rsnode = n->children; + if(rsnode && rsnode->type == XML_ELEMENT_NODE) { + // TODO: check content + iscollection = 1; + } + } else if(xstreq(n->ns->href, DAV_NS)) { + if(xstreq(n->name, "crypto-name")) { + crypto_name = util_xml_get_text(n); + } else if(xstreq(n->name, "crypto-key")) { + crypto_key = util_xml_get_text(n); + } + } + } + n = n->next; + } + } + } + } + node = node->next; + } + + result->href = href; + result->iscollection = iscollection; + result->properties = properties; + result->crypto_name = crypto_name; + result->crypto_key = crypto_key; + + // find next response tag + xmlNode *next = parser->current->next; + while(next) { + if(next->type == XML_ELEMENT_NODE) { + if(xstreq(next->name, "response")) { + break; + } + } + next = next->next; + } + parser->current = next; + + return 1; +} + +int hrefeq(DavSession *sn, char *href1, char *href2) { + sstr_t href_s = sstr(util_url_decode(sn, href1)); + sstr_t href_r = sstr(util_url_decode(sn, href2)); + int ret = 0; + if(!sstrcmp(href_s, href_r)) { + ret = 1; + } else if(href_s.length == href_r.length + 1) { + if(href_s.ptr[href_s.length-1] == '/') { + href_s.length--; + if(!sstrcmp(href_s, href_r)) { + ret = 1; + } + } + } + + free(href_s.ptr); + free(href_r.ptr); + + return ret; +} + + DavResource* parse_propfind_response(DavSession *sn, DavResource *root, UcxBuffer *response, DavQOp *cond, size_t len) { char *url = NULL; curl_easy_getinfo(sn->handle, CURLINFO_EFFECTIVE_URL, &url); @@ -256,6 +406,63 @@ return root; } +DavResource* response2resource(DavSession *sn, ResponseTag *response, char *parent_path) { + // create resource + char *name = NULL; + if(DAV_DECRYPT_NAME(sn) && response->crypto_name) { + if(!response->crypto_key) { + // TODO: error + fprintf(stderr, "encrypted resource without key\n"); + return NULL; + } + name = util_decrypt_str(sn, response->crypto_name, response->crypto_key); + if(!name) { + // TODO: error + fprintf(stderr, "decrypted name is null\n"); + return NULL; + } + } else { + sstr_t resname = sstr(util_resource_name(response->href)); + int nlen = 0; + char *uname = curl_easy_unescape( + sn->handle, + resname.ptr, + resname.length, + &nlen); + name = dav_session_strdup(sn, uname); + curl_free(uname); + } + + char *href = dav_session_strdup(sn, href); + DavResource *res = NULL; + if(parent_path) { + res = dav_resource_new_full(sn, parent_path, name, href); + } else { + res = dav_resource_new_href(sn, href); + } + dav_session_free(sn, name); + + add_properties(res, response); + return res; +} + +void add_properties(DavResource *res, ResponseTag *response) { + res->iscollection = response->iscollection; + + // add properties + UCX_FOREACH(elm, response->properties) { + xmlNode *prop = elm->data; + + // TODO: add xml data instead of a string + char *text = util_xml_get_text(prop); + if(text) { + resource_add_property(res, (char*)prop->ns->href, (char*)prop->name, text); + } + } + + set_davprops(res); +} + int parse_response_tag(DavResource *resource, xmlNode *node, DavQOp *cond, size_t clen) { DavSession *sn = resource->session; diff -r 7072a2b4ae35 -r 649eb328674a libidav/methods.h --- a/libidav/methods.h Tue Jun 02 10:07:20 2015 +0200 +++ b/libidav/methods.h Tue Jun 02 20:57:23 2015 +0200 @@ -32,10 +32,28 @@ #include "webdav.h" #include "resource.h" +#include + #ifdef __cplusplus extern "C" { #endif +typedef struct PropfindParser PropfindParser; +typedef struct ResponseTag ResponseTag; + +struct PropfindParser { + xmlDoc *document; + xmlNode *current; +}; + +struct ResponseTag { + char *href; + int iscollection; + UcxList *properties; + char *crypto_name; + char *crypto_key; +}; + CURLcode do_propfind_request( CURL *handle, UcxBuffer *request, @@ -56,6 +74,13 @@ UcxBuffer* create_propfind_request(DavSession *sn, UcxList *properties); UcxBuffer* create_basic_propfind_request(); +PropfindParser* create_propfind_parser(UcxBuffer *response, char *url); +int get_propfind_response(PropfindParser *parser, ResponseTag *result); + +int hrefeq(DavSession *sn, char *href1, char *href2); +DavResource* response2resource(DavSession *sn, ResponseTag *response, char *parent_path); +void add_properties(DavResource *res, ResponseTag *response); + DavResource* parse_propfind_response(DavSession *sn, DavResource *root, UcxBuffer *response, DavQOp *cond, size_t len); int parse_response_tag(DavResource *resource, xmlNode *node, DavQOp *cond, size_t len); void set_davprops(DavResource *res); diff -r 7072a2b4ae35 -r 649eb328674a libidav/webdav.c --- a/libidav/webdav.c Tue Jun 02 10:07:20 2015 +0200 +++ b/libidav/webdav.c Tue Jun 02 20:57:23 2015 +0200 @@ -220,8 +220,13 @@ DavNamespace *ns = dav_get_namespace_s( ctx, sstrn(prefixed_name, pname-prefixed_name)); - pns = ns->name; - pname++; + if(ns) { + pns = ns->name; + pname++; + } else { + pns = NULL; + pname = NULL; + } } else { pname = prefixed_name; } @@ -304,7 +309,7 @@ return error; } -UcxList* propfind_stack_push(UcxList *stack, DavResource *children) { +static UcxList* propfind_stack_push(UcxList *stack, DavResource *children) { while(children) { if(children->iscollection) { stack = ucx_list_prepend(stack, children); diff -r 7072a2b4ae35 -r 649eb328674a libidav/webdav.h --- a/libidav/webdav.h Tue Jun 02 10:07:20 2015 +0200 +++ b/libidav/webdav.h Tue Jun 02 20:57:23 2015 +0200 @@ -45,7 +45,7 @@ typedef struct DavProxy DavProxy; typedef struct DavSession DavSession; typedef struct DavResource DavResource; -typedef struct DavQLResult DavQLResult; +typedef struct DavResult DavResult; typedef struct DavNamespace DavNamespace; typedef struct DavProperty DavProperty; typedef struct DavPropName DavPropName; @@ -145,7 +145,7 @@ char *name; }; -struct DavQLResult { +struct DavResult { DavResource *result; int status; }; diff -r 7072a2b4ae35 -r 649eb328674a ucx/Makefile --- a/ucx/Makefile Tue Jun 02 10:07:20 2015 +0200 +++ b/ucx/Makefile Tue Jun 02 20:57:23 2015 +0200 @@ -38,6 +38,9 @@ SRC += test.c SRC += allocator.c SRC += buffer.c +SRC += logging.c +SRC += stack.c +SRC += avl.c OBJ = $(SRC:%.c=../build/ucx/%$(OBJ_EXT)) diff -r 7072a2b4ae35 -r 649eb328674a ucx/avl.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/avl.c Tue Jun 02 20:57:23 2015 +0200 @@ -0,0 +1,272 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2015 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "avl.h" + +#define ptrcast(ptr) ((void*)(ptr)) + +static void ucx_avl_connect(UcxAVLTree *tree, + UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { + if (child) { + child->parent = node; + } + // if child is NULL, nullkey decides if left or right pointer is cleared + if (tree->cmpfunc( + ptrcast(child ? child->key : nullkey), + ptrcast(node->key), tree->userdata) > 0) { + node->right = child; + } else { + node->left = child; + } + size_t lh = node->left ? node->left->height : 0; + size_t rh = node->right ? node->right->height : 0; + node->height = 1 + (lh > rh ? lh : rh); +} + +#define avlheight(node) ((node) ? (node)->height : 0) + +static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { + UcxAVLNode *p = l0->parent; + UcxAVLNode *l1 = l0->left; + if (p) { + ucx_avl_connect(tree, p, l1, 0); + } else { + l1->parent = NULL; + } + ucx_avl_connect(tree, l0, l1->right, l1->key); + ucx_avl_connect(tree, l1, l0, 0); + return l1; +} + +static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { + UcxAVLNode *p = l0->parent; + UcxAVLNode *l1 = l0->right; + if (p) { + ucx_avl_connect(tree, p, l1, 0); + } else { + l1->parent = NULL; + } + ucx_avl_connect(tree, l0, l1->left, l1->key); + ucx_avl_connect(tree, l1, l0, 0); + return l1; +} + +static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { + int lh = avlheight(n->left); + int rh = avlheight(n->right); + n->height = 1 + (lh > rh ? lh : rh); + + if (lh - rh == 2) { + UcxAVLNode *c = n->left; + if (avlheight(c->right) - avlheight(c->left) == 1) { + avl_rotleft(tree, c); + } + n = avl_rotright(tree, n); + } else if (rh - lh == 2) { + UcxAVLNode *c = n->right; + if (avlheight(c->left) - avlheight(c->right) == 1) { + avl_rotright(tree, c); + } + n = avl_rotleft(tree, n); + } + + if (n->parent) { + ucx_avl_balance(tree, n->parent); + } else { + tree->root = n; + } +} + +UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { + return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); +} + +UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { + UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); + if (tree) { + tree->allocator = allocator; + tree->cmpfunc = cmpfunc; + tree->root = NULL; + tree->userdata = NULL; + } + + return tree; +} + +static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { + if (node) { + ucx_avl_free_node(al, node->left); + ucx_avl_free_node(al, node->right); + alfree(al, node); + } +} + +void ucx_avl_free(UcxAVLTree *tree) { + UcxAllocator *al = tree->allocator; + ucx_avl_free_node(al, tree->root); + alfree(al, tree); +} + +UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { + UcxAVLNode *n = tree->root; + int cmpresult; + while (n && (cmpresult = tree->cmpfunc( + ptrcast(key), ptrcast(n->key), tree->userdata))) { + n = cmpresult > 0 ? n->right : n->left; + } + return n; +} + +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { + UcxAVLNode *n = ucx_avl_get_node(tree, key); + return n ? n->value : NULL; +} + +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { + return ucx_avl_put_s(tree, key, value, NULL); +} + +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, + void **oldvalue) { + if (tree->root) { + UcxAVLNode *n = tree->root; + int cmpresult; + while ((cmpresult = tree->cmpfunc( + ptrcast(key), ptrcast(n->key), tree->userdata))) { + UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; + if (m) { + n = m; + } else { + break; + } + } + + if (cmpresult) { + UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); + if (e) { + e->key = key; e->value = value; e->height = 1; + e->parent = e->left = e->right = NULL; + ucx_avl_connect(tree, n, e, 0); + ucx_avl_balance(tree, n); + return 0; + } else { + return 1; + } + } else { + if (oldvalue) { + *oldvalue = n->value; + } + n->value = value; + return 0; + } + } else { + tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); + if (tree->root) { + tree->root->key = key; tree->root->value = value; + tree->root->height = 1; + tree->root->parent = tree->root->left = tree->root->right = NULL; + + if (oldvalue) { + *oldvalue = NULL; + } + + return 0; + } else { + return 1; + } + } +} + +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { + return ucx_avl_remove_s(tree, key, NULL, NULL); +} + +int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) { + return ucx_avl_remove_s(tree, node->key, NULL, NULL); +} + +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, + intptr_t *oldkey, void **oldvalue) { + + UcxAVLNode *n = tree->root; + int cmpresult; + while (n && (cmpresult = tree->cmpfunc( + ptrcast(key), ptrcast(n->key), tree->userdata))) { + n = cmpresult > 0 ? n->right : n->left; + } + if (n) { + if (oldkey) { + *oldkey = n->key; + } + if (oldvalue) { + *oldvalue = n->value; + } + + UcxAVLNode *p = n->parent; + if (n->left && n->right) { + UcxAVLNode *s = n->right; + while (s->left) { + s = s->left; + } + ucx_avl_connect(tree, s->parent, s->right, s->key); + n->key = s->key; n->value = s->value; + p = s->parent; + alfree(tree->allocator, s); + } else { + if (p) { + ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); + } else { + tree->root = n->right ? n->right : n->left; + if (tree->root) { + tree->root->parent = NULL; + } + } + alfree(tree->allocator, n); + } + + if (p) { + ucx_avl_balance(tree, p); + } + + return 0; + } else { + return 1; + } +} + +static size_t ucx_avl_countn(UcxAVLNode *node) { + if (node) { + return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); + } else { + return 0; + } +} + +size_t ucx_avl_count(UcxAVLTree *tree) { + return ucx_avl_countn(tree->root); +} diff -r 7072a2b4ae35 -r 649eb328674a ucx/avl.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/avl.h Tue Jun 02 20:57:23 2015 +0200 @@ -0,0 +1,249 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2015 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + + +/** + * @file avl.h + * + * AVL tree implementation. + * + * This binary search tree implementation allows average O(1) insertion and + * removal of elements (excluding binary search time). + * + * @author Mike Becker + * @author Olaf Wintermann + */ + +#ifndef UCX_AVL_H +#define UCX_AVL_H + +#include "ucx.h" +#include "allocator.h" +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * UCX AVL Node type. + * + * @see UcxAVLNode + */ +typedef struct UcxAVLNode UcxAVLNode; + +/** + * UCX AVL Node. + */ +struct UcxAVLNode { + /** + * The key for this node. + */ + intptr_t key; + /** + * Data contained by this node. + */ + void *value; + /** + * The height of this (sub)-tree. + */ + size_t height; + /** + * Parent node. + */ + UcxAVLNode *parent; + /** + * Root node of left subtree. + */ + UcxAVLNode *left; + /** + * Root node of right subtree. + */ + UcxAVLNode *right; +}; + +/** + * UCX AVL Tree. + */ +typedef struct { + /** + * The UcxAllocator that shall be used to manage the memory for node data. + */ + UcxAllocator *allocator; + /** + * Root node of the tree. + */ + UcxAVLNode *root; + /** + * Compare function that shall be used to compare the UcxAVLNode keys. + * @see UcxAVLNode.key + */ + cmp_func cmpfunc; + /** + * Custom user data. + * This data will also be provided to the cmpfunc. + */ + void *userdata; +} UcxAVLTree; + +/** + * Initializes a new UcxAVLTree with a default allocator. + * + * @param cmpfunc the compare function that shall be used + * @return a new UcxAVLTree object + * @see ucx_avl_new_a() + */ +UcxAVLTree *ucx_avl_new(cmp_func cmpfunc); + +/** + * Initializes a new UcxAVLTree with the specified allocator. + * + * The cmpfunc should be capable of comparing two keys within this AVL tree. + * So if you want to use null terminated strings as keys, you could use the + * ucx_strcmp() function here. + * + * @param cmpfunc the compare function that shall be used + * @param allocator the UcxAllocator that shall be used + * @return a new UcxAVLTree object + */ +UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator); + +/** + * Destroys an UcxAVLTree. + * @param tree the tree to destroy + */ +void ucx_avl_free(UcxAVLTree *tree); + +/** + * Macro for initializing a new UcxAVLTree with the default allocator and a + * ucx_ptrcmp() compare function. + * + * @return a new default UcxAVLTree object + */ +#define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator()) + +/** + * Gets the node from the tree, that is associated with the specified key. + * @param tree the UcxAVLTree + * @param key the key + * @return the node (or NULL, if the key is not present) + */ +UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key); + +/** + * Gets the value from the tree, that is associated with the specified key. + * @param tree the UcxAVLTree + * @param key the key + * @return the value (or NULL, if the key is not present) + */ +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); + +/** + * Puts a key/value pair into the tree. + * + * Attention: use this function only, if a possible old value does not need + * to be preserved. + * + * @param tree the UcxAVLTree + * @param key the key + * @param value the new value + * @return zero, if and only if the operation succeeded + */ +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value); + +/** + * Puts a key/value pair into the tree. + * + * This is a secure function which saves the old value to the variable pointed + * at by oldvalue. + * + * @param tree the UcxAVLTree + * @param key the key + * @param value the new value + * @param oldvalue optional: a pointer to the location where a possible old + * value shall be stored + * @return zero, if and only if the operation succeeded + */ +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue); + +/** + * Removes a node from the AVL tree. + * + * Note: the specified node is logically removed. The tree implementation + * decides which memory area is freed. In most cases the here provided node + * is freed, so it's further use is generally undefined. + * + * @param tree the UcxAVLTree + * @param node the node to remove + * @return zero, if and only if an element has been removed + */ +int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node); + +/** + * Removes an element from the AVL tree. + * + * @param tree the UcxAVLTree + * @param key the key + * @return zero, if and only if an element has been removed + */ +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key); + +/** + * Removes an element from the AVL tree. + * + * This is a secure function which saves the old key and value data from node + * to the variables at the location of oldkey and oldvalue (if specified), so + * they can be freed afterwards (if necessary). + * + * Note: the returned key in oldkey is possibly not the same as the provided + * key for the lookup (in terms of memory location). + * + * @param tree the UcxAVLTree + * @param key the key of the element to remove + * @param oldkey optional: a pointer to the location where the old key shall be + * stored + * @param oldvalue optional: a pointer to the location where the old value + * shall be stored + * @return zero, if and only if an element has been removed + */ +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, + intptr_t *oldkey, void **oldvalue); + +/** + * Counts the nodes in the specified UcxAVLTree. + * @param tree the AVL tree + * @return the node count + */ +size_t ucx_avl_count(UcxAVLTree *tree); + +#ifdef __cplusplus +} +#endif + +#endif /* UCX_AVL_H */ + diff -r 7072a2b4ae35 -r 649eb328674a ucx/logging.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/logging.c Tue Jun 02 20:57:23 2015 +0200 @@ -0,0 +1,105 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2015 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "logging.h" +#include +#include +#include +#include + +UcxLogger *ucx_logger_new(void *stream, unsigned int level, unsigned int mask) { + UcxLogger *logger = (UcxLogger*) malloc(sizeof(UcxLogger)); + if (logger != NULL) { + logger->stream = stream; + logger->writer = (write_func)fwrite; + logger->dateformat = (char*) "%F %T %z "; + logger->level = level; + logger->mask = mask; + logger->levels = ucx_map_new(8); + + unsigned int l; + l = UCX_LOGGER_ERROR; + ucx_map_int_put(logger->levels, l, (void*) "[ERROR]"); + l = UCX_LOGGER_WARN; + ucx_map_int_put(logger->levels, l, (void*) "[WARNING]"); + l = UCX_LOGGER_INFO; + ucx_map_int_put(logger->levels, l, (void*) "[INFO]"); + l = UCX_LOGGER_TRACE; + ucx_map_int_put(logger->levels, l, (void*) "[TRACE]"); + } + + return logger; +} + +void ucx_logger_free(UcxLogger *logger) { + ucx_map_free(logger->levels); + free(logger); +} + +// estimated max. message length (documented) +#define UCX_LOGGER_MSGMAX 4096 + +void ucx_logger_logf(UcxLogger *logger, unsigned int level, const char* file, + const unsigned int line, const char *format, ...) { + if (level <= logger->level) { + char msg[UCX_LOGGER_MSGMAX]; + char *text; + size_t k = 0; + size_t n; + + if ((logger->mask & UCX_LOGGER_LEVEL) > 0) { + text = (char*) ucx_map_int_get(logger->levels, level); + n = strlen(text); + n = n > 256 ? 256 : n; + memcpy(msg+k, text, n); + k += n; + msg[k++] = ' '; + } + if ((logger->mask & UCX_LOGGER_TIMESTAMP) > 0) { + time_t now = time(NULL); + k += strftime(msg+k, 128, logger->dateformat, localtime(&now)); + } + if ((logger->mask & UCX_LOGGER_SOURCE) > 0) { + n = strlen(file); + memcpy(msg+k, file, n); + k += n; + k += sprintf(msg+k, ":%u ", line); + } + + msg[k++] = '-'; msg[k++] = ' '; + + va_list args; + va_start (args, format); + k += vsnprintf(msg+k, UCX_LOGGER_MSGMAX-k-1, format, args); + va_end (args); + + msg[k++] = '\n'; + + logger->writer(msg, 1, k, logger->stream); + } +} diff -r 7072a2b4ae35 -r 649eb328674a ucx/logging.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/logging.h Tue Jun 02 20:57:23 2015 +0200 @@ -0,0 +1,238 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2015 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +/** + * Logging API. + * + * @file logging.h + * @author Mike Becker, Olaf Wintermann + */ +#ifndef UCX_LOGGING_H +#define UCX_LOGGING_H + +#include "ucx.h" +#include "map.h" +#include "string.h" +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/* leave enough space for custom log levels */ + +/** Log level for error messages. */ +#define UCX_LOGGER_ERROR 0x00 + +/** Log level for warning messages. */ +#define UCX_LOGGER_WARN 0x10 + +/** Log level for information messages. */ +#define UCX_LOGGER_INFO 0x20 + +/** Log level for debug messages. */ +#define UCX_LOGGER_DEBUG 0x30 + +/** Log level for trace messages. */ +#define UCX_LOGGER_TRACE 0x40 + +/** + * Output flag for the log level. + * If this flag is set, the log message will contain the log level. + * @see UcxLogger.mask + */ +#define UCX_LOGGER_LEVEL 0x01 + +/** + * Output flag for the timestmap. + * If this flag is set, the log message will contain the timestmap. + * @see UcxLogger.mask + */ +#define UCX_LOGGER_TIMESTAMP 0x02 + +/** + * Output flag for the source. + * If this flag is set, the log message will contain the source file and line + * number. + * @see UcxLogger.mask + */ +#define UCX_LOGGER_SOURCE 0x04 + +/** + * The UCX Logger object. + */ +typedef struct { + /** The stream this logger writes its messages to.*/ + void *stream; + + /** + * The write function that shall be used. + * For standard file or stdout loggers this might be standard fwrite + * (default). + */ + write_func writer; + + /** + * The date format for timestamp outputs including the delimiter + * (default: "%F %T %z "). + * @see UCX_LOGGER_TIMESTAMP + */ + char *dateformat; + + /** + * The level, this logger operates on. + * If a log command is issued, the message will only be logged, if the log + * level of the message is less or equal than the log level of the logger. + */ + unsigned int level; + + /** + * A configuration mask for automatic output. + * For each flag that is set, the logger automatically outputs some extra + * information like the timestamp or the source file and line number. + * See the documentation for the flags for details. + */ + unsigned int mask; + + /** + * A map of valid log levels for this logger. + * + * The keys represent all valid log levels and the values provide string + * representations, that are used, if the UCX_LOGGER_LEVEL flag is set. + * + * The exact data types are unsigned int for the key and + * const char* for the value. + * + * @see UCX_LOGGER_LEVEL + */ + UcxMap* levels; +} UcxLogger; + +/** + * Creates a new logger. + * @param stream the stream, which the logger shall write to + * @param level the level on which the logger shall operate + * @param mask configuration mask (cf. UcxLogger.mask) + * @return a new logger object + */ +UcxLogger *ucx_logger_new(void *stream, unsigned int level, unsigned int mask); + +/** + * Destroys the logger. + * + * The map containing the valid log levels is also automatically destroyed. + * + * @param logger the logger to destroy + */ +void ucx_logger_free(UcxLogger* logger); + +/** + * Internal log function - use macros instead. + * + * This function uses the format and variadic arguments for a + * printf()-style output of the log message. + * + * Dependent on the UcxLogger.mask some information is prepended. The complete + * format is: + * + * [LEVEL] [TIMESTAMP] [SOURCEFILE]:[LINENO] message + * + * Attention: the message (including automatically generated information) + * is limited to 4096 characters. The level description is limited to + * 256 characters and the timestamp string is limited to 128 characters. + * + * @param logger the logger to use + * @param level the level to log on + * @param file information about the source file + * @param line information about the source line number + * @param format format string + * @param ... arguments + * @see ucx_logger_log() + */ +void ucx_logger_logf(UcxLogger *logger, unsigned int level, const char* file, + const unsigned int line, const char* format, ...); + +/** + * Logs a message at the specified level. + * @param logger the logger to use + * @param level the level to log the message on + * @param ... format string and arguments + * @see ucx_logger_logf() + */ +#define ucx_logger_log(logger, level, ...) \ + ucx_logger_logf(logger, level, __FILE__, __LINE__, __VA_ARGS__) + +/** + * Shortcut for logging an error message. + * @param logger the logger to use + * @param ... format string and arguments + * @see ucx_logger_logf() + */ +#define ucx_logger_error(logger, ...) \ + ucx_logger_log(logger, UCX_LOGGER_ERROR, __VA_ARGS__) + +/** + * Shortcut for logging an information message. + * @param logger the logger to use + * @param ... format string and arguments + * @see ucx_logger_logf() + */ +#define ucx_logger_info(logger, ...) \ + ucx_logger_log(logger, UCX_LOGGER_INFO, __VA_ARGS__) + +/** + * Shortcut for logging a warning message. + * @param logger the logger to use + * @param ... format string and arguments + * @see ucx_logger_logf() + */ +#define ucx_logger_warn(logger, ...) \ + ucx_logger_log(logger, UCX_LOGGER_WARN, __VA_ARGS__) + +/** + * Shortcut for logging a debug message. + * @param logger the logger to use + * @param ... format string and arguments + * @see ucx_logger_logf() + */ +#define ucx_logger_debug(logger, ...) \ + ucx_logger_log(logger, UCX_LOGGER_DEBUG, __VA_ARGS__) + +/** + * Shortcut for logging a trace message. + * @param logger the logger to use + * @param ... format string and arguments + * @see ucx_logger_logf() + */ +#define ucx_logger_trace(logger, ...) \ + ucx_logger_log(logger, UCX_LOGGER_TRACE, __VA_ARGS__) + +#ifdef __cplusplus +} +#endif + +#endif /* UCX_LOGGING_H */ diff -r 7072a2b4ae35 -r 649eb328674a ucx/stack.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/stack.c Tue Jun 02 20:57:23 2015 +0200 @@ -0,0 +1,143 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2015 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "stack.h" +#include + +static size_t ucx_stack_align(size_t n) { + int align = n % sizeof(void*); + if (align) { + n += sizeof(void*) - align; + } + return n; +} + +void ucx_stack_init(UcxStack *stack, char* space, size_t size) { + stack->size = size - size % sizeof(void*); + stack->space = space; + stack->top = NULL; + + stack->allocator.pool = stack; + stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc; + stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc; + stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc; + stack->allocator.free = (ucx_allocator_free) ucx_stack_free; +} + +void *ucx_stack_malloc(UcxStack *stack, size_t n) { + + if (ucx_stack_avail(stack) < ucx_stack_align(n)) { + return NULL; + } else { + char *prev = stack->top; + if (stack->top) { + stack->top += ucx_stack_align(ucx_stack_topsize(stack)); + } else { + stack->top = stack->space; + } + + ((struct ucx_stack_metadata*)stack->top)->prev = prev; + ((struct ucx_stack_metadata*)stack->top)->size = n; + stack->top += sizeof(struct ucx_stack_metadata); + + return stack->top; + } +} + +void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) { + void *mem = ucx_stack_malloc(stack, nelem*elsize); + memset(mem, 0, nelem*elsize); + return mem; +} + +void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) { + if (ptr == stack->top) { + if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) { + return NULL; + } else { + ((struct ucx_stack_metadata*)stack->top - 1)->size = n; + return ptr; + } + } else { + if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) < + ucx_stack_align(n)) { + void *nptr = ucx_stack_malloc(stack, n); + if (nptr) { + memcpy(nptr, ptr, n); + ucx_stack_free(stack, ptr); + + return nptr; + } else { + return NULL; + } + } else { + ((struct ucx_stack_metadata*)ptr - 1)->size = n; + return ptr; + } + } +} + +void ucx_stack_free(UcxStack *stack, void *ptr) { + if (ptr == stack->top) { + stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev; + } else { + struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)( + (char*)ptr + + ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size) + ); + next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev; + } +} + +void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) { + if (ucx_stack_empty(stack)) { + return; + } + + size_t len = ucx_stack_topsize(stack); + if (len > n) { + len = n; + } + + memcpy(dest, stack->top, len); + + ucx_stack_free(stack, stack->top); +} + +size_t ucx_stack_avail(UcxStack *stack) { + size_t avail = ((stack->top ? (stack->size + - (stack->top - stack->space) + - ucx_stack_align(ucx_stack_topsize(stack))) + : stack->size)); + + if (avail > sizeof(struct ucx_stack_metadata)) { + return avail - sizeof(struct ucx_stack_metadata); + } else { + return 0; + } +} diff -r 7072a2b4ae35 -r 649eb328674a ucx/stack.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/stack.h Tue Jun 02 20:57:23 2015 +0200 @@ -0,0 +1,233 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2015 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * @file stack.h + * + * Default stack memory allocation implementation. + * + * @author Mike Becker + * @author Olaf Wintermann + */ + +#ifndef UCX_STACK_H +#define UCX_STACK_H + +#include "ucx.h" +#include +#include "allocator.h" + +#ifdef __cplusplus +extern "C" { +#endif + + +/** + * UCX stack structure. + */ +typedef struct { + /** UcxAllocator based on this stack */ + UcxAllocator allocator; + + /** Stack size. */ + size_t size; + + /** Pointer to the bottom of the stack */ + char *space; + + /** Pointer to the top of the stack */ + char *top; +} UcxStack; + +/** + * Metadata for each UCX stack element. + */ +struct ucx_stack_metadata { + /** + * Location of the previous element (NULL if this is the first) + */ + char *prev; + + /** Size of this element */ + size_t size; +}; + +/** + * Initializes UcxStack structure with memory. + * + * @param stack a pointer to an uninitialized stack structure + * @param space the memory area that shall be managed + * @param size size of the memory area + * @return a new UcxStack structure + */ +void ucx_stack_init(UcxStack *stack, char* space, size_t size); + +/** + * Allocates stack memory. + * + * @param stack a pointer to the stack + * @param n amount of memory to allocate + * @return a pointer to the allocated memory + * @see ucx_allocator_malloc() + */ +void *ucx_stack_malloc(UcxStack *stack, size_t n); + +/** + * Alias for #ucx_stack_malloc(). + * @param stack a pointer to the stack + * @param n amount of memory to allocate + * @return a pointer to the allocated memory + * @see ucx_stack_malloc + */ +#define ucx_stack_push(stack, n) ucx_stack_malloc(stack, n) + +/** + * Allocates an array of stack memory + * + * The content of the allocated memory is set to zero. + * + * @param stack a pointer to the stack + * @param nelem amount of elements to allocate + * @param elsize amount of memory per element + * @return a pointer to the allocated memory + * @see ucx_allocator_calloc() + */ +void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize); + +/** + * Alias for #ucx_stack_calloc(). + * + * @param stack a pointer to the stack + * @param n amount of elements to allocate + * @param elsize amount of memory per element + * @return a pointer to the allocated memory + * @see ucx_stack_calloc + */ +#define ucx_stack_pusharr(stack,n,elsize) ucx_stack_calloc(stack,n,elssize) + +/** + * Reallocates memory on the stack. + * + * Shrinking memory is always safe. Extending memory can be very expensive. + * + * @param stack the stack + * @param ptr a pointer to the memory that shall be reallocated + * @param n the new size of the memory + * @return a pointer to the new location of the memory + * @see ucx_allocator_realloc() + */ +void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n); + +/** + * Frees memory on the stack. + * + * Freeing stack memory behaves in a special way. + * + * If the element, that should be freed, is the top most element of the stack, + * it is removed from the stack. Otherwise it is marked as freed. Marked + * elements are removed, when they become the top most elements of the stack. + * + * @param stack a pointer to the stack + * @param ptr a pointer to the memory that shall be freed + */ +void ucx_stack_free(UcxStack *stack, void *ptr); + + +/** + * Returns the size of the top most element. + * @param stack a pointer to the stack + * @return the size of the top most element + */ +#define ucx_stack_topsize(stack) ((stack)->top ? ((struct ucx_stack_metadata*)\ + (stack)->top - 1)->size : 0) + +/** + * Removes the top most element from the stack and copies the content to + * dest, if specified. + * + * Use #ucx_stack_topsize()# to get the amount of memory that must be available + * at the location of dest. + * + * @param stack a pointer to the stack + * @param dest the location where the contents shall be written to, or + * NULL, if the element shall only be removed. + * @see ucx_stack_free + * @see ucx_stack_popn + */ +#define ucx_stack_pop(stack, dest) ucx_stack_popn(stack, dest, SIZE_MAX) + +/** + * Removes the top most element from the stack and copies the content to + * dest. + * + * In contrast to #ucx_stack_pop() the dest pointer MUST + * NOT be NULL. + * + * @param stack a pointer to the stack + * @param dest the location where the contents shall be written to + * @param n copies at most n elements to dest + * @see ucx_stack_pop + */ +void ucx_stack_popn(UcxStack *stack, void *dest, size_t n); + +/** + * Returns the remaining available memory on the specified stack. + * + * @param stack a pointer to the stack + * @return the remaining available memory + */ +size_t ucx_stack_avail(UcxStack *stack); + +/** + * Checks, if the stack is empty. + * + * @param stack a pointer to the stack + * @return nonzero, if the stack is empty, zero otherwise + */ +#define ucx_stack_empty(stack) (!(stack)->top) + +/** + * Computes a recommended size for the stack memory area. Note, that + * reallocations have not been taken into account, so you might need to reserve + * twice as much memory to allow many reallocations. + * + * @param size the approximate payload + * @param elems the approximate count of element allocations + * @return a recommended size for the stack space based on the information + * provided + */ +#define ucx_stack_dim(size, elems) (size+sizeof(struct ucx_stack_metadata) * \ + (elems + 1)) + + +#ifdef __cplusplus +} +#endif + +#endif /* UCX_STACK_H */ +