[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;
 }