Relocation of btree iterators' scan positions after modifiation of the index outside the iterator added.
1.1 --- a/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreeListByKey.java Wed Jul 31 12:20:44 2002 +0000
1.2 +++ b/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreeListByKey.java Wed Jul 31 12:24:02 2002 +0000
1.3 @@ -1,3 +1,5 @@
1.4 +package org.netbeans.mdr.persistence.btreeimpl.btreeindex;
1.5 +
1.6 /*
1.7 * Sun Public License Notice
1.8 *
1.9 @@ -10,8 +12,6 @@
1.10 * Code is Sun Microsystems, Inc. Portions Copyright 1997-2001 Sun
1.11 * Microsystems, Inc. All Rights Reserved.
1.12 */
1.13 -package org.netbeans.mdr.persistence.btreeimpl.btreeindex;
1.14 -
1.15 import org.netbeans.mdr.persistence.*;
1.16 import java.util.*;
1.17 import java.text.*;
1.18 @@ -33,7 +33,7 @@
1.19 private byte[] key;
1.20 private Object objectKey;
1.21 private int listModCounter = 0;
1.22 -
1.23 +
1.24 BtreeListByKey(MultivaluedBtree btree, Object key) throws StorageException {
1.25
1.26 this.btree = btree;
1.27 @@ -84,14 +84,25 @@
1.28 public class BtreeListByKeyIterator extends Object
1.29 implements ListIterator {
1.30
1.31 + /* [TODO] Performance of next/previous operations should be improved by
1.32 + * implementing live scan position holder that reflects all changes done over
1.33 + * the index (for now, scan position relocations are required if the index is
1.34 + * modifed outside the iterator and btree pages storing data related to the
1.35 + * iterator are affected).
1.36 + */
1.37 +
1.38 /* Btree scan position */
1.39 private SearchResult current;
1.40 - /* Index of the last item returned. */
1.41 + /* Btree scan position of the leftmost entry matching the key */
1.42 + private SearchResult first;
1.43 + /* Index of the last item returned */
1.44 private int index;
1.45 private boolean empty;
1.46 private int modCount;
1.47 private SinglevaluedIndex repos;
1.48 private boolean itemAvailable = false;
1.49 + /* true if the available item has been retrieved by next operation */
1.50 + private boolean retrievedByNext = false;
1.51
1.52 BtreeListByKeyIterator(int startIndex, SinglevaluedIndex repos)
1.53 throws IndexOutOfBoundsException {
1.54 @@ -101,7 +112,8 @@
1.55 modCount = listModCounter;
1.56 index = -1;
1.57 current = btree.getLocation(key);
1.58 - current.entryNum--;
1.59 + first = new SearchResult (current);
1.60 + current.entryNum--;
1.61 if (!current.matched) {
1.62 empty = true;
1.63 }
1.64 @@ -122,11 +134,11 @@
1.65 }
1.66
1.67 public Object next() throws NoSuchElementException {
1.68 -
1.69 if (!moveForward()) {
1.70 throw new NoSuchElementException();
1.71 - }
1.72 + }
1.73 itemAvailable = true;
1.74 + retrievedByNext = true;
1.75 return getCurrentItem();
1.76 }
1.77
1.78 @@ -140,14 +152,15 @@
1.79 item = getCurrentItem();
1.80 moveBackward();
1.81 itemAvailable = true;
1.82 + retrievedByNext = false;
1.83 return item;
1.84 }
1.85
1.86 - public boolean hasNext() {
1.87 -
1.88 + public boolean hasNext() {
1.89 try {
1.90 btree.beginRead();
1.91 checkModCount();
1.92 + locateCurrentItem();
1.93 return BtreePage.hasNext(key, current);
1.94 } catch (StorageException e) {
1.95 throw new RuntimeStorageException(e);
1.96 @@ -165,6 +178,7 @@
1.97 try {
1.98 btree.beginRead();
1.99 checkModCount();
1.100 + locateCurrentItem();
1.101 BtreePage.getNext(key, current);
1.102 index++;
1.103 return current.matched;
1.104 @@ -176,11 +190,14 @@
1.105 }
1.106
1.107 private void moveBackward() {
1.108 -
1.109 try {
1.110 btree.beginRead();
1.111 checkModCount();
1.112 + locateCurrentItem();
1.113 + int tempEntryNum = current.entryNum;
1.114 BtreePage.getPrevious(key, current);
1.115 + if (!current.matched && (current.entryNum == tempEntryNum))
1.116 + current.entryNum--;
1.117 index--;
1.118 } catch (StorageException e) {
1.119 throw new RuntimeStorageException(e);
1.120 @@ -195,6 +212,7 @@
1.121 try {
1.122 btree.beginRead();
1.123 checkModCount();
1.124 + locateCurrentItem();
1.125 if (repos != null) {
1.126 result = btree.dataInfo.objectFromBuffer(
1.127 current.page.getData(current.entryNum), repos);
1.128 @@ -235,7 +253,8 @@
1.129 checkModCount ();
1.130 removeItem ();
1.131 itemAvailable = false;
1.132 - index--;
1.133 + if (retrievedByNext)
1.134 + index--;
1.135 listModCounter++;
1.136 modCount = listModCounter;
1.137 }
1.138 @@ -252,16 +271,17 @@
1.139 public void add(Object o) {
1.140 checkModCount ();
1.141 addItem (o);
1.142 - itemAvailable = false;
1.143 + itemAvailable = false;
1.144 index++;
1.145 listModCounter++;
1.146 modCount = listModCounter;
1.147 }
1.148
1.149 - private void setItem(Object o) {
1.150 - BtreePage.BtreeEntry entry = new BtreePage.BtreeEntry (key, btree.dataInfo.toBuffer (o));
1.151 + private void setItem(Object o) {
1.152 try {
1.153 btree.beginWrite();
1.154 + locateCurrentItem();
1.155 + BtreePage.BtreeEntry entry = new BtreePage.BtreeEntry (key, btree.dataInfo.toBuffer (o));
1.156 // since replace operation does not split pages in current implementation
1.157 // we can call replace directly on a page (instead of tree) to achieve a better performance
1.158 current.page.replace(entry, current.entryNum);
1.159 @@ -272,16 +292,24 @@
1.160 }
1.161 }
1.162
1.163 - private void removeItem() {
1.164 - BtreePage currentPage = current.page;
1.165 - int currentEntryNum = current.entryNum;
1.166 + private void removeItem() {
1.167 try {
1.168 btree.beginWrite();
1.169 - BtreePage.getPrevious(key, current);
1.170 - if (!current.matched && (current.entryNum == currentEntryNum))
1.171 - current.entryNum--;
1.172 - // delete does not merges pages, thus we can perform it directly on the page
1.173 - currentPage.delete(currentEntryNum, currentEntryNum);
1.174 + locateCurrentItem();
1.175 + SearchResult temp = new SearchResult (current);
1.176 + if (retrievedByNext) {
1.177 + BtreePage.getPrevious(key, current);
1.178 + if (!current.matched && (current.entryNum == temp.entryNum))
1.179 + current.entryNum--;
1.180 + } else {
1.181 + BtreePage.getNext(key, temp);
1.182 + }
1.183 + // delete does not merge pages, thus we can perform it directly on the page
1.184 + temp.page.delete(temp.entryNum, temp.entryNum);
1.185 + if ((retrievedByNext && (index == 0)) || (!retrievedByNext && (index == -1))) {
1.186 + first = new SearchResult(current);
1.187 + BtreePage.getNext(key, first);
1.188 + }
1.189 } catch (StorageException e) {
1.190 throw new RuntimeStorageException(e);
1.191 } finally {
1.192 @@ -292,17 +320,39 @@
1.193 private void addItem(Object o) {
1.194 try {
1.195 btree.beginWrite();
1.196 + locateCurrentItem();
1.197 BtreePage root = btree.pageSource.getPage(btree.rootPageId, btree);
1.198 root.put(key, btree.dataInfo.toBuffer (o), Btree.ADD, index + 1, current);
1.199 btree.pageSource.unpinPage(root);
1.200 - BtreePage.getNext(key, current);
1.201 + if (index == -1) {
1.202 + first = new SearchResult(current);
1.203 + }
1.204 + // BtreePage.getNext(key, current);
1.205 } catch (StorageException e) {
1.206 throw new RuntimeStorageException(e);
1.207 } finally {
1.208 btree.endWrite();
1.209 }
1.210 }
1.211 -
1.212 +
1.213 + private void locateCurrentItem() throws StorageException {
1.214 + SearchResult res = first.page.searchPage(key, first.entryNum);
1.215 + if ((first.entryNum != res.entryNum) || (first.page != res.page)) {
1.216 + first = res;
1.217 + current = new SearchResult (first);
1.218 + if (index == -1) {
1.219 + current.entryNum--;
1.220 + } else {
1.221 + first.page.findNth(current, key, index, false);
1.222 + }
1.223 + } else {
1.224 + if ((index > -1) && (current.page.compare(key, current.entryNum) != EntryTypeInfo.EQUAL)) {
1.225 + current = new SearchResult (first);
1.226 + first.page.findNth(current, key, index, false);
1.227 + }
1.228 + }
1.229 + }
1.230 +
1.231 } // BtreeListByKeyIterator class
1.232
1.233 /**
2.1 --- a/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreePage.java Wed Jul 31 12:20:44 2002 +0000
2.2 +++ b/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreePage.java Wed Jul 31 12:24:02 2002 +0000
2.3 @@ -476,7 +476,7 @@
2.4 * add operation, we're also adding a new last entry. In either case,
2.5 * set searchResult to point to the correct insert location and return true.
2.6 */
2.7 - private boolean findNth(SearchResult searchResult, byte[] key,
2.8 + boolean findNth(SearchResult searchResult, byte[] key,
2.9 int target, boolean adding) throws StorageException {
2.10 BtreePage page;
2.11
2.12 @@ -854,6 +854,24 @@
2.13 }
2.14
2.15 /*
2.16 + * Search the page for an entry matching the specified key. The leftmost
2.17 + * matching entry is returned, which may or may not be on this page. If
2.18 + * no match was found, the location where this key would be inserted is
2.19 + * returned.
2.20 + *
2.21 + * This methods first of all checks if the leftmost matching entry is on the
2.22 + * specified position. If not, standard search page method is called.
2.23 + */
2.24 +
2.25 + SearchResult searchPage(byte[] key, int position) throws StorageException {
2.26 + if (compare(key, position) == EntryTypeInfo.EQUAL) {
2.27 + if ((position == 0) || (compare(key, position - 1) != EntryTypeInfo.EQUAL))
2.28 + return new SearchResult(true, position, this);
2.29 + }
2.30 + return searchPage(key);
2.31 + }
2.32 +
2.33 + /*
2.34 * Get the previous entry, starting from the passed in result. The
2.35 * result is updated to point to the previous entry and indicate whether
2.36 * it matched the key. If key is null, it is considered a match as long
2.37 @@ -1128,7 +1146,7 @@
2.38 * EntryTypeInfo.GREATER if search key is greater than entry's key
2.39 * EntryTypeInfo.LESS if search key is less than entry's key
2.40 */
2.41 - private byte compare(byte[] key, int entryNum) {
2.42 + byte compare(byte[] key, int entryNum) {
2.43
2.44 // The leftmost key on the leftmost page at a non-leaf level
2.45 // is forced to compare as less than any search key. This avoids