/*
- * Copyright (C) International Business Machines Corp., 2000-2004
+ * Copyright (C) International Business Machines Corp., 2000-2005
*
* 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
static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
#endif /* _STILL_TO_PORT */
-/* External references */
-
-/*
- * debug control
- */
-/* #define _JFS_DEBUG_XTREE 1 */
-
-
/*
* xtLookup()
*
/* search hit - internal page:
* descend/search its child page
*/
- if (index < p->header.nextindex - 1)
+ if (index < le16_to_cpu(p->header.nextindex)-1)
next = offsetXAD(&p->xad[index + 1]);
goto next;
}
* base is the smallest index with key (Kj) greater than
* search key (K) and may be zero or maxentry index.
*/
- if (base < p->header.nextindex)
+ if (base < le16_to_cpu(p->header.nextindex))
next = offsetXAD(&p->xad[base]);
/*
* search miss - leaf page:
/* process entries backward from last index */
index = le16_to_cpu(p->header.nextindex) - 1;
- if (p->header.flag & BT_INTERNAL)
- goto getChild;
-
- /*
- * leaf page
- */
- /* Since this is the rightmost leaf, and we may have already freed
- * a page that was formerly to the right, let's make sure that the
- * next pointer is zero.
+ /* Since this is the rightmost page at this level, and we may have
+ * already freed a page that was formerly to the right, let's make
+ * sure that the next pointer is zero.
*/
if (p->header.next) {
if (log)
p->header.next = 0;
}
+ if (p->header.flag & BT_INTERNAL)
+ goto getChild;
+
+ /*
+ * leaf page
+ */
freed = 0;
/* does region covered by leaf page precede Teof ? */
return 0;
}
-
-#ifdef _JFS_DEBUG_XTREE
-/*
- * xtDisplayTree()
- *
- * function: traverse forward
- */
-int xtDisplayTree(struct inode *ip)
-{
- int rc = 0;
- struct metapage *mp;
- xtpage_t *p;
- s64 bn, pbn;
- int index, lastindex, v, h;
- xad_t *xad;
- struct btstack btstack;
- struct btframe *btsp;
- struct btframe *parent;
-
- printk("display B+-tree.\n");
-
- /* clear stack */
- btsp = btstack.stack;
-
- /*
- * start with root
- *
- * root resides in the inode
- */
- bn = 0;
- v = h = 0;
-
- /*
- * first access of each page:
- */
- getPage:
- XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
- if (rc)
- return rc;
-
- /* process entries forward from first index */
- index = XTENTRYSTART;
- lastindex = le16_to_cpu(p->header.nextindex) - 1;
-
- if (p->header.flag & BT_INTERNAL) {
- /*
- * first access of each internal page
- */
- goto getChild;
- } else { /* (p->header.flag & BT_LEAF) */
-
- /*
- * first access of each leaf page
- */
- printf("leaf page ");
- xtDisplayPage(ip, bn, p);
-
- /* unpin the leaf page */
- XT_PUTPAGE(mp);
- }
-
- /*
- * go back up to the parent page
- */
- getParent:
- /* pop/restore parent entry for the current child page */
- if ((parent = (btsp == btstack.stack ? NULL : --btsp)) == NULL)
- /* current page must have been root */
- return;
-
- /*
- * parent page scan completed
- */
- if ((index = parent->index) == (lastindex = parent->lastindex)) {
- /* go back up to the parent page */
- goto getParent;
- }
-
- /*
- * parent page has entries remaining
- */
- /* get back the parent page */
- bn = parent->bn;
- /* v = parent->level; */
- XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
- if (rc)
- return rc;
-
- /* get next parent entry */
- index++;
-
- /*
- * internal page: go down to child page of current entry
- */
- getChild:
- /* push/save current parent entry for the child page */
- btsp->bn = pbn = bn;
- btsp->index = index;
- btsp->lastindex = lastindex;
- /* btsp->level = v; */
- /* btsp->node = h; */
- ++btsp;
-
- /* get child page */
- xad = &p->xad[index];
- bn = addressXAD(xad);
-
- /*
- * first access of each internal entry:
- */
- /* release parent page */
- XT_PUTPAGE(mp);
-
- printk("traverse down 0x%lx[%d]->0x%lx\n", (ulong) pbn, index,
- (ulong) bn);
- v++;
- h = index;
-
- /* process the child page */
- goto getPage;
-}
-
-
-/*
- * xtDisplayPage()
- *
- * function: display page
- */
-int xtDisplayPage(struct inode *ip, s64 bn, xtpage_t * p)
-{
- int rc = 0;
- xad_t *xad;
- s64 xaddr, xoff;
- int xlen, i, j;
-
- /* display page control */
- printf("bn:0x%lx flag:0x%x nextindex:%d\n",
- (ulong) bn, p->header.flag,
- le16_to_cpu(p->header.nextindex));
-
- /* display entries */
- xad = &p->xad[XTENTRYSTART];
- for (i = XTENTRYSTART, j = 1; i < le16_to_cpu(p->header.nextindex);
- i++, xad++, j++) {
- xoff = offsetXAD(xad);
- xaddr = addressXAD(xad);
- xlen = lengthXAD(xad);
- printf("\t[%d] 0x%lx:0x%lx(0x%x)", i, (ulong) xoff,
- (ulong) xaddr, xlen);
-
- if (j == 4) {
- printf("\n");
- j = 0;
- }
- }
-
- printf("\n");
-}
-#endif /* _JFS_DEBUG_XTREE */
-
-
-#ifdef _JFS_WIP
-/*
- * xtGather()
- *
- * function:
- * traverse for allocation acquiring tlock at commit time
- * (vs at the time of update) logging backward top down
- *
- * note:
- * problem - establishing that all new allocation have been
- * processed both for append and random write in sparse file
- * at the current entry at the current subtree root page
- *
- */
-int xtGather(btree_t *t)
-{
- int rc = 0;
- xtpage_t *p;
- u64 bn;
- int index;
- btentry_t *e;
- struct btstack btstack;
- struct btsf *parent;
-
- /* clear stack */
- BT_CLR(&btstack);
-
- /*
- * start with root
- *
- * root resides in the inode
- */
- bn = 0;
- XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
- if (rc)
- return rc;
-
- /* new root is NOT pointed by a new entry
- if (p->header.flag & NEW)
- allocate new page lock;
- write a NEWPAGE log;
- */
-
- dopage:
- /*
- * first access of each page:
- */
- /* process entries backward from last index */
- index = le16_to_cpu(p->header.nextindex) - 1;
-
- if (p->header.flag & BT_LEAF) {
- /*
- * first access of each leaf page
- */
- /* process leaf page entries backward */
- for (; index >= XTENTRYSTART; index--) {
- e = &p->xad[index];
- /*
- * if newpage, log NEWPAGE.
- *
- if (e->flag & XAD_NEW) {
- nfound =+ entry->length;
- update current page lock for the entry;
- newpage(entry);
- *
- * if moved, log move.
- *
- } else if (e->flag & XAD_MOVED) {
- reset flag;
- update current page lock for the entry;
- }
- */
- }
-
- /* unpin the leaf page */
- XT_PUTPAGE(mp);
-
- /*
- * go back up to the parent page
- */
- getParent:
- /* restore parent entry for the current child page */
- if ((parent = BT_POP(&btstack)) == NULL)
- /* current page must have been root */
- return 0;
-
- if ((index = parent->index) == XTENTRYSTART) {
- /*
- * parent page scan completed
- */
- /* go back up to the parent page */
- goto getParent;
- } else {
- /*
- * parent page has entries remaining
- */
- /* get back the parent page */
- bn = parent->bn;
- XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
- if (rc)
- return -EIO;
-
- /* first subroot page which
- * covers all new allocated blocks
- * itself not new/modified.
- * (if modified from split of descendent,
- * go down path of split page)
-
- if (nfound == nnew &&
- !(p->header.flag & (NEW | MOD)))
- exit scan;
- */
-
- /* process parent page entries backward */
- index--;
- }
- } else {
- /*
- * first access of each internal page
- */
- }
-
- /*
- * internal page: go down to child page of current entry
- */
-
- /* save current parent entry for the child page */
- BT_PUSH(&btstack, bn, index);
-
- /* get current entry for the child page */
- e = &p->xad[index];
-
- /*
- * first access of each internal entry:
- */
- /*
- * if new entry, log btree_tnewentry.
- *
- if (e->flag & XAD_NEW)
- update parent page lock for the entry;
- */
-
- /* release parent page */
- XT_PUTPAGE(mp);
-
- /* get child page */
- bn = e->bn;
- XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
- if (rc)
- return rc;
-
- /*
- * first access of each non-root page:
- */
- /*
- * if new, log btree_newpage.
- *
- if (p->header.flag & NEW)
- allocate new page lock;
- write a NEWPAGE log (next, prev);
- */
-
- /* process the child page */
- goto dopage;
-
- out:
- return 0;
-}
-#endif /* _JFS_WIP */
-
-
#ifdef CONFIG_JFS_STATISTICS
int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length,
int *eof, void *data)
git://ftp.safe.ca / safe / jmp / linux-2.6 / blobdiff