Add pt_del

2 files changed, 177 insertions, 140 deletions

diff --git a/pfxtree.c b/pfxtree.c
index fa9a0e7..25ea7d5 100644
--- a/pfxtree.c
+++ b/pfxtree.c
@@ -1,6 +1,6 @@
 /*
  *  libpfxtree - Delwink prefix tree library
- *  Copyright (C) 2015 Delwink, LLC
+ *  Copyright (C) 2015, 2017 Delwink, LLC
  *
  *  This program is free software: you can redistribute it and/or modify
  *  it under the terms of the GNU Affero General Public License as published by
@@ -18,191 +18,217 @@
 #include <stdlib.h>
 #include <string.h>
 
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
 #include "pfxtree.h"
 
-#define pt_child_foreach(S,C) for (C = S->children; C != NULL; C = C->next)
+#define pt_child_foreach(S,C) for ((C) = (S)->children;			\
+				   (C) != NULL; (C) = (C)->next)
 
 PrefixTree *
-pt_new ()
+pt_new()
 {
-  PrefixTree *self = malloc (sizeof (PrefixTree));
-  if (NULL == self)
-    return NULL;
-
-  self->ch = '\0';
-  self->type = '\0';
-  self->data.i = 0;
-  self->children = NULL;
-  self->next = NULL;
-
-  return self;
+	PrefixTree *self = malloc(sizeof(PrefixTree));
+	if (!self)
+		return NULL;
+
+	self->ch = '\0';
+	self->type = '\0';
+	self->data.i = 0;
+	self->parent = NULL;
+	self->children = NULL;
+	self->next = NULL;
+
+	return self;
 }
 
 void
-pt_free (PrefixTree *self)
+pt_free(PrefixTree *self)
 {
-  pt_deep_free (self, false);
+	pt_deep_free(self, false);
 }
 
 void
-pt_deep_free (PrefixTree *self, bool free_data)
+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)
-	free (child->data.p);
+	PrefixTree *child, *next = NULL;
+	for (child = self->children; child != NULL; child = next)
+	{
+		if (free_data && 'p' == child->type && child->data.p != NULL)
+			free(child->data.p);
 
-      next = child->next;
-      pt_deep_free (child, free_data);
-    }
+		next = child->next;
+		pt_deep_free(child, free_data);
+	}
 
-  free (self);
+	free(self);
 }
 
 static PrefixTree *
-get_last_child (const PrefixTree *self)
+get_last_child(const PrefixTree *self)
 {
-  PrefixTree *child;
-  pt_child_foreach (self, child)
-    {
-      if (NULL == child->next)
-	return child;
-    }
-
-  return NULL;
+	PrefixTree *child;
+	pt_child_foreach(self, child)
+	{
+		if (!child->next)
+			return child;
+	}
+
+	return NULL;
 }
 
 static PrefixTree *
-get_child_by_ch (const PrefixTree *self, const char ch)
+get_child_by_ch(const PrefixTree *self, const char ch)
 {
-  PrefixTree *child;
-  pt_child_foreach (self, child)
-    {
-      if (ch == child->ch)
-	return child;
-    }
-
-  return NULL;
+	PrefixTree *child;
+	pt_child_foreach(self, child)
+	{
+		if (ch == child->ch)
+			return child;
+	}
+
+	return NULL;
 }
 
 static int
-add (PrefixTree *self, const char *word, union _pt_data data, char type)
+add(PrefixTree *self, const char *word, union _pt_data data, char type)
 {
-  int rc = 0;
-  PrefixTree *node = self;
-  size_t i, len = strlen (word);
+	int rc = 0;
+	PrefixTree *node = self;
+	size_t i, len = strlen(word);
 
-  for (i = 0; i <= len; ++i)
-    {
-      PrefixTree *child = get_child_by_ch (node, word[i]);
-      if (NULL == child)
-	break;
+	for (i = 0; i <= len; ++i)
+	{
+		PrefixTree *child = get_child_by_ch(node, word[i]);
+		if (!child)
+			break;
 
-      node = child;
-    }
+		node = child;
+	}
 
-  PrefixTree *first_insertion = NULL;
+	PrefixTree *first_insertion = NULL;
 
-  for (; i <= len; ++i)
-    {
-      PrefixTree *new = pt_new ();
-      if (NULL == new)
+	for (; i <= len; ++i)
 	{
-	  rc = PT_EALLOC;
-	  break;
+		PrefixTree *new = pt_new();
+		if (!new)
+		{
+			rc = PT_EALLOC;
+			break;
+		}
+
+		new->ch = word[i];
+		new->parent = node;
+
+		PrefixTree *end = get_last_child(node);
+		if (!end)
+			node->children = new;
+		else
+			end->next = new;
+
+		if (!first_insertion)
+			first_insertion = new;
+
+		node = new;
 	}
 
-      new->ch = word[i];
-
-      PrefixTree *end = get_last_child (node);
-      if (NULL == end)
-	node->children = new;
-      else
-	end->next = new;
-
-      if (NULL == first_insertion)
-	first_insertion = new;
-
-      node = new;
-    }
+	if (rc)
+	{
+		pt_free(first_insertion);
+		return rc;
+	}
 
-  if (rc)
-    {
-      pt_free (first_insertion);
-      return rc;
-    }
+	node->data = data;
+	node->type = type;
 
-  node->data = data;
-  node->type = type;
+	return rc;
+}
 
-  return rc;
+int
+pt_add(PrefixTree *self, const char *word, int data)
+{
+	union _pt_data d;
+	d.i = data;
+	return add(self, word, d, 'i');
 }
 
 int
-pt_add (PrefixTree *self, const char *word, int data)
+pt_add_p(PrefixTree *self, const char *word, void *data)
 {
-  union _pt_data d;
-  d.i = data;
-  return add (self, word, d, 'i');
+	union _pt_data d;
+	d.p = data;
+	return add(self, word, d, 'p');
+}
+
+static size_t
+num_children(PrefixTree *self)
+{
+	if (!self->children)
+		return 0;
+
+	size_t i;
+	self = self->children;
+	for (i = 1; self->next; ++i)
+		self = self->next;
+
+	return i;
 }
 
 int
-pt_add_p (PrefixTree *self, const char *word, void *data)
+pt_del(PrefixTree *self, const char *word)
 {
-  union _pt_data d;
-  d.p = data;
-  return add (self, word, d, 'p');
+	PrefixTree *p = (PrefixTree *) pt_search(self, word);
+	if (!p)
+		return PT_ENOWORD;
+
+	while (p->parent != NULL && num_children(p->parent) == 1)
+		p = p->parent;
+
+	if (!p->parent)
+		p = p->children;
+
+	pt_deep_free(p, true);
+	return 0;
 }
 
 int
-pt_data (const PrefixTree *self)
+pt_data(const PrefixTree *self)
 {
-  return self->data.i;
+	return self->data.i;
 }
 
 void *
-pt_data_p (const PrefixTree *self)
+pt_data_p(const PrefixTree *self)
 {
-  return self->data.p;
+	return self->data.p;
 }
 
 char
-pt_data_type (const PrefixTree *self)
+pt_data_type(const PrefixTree *self)
 {
-  return self->type;
+	return self->type;
 }
 
 const PrefixTree *
-pt_search (const PrefixTree *root, const char *word)
+pt_search(const PrefixTree *root, const char *word)
 {
-  const PrefixTree *node = root;
-  size_t i, len = strlen (word);
+	const PrefixTree *node = root;
+	size_t i, len = strlen(word);
 
-  for (i = 0; i <= len; ++i)
-    {
-      node = get_child_by_ch (node, word[i]);
+	for (i = 0; i <= len; ++i)
+	{
+		node = get_child_by_ch(node, word[i]);
 
-      if (NULL == node)
-	return NULL;
+		if (!node)
+			return NULL;
 
-      if ('\0' == node->ch)
-	return node;
-    }
+		if ('\0' == node->ch)
+			return node;
+	}
 
-  return NULL;
+	return NULL;
 }
 
 const char *
-pt_version ()
+pt_version()
 {
-#ifdef HAVE_CONFIG_H
-  return PACKAGE_VERSION;
-#else
-  return "Unknown";
-#endif
+	return "0.3.0";
 }
diff --git a/pfxtree.h b/pfxtree.h
index 4c2987d..e691fe4 100644
--- a/pfxtree.h
+++ b/pfxtree.h
@@ -1,6 +1,6 @@
 /*
  *  libpfxtree - Delwink prefix tree library
- *  Copyright (C) 2015 Delwink, LLC
+ *  Copyright (C) 2015, 2017 Delwink, LLC
  *
  *  This program is free software: you can redistribute it and/or modify
  *  it under the terms of the GNU Affero General Public License as published by
@@ -17,8 +17,8 @@
 
 /**
  * @file pfxtree.h
- * @version 0.2
- * @date 12/30/2015
+ * @version 0.3
+ * @date 5/12/2017
  * @author David McMackins II
  * @brief Delwink prefix tree (trie) library
  */
@@ -43,13 +43,14 @@ __BEGIN_DECLS
  */
 enum pt_error
 {
-  PT_EALLOC = -1
+	PT_EALLOC  = -1,
+	PT_ENOWORD = -2
 };
 
 union _pt_data
 {
-  int i;
-  void *p;
+	int i;
+	void *p;
 };
 
 /**
@@ -57,12 +58,13 @@ union _pt_data
  */
 typedef struct _pt_trie
 {
-  char ch;
-  char type;
-  union _pt_data data;
+	char ch;
+	char type;
+	union _pt_data data;
 
-  struct _pt_trie *children;
-  struct _pt_trie *next;
+	struct _pt_trie *parent;
+	struct _pt_trie *children;
+	struct _pt_trie *next;
 } PrefixTree;
 
 /**
@@ -70,14 +72,14 @@ typedef struct _pt_trie
  * @return Pointer to the root node of the tree or NULL on failure.
  */
 PrefixTree *
-pt_new (void);
+pt_new(void);
 
 /**
  * @brief Frees an allocated prefix tree (and its child nodes).
  * @param self The tree to free.
  */
 void
-pt_free (PrefixTree *self);
+pt_free(PrefixTree *self);
 
 /**
  * @brief Frees an allocated prefix tree (and its child nodes) and optionally
@@ -86,7 +88,7 @@ pt_free (PrefixTree *self);
  * @param free_data Whether to free memory pointed to by the data (if pointer).
  */
 void
-pt_deep_free (PrefixTree *self, bool free_data);
+pt_deep_free(PrefixTree *self, bool free_data);
 
 /**
  * @brief Adds a new word to a prefix tree with integer data.
@@ -96,7 +98,7 @@ pt_deep_free (PrefixTree *self, bool free_data);
  * @return Nonzero if an error occurred.
  */
 int
-pt_add (PrefixTree *self, const char *word, int data);
+pt_add(PrefixTree *self, const char *word, int data);
 
 /**
  * @brief Adds a new word to a prefix tree with pointer data.
@@ -106,7 +108,16 @@ pt_add (PrefixTree *self, const char *word, int data);
  * @return Nonzero if an error occurred.
  */
 int
-pt_add_p (PrefixTree *self, const char *word, void *data);
+pt_add_p(PrefixTree *self, const char *word, void *data);
+
+/**
+ * @brief Deletes a word from a prefix tree.
+ * @param self The tree from which to delete the word.
+ * @param word The word to be deleted.
+ * @return Nonzero if word not found.
+ */
+int
+pt_del(PrefixTree *self, const char *word);
 
 /**
  * @brief Gets the integer data from a prefix tree node.
@@ -114,7 +125,7 @@ pt_add_p (PrefixTree *self, const char *word, void *data);
  * @return self's data (default 0).
  */
 int
-pt_data (const PrefixTree *self);
+pt_data(const PrefixTree *self);
 
 /**
  * @brief Gets the pointer data from a prefix tree node.
@@ -122,7 +133,7 @@ pt_data (const PrefixTree *self);
  * @return self's data (default NULL).
  */
 void *
-pt_data_p (const PrefixTree *self);
+pt_data_p(const PrefixTree *self);
 
 /**
  * @brief Gets the type of the data stored in the prefix tree node.
@@ -130,7 +141,7 @@ pt_data_p (const PrefixTree *self);
  * @return 'i' if integer, 'p' if pointer, or '\0' if no data.
  */
 char
-pt_data_type (const PrefixTree *self);
+pt_data_type(const PrefixTree *self);
 
 /**
  * @brief Searches for a word in a prefix tree.
@@ -139,14 +150,14 @@ pt_data_type (const PrefixTree *self);
  * @return Pointer to the data-storing node of the word or NULL if not found.
  */
 const PrefixTree *
-pt_search (const PrefixTree *root, const char *word);
+pt_search(const PrefixTree *root, const char *word);
 
 /**
  * @brief Checks the current version of the library.
  * @return A version string for this libpfxtree installation.
  */
 const char *
-pt_version (void);
+pt_version(void);
 
 __END_DECLS