1.1 --- a/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreePage.java Tue Dec 21 13:12:42 2004 +0000
1.2 +++ b/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreePage.java Mon Jan 03 13:43:41 2005 +0000
1.3 @@ -770,90 +770,100 @@
1.4 }
1.5 return pageSource.getPage(getData(childEntry), btree);
1.6 }
1.7 -
1.8 +
1.9 /*
1.10 * Search the page for an entry matching the specified key. The leftmost
1.11 * matching entry is returned, which may or may not be on this page. If
1.12 * no match was found, the location where this key would be inserted is
1.13 * returned.
1.14 */
1.15 -
1.16 private SearchResult searchPage(byte[] key) throws StorageException {
1.17 -
1.18 - int base;
1.19 - int limit;
1.20 - int midpoint;
1.21 - byte compare;
1.22 - SearchResult test, result;
1.23 -
1.24 - // Binary search the entries on this page
1.25 - base = 0;
1.26 - result = null;
1.27 + int base;
1.28 + int limit;
1.29 + int midpoint;
1.30 + byte compare;
1.31 + SearchResult test, result;
1.32
1.33 - if (numEntries() > 0) {
1.34 - for (base=0, limit=numEntries(); limit > 0; limit = limit/2) {
1.35 -
1.36 - midpoint = base + limit/2;
1.37 -
1.38 - if ((compare = compare(key, midpoint))
1.39 - == EntryTypeInfo.EQUAL) {
1.40 - result = new SearchResult(true, midpoint, this);
1.41 - break;
1.42 - } else if (compare == EntryTypeInfo.GREATER) {
1.43 - base = midpoint + 1;
1.44 - limit--;
1.45 - }
1.46 - }
1.47 - }
1.48 -
1.49 - if (result == null) {
1.50 - result = new SearchResult(false, base, this);
1.51 - }
1.52 -
1.53 - // If this is a non-unique index, we're not done.
1.54 -
1.55 - if (!btree.uniqueKeys) {
1.56 -
1.57 - test = new SearchResult(result);
1.58 -
1.59 - if (!result.matched && isLeaf()) {
1.60 - // If there was no match, and this is a leaf page,
1.61 - // there could be a match on an adjoining page (this
1.62 - // could happen if there were duplicate entries
1.63 - // on this page that were deleted).
1.64 - if (result.entryNum == 0) {
1.65 - getPrevious(key, test);
1.66 - if (test.matched) {
1.67 - test.copy(result);
1.68 - }
1.69 - }
1.70 - if (!result.matched &&
1.71 - result.entryNum == numEntries()) {
1.72 - result.copy(test);
1.73 - getNext(key, test);
1.74 - if (test.matched) {
1.75 - test.copy(result);
1.76 - }
1.77 - }
1.78 - }
1.79 - // Get the leftmost match
1.80 - if (result.matched) {
1.81 - result.copy(test);
1.82 - do {
1.83 - getPrevious(key, test);
1.84 - if (test.matched) {
1.85 - if ((test.page != result.page)
1.86 - && (result.page != this)) {
1.87 - pageSource.unpinPage(result.page);
1.88 - }
1.89 - test.copy(result);
1.90 - }
1.91 - } while (test.matched);
1.92 - }
1.93 - }
1.94 - return result;
1.95 + // Binary search the entries on this page
1.96 + base = 0;
1.97 + result = null;
1.98 + if (numEntries() > 0) {
1.99 + for (base = 0, limit = numEntries(); limit > 0; limit = limit/2) {
1.100 +
1.101 + midpoint = base + limit/2;
1.102 +
1.103 + if ((compare = compare(key, midpoint)) == EntryTypeInfo.EQUAL) {
1.104 + result = new SearchResult(true, midpoint, this);
1.105 + if (btree.uniqueKeys) break;
1.106 + } else if (compare == EntryTypeInfo.GREATER) {
1.107 + base = midpoint + 1;
1.108 + limit--;
1.109 + }
1.110 + }
1.111 + }
1.112 +
1.113 + if (result == null) {
1.114 + result = new SearchResult(false, base, this);
1.115 + }
1.116 +
1.117 + // If this is a non-unique index, we're not done.
1.118 + if (!btree.uniqueKeys) {
1.119 +
1.120 + test = new SearchResult(result);
1.121 +
1.122 + if (!result.matched && isLeaf()) {
1.123 + // If there was no match, and this is a leaf page,
1.124 + // there could be a match on an adjoining page (this
1.125 + // could happen if there were duplicate entries
1.126 + // on this page that were deleted).
1.127 + if (result.entryNum == 0) {
1.128 + getPrevious(key, test);
1.129 + if (test.matched) {
1.130 + //System.err.println("matching on previous page");
1.131 + test.copy(result);
1.132 + }
1.133 + }
1.134 + if (!result.matched &&
1.135 + result.entryNum == numEntries()) {
1.136 + //System.err.println("matching on next page");
1.137 + result.copy(test);
1.138 + getNext(key, test);
1.139 + if (test.matched) {
1.140 + test.copy(result);
1.141 + }
1.142 + }
1.143 + }
1.144 + // Get the leftmost match
1.145 + if (result.matched) {
1.146 + result.copy(test);
1.147 + do {
1.148 + // XXX waaay to slow to linearly traverse them.
1.149 + getPrevious(key, test);
1.150 + if (test.matched) {
1.151 + if ((test.page != result.page) && (result.page != this)) {
1.152 + pageSource.unpinPage(result.page);
1.153 + }
1.154 + if (test.page != result.page) { // moved across page
1.155 + // find the leftmost page
1.156 + SearchResult test2 = new SearchResult(test);
1.157 + do {
1.158 + test2.copy(test);
1.159 + test2.entryNum = 0;
1.160 + getPrevious(key, test2); // try previous page
1.161 + } while (test2.matched);
1.162 + // test contains the leftmost page now
1.163 + result = test.page.searchPage(key);
1.164 + result.skipCount = -1;
1.165 + return result;
1.166 + }
1.167 + test.copy(result);
1.168 + }
1.169 + } while (test.matched);
1.170 + }
1.171 + }
1.172 + return result;
1.173 }
1.174 -
1.175 +
1.176 /*
1.177 * Search the page for an entry matching the specified key. The leftmost
1.178 * matching entry is returned, which may or may not be on this page. If