summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid McMackins II <contact@mcmackins.org>2020-02-25 20:53:40 -0600
committerDavid McMackins II <contact@mcmackins.org>2020-02-25 20:53:40 -0600
commit3c1f28a7bf0d7c3335c1cf25d664596a21eb22b0 (patch)
tree2a765cb12a0c91f0f5a75d530c28d9d8628df36e
parent7c9cf4a184595f589ff11bd0008dd4a8c54e1a25 (diff)
Add pt_foreach
-rw-r--r--pfxtree-test.c26
-rw-r--r--pfxtree.c100
-rw-r--r--pfxtree.h40
3 files changed, 146 insertions, 20 deletions
diff --git a/pfxtree-test.c b/pfxtree-test.c
index d176505..345b7bc 100644
--- a/pfxtree-test.c
+++ b/pfxtree-test.c
@@ -38,36 +38,48 @@
#include <assert.h>
#include <stdbool.h>
+#include <stdio.h>
#include <stdlib.h>
#include "pfxtree.h"
+static int
+check_entry(const struct pt_entry *entry, void *data)
+{
+ if (PT_TYPE_PTR == entry->type)
+ assert(entry->data.p == data);
+
+ return 0;
+}
+
int
main(void)
{
PrefixTree *p = pt_new();
+ void *dummy;
assert(p != NULL);
assert(0 == pt_add(p, "hello", 1));
assert(0 == pt_add(p, "world", 2));
+ assert(0 == pt_add(p, "henlo", 3));
assert(0 == pt_add(p, "hell", -1));
- assert('i' == pt_data_type(pt_search(p, "hell")));
+ assert(PT_TYPE_INT == pt_data_type(pt_search(p, "hell")));
assert(-1 == pt_data(pt_search(p, "hell")));
assert(0 == pt_del(p, "hello"));
assert(NULL == pt_search(p, "hello"));
assert(pt_search(p, "hell") != NULL);
- {
- void *dummy = malloc(0xDFDF);
- assert(dummy != NULL);
- assert(0 == pt_add_p(p, "hello", dummy));
- assert('p' == pt_data_type(pt_search(p, "hello")));
- }
+ dummy = malloc(0xDFDF);
+ assert(dummy != NULL);
+ assert(0 == pt_add_p(p, "hello", dummy));
+ assert(PT_TYPE_PTR == pt_data_type(pt_search(p, "hello")));
assert(PT_ENOWORD == pt_del(p, "asdf"));
+ pt_foreach(p, check_entry, dummy);
+
pt_deep_free(p, true);
return 0;
}
diff --git a/pfxtree.c b/pfxtree.c
index 074bab8..c295ada 100644
--- a/pfxtree.c
+++ b/pfxtree.c
@@ -73,7 +73,8 @@ pt_deep_free(PrefixTree *self, bool free_data)
PrefixTree *child, *next = NULL;
for (child = self->children; child != NULL; child = next)
{
- if (free_data && 'p' == child->type && child->data.p != NULL)
+ if (free_data && PT_TYPE_PTR == child->type
+ && child->data.p != NULL)
free(child->data.p);
next = child->next;
@@ -110,7 +111,8 @@ get_child_by_ch(const PrefixTree *self, const int ch)
}
static int
-add(PrefixTree *self, const char *word, union _pt_data data, int type)
+add(PrefixTree *self, const char *word, union pt_data data,
+ enum pt_data_type type)
{
int rc = 0;
PrefixTree *node = self, *first_insertion = NULL;
@@ -164,17 +166,17 @@ add(PrefixTree *self, const char *word, union _pt_data data, int type)
int
pt_add(PrefixTree *self, const char *word, int data)
{
- union _pt_data d;
+ union pt_data d;
d.i = data;
- return add(self, word, d, 'i');
+ return add(self, word, d, PT_TYPE_INT);
}
int
pt_add_p(PrefixTree *self, const char *word, void *data)
{
- union _pt_data d;
+ union pt_data d;
d.p = data;
- return add(self, word, d, 'p');
+ return add(self, word, d, PT_TYPE_PTR);
}
static size_t
@@ -264,6 +266,92 @@ pt_search(const PrefixTree *root, const char *word)
return NULL;
}
+static const PrefixTree *
+delve(const PrefixTree *node, char **bufptr, size_t *bufsize, size_t *i)
+{
+ while (node->children)
+ {
+ char *buf = *bufptr;
+
+ node = node->children;
+ buf[(*i)++] = node->ch;
+ if (*i >= *bufsize)
+ {
+ char *temp;
+ *bufsize += 32;
+ temp = realloc(*bufptr, *bufsize);
+ if (!temp)
+ return NULL;
+
+ *bufptr = temp;
+ }
+ }
+
+ return node;
+}
+
+int
+pt_foreach(const PrefixTree *root, int (*f)(const struct pt_entry *,void *),
+ void *data)
+{
+ int rc = 0;
+ char *buf;
+ size_t i = 0, bufsize = 32;
+ const PrefixTree *node;
+ struct pt_entry entry;
+
+ if (!root)
+ return rc;
+
+ buf = malloc(bufsize);
+ if (!buf)
+ return PT_EALLOC;
+
+ node = delve(root, &buf, &bufsize, &i);
+ if (!node)
+ {
+ rc = PT_EALLOC;
+ goto end;
+ }
+
+ while (node->parent)
+ {
+ PrefixTree *temp;
+
+ if ('\0' == node->ch)
+ {
+ entry.word = buf;
+ entry.type = node->type;
+ entry.data = node->data;
+
+ rc = f(&entry, data);
+ if (rc)
+ goto end;
+ }
+
+ --i;
+ temp = node->next;
+ if (temp)
+ {
+ buf[i++] = temp->ch;
+ node = delve(temp, &buf, &bufsize, &i);
+ if (!node)
+ {
+ rc = PT_EALLOC;
+ goto end;
+ }
+ }
+ else
+ {
+ node = node->parent;
+ }
+ }
+
+end:
+ free(buf);
+ return rc;
+}
+
const char *
pt_version()
{
diff --git a/pfxtree.h b/pfxtree.h
index 6e82a5d..7e1614f 100644
--- a/pfxtree.h
+++ b/pfxtree.h
@@ -1,6 +1,6 @@
/*
* libpfxtree - Delwink prefix tree library
- * Copyright (C) 2015, 2017 Delwink, LLC
+ * Copyright (C) 2015, 2017, 2020 Delwink, LLC
*
* Redistributions, modified or unmodified, in whole or in part, must retain
* applicable copyright or other legal privilege notices, these conditions, and
@@ -38,8 +38,8 @@
/**
* @file pfxtree.h
- * @version 0.3
- * @date 5/12/2017
+ * @version 0.4
+ * @date 2/25/2020
* @author David McMackins II
* @brief Delwink prefix tree (trie) library
*/
@@ -59,6 +59,12 @@
__BEGIN_DECLS
+enum pt_data_type
+{
+ PT_TYPE_INT,
+ PT_TYPE_PTR
+};
+
/**
* @brief Error codes possibly returned by functions in this library.
*/
@@ -68,7 +74,7 @@ enum pt_error
PT_ENOWORD = -2
};
-union _pt_data
+union pt_data
{
int i;
void *p;
@@ -79,13 +85,14 @@ union _pt_data
*/
typedef struct _pt_trie
{
- int ch;
- int type;
- union _pt_data data;
+ union pt_data data;
struct _pt_trie *parent;
struct _pt_trie *children;
struct _pt_trie *next;
+
+ int ch;
+ enum pt_data_type type;
} PrefixTree;
/**
@@ -173,6 +180,25 @@ pt_data_type(const PrefixTree *self);
const PrefixTree *
pt_search(const PrefixTree *root, const char *word);
+struct pt_entry
+{
+ const char *word;
+ union pt_data data;
+ enum pt_data_type type;
+};
+
+/**
+ * @brief Run an operation for each word in a prefix tree.
+ * @param root The node from which to begin the search.
+ * @param f The operation to be run, accepting the word, its data, and
+ * and arbitrary data; returns nonzero to break the loop.
+ * @param data Data to be passed to f.
+ * @return Nonzero on error, or nonzero return from f.
+ */
+int
+pt_foreach(const PrefixTree *root, int (*f)(const struct pt_entry *,void *),
+ void *data);
+
/**
* @brief Checks the current version of the library.
* @return A version string for this libpfxtree installation.