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

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

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

Modified Files:
	inode.c mount.c 
Log Message:


The children of a directory are now maintained as a tree, instead of
as a list.

Along with this, the nasty resursive implementation of pb_prune is
now a de-recursed implementation.

This method is 1 to 1.5 percent slower than the previous list implementation
in my tests.


Index: inode.c
===================================================================
RCS file: /cvsroot/libsysio/libsysio/src/inode.c,v
retrieving revision 1.57
retrieving revision 1.58
diff -u -w -b -B -p -r1.57 -r1.58
--- inode.c	17 Aug 2009 23:00:20 -0000	1.57
+++ inode.c	31 Aug 2009 21:38:29 -0000	1.58
@@ -347,7 +347,7 @@ p_reclaim_debug()
 	while ((pb = nxt)) {
 		nxt = pb->pb_links.tqe_next;
 		npb++;
-		if (!pb->pb_children.lh_first)
+		if (!pb->pb_children)
 			npbleaves++;
 		else if (!pb->pb_aliases.lh_first)
 			npborphans++;
@@ -386,7 +386,7 @@ p_reclaim(unsigned limit)
 			P_UNLOCK(pno);
 			continue;
 		}
-		if (pno->p_base->pb_children.lh_first) {
+		if (pno->p_base->pb_children) {
 			/*
 			 * Must not dismiss from interior nodes. There
 			 * might be aliases on the child pointing
@@ -399,7 +399,7 @@ p_reclaim(unsigned limit)
 		PB_LOCK(pno->p_base);
 		pb = pno->p_base;
 		_sysio_p_gone(pno);
-		if (!(pb->pb_children.lh_first || pb->pb_aliases.lh_first))
+		if (!(pb->pb_children || pb->pb_aliases.lh_first))
 			_sysio_pb_gone(pb);
 		else
 			PB_UNLOCK(pb);
@@ -486,6 +486,22 @@ ncache_lookup(struct pnode_base *pb, str
 }
 
 /*
+ * Compare two addresses.
+ */
+static int
+compar_addr(const void *a, const void *b)
+{
+	ptrdiff_t diff;
+
+	diff = (char *)a - (char *)b;
+	if (diff < 0)
+		return -1;
+	if (diff > 0)
+		return 1;
+	return 0;
+}
+
+/*
  * Allocate and initialize a new base path node.
  */
 struct pnode_base *
@@ -525,7 +541,12 @@ _sysio_pb_new(struct qstr *name, struct 
 			TAILQ_REMOVE(&pb_leaf_nodes, parent, pb_links);
 		}
 #endif
-		LIST_INSERT_HEAD(&parent->pb_children, pb, pb_sibs);
+		if (_sysio_tree_search(&pb->pb_sib,
+				       &pb->pb_key.pbk_parent->pb_children,
+				       (int (*)(const void *,
+				       		const void *))compar_addr) !=
+		    &pb->pb_sib)
+			abort();			/* can't happen */
 	}
 	if (pb->pb_key.pbk_name.len) {
 		char	*cp;
@@ -565,18 +586,23 @@ _sysio_pb_gone(struct pnode_base *pb)
 	n_names--;
 
 	assert(!pb->pb_aliases.lh_first);
-	assert(!pb->pb_children.lh_first);
+	assert(!pb->pb_children);
 
 	if (pb->pb_key.pbk_name.len)
 		ncache_delete(pb);
 	if (pb->pb_key.pbk_parent) {
-		LIST_REMOVE(pb, pb_sibs);
+		if (_sysio_tree_delete(pb,
+				       &pb->pb_key.pbk_parent->pb_children,
+				       (int (*)(const void *,
+				       		const void *))compar_addr) !=
+		    &pb->pb_sib)
+			abort();			/* can't happen */
 #if defined(PB_DEBUG)
 		/*
 		 * If we just removed the last child, put the parent on
 		 * the list of leaves.
 		 */
-		if (!pb->pb_key.pbk_parent->pb_children.lh_first) {
+		if (!pb->pb_key.pbk_parent->pb_children) {
 			TAILQ_INSERT_TAIL(&pb_leaf_nodes,
 					  pb->pb_key.pbk_parent,
 					  pb_links);
@@ -1056,6 +1082,7 @@ p_remove_aliases(struct mount *mnt, stru
 	return count;
 }
 
+#if 0
 static size_t
 pb_prune(struct mount *mnt, struct pnode_base *pb)
 {
@@ -1080,6 +1108,70 @@ pb_prune(struct mount *mnt, struct pnode
 		PB_UNLOCK(pb);
 	return count;
 }
+#endif
+
+static size_t
+pb_prune(struct mount *mnt, struct pnode_base *pb)
+{
+	size_t	count;
+	struct pnode_base *stop, *parent;
+	struct tree_node *tn_next;
+
+	count = 0;
+	stop = parent = pb->pb_key.pbk_parent;
+	do {
+		/*
+		 * Just descended into this node.
+		 */
+		while (pb->pb_children) {
+			_sysio_splay(NULL,
+				     &pb->pb_children,
+				     (int  (*)(const void *,
+					       const void *))compar_addr);
+			parent = pb;
+			pb =
+			    TREE_ENTRY(parent->pb_children,
+				       pnode_base,
+				       pb_sib);
+		}
+		/*
+		 * No children.
+		 */
+		for (;;) {
+			count += p_remove_aliases(mnt, pb);
+			tn_next = pb->pb_sib.tn_right;
+			if (tn_next) {
+				_sysio_splay(NULL,
+					     &pb->pb_sib.tn_right,
+					     (int  (*)(const void *,
+						       const void *))compar_addr);
+				tn_next = pb->pb_sib.tn_right;
+			}
+			if (!(pb->pb_children || pb->pb_aliases.lh_first)) {
+				PB_LOCK(pb);
+				_sysio_pb_gone(pb);
+			}
+			if (!tn_next) {
+				/*
+				 * Ascend.
+				 */
+				pb = parent;
+				if (pb == stop)
+					break;
+				parent = pb->pb_key.pbk_parent;
+				continue;
+			}
+			pb = TREE_ENTRY(tn_next, pnode_base, pb_sib);
+			_sysio_splay(pb,
+				     &parent->pb_children,
+				     (int  (*)(const void *,
+					       const void *))compar_addr);
+			break;
+		}
+	} while (pb != stop);
+
+	return count;
+}
 
 /*
  * Prune idle nodes from the passed sub-tree, including the root.

Index: mount.c
===================================================================
RCS file: /cvsroot/libsysio/libsysio/src/mount.c,v
retrieving revision 1.32
retrieving revision 1.33
diff -u -w -b -B -p -r1.32 -r1.33
--- mount.c	6 Dec 2008 21:56:25 -0000	1.32
+++ mount.c	31 Aug 2009 21:38:29 -0000	1.33
@@ -282,7 +282,7 @@ _sysio_do_unmount(struct mount *mnt)
 	rootpb = root->p_base;
 	PB_LOCK(rootpb);
 	_sysio_p_gone(root);
-	if (!(rootpb->pb_aliases.lh_first || rootpb->pb_children.lh_first))
+	if (!(rootpb->pb_aliases.lh_first || rootpb->pb_children))
 		_sysio_pb_gone(rootpb);
 	else
 		PB_UNLOCK(rootpb);