00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 package org.openmobileis.database.fastobjectdb.db.index;
00030
00031 import java.io.IOException;
00032 import java.lang.reflect.*;
00033
00034 import org.openmobileis.common.util.collection.LongArray;
00035 import org.openmobileis.common.util.log.LogManager;
00036 import org.openmobileis.database.fastobjectdb.FODBIndexDescriptor;
00037 import org.openmobileis.database.fastobjectdb.FODBLongIndexDescriptor;
00038 import org.openmobileis.database.fastobjectdb.db.exception.FODBException;
00039 import org.openmobileis.database.fastobjectdb.db.exception.FODBQueryException;
00040 import org.openmobileis.database.fastobjectdb.db.index.node.LongNode;
00041 import org.openmobileis.database.fastobjectdb.db.index.node.Node;
00042 import org.openmobileis.database.fastobjectdb.db.query.soda.SodaIndexComparator;
00043 import org.openmobileis.database.fastobjectdb.db.query.soda.SodaLongIndexComparator;
00044 import org.openmobileis.database.fastobjectdb.db.store.FODBCollectionIndexFile;
00045
00049 public abstract class FODBLongIndex extends FODBIndex {
00050
00051 public FODBLongIndex(FODBIndexHeader newHeader, FODBCollectionIndexFile cFile, AccessibleObject accObj) throws FODBException {
00052 super(newHeader, cFile, accObj);
00053 }
00054
00055 public FODBLongIndex(FODBLongIndexDescriptor descriptor, FODBCollectionIndexFile cFile, AccessibleObject accObj) throws FODBException {
00056 super(descriptor, cFile, accObj);
00057 }
00058
00059 protected void specificDescriptorVerifications(FODBIndexDescriptor descriptor) throws FODBException {
00060 if (!(descriptor instanceof FODBLongIndexDescriptor)) {
00061 throw new FODBException("Internal Error");
00062 }
00063
00064 FODBLongIndexDescriptor desc = (FODBLongIndexDescriptor) descriptor;
00065
00066
00067 if (desc.getOrder() < 3)
00068 throw new FODBException("ERROR Bad BTree order. BTree order must be more than 3");
00069 }
00070
00071 protected Node initRoot(FODBIndexDescriptor descriptor) throws FODBException {
00072 FODBLongIndexDescriptor desc = (FODBLongIndexDescriptor) descriptor;
00073 return new LongNode(desc.getOrder());
00074 }
00075
00076 public Object getKey(Object obj) throws FODBException {
00077 long key = 0;
00078
00079 if (accessObj instanceof Method) {
00080 try {
00081 key = ((Long) (((Method) accessObj).invoke(obj, new Object[0]))).longValue();
00082 } catch (InvocationTargetException ex) {
00083 throw new FODBException("Unable to execute index's method", ex);
00084 } catch (IllegalAccessException ex) {
00085 throw new FODBException("Unable to execute index's method", ex);
00086 }
00087 } else {
00088 try {
00089 key = (((Field) accessObj).getLong(obj));
00090 } catch (IllegalAccessException ex) {
00091 throw new FODBException("Unable to access index's field", ex);
00092 }
00093 }
00094
00095 return new Long(key);
00096 }
00097
00098 protected void insertKey(Object obj, long ptr) throws IOException, ClassNotFoundException, FODBException {
00099 long key = ((Long)obj).longValue();
00100
00101
00102 LongNode root = (LongNode) this.readRoot();
00103 SearchResult searchResult = new SearchResult();
00104 searchResult = this.search(root, key, searchResult);
00105
00106 if (searchResult.found) {
00107
00108
00109 if (getType() == UNIQUE) {
00110 throw new FODBException("Entry already present in Unique Index");
00111 }
00112
00113
00114
00115
00116
00117
00118
00119 this.writeKeyPtr(searchResult.node, searchResult.pos, ptr);
00120 return;
00121 }
00122 if (getType() != UNIQUE) {
00123 ptr = ((FODBMultipleLongIndex) this).createPtrArray(ptr);
00124 }
00125 LongNode btreenode = (LongNode) searchResult.node;
00126 boolean flag;
00127 for (flag = btreenode.pushInLeaf(key, searchResult.pos, ptr);
00128 flag && btreenode.parentPtr != Node.NO_NODE;
00129 btreenode = (LongNode) colFile.readNode(btreenode.parentPtr)) {
00130 int i1 = this.minKey;
00131 LongNode btreenode1 = new LongNode(header.descriptor.getOrder());
00132 btreenode1.parentPtr = btreenode.parentPtr;
00133 int i;
00134 for (i = i1 + 1; i < btreenode1.getMaxNbKey(); i++) {
00135 btreenode1.setKeyPtrAtPos(btreenode.getKeyAtPos(i), btreenode.getNodePtrAtPos(i), i - i1 - 1);
00136 btreenode1.branchs[i - i1 - 1] = btreenode.branchs[i];
00137 }
00138
00139 btreenode1.branchs[i - i1 - 1] = btreenode.branchs[i];
00140 btreenode1.nbKey = btreenode1.getMaxNbKey() - i1 - 1;
00141 colFile.writeNode(btreenode1, header);
00142 if (btreenode1.branchs[0] != Node.NO_NODE) {
00143 for (int j = 0; j <= btreenode1.nbKey; j++) {
00144 LongNode tempNode = (LongNode) colFile.readNode(btreenode1.branchs[j]);
00145 tempNode.parentPtr = btreenode1.filePtr;
00146 colFile.writeNode(tempNode, header);
00147 }
00148
00149 }
00150
00151 btreenode.nbKey = this.minKey;
00152 colFile.writeNode(btreenode, header);
00153 long newkey = btreenode.getKeyAtPos(i1);
00154 long keyptr = btreenode.getNodePtrAtPos(i1);
00155
00156 LongNode parentNode = (LongNode) colFile.readNode(btreenode.parentPtr);
00157 SearchResult searchResult1 = parentNode.searchNode(newkey, searchResult);
00158 flag = parentNode.promote(newkey, keyptr, searchResult1.pos, btreenode1.filePtr);
00159 colFile.writeNode(parentNode, header);
00160
00161 }
00162 colFile.writeNode(btreenode, header);
00163
00164 if (!flag)
00165 return;
00166
00167
00168 root = (LongNode) this.readRoot();
00169 LongNode parent = new LongNode(header.descriptor.getOrder());
00170 colFile.writeNode(parent, header);
00171 int j1 = this.minKey;
00172 LongNode btreenode2 = new LongNode(header.descriptor.getOrder());
00173 btreenode2.parentPtr = parent.filePtr;
00174 int k;
00175 for (k = j1 + 1; k < btreenode2.getMaxNbKey(); k++) {
00176 btreenode2.setKeyPtrAtPos(root.getKeyAtPos(k), root.getNodePtrAtPos(k), k - j1 - 1);
00177 btreenode2.branchs[k - j1 - 1] = root.branchs[k];
00178 }
00179
00180 btreenode2.branchs[k - j1 - 1] = root.branchs[k];
00181 btreenode2.nbKey = btreenode2.getMaxNbKey() - j1 - 1;
00182 colFile.writeNode(btreenode2, header);
00183 if (btreenode2.branchs[0] != Node.NO_NODE) {
00184 for (int l = 0; l <= btreenode2.nbKey; l++) {
00185 LongNode tempNode = (LongNode) colFile.readNode(btreenode2.branchs[l]);
00186 tempNode.parentPtr = btreenode2.filePtr;
00187 colFile.writeNode(tempNode, header);
00188 }
00189 }
00190 root.nbKey = this.minKey;
00191 root.parentPtr = parent.filePtr;
00192 colFile.writeNode(root, header);
00193 parent.nbKey = 1;
00194 parent.setKeyPtrAtPos(root.getKeyAtPos(j1), root.getNodePtrAtPos(j1), 0);
00195 parent.branchs[0] = root.filePtr;
00196 parent.branchs[1] = btreenode2.filePtr;
00197 colFile.writeNode(parent, header);
00198 return;
00199 }
00200
00201
00202
00203
00204
00205
00206 private SearchResult search(LongNode node, long key, SearchResult searchResult) throws IOException, ClassNotFoundException {
00207 int pos = 0;
00208
00209 if (node.nbKey == 0) {
00210 searchResult.found = false;
00211 searchResult.node = node;
00212 searchResult.pos = pos;
00213 return searchResult;
00214 }
00215 searchResult = node.searchNode(key, searchResult);
00216 if (searchResult.found)
00217 return searchResult;
00218 if (searchResult.node.branchs[0] == Node.NO_NODE) {
00219 return searchResult;
00220 } else {
00221 LongNode newNode = (LongNode) colFile.readNode(node.branchs[searchResult.pos]);
00222
00223 if (newNode.parentPtr != node.filePtr) {
00224 LogManager.traceError(0, "ERROR BAD NODE PARENT");
00225 }
00226 searchResult = this.search(newNode, key, searchResult);
00227 return searchResult;
00228 }
00229 }
00230
00231 public SearchResult getNodeForKey(Object key) throws FODBException {
00232 try {
00233 LongNode root = (LongNode) this.readRoot();
00234 SearchResult searchResult = new SearchResult();
00235 searchResult = this.search(root, ((Long)key).longValue(), searchResult);
00236 return searchResult;
00237 } catch (Throwable ex) {
00238 throw new FODBException(ex);
00239 }
00240 }
00241
00242 public long[] query(SodaIndexComparator comparator) throws FODBQueryException {
00243 try {
00244
00245 LongArray array = new LongArray(15);
00246 LongNode root = (LongNode) this.readRoot();
00247 switch (comparator.getSearchAlgo()) {
00248 case SodaIndexComparator.INF_EQUALS_TRAVERSAL :
00249 this.searchLikeInfEquals(root, array, (SodaLongIndexComparator)comparator);
00250 break;
00251 case SodaIndexComparator.SUP_EQUALS_TRAVERSAL :
00252 this.searchLikeSupEquals(root, array, (SodaLongIndexComparator)comparator);
00253 break;
00254 case SodaIndexComparator.FULL_TRAVERSAL :
00255 this.searchLikeFull(root, array, (SodaLongIndexComparator)comparator);
00256 break;
00257 default :
00258 break;
00259 }
00260
00261
00262 int size = array.size();
00263
00264 if (size == 0) {
00265 return new long[0];
00266 }
00267
00268 return array.toArray();
00269 } catch (Throwable ex) {
00270 throw new FODBQueryException(ex);
00271 }
00272 }
00273
00274
00275 private void searchLikeInfEquals(LongNode node, LongArray array, SodaLongIndexComparator comparator) throws IOException, ClassNotFoundException {
00276 int pos = 0;
00277
00278 if (node.nbKey == 0) {
00279 return;
00280 }
00281
00282 while (true) {
00283 if (pos == node.nbKey)
00284 break;
00285 if (comparator.isSelected(node.getKeyAtPos(pos))) {
00286 addSearchResult(node, pos, array);
00287 if (node.branchs[pos] != Node.NO_NODE) {
00288 searchLikeInfEquals((LongNode)colFile.readNode(node.branchs[pos]), array, comparator);
00289 }
00290 ++pos;
00291 } else {
00292 int comp = comparator.compareTo(node.getKeyAtPos(pos));
00293 if (comp < 0)
00294 ++pos;
00295 else
00296 break;
00297 }
00298 }
00299
00300 if (node.branchs[pos] == Node.NO_NODE) {
00301 return;
00302 } else {
00303 searchLikeInfEquals((LongNode)colFile.readNode(node.branchs[pos]), array, comparator);
00304 }
00305 }
00306
00307
00308 private void searchLikeSupEquals(LongNode node, LongArray array, SodaLongIndexComparator comparator) throws IOException, ClassNotFoundException {
00309 int pos = node.nbKey;
00310
00311 if (node.nbKey == 0) {
00312 return;
00313 }
00314
00315 while (true) {
00316 if (pos == 0)
00317 break;
00318 if (comparator.isSelected(node.getKeyAtPos(pos-1))) {
00319 addSearchResult(node, pos-1, array);
00320 if (node.branchs[pos] != Node.NO_NODE) {
00321 searchLikeSupEquals((LongNode)colFile.readNode(node.branchs[pos]), array, comparator);
00322 }
00323 --pos;
00324 } else {
00325 int comp = comparator.compareTo(node.getKeyAtPos(pos-1));
00326 if (comp < 0)
00327 --pos;
00328 else
00329 break;
00330 }
00331 }
00332
00333 if (node.branchs[pos] == Node.NO_NODE) {
00334 return;
00335 } else {
00336 searchLikeSupEquals((LongNode)colFile.readNode(node.branchs[pos]), array, comparator);
00337 }
00338 }
00339
00340 private void searchLikeFull(LongNode pg, LongArray array, SodaLongIndexComparator comparator) throws IOException, ClassNotFoundException {
00341 int pos = 0;
00342
00343 if (pg.nbKey == 0) {
00344 return;
00345 }
00346
00347 while (true) {
00348 if (pos == pg.nbKey) {
00349 break;
00350 }
00351 if (comparator.isSelected(pg.getKeyAtPos(pos))) {
00352 addSearchResult(pg, pos, array);
00353 }
00354
00355 if (pg.branchs[pos] != Node.NO_NODE) {
00356 searchLikeFull((LongNode) colFile.readNode(pg.branchs[pos]), array, comparator);
00357 }
00358
00359 ++pos;
00360 }
00361
00362 if (pg.branchs[pos] == Node.NO_NODE) {
00363 return;
00364 } else {
00365 searchLikeFull((LongNode) colFile.readNode(pg.branchs[pos]), array, comparator);
00366 }
00367 }
00368
00369 protected boolean deleteKey(Object obj, long dbptr) throws IOException, ClassNotFoundException, FODBException {
00370 long key = ((Long)obj).longValue();
00371
00372
00373 LongNode root = (LongNode) this.readRoot();
00374 SearchResult searchResult = new SearchResult();
00375 searchResult = this.search(root, key, searchResult);
00376 if (!searchResult.found) {
00377 return false;
00378 }
00379 boolean empty = this.removeKeyPtr(searchResult.node, searchResult.pos, dbptr);
00380 if (!empty) {
00381 return true;
00382 }
00383
00384 LongNode btreenode = (LongNode) searchResult.node;
00385 if (btreenode.branchs[0] != Node.NO_NODE) {
00386 btreenode = (LongNode) colFile.readNode(btreenode.branchs[searchResult.pos + 1]);
00387 while (btreenode.branchs[0] != Node.NO_NODE) {
00388 btreenode = (LongNode) colFile.readNode(btreenode.branchs[0]);
00389 }
00390 LongNode resultNode = (LongNode) searchResult.node;
00391 resultNode.setKeyPtrAtPos(btreenode.getKeyAtPos(0), btreenode.getNodePtrAtPos(0), searchResult.pos);
00392 colFile.writeNode(resultNode, header);
00393 searchResult.node = btreenode;
00394 searchResult.pos = 0;
00395 }
00396 btreenode.removeKeyAtPpos(searchResult.pos);
00397 colFile.writeNode(btreenode, header);
00398 for (boolean flag = btreenode.nbKey < this.minKey; flag && (btreenode.parentPtr != Node.NO_NODE); flag = btreenode.nbKey < this.minKey) {
00399
00400 int i = 0;
00401 LongNode parentNode = (LongNode) colFile.readNode(btreenode.parentPtr);
00402 for (i = 0; parentNode.branchs[i] != btreenode.filePtr; i++);
00403 this.restore(parentNode, i);
00404 btreenode = parentNode;
00405 }
00406
00407 if (btreenode.parentPtr != Node.NO_NODE)
00408 return true;
00409 if (btreenode.nbKey > 0)
00410 return true;
00411
00412 if (btreenode.branchs[0] != Node.NO_NODE) {
00413 LongNode firstChild = (LongNode) colFile.readNode(root.branchs[0]);
00414 if (firstChild.nbKey > 0) {
00415 firstChild.parentPtr = Node.NO_NODE;
00416 colFile.writeNode(firstChild, header);
00417 colFile.deleteNode(btreenode);
00418 return true;
00419 }
00420 }
00421 return true;
00422 }
00423
00424
00425
00426 private void moveLeft(LongNode node, int i) throws IOException, ClassNotFoundException {
00427 LongNode btreenode = (LongNode) colFile.readNode(node.branchs[i]);
00428 btreenode.nbKey++;
00429 btreenode.setKeyPtrAtPos(node.getKeyAtPos(i), node.getNodePtrAtPos(i), btreenode.nbKey - 1);
00430 LongNode branch = (LongNode) colFile.readNode(node.branchs[i + 1]);
00431 btreenode.branchs[btreenode.nbKey] = branch.branchs[0];
00432 colFile.writeNode(btreenode, header);
00433 if (btreenode.branchs[btreenode.nbKey] != Node.NO_NODE) {
00434 LongNode tempNode = (LongNode) colFile.readNode(btreenode.branchs[btreenode.nbKey]);
00435 tempNode.parentPtr = btreenode.filePtr;
00436 colFile.writeNode(tempNode, header);
00437 }
00438 btreenode = branch;
00439 node.setKeyPtrAtPos(btreenode.getKeyAtPos(0), btreenode.getNodePtrAtPos(0), i);
00440 colFile.writeNode(node, header);
00441
00442 for (int j = 0; j < btreenode.nbKey - 1; j++) {
00443 btreenode.setKeyPtrAtPos(btreenode.getKeyAtPos(j + 1), btreenode.getNodePtrAtPos(j + 1), j);
00444 btreenode.branchs[j] = btreenode.branchs[j + 1];
00445 }
00446
00447 btreenode.branchs[btreenode.nbKey - 1] = btreenode.branchs[btreenode.nbKey];
00448 btreenode.nbKey--;
00449 colFile.writeNode(btreenode, header);
00450 }
00451
00452 private void moveRight(LongNode node, int pos) throws IOException, ClassNotFoundException {
00453 LongNode rightBranch = (LongNode) colFile.readNode(node.branchs[pos + 1]);
00454 rightBranch.branchs[rightBranch.nbKey + 1] = rightBranch.branchs[rightBranch.nbKey];
00455 for (int j = rightBranch.nbKey - 1; j >= 0; j--) {
00456 rightBranch.setKeyPtrAtPos(rightBranch.getKeyAtPos(j), rightBranch.getNodePtrAtPos(j), j + 1);
00457 rightBranch.branchs[j + 1] = rightBranch.branchs[j];
00458 }
00459
00460 rightBranch.nbKey++;
00461 rightBranch.setKeyPtrAtPos(node.getKeyAtPos(pos), node.getNodePtrAtPos(pos), 0);
00462 LongNode leftBranch = (LongNode) colFile.readNode(node.branchs[pos]);
00463 node.setKeyPtrAtPos(leftBranch.getKeyAtPos(leftBranch.nbKey - 1), leftBranch.getNodePtrAtPos(leftBranch.nbKey - 1), pos);
00464 rightBranch.branchs[0] = leftBranch.branchs[leftBranch.nbKey];
00465 colFile.writeNode(rightBranch, header);
00466 if (rightBranch.branchs[0] != Node.NO_NODE) {
00467 LongNode tempNode = (LongNode) colFile.readNode(rightBranch.branchs[0]);
00468 tempNode.parentPtr = rightBranch.filePtr;
00469 colFile.writeNode(tempNode, header);
00470 }
00471
00472 leftBranch.nbKey--;
00473 colFile.writeNode(leftBranch, header);
00474 colFile.writeNode(node, header);
00475 }
00476
00477 private void combine(LongNode node, int pos) throws IOException, ClassNotFoundException {
00478 LongNode rightBranch = (LongNode) colFile.readNode(node.branchs[pos + 1]);
00479 LongNode leftBranch = (LongNode) colFile.readNode(node.branchs[pos]);
00480 leftBranch.nbKey++;
00481 leftBranch.setKeyPtrAtPos(node.getKeyAtPos(pos), node.getNodePtrAtPos(pos), leftBranch.nbKey - 1);
00482 leftBranch.branchs[leftBranch.nbKey] = rightBranch.branchs[0];
00483 for (int j = 0; j < rightBranch.nbKey; j++) {
00484 leftBranch.nbKey++;
00485 leftBranch.setKeyPtrAtPos(rightBranch.getKeyAtPos(j), rightBranch.getNodePtrAtPos(j), leftBranch.nbKey - 1);
00486 leftBranch.branchs[leftBranch.nbKey] = rightBranch.branchs[j + 1];
00487 }
00488
00489 colFile.writeNode(leftBranch, header);
00490 if (leftBranch.branchs[0] != Node.NO_NODE) {
00491 for (int k = 0; k <= leftBranch.nbKey; k++) {
00492 LongNode tempNode = (LongNode) colFile.readNode(leftBranch.branchs[k]);
00493 tempNode.parentPtr = leftBranch.filePtr;
00494 colFile.writeNode(tempNode, header);
00495 }
00496 }
00497
00498 node.removeKeyAtPpos(pos);
00499 colFile.writeNode(node, header);
00500 colFile.deleteNode(rightBranch);
00501 }
00502
00503 private void restore(LongNode node, int pos) throws IOException, ClassNotFoundException {
00504 if (pos == 0) {
00505 LongNode child = (LongNode) colFile.readNode(node.branchs[1]);
00506 if (child.nbKey > this.minKey) {
00507 this.moveLeft(node, 0);
00508 } else {
00509 this.combine(node, 0);
00510 }
00511 } else if (pos == node.nbKey) {
00512 LongNode child = (LongNode) colFile.readNode(node.branchs[pos - 1]);
00513 if (child.nbKey > this.minKey) {
00514 moveRight(node, pos - 1);
00515 } else {
00516 combine(node, pos - 1);
00517 }
00518 } else {
00519 LongNode childleft = (LongNode) colFile.readNode(node.branchs[pos - 1]);
00520 LongNode childrigth = (LongNode) colFile.readNode(node.branchs[pos + 1]);
00521 if (childleft.nbKey > this.minKey) {
00522 moveRight(node, pos - 1);
00523 } else if (childrigth.nbKey > this.minKey) {
00524 moveLeft(node, pos);
00525 } else {
00526 combine(node, pos);
00527 }
00528 }
00529 }
00530
00531 public org.openmobileis.common.util.collection.Array getArrayKey(Object obj) throws FODBException{
00532 org.openmobileis.common.util.collection.Array keys=new org.openmobileis.common.util.collection.Array();
00533 long [] keyArray;
00534 Long key;
00535 if (accessObj instanceof Method) {
00536 try {
00537 keyArray = (long[]) (((Method) accessObj).invoke(obj, new Object[0]));
00538 for(int i=0;i<keyArray.length;i++){
00539 key=new Long(keyArray[i]);
00540 keys.add(key);
00541 }
00542 }catch (InvocationTargetException ex) {
00543 throw new FODBException("Unable to execute index's method", ex);
00544 } catch (IllegalAccessException ex) {
00545 throw new FODBException("Unable to execute index's method", ex);
00546 }
00547 }else{
00548 try{
00549 keyArray = (long[])((Field) accessObj).get(obj);
00550 for(int i=0;i<keyArray.length;i++){
00551 key=new Long(keyArray[i]);
00552 keys.add(key);
00553 }
00554 } catch (IllegalAccessException ex) {
00555 throw new FODBException("Unable to access index's field", ex);
00556 }
00557 }
00558 return keys;
00559 }
00560 protected abstract void writeKeyPtr(Node pg, int pos, long newptr) throws IOException, ClassNotFoundException;
00561 protected abstract void addSearchResult(LongNode pg, int pos, LongArray array) throws IOException, ClassNotFoundException;
00562
00563 protected abstract boolean removeKeyPtr(Node pg, int pos, long pointer) throws IOException, ClassNotFoundException;
00564 }