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