From 3c1f28a7bf0d7c3335c1cf25d664596a21eb22b0 Mon Sep 17 00:00:00 2001 From: David McMackins II Date: Tue, 25 Feb 2020 20:53:40 -0600 Subject: Add pt_foreach --- pfxtree-test.c | 26 +++++++++++---- pfxtree.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++---- pfxtree.h | 40 +++++++++++++++++++---- 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 #include +#include #include #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. -- cgit v1.2.3