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