From dee23c2058fd33e14610ceda277c11e4d8ce768b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 1 Oct 2014 03:10:53 +0000 Subject: Automatic benchmarking with 'waf bench'. git-svn-id: http://svn.drobilla.net/zix/trunk@94 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- zix/btree.h | 4 + zix/fat_patree.c | 239 ------------------------------------------------------- zix/fat_patree.h | 71 ----------------- 3 files changed, 4 insertions(+), 310 deletions(-) delete mode 100644 zix/fat_patree.c delete mode 100644 zix/fat_patree.h (limited to 'zix') diff --git a/zix/btree.h b/zix/btree.h index 3acd3a4..2de5565 100644 --- a/zix/btree.h +++ b/zix/btree.h @@ -80,6 +80,10 @@ zix_btree_insert(ZixBTree* t, void* e); /** Remove the value `e` from `t`. + @param t Tree to remove from. + + @param e Value to remove. + @param out Set to point to the removed pointer (which may not equal `e`). @param next If non-NULL, pointed to the value following `e`. If *next is diff --git a/zix/fat_patree.c b/zix/fat_patree.c deleted file mode 100644 index 454cfba..0000000 --- a/zix/fat_patree.c +++ /dev/null @@ -1,239 +0,0 @@ -/* - Copyright 2011 David Robillard - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#define _XOPEN_SOURCE 500 - -#include -#include -#include -#include -#include - -#include "zix/common.h" -#include "zix/fat_patree.h" - -#define N_CHILDREN 256 - -typedef uint_fast8_t n_edges_t; - -typedef struct _ZixFatPatreeNode { - char* label_first; /* Start of incoming label */ - char* label_last; /* End of incoming label */ - char* str; /* String stored at this node */ - struct _ZixFatPatreeNode* children[N_CHILDREN]; /* Children of this node */ -} ZixFatPatreeNode; - -struct _ZixFatPatree { - ZixFatPatreeNode* root; /* Root of the tree */ -}; - -ZIX_API -ZixFatPatree* -zix_fat_patree_new(void) -{ - ZixFatPatree* t = (ZixFatPatree*)malloc(sizeof(ZixFatPatree)); - memset(t, '\0', sizeof(struct _ZixFatPatree)); - - t->root = (ZixFatPatreeNode*)malloc(sizeof(ZixFatPatreeNode)); - memset(t->root, '\0', sizeof(ZixFatPatreeNode)); - - return t; -} - -static void -zix_fat_patree_free_rec(ZixFatPatreeNode* n) -{ - if (n) { - for (int i = 0; i < N_CHILDREN; ++i) { - zix_fat_patree_free_rec(n->children[i]); - } - } -} - -ZIX_API -void -zix_fat_patree_free(ZixFatPatree* t) -{ - zix_fat_patree_free_rec(t->root); - free(t->root); - free(t); -} - -static inline bool -patree_find_edge(ZixFatPatreeNode* n, uint8_t c, n_edges_t* index) -{ - if (n->children[c]) { - *index = c; - return true; - } - return false; -} - -static void -patree_add_edge(ZixFatPatreeNode* n, - char* str, - char* first, - char* last) -{ - assert(last >= first); - const int index = (uint8_t)first[0]; - assert(!n->children[index]); - - ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc( - sizeof(ZixFatPatreeNode)); - n->children[index] = new_node; - n->children[index]->label_first = first; - n->children[index]->label_last = last; - n->children[index]->str = str; - for (int i = 0; i < N_CHILDREN; ++i) { - n->children[index]->children[i] = NULL; - } -} - -/* Split an outgoing edge (to a child) at the given index */ -static void -patree_split_edge(ZixFatPatreeNode* child, - size_t index) -{ - char* const first = child->label_first + index; - char* const last = child->label_last; - assert(last >= first); - - ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc( - sizeof(ZixFatPatreeNode)); - new_node->label_first = first; - new_node->label_last = last; - new_node->str = child->str; - memcpy(new_node->children, child->children, - sizeof(ZixFatPatreeNode*) * N_CHILDREN); - - child->label_last = child->label_first + (index - 1); // chop end - child->str = NULL; - - for (int i = 0; i < N_CHILDREN; ++i) { - child->children[i] = NULL; - } - const int new_node_index = (int)first[0]; - assert(new_node_index < N_CHILDREN); - assert(!child->children[new_node_index]); - child->children[new_node_index] = new_node; -} - -static ZixStatus -patree_insert_internal(ZixFatPatreeNode* n, char* str, char* first, char* last) -{ - n_edges_t child_i; - assert(first <= last); - - if (patree_find_edge(n, *first, &child_i)) { - ZixFatPatreeNode* child = n->children[child_i]; - char* const label_first = child->label_first; - char* const label_last = child->label_last; - size_t split_i = 0; - const size_t label_len = label_last - label_first + 1; - const size_t s_len = last - first + 1; - const size_t max_len = (s_len < label_len) ? s_len : label_len; - - while (split_i < max_len && first[split_i] == label_first[split_i]) { - ++split_i; - } - child = n->children[child_i]; - - if (label_len < s_len) { - if (split_i == label_len) { - return patree_insert_internal(child, str, first + label_len, last); - } else { - patree_split_edge(child, split_i); - return patree_insert_internal(child, str, first + split_i, last); - } - } else if (label_len != split_i) { - patree_split_edge(child, split_i); - if (split_i != s_len) { - patree_add_edge(child, str, first + split_i, last); - } else { - assert(!child->str); - child->str = str; - } - return ZIX_STATUS_SUCCESS; - } else if (label_len == s_len && !child->str) { - child->str = str; - } else { - return ZIX_STATUS_EXISTS; - } - - } else { - patree_add_edge(n, str, first, last); - } - - return ZIX_STATUS_SUCCESS; -} - -ZIX_API -ZixStatus -zix_fat_patree_insert(ZixFatPatree* t, const char* str) -{ - const size_t len = strlen(str); - // FIXME: awful casts - return patree_insert_internal(t->root, (char*)str, (char*)str, (char*)str + len - 1); -} - -ZIX_API -ZixStatus -zix_fat_patree_find(ZixFatPatree* t, const char* p, char** match) -{ - ZixFatPatreeNode* n = t->root; - n_edges_t child_i; - - *match = NULL; - - while (*p != '\0') { - if (patree_find_edge(n, p[0], &child_i)) { - ZixFatPatreeNode* const child = n->children[child_i]; - const char* const label_first = child->label_first; - const char* const label_last = child->label_last; - - /* Prefix compare search string and label */ - const char* l = label_first; - while (*p != '\0' && l <= label_last) { - if (*l++ != *p++) { - return ZIX_STATUS_NOT_FOUND; - } - } - - if (!*p) { - /* Reached end of search string */ - if (l == label_last + 1) { - /* Reached end of label string as well, match */ - *match = child->str; - return *match ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; - } else { - /* Label string is longer, no match (prefix match) */ - return ZIX_STATUS_NOT_FOUND; - } - } else { - /* Match at this node, continue search downwards. - Possibly we have prematurely hit a leaf, so the next - edge search will fail. - */ - n = child; - } - } else { - return ZIX_STATUS_NOT_FOUND; - } - } - - return ZIX_STATUS_NOT_FOUND; -} diff --git a/zix/fat_patree.h b/zix/fat_patree.h deleted file mode 100644 index 2fb1b4d..0000000 --- a/zix/fat_patree.h +++ /dev/null @@ -1,71 +0,0 @@ -/* - Copyright 2011-2014 David Robillard - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#ifndef ZIX_FAT_PATREE_H -#define ZIX_FAT_PATREE_H - -#include "zix/common.h" - -/** - @addtogroup zix - @{ - @name FatPatree - @{ -*/ - -typedef struct _ZixFatPatree ZixFatPatree; - -/** - Construct a new Patree. -*/ -ZIX_API -ZixFatPatree* -zix_fat_patree_new(void); - -/** - Destroy `t`. -*/ -ZIX_API -void -zix_fat_patree_free(ZixFatPatree* t); - -/** - Print a DOT description of `t` to `fd`. -*/ -ZIX_API -void -zix_fat_patree_print_dot(const ZixFatPatree* t, FILE* fd); - -/** - Insert `str` into `t`. -*/ -ZIX_API -ZixStatus -zix_fat_patree_insert(ZixFatPatree* t, const char* str); - -/** - Search for `str` in `t`. -*/ -ZIX_API -ZixStatus -zix_fat_patree_find(ZixFatPatree* t, const char* str, char** match); - -/** - @} - @} -*/ - -#endif /* ZIX_FAT_PATREE_H */ -- cgit v1.2.1