* --------------------------------------------------------------------- */
#include <sys/dirent.h>
#include <sys/mount.h>
-#include <sys/queue.h>
+#include <sys/tree.h>
#include <sys/vnode.h>
#include <sys/file.h>
#include <sys/lock.h>
* Internal representation of a tmpfs directory entry.
*/
struct tmpfs_dirent {
- TAILQ_ENTRY(tmpfs_dirent) td_entries;
+ RB_ENTRY(tmpfs_dirent) rb_node;
/* Length of the name stored in this directory entry. This avoids
* the need to recalculate it every time the name is used. */
struct tmpfs_node * td_node;
};
-/* A directory in tmpfs holds a sorted list of directory entries, which in
+struct tmpfs_dirtree;
+RB_HEAD(tmpfs_dirtree, tmpfs_dirent);
+RB_PROTOTYPE(tmpfs_dirtree, tmpfs_dirent, rb_node,
+ tmpfs_dirtree_compare);
+
+
+/* A directory in tmpfs holds a set of directory entries, which in
* turn point to other files (which can be directories themselves).
*
- * In tmpfs, this list is managed by a tail queue, whose head is defined by
- * the struct tmpfs_dir type.
+ * In tmpfs, this set is managed by a red-black tree, whose root is defined
+ * by the struct tmpfs_dirtree type.
*
- * It is imporant to notice that directories do not have entries for . and
+ * It is important to notice that directories do not have entries for . and
* .. as other file systems do. These can be generated when requested
* based on information available by other means, such as the pointer to
* the node itself in the former case or the pointer to the parent directory
* in the latter case. This is done to simplify tmpfs's code and, more
* importantly, to remove redundancy. */
-TAILQ_HEAD(tmpfs_dir, tmpfs_dirent);
/* Each entry in a directory has a cookie that identifies it. Cookies
* supersede offsets within directories because, given how tmpfs stores
* this property identifies the root node. */
struct tmpfs_node * tn_parent;
- /* Head of a tail-queue that links the contents of
+ /* Root of a red-black tree that links the contents of
* the directory together. See above for a
* description of its contents. */
- struct tmpfs_dir tn_dirhead;
+ struct tmpfs_dirtree tn_dirtree;
/* Number and pointer of the first directory entry
* returned by the readdir operation if it were
#include <vfs/tmpfs/tmpfs_vnops.h>
static ino_t tmpfs_fetch_ino(struct tmpfs_mount *);
+static int tmpfs_dirtree_compare(struct tmpfs_dirent *a,
+ struct tmpfs_dirent *b);
+
+RB_GENERATE(tmpfs_dirtree, tmpfs_dirent, rb_node, tmpfs_dirtree_compare);
+
/* --------------------------------------------------------------------- */
break;
case VDIR:
- TAILQ_INIT(&nnode->tn_dir.tn_dirhead);
+ RB_INIT(&nnode->tn_dir.tn_dirtree);
KKASSERT(parent != nnode);
KKASSERT(IMPLIES(parent == NULL, tmp->tm_root == NULL));
nnode->tn_dir.tn_parent = parent;
tmpfs_dir_attach(struct tmpfs_node *dnode, struct tmpfs_dirent *de)
{
TMPFS_NODE_LOCK(dnode);
- TAILQ_INSERT_TAIL(&dnode->tn_dir.tn_dirhead, de, td_entries);
+ RB_INSERT(tmpfs_dirtree, &dnode->tn_dir.tn_dirtree, de);
TMPFS_ASSERT_ELOCKED(dnode);
dnode->tn_size += sizeof(struct tmpfs_dirent);
dnode->tn_dir.tn_readdir_lastn = 0;
dnode->tn_dir.tn_readdir_lastp = NULL;
}
- TAILQ_REMOVE(&dnode->tn_dir.tn_dirhead, de, td_entries);
+ RB_REMOVE(tmpfs_dirtree, &dnode->tn_dir.tn_dirtree, de);
TMPFS_ASSERT_ELOCKED(dnode);
dnode->tn_size -= sizeof(struct tmpfs_dirent);
{
struct tmpfs_dirent *de;
int len = ncp->nc_nlen;
+ struct tmpfs_dirent wanted;
+
+ wanted.td_namelen = len;
+ wanted.td_name = ncp->nc_name;
TMPFS_VALIDATE_DIR(node);
- TAILQ_FOREACH(de, &node->tn_dir.tn_dirhead, td_entries) {
- if (f != NULL && de->td_node != f)
- continue;
- if (len == de->td_namelen) {
- if (!memcmp(ncp->nc_name, de->td_name, len))
- break;
- }
- }
+ de = RB_FIND(tmpfs_dirtree, &node->tn_dir.tn_dirtree, &wanted);
+
+ KKASSERT(f == NULL || f == de->td_node);
TMPFS_NODE_LOCK(node);
node->tn_status |= TMPFS_NODE_ACCESSED;
if (error == 0) {
struct tmpfs_dirent *de;
- de = TAILQ_FIRST(&node->tn_dir.tn_dirhead);
+ de = RB_MIN(tmpfs_dirtree, &node->tn_dir.tn_dirtree);
if (de == NULL)
uio->uio_offset = TMPFS_DIRCOOKIE_EOF;
else
return node->tn_dir.tn_readdir_lastp;
}
- TAILQ_FOREACH(de, &node->tn_dir.tn_dirhead, td_entries) {
+ RB_FOREACH(de, tmpfs_dirtree, &node->tn_dir.tn_dirtree) {
if (tmpfs_dircookie(de) == cookie) {
break;
}
error = uiomove((caddr_t)&d, reclen, uio);
(*cntp)++;
- de = TAILQ_NEXT(de, td_entries);
+ de = RB_NEXT(tmpfs_dirtree, node->tn_dir.tn_dirtree, de);
} while (error == 0 && uio->uio_resid > 0 && de != NULL);
/* Update the offset and cache. */
return (ret);
}
+
+static int
+tmpfs_dirtree_compare(struct tmpfs_dirent *a, struct tmpfs_dirent *b)
+{
+ if (a->td_namelen > b->td_namelen)
+ return 1;
+ else if (a->td_namelen < b->td_namelen)
+ return -1;
+ else
+ return strncmp(a->td_name, b->td_name, a->td_namelen);
+}
if (node->tn_type == VDIR) {
struct tmpfs_dirent *de;
- while (!TAILQ_EMPTY(&node->tn_dir.tn_dirhead)) {
- de = TAILQ_FIRST(&node->tn_dir.tn_dirhead);
+ while (!RB_EMPTY(&node->tn_dir.tn_dirtree)) {
+ de = RB_FIRST(tmpfs_dirtree, &node->tn_dir.tn_dirtree);
tmpfs_dir_detach(node, de);
tmpfs_free_dirent(tmp, de);
node->tn_size -= sizeof(struct tmpfs_dirent);
struct vnode *tdvp = v->a_tdvp;
struct namecache *tncp = v->a_tnch->ncp;
struct vnode *tvp;
- struct tmpfs_dirent *de;
+ struct tmpfs_dirent *de, *tde;
struct tmpfs_mount *tmp;
struct tmpfs_node *fdnode;
struct tmpfs_node *fnode;
*/
if (fdnode != tdnode)
tmpfs_dir_detach(fdnode, de);
+ else {
+ RB_REMOVE(tmpfs_dirtree, &fdnode->tn_dir.tn_dirtree, de);
+ }
/*
* Handle any name change. Swap with newname, we will
}
/*
+ * If we are overwriting an entry, we have to remove the old one
+ * from the target directory.
+ */
+ if (tvp != NULL) {
+ /* Remove the old entry from the target directory. */
+ tde = tmpfs_dir_lookup(tdnode, tnode, tncp);
+ tmpfs_dir_detach(tdnode, tde);
+ tmpfs_knote(tdnode->tn_vnode, NOTE_DELETE);
+
+ /*
+ * Free the directory entry we just deleted. Note that the
+ * node referred by it will not be removed until the vnode is
+ * really reclaimed.
+ */
+ tmpfs_free_dirent(VFS_TO_TMPFS(tvp->v_mount), tde);
+ /*cache_inval_vp(tvp, CINV_DESTROY);*/
+ }
+
+ /*
* Link entry to target directory. If the entry
* represents a directory move the parent linkage
* as well.
} else {
TMPFS_NODE_LOCK(tdnode);
tdnode->tn_status |= TMPFS_NODE_MODIFIED;
+ RB_INSERT(tmpfs_dirtree, &tdnode->tn_dir.tn_dirtree, de);
TMPFS_NODE_UNLOCK(tdnode);
}
/*
- * If we are overwriting an entry, we have to remove the old one
- * from the target directory.
- */
- if (tvp != NULL) {
- /* Remove the old entry from the target directory. */
- de = tmpfs_dir_lookup(tdnode, tnode, tncp);
- tmpfs_dir_detach(tdnode, de);
- tmpfs_knote(tdnode->tn_vnode, NOTE_DELETE);
-
- /*
- * Free the directory entry we just deleted. Note that the
- * node referred by it will not be removed until the vnode is
- * really reclaimed.
- */
- tmpfs_free_dirent(VFS_TO_TMPFS(tvp->v_mount), de);
- /*cache_inval_vp(tvp, CINV_DESTROY);*/
- }
-
- /*
* Finish up
*/
if (newname) {
off = TMPFS_DIRCOOKIE_DOTDOT;
} else {
if (off == TMPFS_DIRCOOKIE_DOTDOT) {
- de = TAILQ_FIRST(&node->tn_dir.tn_dirhead);
+ de = RB_MIN(tmpfs_dirtree, &node->tn_dir.tn_dirtree);
} else if (de != NULL) {
- de = TAILQ_NEXT(de, td_entries);
+ de = RB_NEXT(tmpfs_dirtree, &node->tn_dir.tn_dirtree, de);
} else {
de = tmpfs_dir_lookupbycookie(node,
off);
KKASSERT(de != NULL);
- de = TAILQ_NEXT(de, td_entries);
+ de = RB_NEXT(tmpfs_dirtree, &node->tn_dir.tn_dirtree, de);
}
if (de == NULL)
off = TMPFS_DIRCOOKIE_EOF;
projects / dragonfly.git / commitdiff