Remove ZixStrindex

1 files changed, 0 insertions, 263 deletions

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 <d@drobilla.net>
-
-  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 <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-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;
-}