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