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