From 87ae32d754d211d1f6510af098c2349a28f17351 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 10 Sep 2021 20:11:26 -0400 Subject: Remove ZixStrindex --- include/zix/strindex.h | 59 ----------- meson.build | 3 - src/strindex.c | 263 ------------------------------------------------- test/strindex_test.c | 66 ------------- 4 files changed, 391 deletions(-) delete mode 100644 include/zix/strindex.h delete mode 100644 src/strindex.c delete mode 100644 test/strindex_test.c diff --git a/include/zix/strindex.h b/include/zix/strindex.h deleted file mode 100644 index 8493b8c..0000000 --- a/include/zix/strindex.h +++ /dev/null @@ -1,59 +0,0 @@ -/* - Copyright 2011-2020 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_STRINDEX_H -#define ZIX_STRINDEX_H - -#include "zix/common.h" - -/** - @addtogroup zix - @{ - @name Strindex - @{ -*/ - -typedef struct ZixStrindexImpl ZixStrindex; - -/** - Construct a new strindex that contains all suffixes of the string `s`. - - A copy of `s` is taken and stored for the lifetime of the strindex. -*/ -ZIX_API -ZixStrindex* -zix_strindex_new(const char* s); - -/// Destroy `t` -ZIX_API -void -zix_strindex_free(ZixStrindex* strindex); - -/** - Check if the string in `strindex` contains the substring `str`. - - If such a substring is found, `match` is pointed at an occurrence of it. -*/ -ZIX_API -ZixStatus -zix_strindex_find(ZixStrindex* strindex, const char* str, char** match); - -/** - @} - @} -*/ - -#endif /* ZIX_STRINDEX_H */ diff --git a/meson.build b/meson.build index 5651c0c..bc32e80 100644 --- a/meson.build +++ b/meson.build @@ -177,7 +177,6 @@ sources = [ 'src/digest.c', 'src/hash.c', 'src/ring.c', - 'src/strindex.c', 'src/tree.c', ] @@ -215,7 +214,6 @@ headers = [ 'include/zix/hash.h', 'include/zix/ring.h', 'include/zix/sem.h', - 'include/zix/strindex.h', 'include/zix/thread.h', 'include/zix/tree.h', ] @@ -234,7 +232,6 @@ tests = [ 'hash_test', 'ring_test', 'sem_test', - 'strindex_test', 'tree_test', ] diff --git a/src/strindex.c b/src/strindex.c deleted file mode 100644 index f800210..0000000 --- a/src/strindex.c +++ /dev/null @@ -1,263 +0,0 @@ -/* - Copyright 2011-2020 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 "zix/strindex.h" - -#include "zix/common.h" - -#include -#include -#include -#include - -typedef struct ZixStrindexNode { - struct ZixStrindexNode* children; /* Children of this node */ - size_t num_children; /* Number of outgoing edges */ - char* first; /* Start of this suffix */ - char* label_first; /* Start of incoming label */ - char* label_last; /* End of incoming label */ -} ZixStrindexNode; - -struct ZixStrindexImpl { - char* s; /* String contained in this tree */ - ZixStrindexNode* root; /* Root of the tree */ -}; - -static ZixStatus -strindex_insert(ZixStrindexNode* n, - char* suffix_first, - char* first, - char* last); - -ZixStrindex* -zix_strindex_new(const char* s) -{ - const size_t len = strlen(s); - - ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex)); - memset(t, '\0', sizeof(ZixStrindex)); - - t->s = (char*)calloc(1, len + 1); - memcpy(t->s, s, len); - - t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode)); - memset(t->root, '\0', sizeof(ZixStrindexNode)); - t->root->num_children = 0; - t->root->first = t->s; - - for (size_t i = 0; i < len; ++i) { - strindex_insert(t->root, t->s + i, t->s + i, t->s + (len - 1)); - } - - return t; -} - -static void -zix_strindex_free_rec(ZixStrindexNode* n) -{ - if (n) { - for (size_t i = 0; i < n->num_children; ++i) { - zix_strindex_free_rec(&n->children[i]); - } - - free(n->children); - } -} - -void -zix_strindex_free(ZixStrindex* strindex) -{ - if (strindex) { - zix_strindex_free_rec(strindex->root); - free(strindex->s); - free(strindex->root); - free(strindex); - } -} - -static inline int -strindex_is_leaf(ZixStrindexNode* n) -{ - return n->num_children == 0; -} - -static int -strindex_find_edge(ZixStrindexNode* n, char c, size_t* index) -{ - for (size_t i = 0; i < n->num_children; ++i) { - if (n->children[i].label_first[0] == c) { - *index = i; - return 1; - } - } - - return 0; -} - -static void -strindex_add_edge(ZixStrindexNode* n, - char* suffix_first, - char* first, - char* last) -{ - assert(last > first); - n->children = (ZixStrindexNode*)realloc( - n->children, (n->num_children + 1) * sizeof(ZixStrindexNode)); - - memset(&n->children[n->num_children], '\0', sizeof(ZixStrindexNode)); - - n->children[n->num_children].first = suffix_first; - n->children[n->num_children].label_first = first; - n->children[n->num_children].label_last = last; - ++n->num_children; -} - -/* Split an outgoing edge (to a child) at the given index */ -static void -strindex_split_edge(ZixStrindexNode* child, size_t index) -{ - ZixStrindexNode* children = child->children; - size_t num_children = child->num_children; - - char* first = child->label_first + index; - char* last = child->label_last; - assert(last > first); - assert(child->first); - - child->children = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode)); - - child->children[0].children = children; - child->children[0].num_children = num_children; - child->children[0].first = child->first; - child->children[0].label_first = first; - child->children[0].label_last = last; - - child->label_last = child->label_first + (index - 1); // chop end - - child->num_children = 1; -} - -static ZixStatus -strindex_insert(ZixStrindexNode* n, char* suffix_first, char* first, char* last) -{ - size_t child_i = 0; - ZixStrindexNode* child = NULL; - assert(first <= last); - - if (strindex_find_edge(n, *first, &child_i)) { - char* label_first = n->children[child_i].label_first; - char* label_last = n->children[child_i].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) { - strindex_insert(child, suffix_first, first + label_len, last); - } else { - strindex_split_edge(child, split_i); - strindex_insert(child, suffix_first, first + split_i, last); - } - } else if ((label_len != split_i) && (label_len != s_len)) { - strindex_split_edge(child, split_i); - if (split_i != s_len) { - strindex_add_edge(child, suffix_first, first + split_i, last); - } - } - } else { - strindex_add_edge(n, suffix_first, first, last); - } - - return ZIX_STATUS_SUCCESS; -} - -ZixStatus -zix_strindex_find(ZixStrindex* strindex, const char* const str, char** match) -{ - const char* p = str; - -#ifndef NDEBUG - const char* orig_p = p; -#endif - - ZixStrindexNode* n = strindex->root; - size_t child_i = 0; - - *match = NULL; - - while (*p != '\0') { - size_t p_len = strlen(p); - if (strindex_find_edge(n, p[0], &child_i)) { - char* label_first = n->children[child_i].label_first; - char* label_last = n->children[child_i].label_last; - size_t label_len = label_last - label_first + 1; - size_t max_len = (p_len < label_len) ? p_len : label_len; - assert(child_i <= n->num_children); - assert(max_len > 0); - - /* Set match to the start of substring - (but may not actually be a complete match yet) - */ - if (*match == NULL) { - assert(p[0] == orig_p[0]); - assert(orig_p[0] == label_first[0]); - *match = n->children[child_i].first; - assert((*match)[0] == orig_p[0]); - } - - if (!!strncmp(p, label_first, max_len)) { - /* no match */ - *match = NULL; - return ZIX_STATUS_NOT_FOUND; - } - - if (p_len <= label_len) { - /* At the last node, match */ - *match = n->children[child_i].first; - assert(!strncmp(*match, orig_p, strlen(orig_p))); - return ZIX_STATUS_SUCCESS; - } - - if (strindex_is_leaf(n)) { - /* Hit leaf early, no match */ - return ZIX_STATUS_NOT_FOUND; - } - - /* Match at this node, continue search downwards (or match) */ - p += label_len; - n = &n->children[child_i]; - if (label_len >= p_len) { - assert(strstr(strindex->s, orig_p) != NULL); - assert(strncmp(orig_p, *match, max_len)); - return ZIX_STATUS_SUCCESS; - } - - } else { - assert(strstr(strindex->s, orig_p) == NULL); - return ZIX_STATUS_NOT_FOUND; - } - } - - return ZIX_STATUS_NOT_FOUND; -} diff --git a/test/strindex_test.c b/test/strindex_test.c deleted file mode 100644 index bd6a389..0000000 --- a/test/strindex_test.c +++ /dev/null @@ -1,66 +0,0 @@ -/* - Copyright 2011-2020 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. -*/ - -#include "zix/common.h" -#include "zix/strindex.h" - -#include -#include -#include -#include - -ZIX_LOG_FUNC(1, 2) -static int -test_fail(const char* fmt, ...) -{ - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; -} - -int -main(void) -{ - zix_strindex_free(NULL); - - const char* str = "BANANA"; - const size_t str_len = strlen(str); - ZixStrindex* strindex = zix_strindex_new(str); - - for (size_t l = 1; l <= str_len; ++l) { - for (size_t i = 0; i < str_len - l; ++i) { - char* match = NULL; - ZixStatus ret = zix_strindex_find(strindex, str + i, &match); - if (ret) { - return test_fail( - "No match for substring at %" PRIuPTR " length %" PRIuPTR "\n", i, l); - } - - if (!!strncmp(str + i, match, l)) { - return test_fail("Bad match for substring at %" PRIuPTR - " length %" PRIuPTR "\n", - i, - l); - } - } - } - - zix_strindex_free(strindex); - return 0; -} -- cgit v1.2.1