From: Darrick J. Wong <darrick.wong@xxxxxxxxxx>
xfs_scrub will make use of the avl64 code, so promote it out of repair
and into libfrog.
Signed-off-by: Darrick J. Wong <darrick.wong@xxxxxxxxxx>
---
include/avl64.h | 133 +++++
libfrog/Makefile | 1
libfrog/avl64.c | 1418 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
repair/Makefile | 4
repair/avl64.c | 1418 ------------------------------------------------------
repair/avl64.h | 133 -----
6 files changed, 1554 insertions(+), 1553 deletions(-)
create mode 100644 include/avl64.h
create mode 100644 libfrog/avl64.c
delete mode 100644 repair/avl64.c
delete mode 100644 repair/avl64.h
diff --git a/include/avl64.h b/include/avl64.h
new file mode 100644
index 0000000..cd079a0
--- /dev/null
+++ b/include/avl64.h
@@ -0,0 +1,133 @@
+/*
+ * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
+ * All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it would be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+#ifndef __XR_AVL64_H__
+#define __XR_AVL64_H__
+
+#include <sys/types.h>
+
+typedef struct avl64node {
+ struct avl64node *avl_forw; /* pointer to right child (> parent) */
+ struct avl64node *avl_back; /* pointer to left child (< parent) */
+ struct avl64node *avl_parent; /* parent pointer */
+ struct avl64node *avl_nextino; /* next in-order; NULL terminated list*/
+ char avl_balance; /* tree balance */
+} avl64node_t;
+
+/*
+ * avl-tree operations
+ */
+typedef struct avl64ops {
+ uint64_t (*avl_start)(avl64node_t *);
+ uint64_t (*avl_end)(avl64node_t *);
+} avl64ops_t;
+
+/*
+ * avoid complaints about multiple def's since these are only used by
+ * the avl code internally
+ */
+#ifndef AVL_START
+#define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n)
+#define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n)
+#endif
+
+/*
+ * tree descriptor:
+ * root points to the root of the tree.
+ * firstino points to the first in the ordered list.
+ */
+typedef struct avl64tree_desc {
+ avl64node_t *avl_root;
+ avl64node_t *avl_firstino;
+ avl64ops_t *avl_ops;
+} avl64tree_desc_t;
+
+/* possible values for avl_balance */
+
+#define AVL_BACK 1
+#define AVL_BALANCE 0
+#define AVL_FORW 2
+
+/*
+ * 'Exported' avl tree routines
+ */
+avl64node_t
+*avl64_insert(
+ avl64tree_desc_t *tree,
+ avl64node_t *newnode);
+
+void
+avl64_delete(
+ avl64tree_desc_t *tree,
+ avl64node_t *np);
+
+void
+avl64_insert_immediate(
+ avl64tree_desc_t *tree,
+ avl64node_t *afterp,
+ avl64node_t *newnode);
+
+void
+avl64_init_tree(
+ avl64tree_desc_t *tree,
+ avl64ops_t *ops);
+
+avl64node_t *
+avl64_findrange(
+ avl64tree_desc_t *tree,
+ uint64_t value);
+
+avl64node_t *
+avl64_find(
+ avl64tree_desc_t *tree,
+ uint64_t value);
+
+avl64node_t *
+avl64_findanyrange(
+ avl64tree_desc_t *tree,
+ uint64_t start,
+ uint64_t end,
+ int checklen);
+
+
+avl64node_t *
+avl64_findadjacent(
+ avl64tree_desc_t *tree,
+ uint64_t value,
+ int dir);
+
+void
+avl64_findranges(
+ avl64tree_desc_t *tree,
+ uint64_t start,
+ uint64_t end,
+ avl64node_t **startp,
+ avl64node_t **endp);
+
+/*
+ * avoid complaints about multiple def's since these are only used by
+ * the avl code internally
+ */
+#ifndef AVL_PRECEED
+#define AVL_PRECEED 0x1
+#define AVL_SUCCEED 0x2
+
+#define AVL_INCLUDE_ZEROLEN 0x0000
+#define AVL_EXCLUDE_ZEROLEN 0x0001
+#endif
+
+#endif /* __XR_AVL64_H__ */
diff --git a/libfrog/Makefile b/libfrog/Makefile
index 6034da5..3fd42a4 100644
--- a/libfrog/Makefile
+++ b/libfrog/Makefile
@@ -11,6 +11,7 @@ LT_REVISION = 0
LT_AGE = 0
CFILES = \
+avl64.c \
list_sort.c \
radix-tree.c \
util.c
diff --git a/libfrog/avl64.c b/libfrog/avl64.c
new file mode 100644
index 0000000..01cfee4
--- /dev/null
+++ b/libfrog/avl64.c
@@ -0,0 +1,1418 @@
+/*
+ * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
+ * All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it would be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+#include <stdint.h>
+#include <stdio.h>
+#include "platform_defs.h"
+#include "avl64.h"
+
+#define CERT ASSERT
+
+#ifdef AVL_DEBUG
+
+static void
+avl64_checknode(
+ avl64tree_desc_t *tree,
+ avl64node_t *np)
+{
+ avl64node_t *back = np->avl_back;
+ avl64node_t *forw = np->avl_forw;
+ avl64node_t *nextino = np->avl_nextino;
+ int bal = np->avl_balance;
+
+ ASSERT(bal != AVL_BALANCE || (!back && !forw) || (back && forw));
+ ASSERT(bal != AVL_FORW || forw);
+ ASSERT(bal != AVL_BACK || back);
+
+ if (forw) {
+ ASSERT(AVL_START(tree, np) < AVL_START(tree, forw));
+ ASSERT(np->avl_forw->avl_parent == np);
+ ASSERT(back || bal == AVL_FORW);
+ } else {
+ ASSERT(bal != AVL_FORW);
+ ASSERT(bal == AVL_BALANCE || back);
+ ASSERT(bal == AVL_BACK || !back);
+ }
+
+ if (back) {
+ ASSERT(AVL_START(tree, np) > AVL_START(tree, back));
+ ASSERT(np->avl_back->avl_parent == np);
+ ASSERT(forw || bal == AVL_BACK);
+ } else {
+ ASSERT(bal != AVL_BACK);
+ ASSERT(bal == AVL_BALANCE || forw);
+ ASSERT(bal == AVL_FORW || !forw);
+ }
+
+ if (nextino == NULL)
+ ASSERT(forw == NULL);
+ else
+ ASSERT(AVL_END(tree, np) <= AVL_START(tree, nextino));
+}
+
+static void
+avl64_checktree(
+ avl64tree_desc_t *tree,
+ avl64node_t *root)
+{
+ avl64node_t *nlast, *nnext, *np;
+ uint64_t offset = 0;
+ uint64_t end;
+
+ nlast = nnext = root;
+
+ ASSERT(!nnext || nnext->avl_parent == NULL);
+
+ while (nnext) {
+
+ avl64_checknode(tree, nnext);
+ end = AVL_END(tree, nnext);
+
+ if (end <= offset) {
+ if ((np = nnext->avl_forw) && np != nlast) {
+ nlast = nnext;
+ nnext = np;
+ } else {
+ nlast = nnext;
+ nnext = nnext->avl_parent;
+ }
+ continue;
+ }
+
+ nlast = nnext;
+ if (np = nnext->avl_back) {
+ if (AVL_END(tree, np) > offset) {
+ nnext = np;
+ continue;
+ }
+ }
+
+ np = nnext;
+ nnext = nnext->avl_forw;
+ if (!nnext)
+ nnext = np->avl_parent;
+
+ offset = end;
+ }
+}
+#else /* ! AVL_DEBUG */
+#define avl64_checktree(t,x)
+#endif /* AVL_DEBUG */
+
+
+/*
+ * Reset balance for np up through tree.
+ * ``direction'' is the way that np's balance
+ * is headed after the deletion of one of its children --
+ * e.g., deleting a avl_forw child sends avl_balance toward AVL_BACK.
+ * Called only when deleting a node from the tree.
+ */
+static void
+retreat(
+ avl64tree_desc_t *tree,
+ avl64node_t *np,
+ int direction)
+{
+ avl64node_t **rootp = &tree->avl_root;
+ avl64node_t *parent;
+ avl64node_t *child;
+ avl64node_t *tmp;
+ int bal;
+
+ do {
+ ASSERT(direction == AVL_BACK || direction == AVL_FORW);
+
+ if (np->avl_balance == AVL_BALANCE) {
+ np->avl_balance = direction;
+ return;
+ }
+
+ parent = np->avl_parent;
+
+ /*
+ * If balance is being restored, no local node
+ * reorganization is necessary, but may be at
+ * a higher node. Reset direction and continue.
+ */
+ if (direction != np->avl_balance) {
+ np->avl_balance = AVL_BALANCE;
+ if (parent) {
+ if (parent->avl_forw == np)
+ direction = AVL_BACK;
+ else
+ direction = AVL_FORW;
+
+ np = parent;
+ continue;
+ }
+ return;
+ }
+
+ /*
+ * Imbalance. If a avl_forw node was removed, direction
+ * (and, by reduction, np->avl_balance) is/was AVL_BACK.
+ */
+ if (np->avl_balance == AVL_BACK) {
+
+ ASSERT(direction == AVL_BACK);
+ child = np->avl_back;
+ bal = child->avl_balance;
+
+ if (bal != AVL_FORW) /* single LL */ {
+ /*
+ * np gets pushed down to lesser child's
+ * avl_forw branch.
+ *
+ * np-> -D +B
+ * / \ / \
+ * child-> B deleted A -D
+ * / \ /
+ * A C C
+ cmn_err(CE_CONT, "!LL delete b 0x%x c 0x%x\n",
+ np, child);
+ */
+
+ np->avl_back = child->avl_forw;
+ if (child->avl_forw)
+ child->avl_forw->avl_parent = np;
+ child->avl_forw = np;
+
+ if (parent) {
+ if (parent->avl_forw == np) {
+ parent->avl_forw = child;
+ direction = AVL_BACK;
+ } else {
+ ASSERT(parent->avl_back == np);
+ parent->avl_back = child;
+ direction = AVL_FORW;
+ }
+ } else {
+ ASSERT(*rootp == np);
+ *rootp = child;
+ }
+ np->avl_parent = child;
+ child->avl_parent = parent;
+
+ if (bal == AVL_BALANCE) {
+ np->avl_balance = AVL_BACK;
+ child->avl_balance = AVL_FORW;
+ return;
+ } else {
+ np->avl_balance = AVL_BALANCE;
+ child->avl_balance = AVL_BALANCE;
+ np = parent;
+ avl64_checktree(tree, *rootp);
+ continue;
+ }
+ }
+
+ /* child->avl_balance == AVL_FORW double LR rotation
+ *
+ * child's avl_forw node gets promoted up, along with
+ * its avl_forw subtree
+ *
+ * np-> -G C
+ * / \ / \
+ * child-> +B H -B G
+ * / \ \ / / \
+ * A +C deleted A D H
+ * \
+ * D
+ cmn_err(CE_CONT, "!LR delete b 0x%x c 0x%x t 0x%x\n",
+ np, child, child->avl_forw);
+ */
+
+ tmp = child->avl_forw;
+ bal = tmp->avl_balance;
+
+ child->avl_forw = tmp->avl_back;
+ if (tmp->avl_back)
+ tmp->avl_back->avl_parent = child;
+
+ tmp->avl_back = child;
+ child->avl_parent = tmp;
+
+ np->avl_back = tmp->avl_forw;
+ if (tmp->avl_forw)
+ tmp->avl_forw->avl_parent = np;
+ tmp->avl_forw = np;
+
+ if (bal == AVL_FORW)
+ child->avl_balance = AVL_BACK;
+ else
+ child->avl_balance = AVL_BALANCE;
+
+ if (bal == AVL_BACK)
+ np->avl_balance = AVL_FORW;
+ else
+ np->avl_balance = AVL_BALANCE;
+
+ goto next;
+ }
+
+ ASSERT(np->avl_balance == AVL_FORW && direction == AVL_FORW);
+
+ child = np->avl_forw;
+ bal = child->avl_balance;
+
+ if (bal != AVL_BACK) /* single RR */ {
+ /*
+ * np gets pushed down to greater child's
+ * avl_back branch.
+ *
+ * np-> +B -D
+ * / \ / \
+ * deleted D <-child +B E
+ * / \ \
+ * C E C
+ cmn_err(CE_CONT, "!RR delete b 0x%x c 0x%x\n",
+ np, child);
+ */
+
+ np->avl_forw = child->avl_back;
+ if (child->avl_back)
+ child->avl_back->avl_parent = np;
+ child->avl_back = np;
+
+ if (parent) {
+ if (parent->avl_forw == np) {
+ parent->avl_forw = child;
+ direction = AVL_BACK;
+ } else {
+ ASSERT(parent->avl_back == np);
+ parent->avl_back = child;
+ direction = AVL_FORW;
+ }
+ } else {
+ ASSERT(*rootp == np);
+ *rootp = child;
+ }
+ np->avl_parent = child;
+ child->avl_parent = parent;
+
+ if (bal == AVL_BALANCE) {
+ np->avl_balance = AVL_FORW;
+ child->avl_balance = AVL_BACK;
+ return;
+ } else {
+ np->avl_balance = AVL_BALANCE;
+ child->avl_balance = AVL_BALANCE;
+ np = parent;
+ avl64_checktree(tree, *rootp);
+ continue;
+ }
+ }
+
+ /* child->avl_balance == AVL_BACK double RL rotation
+ cmn_err(CE_CONT, "!RL delete b 0x%x c 0x%x t 0x%x\n",
+ np, child, child->avl_back);
+ */
+
+ tmp = child->avl_back;
+ bal = tmp->avl_balance;
+
+ child->avl_back = tmp->avl_forw;
+ if (tmp->avl_forw)
+ tmp->avl_forw->avl_parent = child;
+
+ tmp->avl_forw = child;
+ child->avl_parent = tmp;
+
+ np->avl_forw = tmp->avl_back;
+ if (tmp->avl_back)
+ tmp->avl_back->avl_parent = np;
+ tmp->avl_back = np;
+
+ if (bal == AVL_BACK)
+ child->avl_balance = AVL_FORW;
+ else
+ child->avl_balance = AVL_BALANCE;
+
+ if (bal == AVL_FORW)
+ np->avl_balance = AVL_BACK;
+ else
+ np->avl_balance = AVL_BALANCE;
+next:
+ np->avl_parent = tmp;
+ tmp->avl_balance = AVL_BALANCE;
+ tmp->avl_parent = parent;
+
+ if (parent) {
+ if (parent->avl_forw == np) {
+ parent->avl_forw = tmp;
+ direction = AVL_BACK;
+ } else {
+ ASSERT(parent->avl_back == np);
+ parent->avl_back = tmp;
+ direction = AVL_FORW;
+ }
+ } else {
+ ASSERT(*rootp == np);
+ *rootp = tmp;
+ return;
+ }
+
+ np = parent;
+ avl64_checktree(tree, *rootp);
+ } while (np);
+}
+
+/*
+ * Remove node from tree.
+ * avl_delete does the local tree manipulations,
+ * calls retreat() to rebalance tree up to its root.
+ */
+void
+avl64_delete(
+ avl64tree_desc_t *tree,
+ avl64node_t *np)
+{
+ avl64node_t *forw = np->avl_forw;
+ avl64node_t *back = np->avl_back;
+ avl64node_t *parent = np->avl_parent;
+ avl64node_t *nnext;
+
+
+ if (np->avl_back) {
+ /*
+ * a left child exits, then greatest left descendent's nextino
+ * is pointing to np; make it point to np->nextino.
+ */
+ nnext = np->avl_back;
+ while (nnext) {
+ if (!nnext->avl_forw)
+ break; /* can't find anything bigger */
+ nnext = nnext->avl_forw;
+ }
+ } else
+ if (np->avl_parent) {
+ /*
+ * find nearest ancestor with lesser value. That ancestor's
+ * nextino is pointing to np; make it point to np->nextino
+ */
+ nnext = np->avl_parent;
+ while (nnext) {
+ if (AVL_END(tree, nnext) <= AVL_END(tree, np))
+ break;
+ nnext = nnext->avl_parent;
+ }
+ } else
+ nnext = NULL;
+
+ if (nnext) {
+ ASSERT(nnext->avl_nextino == np);
+ nnext->avl_nextino = np->avl_nextino;
+ /*
+ * Something preceeds np; np cannot be firstino.
+ */
+ ASSERT(tree->avl_firstino != np);
+ }
+ else {
+ /*
+ * Nothing preceeding np; after deletion, np's nextino
+ * is firstino of tree.
+ */
+ ASSERT(tree->avl_firstino == np);
+ tree->avl_firstino = np->avl_nextino;
+ }
+
+
+ /*
+ * Degenerate cases...
+ */
+ if (forw == NULL) {
+ forw = back;
+ goto attach;
+ }
+
+ if (back == NULL) {
+attach:
+ if (forw)
+ forw->avl_parent = parent;
+ if (parent) {
+ if (parent->avl_forw == np) {
+ parent->avl_forw = forw;
+ retreat(tree, parent, AVL_BACK);
+ } else {
+ ASSERT(parent->avl_back == np);
+ parent->avl_back = forw;
+ retreat(tree, parent, AVL_FORW);
+ }
+ } else {
+ ASSERT(tree->avl_root == np);
+ tree->avl_root = forw;
+ }
+ avl64_checktree(tree, tree->avl_root);
+ return;
+ }
+
+ /*
+ * Harder case: children on both sides.
+ * If back's avl_forw pointer is null, just have back
+ * inherit np's avl_forw tree, remove np from the tree
+ * and adjust balance counters starting at back.
+ *
+ * np-> xI xH (befor retreat())
+ * / \ / \
+ * back-> H J G J
+ * / / \ / \
+ * G ? ? ? ?
+ * / \
+ * ? ?
+ */
+ if ((forw = back->avl_forw) == NULL) {
+ /*
+ * AVL_FORW retreat below will set back's
+ * balance to AVL_BACK.
+ */
+ back->avl_balance = np->avl_balance;
+ back->avl_forw = forw = np->avl_forw;
+ forw->avl_parent = back;
+ back->avl_parent = parent;
+
+ if (parent) {
+ if (parent->avl_forw == np)
+ parent->avl_forw = back;
+ else {
+ ASSERT(parent->avl_back == np);
+ parent->avl_back = back;
+ }
+ } else {
+ ASSERT(tree->avl_root == np);
+ tree->avl_root = back;
+ }
+
+ /*
+ * back is taking np's place in the tree, and
+ * has therefore lost a avl_back node (itself).
+ */
+ retreat(tree, back, AVL_FORW);
+ avl64_checktree(tree, tree->avl_root);
+ return;
+ }
+
+ /*
+ * Hardest case: children on both sides, and back's
+ * avl_forw pointer isn't null. Find the immediately
+ * inferior buffer by following back's avl_forw line
+ * to the end, then have it inherit np's avl_forw tree.
+ *
+ * np-> xI xH
+ * / \ / \
+ * G J back-> G J (before retreat())
+ * / \ / \
+ * F ?... F ?1
+ * / \
+ * ? H <-forw
+ * /
+ * ?1
+ */
+ while ((back = forw->avl_forw))
+ forw = back;
+
+ /*
+ * Will be adjusted by retreat() below.
+ */
+ forw->avl_balance = np->avl_balance;
+
+ /*
+ * forw inherits np's avl_forw...
+ */
+ forw->avl_forw = np->avl_forw;
+ np->avl_forw->avl_parent = forw;
+
+ /*
+ * ... forw's parent gets forw's avl_back...
+ */
+ back = forw->avl_parent;
+ back->avl_forw = forw->avl_back;
+ if (forw->avl_back)
+ forw->avl_back->avl_parent = back;
+
+ /*
+ * ... forw gets np's avl_back...
+ */
+ forw->avl_back = np->avl_back;
+ np->avl_back->avl_parent = forw;
+
+ /*
+ * ... and forw gets np's parent.
+ */
+ forw->avl_parent = parent;
+
+ if (parent) {
+ if (parent->avl_forw == np)
+ parent->avl_forw = forw;
+ else
+ parent->avl_back = forw;
+ } else {
+ ASSERT(tree->avl_root == np);
+ tree->avl_root = forw;
+ }
+
+ /*
+ * What used to be forw's parent is the starting
+ * point for rebalancing. It has lost a avl_forw node.
+ */
+ retreat(tree, back, AVL_BACK);
+ avl64_checktree(tree, tree->avl_root);
+}
+
+
+/*
+ * avl_findanyrange:
+ *
+ * Given range r [start, end), find any range which is contained in r.
+ * if checklen is non-zero, then only ranges of non-zero length are
+ * considered in finding a match.
+ */
+avl64node_t *
+avl64_findanyrange(
+ avl64tree_desc_t *tree,
+ uint64_t start,
+ uint64_t end,
+ int checklen)
+{
+ avl64node_t *np = tree->avl_root;
+
+ /* np = avl64_findadjacent(tree, start, AVL_SUCCEED); */
+ while (np) {
+ if (start < AVL_START(tree, np)) {
+ if (np->avl_back) {
+ np = np->avl_back;
+ continue;
+ }
+ /* if we were to add node with start, would
+ * have a growth of AVL_BACK
+ */
+ /* if succeeding node is needed, this is it.
+ */
+ break;
+ }
+ if (start >= AVL_END(tree, np)) {
+ if (np->avl_forw) {
+ np = np->avl_forw;
+ continue;
+ }
+ /* if we were to add node with start, would
+ * have a growth of AVL_FORW;
+ */
+ /* we are looking for a succeeding node;
+ * this is nextino.
+ */
+ np = np->avl_nextino;
+ break;
+ }
+ /* AVL_START(tree, np) <= start < AVL_END(tree, np) */
+ break;
+ }
+ if (np) {
+ if (checklen == AVL_INCLUDE_ZEROLEN) {
+ if (end <= AVL_START(tree, np)) {
+ /* something follows start, but is
+ * is entierly after the range (end)
+ */
+ return(NULL);
+ }
+ /* np may stradle [start, end) */
+ return(np);
+ }
+ /*
+ * find non-zero length region
+ */
+ while (np && (AVL_END(tree, np) - AVL_START(tree, np) == 0)
+ && (AVL_START(tree, np) < end))
+ np = np->avl_nextino;
+
+ if ((np == NULL) || (AVL_START(tree, np) >= end))
+ return NULL;
+ return(np);
+ }
+ /*
+ * nothing succeeds start, all existing ranges are before start.
+ */
+ return NULL;
+}
+
+
+/*
+ * Returns a pointer to range which contains value.
+ */
+avl64node_t *
+avl64_findrange(
+ avl64tree_desc_t *tree,
+ uint64_t value)
+{
+ avl64node_t *np = tree->avl_root;
+
+ while (np) {
+ if (value < AVL_START(tree, np)) {
+ np = np->avl_back;
+ continue;
+ }
+ if (value >= AVL_END(tree, np)) {
+ np = np->avl_forw;
+ continue;
+ }
+ ASSERT(AVL_START(tree, np) <= value &&
+ value < AVL_END(tree, np));
+ return np;
+ }
+ return NULL;
+}
+
+
+/*
+ * Returns a pointer to node which contains exact value.
+ */
+avl64node_t *
+avl64_find(
+ avl64tree_desc_t *tree,
+ uint64_t value)
+{
+ avl64node_t *np = tree->avl_root;
+ uint64_t nvalue;
+
+ while (np) {
+ nvalue = AVL_START(tree, np);
+ if (value < nvalue) {
+ np = np->avl_back;
+ continue;
+ }
+ if (value == nvalue) {
+ return np;
+ }
+ np = np->avl_forw;
+ }
+ return NULL;
+}
+
+
+/*
+ * Balance buffer AVL tree after attaching a new node to root.
+ * Called only by avl_insert.
+ */
+static void
+avl64_balance(
+ avl64node_t **rootp,
+ avl64node_t *np,
+ int growth)
+{
+ /*
+ * At this point, np points to the node to which
+ * a new node has been attached. All that remains is to
+ * propagate avl_balance up the tree.
+ */
+ for ( ; ; ) {
+ avl64node_t *parent = np->avl_parent;
+ avl64node_t *child;
+
+ CERT(growth == AVL_BACK || growth == AVL_FORW);
+
+ /*
+ * If the buffer was already balanced, set avl_balance
+ * to the new direction. Continue if there is a
+ * parent after setting growth to reflect np's
+ * relation to its parent.
+ */
+ if (np->avl_balance == AVL_BALANCE) {
+ np->avl_balance = growth;
+ if (parent) {
+ if (parent->avl_forw == np)
+ growth = AVL_FORW;
+ else {
+ ASSERT(parent->avl_back == np);
+ growth = AVL_BACK;
+ }
+
+ np = parent;
+ continue;
+ }
+ break;
+ }
+
+ if (growth != np->avl_balance) {
+ /*
+ * Subtree is now balanced -- no net effect
+ * in the size of the subtree, so leave.
+ */
+ np->avl_balance = AVL_BALANCE;
+ break;
+ }
+
+ if (growth == AVL_BACK) {
+
+ child = np->avl_back;
+ CERT(np->avl_balance == AVL_BACK && child);
+
+ if (child->avl_balance == AVL_BACK) { /* single LL */
+ /*
+ * ``A'' just got inserted;
+ * np points to ``E'', child to ``C'',
+ * and it is already AVL_BACK --
+ * child will get promoted to top of subtree.
+
+ np-> -E C
+ / \ / \
+ child-> -C F -B E
+ / \ / / \
+ -B D A D F
+ /
+ A
+
+ Note that child->avl_parent and
+ avl_balance get set in common code.
+ */
+ np->avl_parent = child;
+ np->avl_balance = AVL_BALANCE;
+ np->avl_back = child->avl_forw;
+ if (child->avl_forw)
+ child->avl_forw->avl_parent = np;
+ child->avl_forw = np;
+ } else {
+ /*
+ * double LR
+ *
+ * child's avl_forw node gets promoted to
+ * the top of the subtree.
+
+ np-> -E C
+ / \ / \
+ child-> +B F -B E
+ / \ / / \
+ A +C A D F
+ \
+ D
+
+ */
+ avl64node_t *tmp = child->avl_forw;
+
+ CERT(child->avl_balance == AVL_FORW && tmp);
+
+ child->avl_forw = tmp->avl_back;
+ if (tmp->avl_back)
+ tmp->avl_back->avl_parent = child;
+
+ tmp->avl_back = child;
+ child->avl_parent = tmp;
+
+ np->avl_back = tmp->avl_forw;
+ if (tmp->avl_forw)
+ tmp->avl_forw->avl_parent = np;
+
+ tmp->avl_forw = np;
+ np->avl_parent = tmp;
+
+ if (tmp->avl_balance == AVL_BACK)
+ np->avl_balance = AVL_FORW;
+ else
+ np->avl_balance = AVL_BALANCE;
+
+ if (tmp->avl_balance == AVL_FORW)
+ child->avl_balance = AVL_BACK;
+ else
+ child->avl_balance = AVL_BALANCE;
+
+ /*
+ * Set child to point to tmp since it is
+ * now the top of the subtree, and will
+ * get attached to the subtree parent in
+ * the common code below.
+ */
+ child = tmp;
+ }
+
+ } else /* growth == AVL_BACK */ {
+
+ /*
+ * This code is the mirror image of AVL_FORW above.
+ */
+
+ child = np->avl_forw;
+ CERT(np->avl_balance == AVL_FORW && child);
+
+ if (child->avl_balance == AVL_FORW) { /* single RR */
+ np->avl_parent = child;
+ np->avl_balance = AVL_BALANCE;
+ np->avl_forw = child->avl_back;
+ if (child->avl_back)
+ child->avl_back->avl_parent = np;
+ child->avl_back = np;
+ } else {
+ /*
+ * double RL
+ */
+ avl64node_t *tmp = child->avl_back;
+
+ ASSERT(child->avl_balance == AVL_BACK && tmp);
+
+ child->avl_back = tmp->avl_forw;
+ if (tmp->avl_forw)
+ tmp->avl_forw->avl_parent = child;
+
+ tmp->avl_forw = child;
+ child->avl_parent = tmp;
+
+ np->avl_forw = tmp->avl_back;
+ if (tmp->avl_back)
+ tmp->avl_back->avl_parent = np;
+
+ tmp->avl_back = np;
+ np->avl_parent = tmp;
+
+ if (tmp->avl_balance == AVL_FORW)
+ np->avl_balance = AVL_BACK;
+ else
+ np->avl_balance = AVL_BALANCE;
+
+ if (tmp->avl_balance == AVL_BACK)
+ child->avl_balance = AVL_FORW;
+ else
+ child->avl_balance = AVL_BALANCE;
+
+ child = tmp;
+ }
+ }
+
+ child->avl_parent = parent;
+ child->avl_balance = AVL_BALANCE;
+
+ if (parent) {
+ if (parent->avl_back == np)
+ parent->avl_back = child;
+ else
+ parent->avl_forw = child;
+ } else {
+ ASSERT(*rootp == np);
+ *rootp = child;
+ }
+
+ break;
+ }
+}
+
+static
+avl64node_t *
+avl64_insert_find_growth(
+ avl64tree_desc_t *tree,
+ uint64_t start, /* range start at start, */
+ uint64_t end, /* exclusive */
+ int *growthp) /* OUT */
+{
+ avl64node_t *root = tree->avl_root;
+ avl64node_t *np;
+
+ np = root;
+ ASSERT(np); /* caller ensures that there is atleast one node in tree */
+
+ for ( ; ; ) {
+ CERT(np->avl_parent || root == np);
+ CERT(!np->avl_parent || root != np);
+ CERT(!(np->avl_back) || np->avl_back->avl_parent == np);
+ CERT(!(np->avl_forw) || np->avl_forw->avl_parent == np);
+ CERT(np->avl_balance != AVL_FORW || np->avl_forw);
+ CERT(np->avl_balance != AVL_BACK || np->avl_back);
+ CERT(np->avl_balance != AVL_BALANCE ||
+ np->avl_back == NULL || np->avl_forw);
+ CERT(np->avl_balance != AVL_BALANCE ||
+ np->avl_forw == NULL || np->avl_back);
+
+ if (AVL_START(tree, np) >= end) {
+ if (np->avl_back) {
+ np = np->avl_back;
+ continue;
+ }
+ *growthp = AVL_BACK;
+ break;
+ }
+
+ if (AVL_END(tree, np) <= start) {
+ if (np->avl_forw) {
+ np = np->avl_forw;
+ continue;
+ }
+ *growthp = AVL_FORW;
+ break;
+ }
+ /* found exact match -- let caller decide if it is an error */
+ return(NULL);
+ }
+ return(np);
+}
+
+
+static void
+avl64_insert_grow(
+ avl64tree_desc_t *tree,
+ avl64node_t *parent,
+ avl64node_t *newnode,
+ int growth)
+{
+ avl64node_t *nnext;
+ uint64_t start = AVL_START(tree, newnode);
+
+ if (growth == AVL_BACK) {
+
+ parent->avl_back = newnode;
+ /*
+ * we are growing to the left; previous in-order to newnode is
+ * closest ancestor with lesser value. Before this
+ * insertion, this ancestor will be pointing to
+ * newnode's parent. After insertion, next in-order to newnode
+ * is the parent.
+ */
+ newnode->avl_nextino = parent;
+ nnext = parent;
+ while (nnext) {
+ if (AVL_END(tree, nnext) <= start)
+ break;
+ nnext = nnext->avl_parent;
+ }
+ if (nnext) {
+ /*
+ * nnext will be null if newnode is
+ * the least element, and hence very first in the list.
+ */
+ ASSERT(nnext->avl_nextino == parent);
+ nnext->avl_nextino = newnode;
+ }
+ }
+ else {
+ parent->avl_forw = newnode;
+ newnode->avl_nextino = parent->avl_nextino;
+ parent->avl_nextino = newnode;
+ }
+}
+
+
+avl64node_t *
+avl64_insert(
+ avl64tree_desc_t *tree,
+ avl64node_t *newnode)
+{
+ avl64node_t *np;
+ uint64_t start = AVL_START(tree, newnode);
+ uint64_t end = AVL_END(tree, newnode);
+ int growth;
+
+ ASSERT(newnode);
+ /*
+ * Clean all pointers for sanity; some will be reset as necessary.
+ */
+ newnode->avl_nextino = NULL;
+ newnode->avl_parent = NULL;
+ newnode->avl_forw = NULL;
+ newnode->avl_back = NULL;
+ newnode->avl_balance = AVL_BALANCE;
+
+ if ((np = tree->avl_root) == NULL) { /* degenerate case... */
+ tree->avl_root = newnode;
+ tree->avl_firstino = newnode;
+ return newnode;
+ }
+
+ if ((np = avl64_insert_find_growth(tree, start, end, &growth))
+ == NULL) {
+ if (start != end) { /* non-zero length range */
+ fprintf(stderr,
+ _("avl_insert: Warning! duplicate range [%llu,%llu]\n"),
+ (unsigned long long)start,
+ (unsigned long long)end);
+ }
+ return(NULL);
+ }
+
+ avl64_insert_grow(tree, np, newnode, growth);
+ if (growth == AVL_BACK) {
+ /*
+ * Growing to left. if np was firstino, newnode will be firstino
+ */
+ if (tree->avl_firstino == np)
+ tree->avl_firstino = newnode;
+ }
+#ifdef notneeded
+ else
+ if (growth == AVL_FORW)
+ /*
+ * Cannot possibly be firstino; there is somebody to our left.
+ */
+ ;
+#endif
+
+ newnode->avl_parent = np;
+ CERT(np->avl_forw == newnode || np->avl_back == newnode);
+
+ avl64_balance(&tree->avl_root, np, growth);
+
+ avl64_checktree(tree, tree->avl_root);
+
+ return newnode;
+}
+
+/*
+ *
+ * avl64_insert_immediate(tree, afterp, newnode):
+ * insert newnode immediately into tree immediately after afterp.
+ * after insertion, newnode is right child of afterp.
+ */
+void
+avl64_insert_immediate(
+ avl64tree_desc_t *tree,
+ avl64node_t *afterp,
+ avl64node_t *newnode)
+{
+ /*
+ * Clean all pointers for sanity; some will be reset as necessary.
+ */
+ newnode->avl_nextino = NULL;
+ newnode->avl_parent = NULL;
+ newnode->avl_forw = NULL;
+ newnode->avl_back = NULL;
+ newnode->avl_balance = AVL_BALANCE;
+
+ if (afterp == NULL) {
+ tree->avl_root = newnode;
+ tree->avl_firstino = newnode;
+ return;
+ }
+
+ ASSERT(afterp->avl_forw == NULL);
+ avl64_insert_grow(tree, afterp, newnode, AVL_FORW); /* grow to right */
+ CERT(afterp->avl_forw == newnode);
+ avl64_balance(&tree->avl_root, afterp, AVL_FORW);
+ avl64_checktree(tree, tree->avl_root);
+}
+
+
+/*
+ * Returns first in order node
+ */
+avl64node_t *
+avl64_firstino(avl64node_t *root)
+{
+ avl64node_t *np;
+
+ if ((np = root) == NULL)
+ return NULL;
+
+ while (np->avl_back)
+ np = np->avl_back;
+ return np;
+}
+
+/*
+ * Returns last in order node
+ */
+avl64node_t *
+avl64_lastino(avl64node_t *root)
+{
+ avl64node_t *np;
+
+ if ((np = root) == NULL)
+ return NULL;
+
+ while (np->avl_forw)
+ np = np->avl_forw;
+ return np;
+}
+
+void
+avl64_init_tree(avl64tree_desc_t *tree, avl64ops_t *ops)
+{
+ tree->avl_root = NULL;
+ tree->avl_firstino = NULL;
+ tree->avl_ops = ops;
+}
+
+#ifdef AVL_DEBUG
+static void
+avl64_printnode(avl64tree_desc_t *tree, avl64node_t *np, int nl)
+{
+ printf("[%d-%d]%c", AVL_START(tree, np),
+ (AVL_END(tree, np) - 1), nl ? '\n' : ' ');
+}
+#endif
+#ifdef STAND_ALONE_DEBUG
+
+struct avl_debug_node {
+ avl64node_t avl_node;
+ xfs_off_t avl_start;
+ unsigned int avl_size;
+}
+
+avl64ops_t avl_debug_ops = {
+ avl_debug_start,
+ avl_debug_end,
+}
+
+static uint64_t
+avl64_debug_start(avl64node_t *node)
+{
+ return (uint64_t)(struct avl_debug_node *)node->avl_start;
+}
+
+static uint64_t
+avl64_debug_end(avl64node_t *node)
+{
+ return (uint64_t)
+ ((struct avl_debug_node *)node->avl_start +
+ (struct avl_debug_node *)node->avl_size);
+}
+
+avl_debug_node freenodes[100];
+avl_debug_node *freehead = &freenodes[0];
+
+static avl64node_t *
+alloc_avl64_debug_node()
+{
+ freehead->avl_balance = AVL_BALANCE;
+ freehead->avl_parent = freehead->avl_forw = freehead->avl_back = NULL;
+ return(freehead++);
+}
+
+static void
+avl64_print(avl64tree_desc_t *tree, avl64node_t *root, int depth)
+{
+ int i;
+
+ if (!root)
+ return;
+ if (root->avl_forw)
+ avl64_print(tree, root->avl_forw, depth+5);
+ for (i = 0; i < depth; i++)
+ putchar((int) ' ');
+ avl64_printnode(tree, root,1);
+ if (root->avl_back)
+ avl64_print(tree, root->avl_back, depth+5);
+}
+
+main()
+{
+ int i, j;
+ avl64node_t *np;
+ avl64tree_desc_t tree;
+ char linebuf[256], cmd[256];
+
+ avl64_init_tree(&tree, &avl_debug_ops);
+
+ for (i = 100; i > 0; i = i - 10)
+ {
+ np = alloc__debug_avlnode();
+ ASSERT(np);
+ np->avl_start = i;
+ np->avl_size = 10;
+ avl64_insert(&tree, np);
+ }
+ avl64_print(&tree, tree.avl_root, 0);
+
+ for (np = tree.avl_firstino; np != NULL; np = np->avl_nextino)
+ avl64_printnode(&tree, np, 0);
+ printf("\n");
+
+ while (1) {
+ printf(_("Command [fpdir] : "));
+ fgets(linebuf, 256, stdin);
+ if (feof(stdin)) break;
+ cmd[0] = NULL;
+ if (sscanf(linebuf, "%[fpdir]%d", cmd, &i) != 2)
+ continue;
+ switch (cmd[0]) {
+ case 'd':
+ case 'f':
+ printf(_("end of range ? "));
+ fgets(linebuf, 256, stdin);
+ j = atoi(linebuf);
+
+ if (i == j) j = i+1;
+ np = avl64_findinrange(&tree,i,j);
+ if (np) {
+ avl64_printnode(&tree, np, 1);
+ if (cmd[0] == 'd')
+ avl64_delete(&tree, np);
+ } else
+ printf(_("Cannot find %d\n"), i);
+ break;
+ case 'p':
+ avl64_print(&tree, tree.avl_root, 0);
+ for (np = tree.avl_firstino;
+ np != NULL; np = np->avl_nextino)
+ avl64_printnode(&tree, np, 0);
+ printf("\n");
+ break;
+ case 'i':
+ np = alloc_avlnode();
+ ASSERT(np);
+ np->avl_start = i;
+ printf(_("size of range ? "));
+ fgets(linebuf, 256, stdin);
+ j = atoi(linebuf);
+
+ np->avl_size = j;
+ avl64_insert(&tree, np);
+ break;
+ case 'r': {
+ avl64node_t *b, *e, *t;
+ int checklen;
+
+ printf(_("End of range ? "));
+ fgets(linebuf, 256, stdin);
+ j = atoi(linebuf);
+
+ printf(_("checklen 0/1 ? "));
+ fgets(linebuf, 256, stdin);
+ checklen = atoi(linebuf);
+
+
+ b = avl64_findanyrange(&tree, i, j, checklen);
+ if (b) {
+ printf(_("Found something\n"));
+ t = b;
+ while (t) {
+ if (t != b &&
+ AVL_START(&tree, t) >= j)
+ break;
+ avl64_printnode(&tree, t, 0);
+ t = t->avl_nextino;
+ }
+ printf("\n");
+ }
+ }
+ }
+ }
+}
+#endif
+
+/*
+ * Given a tree, find value; will find return range enclosing value,
+ * or range immediately succeeding value,
+ * or range immediately preceeding value.
+ */
+avl64node_t *
+avl64_findadjacent(
+ avl64tree_desc_t *tree,
+ uint64_t value,
+ int dir)
+{
+ avl64node_t *np = tree->avl_root;
+
+ while (np) {
+ if (value < AVL_START(tree, np)) {
+ if (np->avl_back) {
+ np = np->avl_back;
+ continue;
+ }
+ /* if we were to add node with value, would
+ * have a growth of AVL_BACK
+ */
+ if (dir == AVL_SUCCEED) {
+ /* if succeeding node is needed, this is it.
+ */
+ return(np);
+ }
+ if (dir == AVL_PRECEED) {
+ /*
+ * find nearest ancestor with lesser value.
+ */
+ np = np->avl_parent;
+ while (np) {
+ if (AVL_END(tree, np) <= value)
+ break;
+ np = np->avl_parent;
+ }
+ return(np);
+ }
+ ASSERT(dir == AVL_SUCCEED || dir == AVL_PRECEED);
+ break;
+ }
+ if (value >= AVL_END(tree, np)) {
+ if (np->avl_forw) {
+ np = np->avl_forw;
+ continue;
+ }
+ /* if we were to add node with value, would
+ * have a growth of AVL_FORW;
+ */
+ if (dir == AVL_SUCCEED) {
+ /* we are looking for a succeeding node;
+ * this is nextino.
+ */
+ return(np->avl_nextino);
+ }
+ if (dir == AVL_PRECEED) {
+ /* looking for a preceeding node; this is it. */
+ return(np);
+ }
+ ASSERT(dir == AVL_SUCCEED || dir == AVL_PRECEED);
+ }
+ /* AVL_START(tree, np) <= value < AVL_END(tree, np) */
+ return(np);
+ }
+ return NULL;
+}
+
+
+/*
+ * avl_findranges:
+ *
+ * Given range r [start, end), find all ranges in tree which are contained
+ * in r. At return, startp and endp point to first and last of
+ * a chain of elements which describe the contained ranges. Elements
+ * in startp ... endp are in sort order, and can be accessed by
+ * using avl_nextino.
+ */
+
+void
+avl64_findranges(
+ avl64tree_desc_t *tree,
+ uint64_t start,
+ uint64_t end,
+ avl64node_t **startp,
+ avl64node_t **endp)
+{
+ avl64node_t *np;
+
+ np = avl64_findadjacent(tree, start, AVL_SUCCEED);
+ if (np == NULL /* nothing succeding start */
+ || (np && (end <= AVL_START(tree, np))))
+ /* something follows start,
+ but... is entirely after end */
+ {
+ *startp = NULL;
+ *endp = NULL;
+ return;
+ }
+
+ *startp = np;
+
+ /* see if end is in this region itself */
+ if (end <= AVL_END(tree, np) ||
+ np->avl_nextino == NULL ||
+ (np->avl_nextino &&
+ (end <= AVL_START(tree, np->avl_nextino)))) {
+ *endp = np;
+ return;
+ }
+ /* have to munge for end */
+ /*
+ * note: have to look for (end - 1), since
+ * findadjacent will look for exact value, and does not
+ * care about the fact that end is actually one more
+ * than the value actually being looked for; thus feed it one less.
+ */
+ *endp = avl64_findadjacent(tree, (end-1), AVL_PRECEED);
+ ASSERT(*endp);
+}
diff --git a/repair/Makefile b/repair/Makefile
index 4184a70..c348cec 100644
--- a/repair/Makefile
+++ b/repair/Makefile
@@ -9,11 +9,11 @@ LSRCFILES = README
LTCOMMAND = xfs_repair
-HFILES = agheader.h attr_repair.h avl.h avl64.h bmap.h btree.h \
+HFILES = agheader.h attr_repair.h avl.h bmap.h btree.h \
da_util.h dinode.h dir2.h err_protos.h globals.h incore.h protos.h \
rt.h progress.h scan.h versions.h prefetch.h rmap.h slab.h threads.h
-CFILES = agheader.c attr_repair.c avl.c avl64.c bmap.c btree.c \
+CFILES = agheader.c attr_repair.c avl.c bmap.c btree.c \
da_util.c dino_chunks.c dinode.c dir2.c globals.c incore.c \
incore_bmc.c init.c incore_ext.c incore_ino.c phase1.c \
phase2.c phase3.c phase4.c phase5.c phase6.c phase7.c \
diff --git a/repair/avl64.c b/repair/avl64.c
deleted file mode 100644
index 8f4a121..0000000
--- a/repair/avl64.c
+++ /dev/null
@@ -1,1418 +0,0 @@
-/*
- * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
- * All Rights Reserved.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it would be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
- */
-
-#include <stdio.h>
-#include "libxfs.h"
-#include "avl64.h"
-
-#define CERT ASSERT
-
-#ifdef AVL_DEBUG
-
-static void
-avl64_checknode(
- avl64tree_desc_t *tree,
- avl64node_t *np)
-{
- avl64node_t *back = np->avl_back;
- avl64node_t *forw = np->avl_forw;
- avl64node_t *nextino = np->avl_nextino;
- int bal = np->avl_balance;
-
- ASSERT(bal != AVL_BALANCE || (!back && !forw) || (back && forw));
- ASSERT(bal != AVL_FORW || forw);
- ASSERT(bal != AVL_BACK || back);
-
- if (forw) {
- ASSERT(AVL_START(tree, np) < AVL_START(tree, forw));
- ASSERT(np->avl_forw->avl_parent == np);
- ASSERT(back || bal == AVL_FORW);
- } else {
- ASSERT(bal != AVL_FORW);
- ASSERT(bal == AVL_BALANCE || back);
- ASSERT(bal == AVL_BACK || !back);
- }
-
- if (back) {
- ASSERT(AVL_START(tree, np) > AVL_START(tree, back));
- ASSERT(np->avl_back->avl_parent == np);
- ASSERT(forw || bal == AVL_BACK);
- } else {
- ASSERT(bal != AVL_BACK);
- ASSERT(bal == AVL_BALANCE || forw);
- ASSERT(bal == AVL_FORW || !forw);
- }
-
- if (nextino == NULL)
- ASSERT(forw == NULL);
- else
- ASSERT(AVL_END(tree, np) <= AVL_START(tree, nextino));
-}
-
-static void
-avl64_checktree(
- avl64tree_desc_t *tree,
- avl64node_t *root)
-{
- avl64node_t *nlast, *nnext, *np;
- uint64_t offset = 0;
- uint64_t end;
-
- nlast = nnext = root;
-
- ASSERT(!nnext || nnext->avl_parent == NULL);
-
- while (nnext) {
-
- avl64_checknode(tree, nnext);
- end = AVL_END(tree, nnext);
-
- if (end <= offset) {
- if ((np = nnext->avl_forw) && np != nlast) {
- nlast = nnext;
- nnext = np;
- } else {
- nlast = nnext;
- nnext = nnext->avl_parent;
- }
- continue;
- }
-
- nlast = nnext;
- if (np = nnext->avl_back) {
- if (AVL_END(tree, np) > offset) {
- nnext = np;
- continue;
- }
- }
-
- np = nnext;
- nnext = nnext->avl_forw;
- if (!nnext)
- nnext = np->avl_parent;
-
- offset = end;
- }
-}
-#else /* ! AVL_DEBUG */
-#define avl64_checktree(t,x)
-#endif /* AVL_DEBUG */
-
-
-/*
- * Reset balance for np up through tree.
- * ``direction'' is the way that np's balance
- * is headed after the deletion of one of its children --
- * e.g., deleting a avl_forw child sends avl_balance toward AVL_BACK.
- * Called only when deleting a node from the tree.
- */
-static void
-retreat(
- avl64tree_desc_t *tree,
- avl64node_t *np,
- int direction)
-{
- avl64node_t **rootp = &tree->avl_root;
- avl64node_t *parent;
- avl64node_t *child;
- avl64node_t *tmp;
- int bal;
-
- do {
- ASSERT(direction == AVL_BACK || direction == AVL_FORW);
-
- if (np->avl_balance == AVL_BALANCE) {
- np->avl_balance = direction;
- return;
- }
-
- parent = np->avl_parent;
-
- /*
- * If balance is being restored, no local node
- * reorganization is necessary, but may be at
- * a higher node. Reset direction and continue.
- */
- if (direction != np->avl_balance) {
- np->avl_balance = AVL_BALANCE;
- if (parent) {
- if (parent->avl_forw == np)
- direction = AVL_BACK;
- else
- direction = AVL_FORW;
-
- np = parent;
- continue;
- }
- return;
- }
-
- /*
- * Imbalance. If a avl_forw node was removed, direction
- * (and, by reduction, np->avl_balance) is/was AVL_BACK.
- */
- if (np->avl_balance == AVL_BACK) {
-
- ASSERT(direction == AVL_BACK);
- child = np->avl_back;
- bal = child->avl_balance;
-
- if (bal != AVL_FORW) /* single LL */ {
- /*
- * np gets pushed down to lesser child's
- * avl_forw branch.
- *
- * np-> -D +B
- * / \ / \
- * child-> B deleted A -D
- * / \ /
- * A C C
- cmn_err(CE_CONT, "!LL delete b 0x%x c 0x%x\n",
- np, child);
- */
-
- np->avl_back = child->avl_forw;
- if (child->avl_forw)
- child->avl_forw->avl_parent = np;
- child->avl_forw = np;
-
- if (parent) {
- if (parent->avl_forw == np) {
- parent->avl_forw = child;
- direction = AVL_BACK;
- } else {
- ASSERT(parent->avl_back == np);
- parent->avl_back = child;
- direction = AVL_FORW;
- }
- } else {
- ASSERT(*rootp == np);
- *rootp = child;
- }
- np->avl_parent = child;
- child->avl_parent = parent;
-
- if (bal == AVL_BALANCE) {
- np->avl_balance = AVL_BACK;
- child->avl_balance = AVL_FORW;
- return;
- } else {
- np->avl_balance = AVL_BALANCE;
- child->avl_balance = AVL_BALANCE;
- np = parent;
- avl64_checktree(tree, *rootp);
- continue;
- }
- }
-
- /* child->avl_balance == AVL_FORW double LR rotation
- *
- * child's avl_forw node gets promoted up, along with
- * its avl_forw subtree
- *
- * np-> -G C
- * / \ / \
- * child-> +B H -B G
- * / \ \ / / \
- * A +C deleted A D H
- * \
- * D
- cmn_err(CE_CONT, "!LR delete b 0x%x c 0x%x t 0x%x\n",
- np, child, child->avl_forw);
- */
-
- tmp = child->avl_forw;
- bal = tmp->avl_balance;
-
- child->avl_forw = tmp->avl_back;
- if (tmp->avl_back)
- tmp->avl_back->avl_parent = child;
-
- tmp->avl_back = child;
- child->avl_parent = tmp;
-
- np->avl_back = tmp->avl_forw;
- if (tmp->avl_forw)
- tmp->avl_forw->avl_parent = np;
- tmp->avl_forw = np;
-
- if (bal == AVL_FORW)
- child->avl_balance = AVL_BACK;
- else
- child->avl_balance = AVL_BALANCE;
-
- if (bal == AVL_BACK)
- np->avl_balance = AVL_FORW;
- else
- np->avl_balance = AVL_BALANCE;
-
- goto next;
- }
-
- ASSERT(np->avl_balance == AVL_FORW && direction == AVL_FORW);
-
- child = np->avl_forw;
- bal = child->avl_balance;
-
- if (bal != AVL_BACK) /* single RR */ {
- /*
- * np gets pushed down to greater child's
- * avl_back branch.
- *
- * np-> +B -D
- * / \ / \
- * deleted D <-child +B E
- * / \ \
- * C E C
- cmn_err(CE_CONT, "!RR delete b 0x%x c 0x%x\n",
- np, child);
- */
-
- np->avl_forw = child->avl_back;
- if (child->avl_back)
- child->avl_back->avl_parent = np;
- child->avl_back = np;
-
- if (parent) {
- if (parent->avl_forw == np) {
- parent->avl_forw = child;
- direction = AVL_BACK;
- } else {
- ASSERT(parent->avl_back == np);
- parent->avl_back = child;
- direction = AVL_FORW;
- }
- } else {
- ASSERT(*rootp == np);
- *rootp = child;
- }
- np->avl_parent = child;
- child->avl_parent = parent;
-
- if (bal == AVL_BALANCE) {
- np->avl_balance = AVL_FORW;
- child->avl_balance = AVL_BACK;
- return;
- } else {
- np->avl_balance = AVL_BALANCE;
- child->avl_balance = AVL_BALANCE;
- np = parent;
- avl64_checktree(tree, *rootp);
- continue;
- }
- }
-
- /* child->avl_balance == AVL_BACK double RL rotation
- cmn_err(CE_CONT, "!RL delete b 0x%x c 0x%x t 0x%x\n",
- np, child, child->avl_back);
- */
-
- tmp = child->avl_back;
- bal = tmp->avl_balance;
-
- child->avl_back = tmp->avl_forw;
- if (tmp->avl_forw)
- tmp->avl_forw->avl_parent = child;
-
- tmp->avl_forw = child;
- child->avl_parent = tmp;
-
- np->avl_forw = tmp->avl_back;
- if (tmp->avl_back)
- tmp->avl_back->avl_parent = np;
- tmp->avl_back = np;
-
- if (bal == AVL_BACK)
- child->avl_balance = AVL_FORW;
- else
- child->avl_balance = AVL_BALANCE;
-
- if (bal == AVL_FORW)
- np->avl_balance = AVL_BACK;
- else
- np->avl_balance = AVL_BALANCE;
-next:
- np->avl_parent = tmp;
- tmp->avl_balance = AVL_BALANCE;
- tmp->avl_parent = parent;
-
- if (parent) {
- if (parent->avl_forw == np) {
- parent->avl_forw = tmp;
- direction = AVL_BACK;
- } else {
- ASSERT(parent->avl_back == np);
- parent->avl_back = tmp;
- direction = AVL_FORW;
- }
- } else {
- ASSERT(*rootp == np);
- *rootp = tmp;
- return;
- }
-
- np = parent;
- avl64_checktree(tree, *rootp);
- } while (np);
-}
-
-/*
- * Remove node from tree.
- * avl_delete does the local tree manipulations,
- * calls retreat() to rebalance tree up to its root.
- */
-void
-avl64_delete(
- avl64tree_desc_t *tree,
- avl64node_t *np)
-{
- avl64node_t *forw = np->avl_forw;
- avl64node_t *back = np->avl_back;
- avl64node_t *parent = np->avl_parent;
- avl64node_t *nnext;
-
-
- if (np->avl_back) {
- /*
- * a left child exits, then greatest left descendent's nextino
- * is pointing to np; make it point to np->nextino.
- */
- nnext = np->avl_back;
- while (nnext) {
- if (!nnext->avl_forw)
- break; /* can't find anything bigger */
- nnext = nnext->avl_forw;
- }
- } else
- if (np->avl_parent) {
- /*
- * find nearest ancestor with lesser value. That ancestor's
- * nextino is pointing to np; make it point to np->nextino
- */
- nnext = np->avl_parent;
- while (nnext) {
- if (AVL_END(tree, nnext) <= AVL_END(tree, np))
- break;
- nnext = nnext->avl_parent;
- }
- } else
- nnext = NULL;
-
- if (nnext) {
- ASSERT(nnext->avl_nextino == np);
- nnext->avl_nextino = np->avl_nextino;
- /*
- * Something preceeds np; np cannot be firstino.
- */
- ASSERT(tree->avl_firstino != np);
- }
- else {
- /*
- * Nothing preceeding np; after deletion, np's nextino
- * is firstino of tree.
- */
- ASSERT(tree->avl_firstino == np);
- tree->avl_firstino = np->avl_nextino;
- }
-
-
- /*
- * Degenerate cases...
- */
- if (forw == NULL) {
- forw = back;
- goto attach;
- }
-
- if (back == NULL) {
-attach:
- if (forw)
- forw->avl_parent = parent;
- if (parent) {
- if (parent->avl_forw == np) {
- parent->avl_forw = forw;
- retreat(tree, parent, AVL_BACK);
- } else {
- ASSERT(parent->avl_back == np);
- parent->avl_back = forw;
- retreat(tree, parent, AVL_FORW);
- }
- } else {
- ASSERT(tree->avl_root == np);
- tree->avl_root = forw;
- }
- avl64_checktree(tree, tree->avl_root);
- return;
- }
-
- /*
- * Harder case: children on both sides.
- * If back's avl_forw pointer is null, just have back
- * inherit np's avl_forw tree, remove np from the tree
- * and adjust balance counters starting at back.
- *
- * np-> xI xH (befor retreat())
- * / \ / \
- * back-> H J G J
- * / / \ / \
- * G ? ? ? ?
- * / \
- * ? ?
- */
- if ((forw = back->avl_forw) == NULL) {
- /*
- * AVL_FORW retreat below will set back's
- * balance to AVL_BACK.
- */
- back->avl_balance = np->avl_balance;
- back->avl_forw = forw = np->avl_forw;
- forw->avl_parent = back;
- back->avl_parent = parent;
-
- if (parent) {
- if (parent->avl_forw == np)
- parent->avl_forw = back;
- else {
- ASSERT(parent->avl_back == np);
- parent->avl_back = back;
- }
- } else {
- ASSERT(tree->avl_root == np);
- tree->avl_root = back;
- }
-
- /*
- * back is taking np's place in the tree, and
- * has therefore lost a avl_back node (itself).
- */
- retreat(tree, back, AVL_FORW);
- avl64_checktree(tree, tree->avl_root);
- return;
- }
-
- /*
- * Hardest case: children on both sides, and back's
- * avl_forw pointer isn't null. Find the immediately
- * inferior buffer by following back's avl_forw line
- * to the end, then have it inherit np's avl_forw tree.
- *
- * np-> xI xH
- * / \ / \
- * G J back-> G J (before retreat())
- * / \ / \
- * F ?... F ?1
- * / \
- * ? H <-forw
- * /
- * ?1
- */
- while ((back = forw->avl_forw))
- forw = back;
-
- /*
- * Will be adjusted by retreat() below.
- */
- forw->avl_balance = np->avl_balance;
-
- /*
- * forw inherits np's avl_forw...
- */
- forw->avl_forw = np->avl_forw;
- np->avl_forw->avl_parent = forw;
-
- /*
- * ... forw's parent gets forw's avl_back...
- */
- back = forw->avl_parent;
- back->avl_forw = forw->avl_back;
- if (forw->avl_back)
- forw->avl_back->avl_parent = back;
-
- /*
- * ... forw gets np's avl_back...
- */
- forw->avl_back = np->avl_back;
- np->avl_back->avl_parent = forw;
-
- /*
- * ... and forw gets np's parent.
- */
- forw->avl_parent = parent;
-
- if (parent) {
- if (parent->avl_forw == np)
- parent->avl_forw = forw;
- else
- parent->avl_back = forw;
- } else {
- ASSERT(tree->avl_root == np);
- tree->avl_root = forw;
- }
-
- /*
- * What used to be forw's parent is the starting
- * point for rebalancing. It has lost a avl_forw node.
- */
- retreat(tree, back, AVL_BACK);
- avl64_checktree(tree, tree->avl_root);
-}
-
-
-/*
- * avl_findanyrange:
- *
- * Given range r [start, end), find any range which is contained in r.
- * if checklen is non-zero, then only ranges of non-zero length are
- * considered in finding a match.
- */
-avl64node_t *
-avl64_findanyrange(
- avl64tree_desc_t *tree,
- uint64_t start,
- uint64_t end,
- int checklen)
-{
- avl64node_t *np = tree->avl_root;
-
- /* np = avl64_findadjacent(tree, start, AVL_SUCCEED); */
- while (np) {
- if (start < AVL_START(tree, np)) {
- if (np->avl_back) {
- np = np->avl_back;
- continue;
- }
- /* if we were to add node with start, would
- * have a growth of AVL_BACK
- */
- /* if succeeding node is needed, this is it.
- */
- break;
- }
- if (start >= AVL_END(tree, np)) {
- if (np->avl_forw) {
- np = np->avl_forw;
- continue;
- }
- /* if we were to add node with start, would
- * have a growth of AVL_FORW;
- */
- /* we are looking for a succeeding node;
- * this is nextino.
- */
- np = np->avl_nextino;
- break;
- }
- /* AVL_START(tree, np) <= start < AVL_END(tree, np) */
- break;
- }
- if (np) {
- if (checklen == AVL_INCLUDE_ZEROLEN) {
- if (end <= AVL_START(tree, np)) {
- /* something follows start, but is
- * is entierly after the range (end)
- */
- return(NULL);
- }
- /* np may stradle [start, end) */
- return(np);
- }
- /*
- * find non-zero length region
- */
- while (np && (AVL_END(tree, np) - AVL_START(tree, np) == 0)
- && (AVL_START(tree, np) < end))
- np = np->avl_nextino;
-
- if ((np == NULL) || (AVL_START(tree, np) >= end))
- return NULL;
- return(np);
- }
- /*
- * nothing succeeds start, all existing ranges are before start.
- */
- return NULL;
-}
-
-
-/*
- * Returns a pointer to range which contains value.
- */
-avl64node_t *
-avl64_findrange(
- avl64tree_desc_t *tree,
- uint64_t value)
-{
- avl64node_t *np = tree->avl_root;
-
- while (np) {
- if (value < AVL_START(tree, np)) {
- np = np->avl_back;
- continue;
- }
- if (value >= AVL_END(tree, np)) {
- np = np->avl_forw;
- continue;
- }
- ASSERT(AVL_START(tree, np) <= value &&
- value < AVL_END(tree, np));
- return np;
- }
- return NULL;
-}
-
-
-/*
- * Returns a pointer to node which contains exact value.
- */
-avl64node_t *
-avl64_find(
- avl64tree_desc_t *tree,
- uint64_t value)
-{
- avl64node_t *np = tree->avl_root;
- uint64_t nvalue;
-
- while (np) {
- nvalue = AVL_START(tree, np);
- if (value < nvalue) {
- np = np->avl_back;
- continue;
- }
- if (value == nvalue) {
- return np;
- }
- np = np->avl_forw;
- }
- return NULL;
-}
-
-
-/*
- * Balance buffer AVL tree after attaching a new node to root.
- * Called only by avl_insert.
- */
-static void
-avl64_balance(
- avl64node_t **rootp,
- avl64node_t *np,
- int growth)
-{
- /*
- * At this point, np points to the node to which
- * a new node has been attached. All that remains is to
- * propagate avl_balance up the tree.
- */
- for ( ; ; ) {
- avl64node_t *parent = np->avl_parent;
- avl64node_t *child;
-
- CERT(growth == AVL_BACK || growth == AVL_FORW);
-
- /*
- * If the buffer was already balanced, set avl_balance
- * to the new direction. Continue if there is a
- * parent after setting growth to reflect np's
- * relation to its parent.
- */
- if (np->avl_balance == AVL_BALANCE) {
- np->avl_balance = growth;
- if (parent) {
- if (parent->avl_forw == np)
- growth = AVL_FORW;
- else {
- ASSERT(parent->avl_back == np);
- growth = AVL_BACK;
- }
-
- np = parent;
- continue;
- }
- break;
- }
-
- if (growth != np->avl_balance) {
- /*
- * Subtree is now balanced -- no net effect
- * in the size of the subtree, so leave.
- */
- np->avl_balance = AVL_BALANCE;
- break;
- }
-
- if (growth == AVL_BACK) {
-
- child = np->avl_back;
- CERT(np->avl_balance == AVL_BACK && child);
-
- if (child->avl_balance == AVL_BACK) { /* single LL */
- /*
- * ``A'' just got inserted;
- * np points to ``E'', child to ``C'',
- * and it is already AVL_BACK --
- * child will get promoted to top of subtree.
-
- np-> -E C
- / \ / \
- child-> -C F -B E
- / \ / / \
- -B D A D F
- /
- A
-
- Note that child->avl_parent and
- avl_balance get set in common code.
- */
- np->avl_parent = child;
- np->avl_balance = AVL_BALANCE;
- np->avl_back = child->avl_forw;
- if (child->avl_forw)
- child->avl_forw->avl_parent = np;
- child->avl_forw = np;
- } else {
- /*
- * double LR
- *
- * child's avl_forw node gets promoted to
- * the top of the subtree.
-
- np-> -E C
- / \ / \
- child-> +B F -B E
- / \ / / \
- A +C A D F
- \
- D
-
- */
- avl64node_t *tmp = child->avl_forw;
-
- CERT(child->avl_balance == AVL_FORW && tmp);
-
- child->avl_forw = tmp->avl_back;
- if (tmp->avl_back)
- tmp->avl_back->avl_parent = child;
-
- tmp->avl_back = child;
- child->avl_parent = tmp;
-
- np->avl_back = tmp->avl_forw;
- if (tmp->avl_forw)
- tmp->avl_forw->avl_parent = np;
-
- tmp->avl_forw = np;
- np->avl_parent = tmp;
-
- if (tmp->avl_balance == AVL_BACK)
- np->avl_balance = AVL_FORW;
- else
- np->avl_balance = AVL_BALANCE;
-
- if (tmp->avl_balance == AVL_FORW)
- child->avl_balance = AVL_BACK;
- else
- child->avl_balance = AVL_BALANCE;
-
- /*
- * Set child to point to tmp since it is
- * now the top of the subtree, and will
- * get attached to the subtree parent in
- * the common code below.
- */
- child = tmp;
- }
-
- } else /* growth == AVL_BACK */ {
-
- /*
- * This code is the mirror image of AVL_FORW above.
- */
-
- child = np->avl_forw;
- CERT(np->avl_balance == AVL_FORW && child);
-
- if (child->avl_balance == AVL_FORW) { /* single RR */
- np->avl_parent = child;
- np->avl_balance = AVL_BALANCE;
- np->avl_forw = child->avl_back;
- if (child->avl_back)
- child->avl_back->avl_parent = np;
- child->avl_back = np;
- } else {
- /*
- * double RL
- */
- avl64node_t *tmp = child->avl_back;
-
- ASSERT(child->avl_balance == AVL_BACK && tmp);
-
- child->avl_back = tmp->avl_forw;
- if (tmp->avl_forw)
- tmp->avl_forw->avl_parent = child;
-
- tmp->avl_forw = child;
- child->avl_parent = tmp;
-
- np->avl_forw = tmp->avl_back;
- if (tmp->avl_back)
- tmp->avl_back->avl_parent = np;
-
- tmp->avl_back = np;
- np->avl_parent = tmp;
-
- if (tmp->avl_balance == AVL_FORW)
- np->avl_balance = AVL_BACK;
- else
- np->avl_balance = AVL_BALANCE;
-
- if (tmp->avl_balance == AVL_BACK)
- child->avl_balance = AVL_FORW;
- else
- child->avl_balance = AVL_BALANCE;
-
- child = tmp;
- }
- }
-
- child->avl_parent = parent;
- child->avl_balance = AVL_BALANCE;
-
- if (parent) {
- if (parent->avl_back == np)
- parent->avl_back = child;
- else
- parent->avl_forw = child;
- } else {
- ASSERT(*rootp == np);
- *rootp = child;
- }
-
- break;
- }
-}
-
-static
-avl64node_t *
-avl64_insert_find_growth(
- avl64tree_desc_t *tree,
- uint64_t start, /* range start at start, */
- uint64_t end, /* exclusive */
- int *growthp) /* OUT */
-{
- avl64node_t *root = tree->avl_root;
- avl64node_t *np;
-
- np = root;
- ASSERT(np); /* caller ensures that there is atleast one node in tree */
-
- for ( ; ; ) {
- CERT(np->avl_parent || root == np);
- CERT(!np->avl_parent || root != np);
- CERT(!(np->avl_back) || np->avl_back->avl_parent == np);
- CERT(!(np->avl_forw) || np->avl_forw->avl_parent == np);
- CERT(np->avl_balance != AVL_FORW || np->avl_forw);
- CERT(np->avl_balance != AVL_BACK || np->avl_back);
- CERT(np->avl_balance != AVL_BALANCE ||
- np->avl_back == NULL || np->avl_forw);
- CERT(np->avl_balance != AVL_BALANCE ||
- np->avl_forw == NULL || np->avl_back);
-
- if (AVL_START(tree, np) >= end) {
- if (np->avl_back) {
- np = np->avl_back;
- continue;
- }
- *growthp = AVL_BACK;
- break;
- }
-
- if (AVL_END(tree, np) <= start) {
- if (np->avl_forw) {
- np = np->avl_forw;
- continue;
- }
- *growthp = AVL_FORW;
- break;
- }
- /* found exact match -- let caller decide if it is an error */
- return(NULL);
- }
- return(np);
-}
-
-
-static void
-avl64_insert_grow(
- avl64tree_desc_t *tree,
- avl64node_t *parent,
- avl64node_t *newnode,
- int growth)
-{
- avl64node_t *nnext;
- uint64_t start = AVL_START(tree, newnode);
-
- if (growth == AVL_BACK) {
-
- parent->avl_back = newnode;
- /*
- * we are growing to the left; previous in-order to newnode is
- * closest ancestor with lesser value. Before this
- * insertion, this ancestor will be pointing to
- * newnode's parent. After insertion, next in-order to newnode
- * is the parent.
- */
- newnode->avl_nextino = parent;
- nnext = parent;
- while (nnext) {
- if (AVL_END(tree, nnext) <= start)
- break;
- nnext = nnext->avl_parent;
- }
- if (nnext) {
- /*
- * nnext will be null if newnode is
- * the least element, and hence very first in the list.
- */
- ASSERT(nnext->avl_nextino == parent);
- nnext->avl_nextino = newnode;
- }
- }
- else {
- parent->avl_forw = newnode;
- newnode->avl_nextino = parent->avl_nextino;
- parent->avl_nextino = newnode;
- }
-}
-
-
-avl64node_t *
-avl64_insert(
- avl64tree_desc_t *tree,
- avl64node_t *newnode)
-{
- avl64node_t *np;
- uint64_t start = AVL_START(tree, newnode);
- uint64_t end = AVL_END(tree, newnode);
- int growth;
-
- ASSERT(newnode);
- /*
- * Clean all pointers for sanity; some will be reset as necessary.
- */
- newnode->avl_nextino = NULL;
- newnode->avl_parent = NULL;
- newnode->avl_forw = NULL;
- newnode->avl_back = NULL;
- newnode->avl_balance = AVL_BALANCE;
-
- if ((np = tree->avl_root) == NULL) { /* degenerate case... */
- tree->avl_root = newnode;
- tree->avl_firstino = newnode;
- return newnode;
- }
-
- if ((np = avl64_insert_find_growth(tree, start, end, &growth))
- == NULL) {
- if (start != end) { /* non-zero length range */
- fprintf(stderr,
- _("avl_insert: Warning! duplicate range [%llu,%llu]\n"),
- (unsigned long long)start,
- (unsigned long long)end);
- }
- return(NULL);
- }
-
- avl64_insert_grow(tree, np, newnode, growth);
- if (growth == AVL_BACK) {
- /*
- * Growing to left. if np was firstino, newnode will be firstino
- */
- if (tree->avl_firstino == np)
- tree->avl_firstino = newnode;
- }
-#ifdef notneeded
- else
- if (growth == AVL_FORW)
- /*
- * Cannot possibly be firstino; there is somebody to our left.
- */
- ;
-#endif
-
- newnode->avl_parent = np;
- CERT(np->avl_forw == newnode || np->avl_back == newnode);
-
- avl64_balance(&tree->avl_root, np, growth);
-
- avl64_checktree(tree, tree->avl_root);
-
- return newnode;
-}
-
-/*
- *
- * avl64_insert_immediate(tree, afterp, newnode):
- * insert newnode immediately into tree immediately after afterp.
- * after insertion, newnode is right child of afterp.
- */
-void
-avl64_insert_immediate(
- avl64tree_desc_t *tree,
- avl64node_t *afterp,
- avl64node_t *newnode)
-{
- /*
- * Clean all pointers for sanity; some will be reset as necessary.
- */
- newnode->avl_nextino = NULL;
- newnode->avl_parent = NULL;
- newnode->avl_forw = NULL;
- newnode->avl_back = NULL;
- newnode->avl_balance = AVL_BALANCE;
-
- if (afterp == NULL) {
- tree->avl_root = newnode;
- tree->avl_firstino = newnode;
- return;
- }
-
- ASSERT(afterp->avl_forw == NULL);
- avl64_insert_grow(tree, afterp, newnode, AVL_FORW); /* grow to right */
- CERT(afterp->avl_forw == newnode);
- avl64_balance(&tree->avl_root, afterp, AVL_FORW);
- avl64_checktree(tree, tree->avl_root);
-}
-
-
-/*
- * Returns first in order node
- */
-avl64node_t *
-avl64_firstino(avl64node_t *root)
-{
- avl64node_t *np;
-
- if ((np = root) == NULL)
- return NULL;
-
- while (np->avl_back)
- np = np->avl_back;
- return np;
-}
-
-/*
- * Returns last in order node
- */
-avl64node_t *
-avl64_lastino(avl64node_t *root)
-{
- avl64node_t *np;
-
- if ((np = root) == NULL)
- return NULL;
-
- while (np->avl_forw)
- np = np->avl_forw;
- return np;
-}
-
-void
-avl64_init_tree(avl64tree_desc_t *tree, avl64ops_t *ops)
-{
- tree->avl_root = NULL;
- tree->avl_firstino = NULL;
- tree->avl_ops = ops;
-}
-
-#ifdef AVL_DEBUG
-static void
-avl64_printnode(avl64tree_desc_t *tree, avl64node_t *np, int nl)
-{
- printf("[%d-%d]%c", AVL_START(tree, np),
- (AVL_END(tree, np) - 1), nl ? '\n' : ' ');
-}
-#endif
-#ifdef STAND_ALONE_DEBUG
-
-struct avl_debug_node {
- avl64node_t avl_node;
- xfs_off_t avl_start;
- unsigned int avl_size;
-}
-
-avl64ops_t avl_debug_ops = {
- avl_debug_start,
- avl_debug_end,
-}
-
-static uint64_t
-avl64_debug_start(avl64node_t *node)
-{
- return (uint64_t)(struct avl_debug_node *)node->avl_start;
-}
-
-static uint64_t
-avl64_debug_end(avl64node_t *node)
-{
- return (uint64_t)
- ((struct avl_debug_node *)node->avl_start +
- (struct avl_debug_node *)node->avl_size);
-}
-
-avl_debug_node freenodes[100];
-avl_debug_node *freehead = &freenodes[0];
-
-static avl64node_t *
-alloc_avl64_debug_node()
-{
- freehead->avl_balance = AVL_BALANCE;
- freehead->avl_parent = freehead->avl_forw = freehead->avl_back = NULL;
- return(freehead++);
-}
-
-static void
-avl64_print(avl64tree_desc_t *tree, avl64node_t *root, int depth)
-{
- int i;
-
- if (!root)
- return;
- if (root->avl_forw)
- avl64_print(tree, root->avl_forw, depth+5);
- for (i = 0; i < depth; i++)
- putchar((int) ' ');
- avl64_printnode(tree, root,1);
- if (root->avl_back)
- avl64_print(tree, root->avl_back, depth+5);
-}
-
-main()
-{
- int i, j;
- avl64node_t *np;
- avl64tree_desc_t tree;
- char linebuf[256], cmd[256];
-
- avl64_init_tree(&tree, &avl_debug_ops);
-
- for (i = 100; i > 0; i = i - 10)
- {
- np = alloc__debug_avlnode();
- ASSERT(np);
- np->avl_start = i;
- np->avl_size = 10;
- avl64_insert(&tree, np);
- }
- avl64_print(&tree, tree.avl_root, 0);
-
- for (np = tree.avl_firstino; np != NULL; np = np->avl_nextino)
- avl64_printnode(&tree, np, 0);
- printf("\n");
-
- while (1) {
- printf(_("Command [fpdir] : "));
- fgets(linebuf, 256, stdin);
- if (feof(stdin)) break;
- cmd[0] = NULL;
- if (sscanf(linebuf, "%[fpdir]%d", cmd, &i) != 2)
- continue;
- switch (cmd[0]) {
- case 'd':
- case 'f':
- printf(_("end of range ? "));
- fgets(linebuf, 256, stdin);
- j = atoi(linebuf);
-
- if (i == j) j = i+1;
- np = avl64_findinrange(&tree,i,j);
- if (np) {
- avl64_printnode(&tree, np, 1);
- if (cmd[0] == 'd')
- avl64_delete(&tree, np);
- } else
- printf(_("Cannot find %d\n"), i);
- break;
- case 'p':
- avl64_print(&tree, tree.avl_root, 0);
- for (np = tree.avl_firstino;
- np != NULL; np = np->avl_nextino)
- avl64_printnode(&tree, np, 0);
- printf("\n");
- break;
- case 'i':
- np = alloc_avlnode();
- ASSERT(np);
- np->avl_start = i;
- printf(_("size of range ? "));
- fgets(linebuf, 256, stdin);
- j = atoi(linebuf);
-
- np->avl_size = j;
- avl64_insert(&tree, np);
- break;
- case 'r': {
- avl64node_t *b, *e, *t;
- int checklen;
-
- printf(_("End of range ? "));
- fgets(linebuf, 256, stdin);
- j = atoi(linebuf);
-
- printf(_("checklen 0/1 ? "));
- fgets(linebuf, 256, stdin);
- checklen = atoi(linebuf);
-
-
- b = avl64_findanyrange(&tree, i, j, checklen);
- if (b) {
- printf(_("Found something\n"));
- t = b;
- while (t) {
- if (t != b &&
- AVL_START(&tree, t) >= j)
- break;
- avl64_printnode(&tree, t, 0);
- t = t->avl_nextino;
- }
- printf("\n");
- }
- }
- }
- }
-}
-#endif
-
-/*
- * Given a tree, find value; will find return range enclosing value,
- * or range immediately succeeding value,
- * or range immediately preceeding value.
- */
-avl64node_t *
-avl64_findadjacent(
- avl64tree_desc_t *tree,
- uint64_t value,
- int dir)
-{
- avl64node_t *np = tree->avl_root;
-
- while (np) {
- if (value < AVL_START(tree, np)) {
- if (np->avl_back) {
- np = np->avl_back;
- continue;
- }
- /* if we were to add node with value, would
- * have a growth of AVL_BACK
- */
- if (dir == AVL_SUCCEED) {
- /* if succeeding node is needed, this is it.
- */
- return(np);
- }
- if (dir == AVL_PRECEED) {
- /*
- * find nearest ancestor with lesser value.
- */
- np = np->avl_parent;
- while (np) {
- if (AVL_END(tree, np) <= value)
- break;
- np = np->avl_parent;
- }
- return(np);
- }
- ASSERT(dir == AVL_SUCCEED || dir == AVL_PRECEED);
- break;
- }
- if (value >= AVL_END(tree, np)) {
- if (np->avl_forw) {
- np = np->avl_forw;
- continue;
- }
- /* if we were to add node with value, would
- * have a growth of AVL_FORW;
- */
- if (dir == AVL_SUCCEED) {
- /* we are looking for a succeeding node;
- * this is nextino.
- */
- return(np->avl_nextino);
- }
- if (dir == AVL_PRECEED) {
- /* looking for a preceeding node; this is it. */
- return(np);
- }
- ASSERT(dir == AVL_SUCCEED || dir == AVL_PRECEED);
- }
- /* AVL_START(tree, np) <= value < AVL_END(tree, np) */
- return(np);
- }
- return NULL;
-}
-
-
-/*
- * avl_findranges:
- *
- * Given range r [start, end), find all ranges in tree which are contained
- * in r. At return, startp and endp point to first and last of
- * a chain of elements which describe the contained ranges. Elements
- * in startp ... endp are in sort order, and can be accessed by
- * using avl_nextino.
- */
-
-void
-avl64_findranges(
- avl64tree_desc_t *tree,
- uint64_t start,
- uint64_t end,
- avl64node_t **startp,
- avl64node_t **endp)
-{
- avl64node_t *np;
-
- np = avl64_findadjacent(tree, start, AVL_SUCCEED);
- if (np == NULL /* nothing succeding start */
- || (np && (end <= AVL_START(tree, np))))
- /* something follows start,
- but... is entirely after end */
- {
- *startp = NULL;
- *endp = NULL;
- return;
- }
-
- *startp = np;
-
- /* see if end is in this region itself */
- if (end <= AVL_END(tree, np) ||
- np->avl_nextino == NULL ||
- (np->avl_nextino &&
- (end <= AVL_START(tree, np->avl_nextino)))) {
- *endp = np;
- return;
- }
- /* have to munge for end */
- /*
- * note: have to look for (end - 1), since
- * findadjacent will look for exact value, and does not
- * care about the fact that end is actually one more
- * than the value actually being looked for; thus feed it one less.
- */
- *endp = avl64_findadjacent(tree, (end-1), AVL_PRECEED);
- ASSERT(*endp);
-}
diff --git a/repair/avl64.h b/repair/avl64.h
deleted file mode 100644
index cd079a0..0000000
--- a/repair/avl64.h
+++ /dev/null
@@ -1,133 +0,0 @@
-/*
- * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
- * All Rights Reserved.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it would be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
- */
-#ifndef __XR_AVL64_H__
-#define __XR_AVL64_H__
-
-#include <sys/types.h>
-
-typedef struct avl64node {
- struct avl64node *avl_forw; /* pointer to right child (> parent) */
- struct avl64node *avl_back; /* pointer to left child (< parent) */
- struct avl64node *avl_parent; /* parent pointer */
- struct avl64node *avl_nextino; /* next in-order; NULL terminated list*/
- char avl_balance; /* tree balance */
-} avl64node_t;
-
-/*
- * avl-tree operations
- */
-typedef struct avl64ops {
- uint64_t (*avl_start)(avl64node_t *);
- uint64_t (*avl_end)(avl64node_t *);
-} avl64ops_t;
-
-/*
- * avoid complaints about multiple def's since these are only used by
- * the avl code internally
- */
-#ifndef AVL_START
-#define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n)
-#define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n)
-#endif
-
-/*
- * tree descriptor:
- * root points to the root of the tree.
- * firstino points to the first in the ordered list.
- */
-typedef struct avl64tree_desc {
- avl64node_t *avl_root;
- avl64node_t *avl_firstino;
- avl64ops_t *avl_ops;
-} avl64tree_desc_t;
-
-/* possible values for avl_balance */
-
-#define AVL_BACK 1
-#define AVL_BALANCE 0
-#define AVL_FORW 2
-
-/*
- * 'Exported' avl tree routines
- */
-avl64node_t
-*avl64_insert(
- avl64tree_desc_t *tree,
- avl64node_t *newnode);
-
-void
-avl64_delete(
- avl64tree_desc_t *tree,
- avl64node_t *np);
-
-void
-avl64_insert_immediate(
- avl64tree_desc_t *tree,
- avl64node_t *afterp,
- avl64node_t *newnode);
-
-void
-avl64_init_tree(
- avl64tree_desc_t *tree,
- avl64ops_t *ops);
-
-avl64node_t *
-avl64_findrange(
- avl64tree_desc_t *tree,
- uint64_t value);
-
-avl64node_t *
-avl64_find(
- avl64tree_desc_t *tree,
- uint64_t value);
-
-avl64node_t *
-avl64_findanyrange(
- avl64tree_desc_t *tree,
- uint64_t start,
- uint64_t end,
- int checklen);
-
-
-avl64node_t *
-avl64_findadjacent(
- avl64tree_desc_t *tree,
- uint64_t value,
- int dir);
-
-void
-avl64_findranges(
- avl64tree_desc_t *tree,
- uint64_t start,
- uint64_t end,
- avl64node_t **startp,
- avl64node_t **endp);
-
-/*
- * avoid complaints about multiple def's since these are only used by
- * the avl code internally
- */
-#ifndef AVL_PRECEED
-#define AVL_PRECEED 0x1
-#define AVL_SUCCEED 0x2
-
-#define AVL_INCLUDE_ZEROLEN 0x0000
-#define AVL_EXCLUDE_ZEROLEN 0x0001
-#endif
-
-#endif /* __XR_AVL64_H__ */
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
