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);
|
