libsysio-commit

[Libsysio-commit] HEAD: libsysio/src tree.c

[Lee W. <lw...@us...>]

Update of /cvsroot/libsysio/libsysio/src
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12701/src

Modified Files:
	tree.c 
Log Message:


A new routine, _sysio_enumerate_tree, is added that supports pre-order,
in-order, and post-order traversals of a tree with callbacks at each node.


Index: tree.c
===================================================================
RCS file: /cvsroot/libsysio/libsysio/src/tree.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -w -b -B -p -r1.1 -r1.2
--- tree.c	21 Sep 2007 19:35:53 -0000	1.1
+++ tree.c	19 Apr 2008 19:09:14 -0000	1.2
@@ -174,3 +174,26 @@ _sysio_tree_delete(const void *key,
 	}
 	return tn;
 }
+
+/*
+ * Enumerate the passed tree calling the pre, in, and post routines at each
+ * node if they aren't NULL.
+ */
+void
+_sysio_tree_enumerate(const struct tree_node *tn,
+		      void (*pre)(const struct tree_node *),
+		      void (*in)(const struct tree_node *),
+		      void (*post)(const struct tree_node *))
+{
+
+	if (pre)
+		(*pre)(tn);
+	if (tn->tn_left)
+		_sysio_tree_enumerate(tn->tn_left, pre, in, post);
+	if (in)
+		(*in)(tn);
+	if (tn->tn_right)
+		_sysio_tree_enumerate(tn->tn_right, pre, in, post);
+	if (post)
+		(*post)(tn);
+}

[Libsysio-commit] HEAD: libsysio/src tree.c

[Lee W. <lw...@us...>]

Update of /cvsroot/libsysio/libsysio/src
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv9079/src

Modified Files:
	tree.c 
Log Message:


Altered the, so far unused by anyone, enumerate routine to take
an extra argument and pass same to the pre, in, and post callbacks. This,
to allow the caller to pass and maintain context.

Also, the enumerate routine has been re-implemented with a de-recursed
version. Strange that has been done here first since it's badly needed
in other parts of the core and this routine is used nowhere.

Obviously, these changes are not well tested.


Index: tree.c
===================================================================
RCS file: /cvsroot/libsysio/libsysio/src/tree.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -w -b -B -p -r1.2 -r1.3
--- tree.c	19 Apr 2008 19:09:14 -0000	1.2
+++ tree.c	17 Apr 2009 14:54:35 -0000	1.3
@@ -42,6 +42,7 @@
  */
 
 #include <stdlib.h>
+#include <errno.h>
 
 #include "tree.h"
 
@@ -179,21 +180,114 @@ _sysio_tree_delete(const void *key,
  * Enumerate the passed tree calling the pre, in, and post routines at each
  * node if they aren't NULL.
  */
-void
+int
 _sysio_tree_enumerate(const struct tree_node *tn,
-		      void (*pre)(const struct tree_node *),
-		      void (*in)(const struct tree_node *),
-		      void (*post)(const struct tree_node *))
+		      int (*pre)(const struct tree_node *, void *),
+		      int (*in)(const struct tree_node *, void *),
+		      int (*post)(const struct tree_node *, void *),
+		      void *data)
 {
+	struct stk_entry {
+		enum { PRE, IN, POST } state;
+		union {
+			const struct tree_node *tn;
+			struct stk_entry *next;
+		} u;
+	} *_free, *_list, *_tmp, *_seg_end, *top;
+	int	result;
+
+#define _NPERSEG	20
+
+#define _GET_FREE \
+	(_free \
+	   ? ((_tmp = _free), \
+	      (_free = _tmp->u.next), \
+	      (_tmp->u.next = _list), \
+	      (_list = _tmp)) \
+	   : ((_tmp = malloc(_NPERSEG * sizeof(struct stk_entry))) \
+		? ((_tmp->u.next = _list), \
+		   (_list = _tmp)) \
+		: NULL))
+
+#define _PUSH \
+	((++top < _seg_end) \
+	   ? 0 \
+	   : (_GET_FREE \
+		? ((_seg_end = _list + _NPERSEG), \
+		   (top = _list + 1), \
+		   0) \
+		: -ENOMEM))
+#define _POP \
+	((--top > _list) \
+	   ? 0 \
+	   : ((_tmp = _list) \
+	        ? ((_list = _list->u.next), \
+		   (top = (_seg_end = _list + _NPERSEG) - 1), \
+		   (_tmp->u.next = _free), \
+		   (_free = _tmp->u.next), \
+		   0) \
+		: 1))
+
+	top = _free = _list = _seg_end = NULL;
+	result = ((++top < _seg_end)
+	   ? 0
+	   : (_GET_FREE
+		? ((_seg_end = _list + _NPERSEG),
+		   (top = _list + 1),
+		   0)
+		: -ENOMEM));
+	if (!result) {
+		top->state = PRE;
+		top->u.tn = tn;
+	}
+	while (!result && _POP) {
+		tn = top->u.tn;
+		switch (top->state) {
+		case PRE:
+			if (pre && (result = (*pre)(tn, data)))
+				break;
+			top->state = IN;
+			if (tn->tn_left) {
+				if ((result = _PUSH))
+					break;
+				top->state = PRE;
+				top->u.tn = tn->tn_left;
+				break;
+			}
+		case IN:
+			if (in && (result = (*in)(tn, data)))
+				break;
+			top->state = POST;
+			if (tn->tn_right) {
+				if ((result = _PUSH))
+					break;
+				top->state = PRE;
+				top->u.tn = tn->tn_right;
+				break;
+			}
+		case POST:
+			if (post && (result = (*post)(tn, data)))
+				break;
+			break;
+		default:
+			result = -EINVAL;
+		}
+	}
 
-	if (pre)
-		(*pre)(tn);
-	if (tn->tn_left)
-		_sysio_tree_enumerate(tn->tn_left, pre, in, post);
-	if (in)
-		(*in)(tn);
-	if (tn->tn_right)
-		_sysio_tree_enumerate(tn->tn_right, pre, in, post);
-	if (post)
-		(*post)(tn);
+#undef _POP
+#undef _PUSH
+#undef _GET_FREE
+#undef _NPERSEG
+
+	while (_list) {
+		_tmp = _list;
+		_list = _list->u.next;
+		free(_tmp);
+	}
+	while (_free) {
+		_tmp = _free;
+		_free = _free->u.next;
+		free(_tmp);
+	}
+	return result;
 }

[Libsysio-commit] HEAD: libsysio/src tree.c

[Lee W. <lw...@us...>]

Update of /cvsroot/libsysio/libsysio/src
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv26922/src

Modified Files:
	tree.c 
Log Message:


The splay routine is now public, called _sysio_splay. Note, it's still
a really bad idea to depend on the other tree routines maintaining their
trees as a splay-tree.


Index: tree.c
===================================================================
RCS file: /cvsroot/libsysio/libsysio/src/tree.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -w -b -B -p -r1.3 -r1.4
--- tree.c	17 Apr 2009 14:54:35 -0000	1.3
+++ tree.c	31 Aug 2009 21:35:45 -0000	1.4
@@ -52,8 +52,8 @@
  * Returns the value from the last compare; The one that brought, or left,
  * the root node at return.
  */
-static int
-splay(const void *key,
+int
+_sysio_splay(const void *key,
       struct tree_node **rootp,
       int (*compar)(const void *, const void *))
 {
@@ -120,7 +120,7 @@ _sysio_tree_search(struct tree_node *tn,
 	if (!*rootp) {
 		tn->tn_left = tn->tn_right = NULL;
 	} else {
-		i = splay(tn->tn_key, rootp, compar);
+		i = _sysio_splay(tn->tn_key, rootp, compar);
 		if (i < 0) {
 			tn->tn_left = (*rootp)->tn_left;
 			tn->tn_right = *rootp;
@@ -147,7 +147,7 @@ _sysio_tree_find(const void *key,
 
 	if (!*rootp)
 		return NULL;
-	return splay(key, rootp, compar) == 0 ? *rootp : NULL;
+	return _sysio_splay(key, rootp, compar) == 0 ? *rootp : NULL;
 }
 
 /*
@@ -169,7 +169,7 @@ _sysio_tree_delete(const void *key,
 	if (!(*rootp)->tn_left)
 		*rootp = (*rootp)->tn_right;
 	else {
-		splay((*rootp)->tn_key, &(*rootp)->tn_left, compar);
+		_sysio_splay((*rootp)->tn_key, &(*rootp)->tn_left, compar);
 		(*rootp)->tn_left->tn_right = (*rootp)->tn_right;
 		*rootp = (*rootp)->tn_left;
 	}