KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > indexing > IndexNode


1 /*******************************************************************************
2  * Copyright (c) 2000, 2005 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.core.internal.indexing;
12
13 import java.util.HashSet JavaDoc;
14
15 class IndexNode extends IndexedStoreObject {
16
17     /* needed for all stored objects */
18     public static final int SIZE = MAXIMUM_OBJECT_SIZE;
19     public static final int TYPE = 3;
20
21     /* field definitions */
22     private static final int EntriesFieldOffset = 64;
23     private static final int EntriesFieldSize = SIZE - EntriesFieldOffset;
24     private static final FieldDef NodeType = new FieldDef(FieldDef.F_INT, 2, 2);
25     private static final FieldDef AnchorAddress = new FieldDef(FieldDef.F_BYTES, 4, 4);
26     private static final FieldDef ParentAddress = new FieldDef(FieldDef.F_BYTES, 8, 4);
27     private static final FieldDef PreviousAddress = new FieldDef(FieldDef.F_BYTES, 12, 4);
28     private static final FieldDef NextAddress = new FieldDef(FieldDef.F_BYTES, 16, 4);
29     private static final FieldDef NumberOfEntries = new FieldDef(FieldDef.F_INT, 20, 2);
30     private static final FieldDef UsedSpace = new FieldDef(FieldDef.F_INT, 22, 2);
31     private static final FieldDef UsedSpaceMax = new FieldDef(FieldDef.F_INT, 24, 2);
32     private static final FieldDef EntriesField = new FieldDef(FieldDef.F_BYTES, EntriesFieldOffset, EntriesFieldSize);
33
34     /* field values */
35     private int nodeType;
36     private ObjectAddress anchorAddress;
37     private ObjectAddress parentAddress;
38     private ObjectAddress previousAddress;
39     private ObjectAddress nextAddress;
40     private int numberOfEntries;
41     private int usedSpace;
42     private int usedSpaceMax;
43     private Field entriesField;
44
45     /* types of nodes in the index */
46     private static final int RootNode = 1;
47     private static final int InteriorNode = 2;
48     private static final int LeafNode = 3;
49
50     /* miscellaneous constants */
51     private static final int DescriptorLength = 6;
52
53     /* cursors in this node */
54     private HashSet JavaDoc cursors = new HashSet JavaDoc();
55
56     /**
57      * Reconstructs a node from a field.
58      */
59     IndexNode(Field f, ObjectStore store, ObjectAddress address) throws ObjectStoreException {
60         super(f, store, address);
61     }
62
63     /**
64      * Constructor that creates a root node.
65      */
66     IndexNode(ObjectAddress anchorAddress) {
67         super();
68         this.anchorAddress = anchorAddress;
69         this.parentAddress = ObjectAddress.Null;
70         this.previousAddress = ObjectAddress.Null;
71         this.nextAddress = ObjectAddress.Null;
72         this.usedSpace = 0;
73         this.usedSpaceMax = 0;
74         this.numberOfEntries = 0;
75         this.nodeType = RootNode;
76         this.entriesField = new Field(SIZE - EntriesFieldOffset);
77     }
78
79     /**
80      * Constructor that creates an interior node.
81      */
82     IndexNode(ObjectAddress anchorAddress, ObjectAddress parentAddress) {
83         this(anchorAddress);
84         this.parentAddress = parentAddress;
85         this.nodeType = InteriorNode;
86     }
87
88     /**
89      * Constructor that creates a leaf node.
90      */
91     IndexNode(ObjectAddress anchorAddress, ObjectAddress parentAddress, ObjectAddress previousAddress, ObjectAddress nextAddress) {
92         this(anchorAddress, parentAddress);
93         this.previousAddress = previousAddress;
94         this.nextAddress = nextAddress;
95         this.nodeType = LeafNode;
96     }
97
98     /**
99      * Registers a cursor with this node.
100      */
101     void addCursor(IndexCursor cursor) {
102         cursors.add(cursor);
103     }
104
105     /**
106      * Compares the key at a particular entry to a byte array.
107      */
108     private int compareEntryToKey(int entryNumber, byte[] key) throws IndexedStoreException {
109         Field keyField = new Field(key);
110         Field entryKeyField = getKeyField(entryNumber);
111         return entryKeyField.compareTo(keyField);
112     }
113
114     /**
115      * Compresses the space in the entries area of the node.
116      */
117     private void compress() throws IndexedStoreException {
118
119         /* some preliminaries */
120         int entriesLength = entriesField.length();
121         int descriptorBlockSize = numberOfEntries * DescriptorLength;
122
123         /* need to make a copy of the entries in the area, this will compress it */
124         Field f2 = new Field(entriesField.length());
125         copyEntries(entriesField, 0, numberOfEntries, f2);
126
127         /* copy the entries area back to the node and modify the usedSpaceMax to reflect the compression */
128         entriesField.put(f2.get());
129         usedSpaceMax = usedSpace;
130
131         /* clear the space in the between the descriptor array and the entries heap */
132         int freeBlockSize = entriesLength - (descriptorBlockSize + usedSpaceMax);
133         Field f3 = entriesField.subfield(descriptorBlockSize, freeBlockSize);
134         f3.clear();
135         setChanged();
136     }
137
138     /**
139      * Compresses the space in the entries area of the node if the free space block
140      * is smaller than the given threshold.
141      */
142     private void compress(int threshold) throws IndexedStoreException {
143         int entriesLength = entriesField.length();
144         int descriptorBlockSize = numberOfEntries * DescriptorLength;
145         int freeBlockSize = entriesLength - (descriptorBlockSize + usedSpaceMax);
146         if (freeBlockSize >= threshold)
147             return;
148         compress();
149     }
150
151     /**
152      * Copies entries from one Field to another. Fields are assumed to contain an array of descriptors at the
153      * low end and a heap of (key,value) pairs at the high end.
154      */
155     private static int copyEntries(Field sourceField, int sourceIndex, int numberOfEntries, Field targetField) {
156
157         Pointer tDescriptor = targetField.pointTo(0);
158         Pointer sDescriptor = sourceField.pointTo(sourceIndex * DescriptorLength);
159         int tEntryOffset = targetField.length();
160
161         // for each descriptor make a new one in the new area and copy its (key,value) entry
162 for (int i = 0; i < numberOfEntries; i++) {
163
164             // extract information from old descriptor
165 int sEntryOffset = sDescriptor.getField(0, 2).getUInt();
166             int keyLength = sDescriptor.getField(2, 2).getUInt();
167             int valueLength = sDescriptor.getField(4, 2).getUInt();
168             int entryLength = keyLength + valueLength;
169             Field sEntry = sourceField.subfield(sEntryOffset, entryLength);
170
171             // copy the (key,value) entry from the old to the new space
172 tEntryOffset -= entryLength;
173             Field tEntry = targetField.subfield(tEntryOffset, entryLength);
174             tEntry.put(sEntry.get());
175
176             // create a new descriptor
177 tDescriptor.getField(0, 2).put(tEntryOffset);
178             tDescriptor.getField(2, 2).put(keyLength);
179             tDescriptor.getField(4, 2).put(valueLength);
180
181             // on to the next one
182 tDescriptor.inc(DescriptorLength);
183             sDescriptor.inc(DescriptorLength);
184         }
185         return targetField.length() - tEntryOffset;
186     }
187
188     /**
189      * Places the contents of the fields into the buffer.
190      * Subclasses should implement and call super.
191      */
192     protected void insertValues(Field f) {
193         super.insertValues(f);
194         f.put(AnchorAddress, anchorAddress);
195         f.put(ParentAddress, parentAddress);
196         f.put(NextAddress, nextAddress);
197         f.put(PreviousAddress, previousAddress);
198         f.put(NodeType, nodeType);
199         f.put(NumberOfEntries, numberOfEntries);
200         f.put(UsedSpace, usedSpace);
201         f.put(UsedSpaceMax, usedSpaceMax);
202         f.put(EntriesField, entriesField);
203     }
204
205     /**
206      * Causes the node to remove its children from the store.
207      */
208     void destroyChildren() throws IndexedStoreException {
209         if (!isLeaf()) {
210             for (int i = 0; i < numberOfEntries; i++) {
211                 ObjectAddress childNodeAddress = new ObjectAddress(getValue(i));
212                 IndexNode childNode = acquireNode(childNodeAddress);
213                 childNode.destroyChildren();
214                 childNode.release();
215                 removeObject(childNodeAddress);
216             }
217         }
218     }
219
220     /**
221      * Places a cursor and the first entry greater than or equal to a key.
222      */
223     void find(byte[] key, IndexCursor cursor) throws IndexedStoreException {
224         int i;
225         i = findLastEntryLT(key);
226         if (isLeaf()) {
227             cursor.set(address, i + 1);
228         } else if (i >= 0) {
229             IndexNode childNode = acquireNode(new ObjectAddress(getValue(i)));
230             childNode.find(key, cursor);
231             childNode.release();
232         } else if (numberOfEntries > 0) {
233             IndexNode childNode = acquireNode(new ObjectAddress(getValue(0)));
234             childNode.find(key, cursor);
235             childNode.release();
236         } else {
237             cursor.reset();
238         }
239     }
240
241     /**
242      * Places a cursor at the first entry of a node.
243      */
244     void findFirstEntry(IndexCursor cursor) throws IndexedStoreException {
245         if (numberOfEntries == 0) {
246             cursor.reset();
247         } else if (!isLeaf()) {
248             IndexNode childNode = acquireNode(new ObjectAddress(getValue(0)));
249             childNode.findFirstEntry(cursor);
250             childNode.release();
251         } else {
252             cursor.set(address, 0);
253         }
254     }
255
256     /**
257      * Returns the index of the first entry greater than a key.
258      */
259     private int findFirstEntryGT(byte[] key) throws IndexedStoreException {
260         int lo = 0;
261         int hi = numberOfEntries - 1;
262         while (lo <= hi) {
263             int i = (lo + hi) / 2;
264             int c = compareEntryToKey(i, key);
265             if (c <= 0) {
266                 lo = i + 1;
267             } else {
268                 hi = i - 1;
269             }
270         }
271         return lo;
272     }
273
274     /**
275      * Places a cursor at the last entry of a node.
276      */
277     void findLastEntry(IndexCursor cursor) throws IndexedStoreException {
278         if (numberOfEntries == 0) {
279             cursor.reset();
280             return;
281         }
282         int i = numberOfEntries - 1;
283         if (!isLeaf()) {
284             IndexNode childNode = acquireNode(new ObjectAddress(getValue(i)));
285             childNode.findLastEntry(cursor);
286             childNode.release();
287         } else {
288             cursor.set(address, i);
289         }
290     }
291
292     /**
293      * Returns the index of the last entry less than a key.
294      */
295     private int findLastEntryLT(byte[] key) throws IndexedStoreException {
296         int lo = 0;
297         int hi = numberOfEntries - 1;
298         Field keyField = new Field(key);
299         while (lo <= hi) {
300             int i = (lo + hi) / 2;
301             int c = getKeyField(i).compareTo(keyField);
302             if (c < 0) {
303                 lo = i + 1;
304             } else {
305                 hi = i - 1;
306             }
307         }
308         return hi;
309     }
310
311     /**
312      * Returns the descriptor field for the node entry at a given index.
313      */
314     private Field getDescriptor(int i) {
315         return entriesField.subfield(i * DescriptorLength, DescriptorLength);
316     }
317
318     /**
319      * Returns the entire array of entry descriptors.
320      */
321     private FieldArray getDescriptorArray() {
322         return entriesField.pointTo(0).getArray(DescriptorLength, DescriptorLength, numberOfEntries);
323     }
324
325     private Field getEntriesField() {
326         return entriesField;
327     }
328
329     /**
330      * Returns the value of the key for an entry at a given index.
331      */
332     byte[] getKey(int i) {
333         return getKeyField(i).get();
334     }
335
336     /**
337      * Returns a Field covering the key for an entry at a given index.
338      */
339     private Field getKeyField(int i) {
340         // Field descriptor = getDescriptor(i);
341 // int keyOffset = descriptor.subfield(0, 2).getUInt();
342 // int keyLength = descriptor.subfield(2, 2).getUInt();
343 // return entriesField.subfield(keyOffset, keyLength);
344 //above is the original code that created three garbage field objects
345 //below is the optimized code that only creates one field object
346 int descriptorOff = i * DescriptorLength;
347         Buffer buffer = entriesField.buffer;
348         return entriesField.subfield(buffer.getUInt(descriptorOff, 2), //these bytes hold the key offset
349 buffer.getUInt(descriptorOff + 2, 2));//these bytes hold the key length
350 }
351
352     /**
353      * Returns a Field covering the (key, value) pair for an entry at a given index.
354      */
355     private Field getKeyValueField(int i) {
356         Field descriptor = getDescriptor(i);
357         int offset = descriptor.subfield(0, 2).getUInt();
358         int keyLength = descriptor.subfield(2, 2).getUInt();
359         int valueLength = descriptor.subfield(4, 2).getUInt();
360         return entriesField.subfield(offset, keyLength + valueLength);
361     }
362
363     /**
364      * Returns the lowest key in the node. If none, returns an empty byte arrray.
365      */
366     private byte[] getLowKey() {
367         if (numberOfEntries == 0)
368             return new byte[0];
369         return getKey(0);
370     }
371
372     /**
373      * Returns the minimum size of this object's instance -- including its type field.
374      * Subclasses should override.
375      */
376     protected int getMinimumSize() {
377         return SIZE;
378     }
379
380     ObjectAddress getNextAddress() {
381         return nextAddress;
382     }
383
384     int getNumberOfEntries() {
385         return numberOfEntries;
386     }
387
388     /**
389      * Returns the number of nodes in this subtree (this one plus all descendants).
390      */
391     int getNumberOfNodes() throws IndexedStoreException {
392         if (isLeaf())
393             return 1;
394         int sum = 0;
395         for (int i = 0; i < numberOfEntries; i++) {
396             ObjectAddress childAddress = new ObjectAddress(getValue(i));
397             IndexNode childNode = acquireNode(childAddress);
398             sum += childNode.getNumberOfNodes();
399             childNode.release();
400         }
401         return sum + 1;
402     }
403
404     ObjectAddress getParentAddress() {
405         return parentAddress;
406     }
407
408     ObjectAddress getPreviousAddress() {
409         return previousAddress;
410     }
411
412     /**
413      * Returns the required type of this class of object.
414      * Subclasses must override.
415      */
416     protected int getRequiredType() {
417         return TYPE;
418     }
419
420     private int getUsedSpace() {
421         return usedSpace;
422     }
423
424     /**
425      * Returns the value for an entry at a given index.
426      */
427     byte[] getValue(int i) {
428         return getValueField(i).get();
429     }
430
431     /**
432      * Returns a Field covering the value for an entry at a given index.
433      */
434     private Field getValueField(int i) {
435         Field descriptor = getDescriptor(i);
436         int keyOffset = descriptor.subfield(0, 2).getUInt();
437         int keyLength = descriptor.subfield(2, 2).getUInt();
438         int valueLength = descriptor.subfield(4, 2).getUInt();
439         int valueOffset = keyOffset + keyLength;
440         return entriesField.subfield(valueOffset, valueLength);
441     }
442
443     /**
444      * Inserts an entry into the node. If this was inserted in slot 0, then we must update the parent
445      * node's low key. If this was a leaf node then we must update the anchor'ss number of entries and
446      * adjust any cursors for this node. This may also cause a split.
447      *
448      * Implementation Note: Cannot use an iterator over the cursor set because
449      * notification of an insert may remove the cursor being notified from the cursor set.
450      */
451     void insertEntry(byte[] key, byte[] value) throws IndexedStoreException {
452         int i = findFirstEntryGT(key);
453         if (isLeaf()) {
454             insertEntryBefore(i, key, value);
455             Object JavaDoc[] cursorArray = cursors.toArray();
456             for (int j = 0; j < cursorArray.length; j++) {
457                 IndexCursor cursor = (IndexCursor) cursorArray[j];
458                 cursor.entryInserted(i);
459             }
460             IndexAnchor anchor = acquireAnchor(anchorAddress);
461             anchor.entryInserted(this);
462             anchor.release();
463         } else {
464             ObjectAddress childNodeAddress = null;
465             if (getNumberOfEntries() == 0) {
466                 IndexNode childNode = new IndexNode(anchorAddress, address, ObjectAddress.Null, ObjectAddress.Null);
467                 childNodeAddress = insertObject(childNode);
468             } else {
469                 childNodeAddress = new ObjectAddress(getValue(Math.max(0, (i - 1))));
470             }
471             IndexNode childNode = acquireNode(childNodeAddress);
472             childNode.insertEntry(key, value);
473             childNode.release();
474         }
475     }
476
477     /**
478      * Inserts a new (key, value) pair in front of the entry at the given index.
479      * If the node needs to be split, split it and then attempt the insert again. If this is a
480      * non-leaf node then the value is the address of a child. That child's parent address
481      * will be updated if that (key, value) is to be inserted into a new node.
482      */
483     private void insertEntryBefore(int i, byte[] key, byte[] value) throws IndexedStoreException {
484         Field entries = entriesField;
485         int entriesLength = entries.length();
486         int keyValueLength = key.length + value.length;
487         int neededSpace = keyValueLength + DescriptorLength;
488         int freeSpace = entriesLength - ((numberOfEntries * DescriptorLength) + usedSpace);
489         if (freeSpace < neededSpace) {
490             ObjectAddress newNodeAddress = split();
491             if (i > numberOfEntries) {
492                 if (!isLeaf()) {
493                     ObjectAddress childAddress = new ObjectAddress(value);
494                     IndexNode child = acquireNode(childAddress);
495                     child.setParentAddress(newNodeAddress);
496                     child.release();
497                 }
498                 IndexNode newNode = acquireNode(newNodeAddress);
499                 newNode.insertEntryBefore(i - getNumberOfEntries(), key, value);
500                 newNode.release();
501             } else {
502                 insertEntryBefore(i, key, value);
503             }
504             return;
505         }
506
507         /* place the value and key fields into the space */
508         compress(neededSpace);
509         Pointer p = entries.pointTo(entriesLength - usedSpaceMax);
510         p.dec(value.length).put(value);
511         p.dec(key.length).put(key);
512         usedSpaceMax += keyValueLength;
513         usedSpace += keyValueLength;
514
515         /* create a hole in the descriptor area for a new descriptor */
516         Field newDescriptor = getDescriptorArray().insert(i);
517         numberOfEntries++;
518
519         /* create a new descriptor */
520         newDescriptor.subfield(0, 2).put(entriesLength - usedSpaceMax);
521         newDescriptor.subfield(2, 2).put(key.length);
522         newDescriptor.subfield(4, 2).put(value.length);
523
524         /* update the parent key for this node if this was the 0th entry */
525         if (i == 0 && !parentAddress.isNull()) {
526             IndexNode parent = acquireNode(parentAddress);
527             if (numberOfEntries == 1) {
528                 parent.insertKeyForChild(address, key);
529             } else {
530                 parent.updateKeyForChild(getKey(1), address, key);
531             }
532             parent.release();
533         }
534         setChanged();
535     }
536
537     /**
538      * Inserts a child address into a non-leaf node. This may result in this node splitting.
539      */
540     private void insertKeyForChild(ObjectAddress childAddress, byte[] key) throws IndexedStoreException {
541         int i = findFirstEntryGT(key);
542         insertEntryBefore(i, key, childAddress.toByteArray());
543         if (i == 0 && !parentAddress.isNull()) {
544             IndexNode parent = acquireNode(parentAddress);
545             parent.updateKeyForChild(getKey(1), address, key);
546             parent.release();
547         }
548     }
549
550     boolean isInterior() {
551         return (nodeType == InteriorNode);
552     }
553
554     boolean isLeaf() {
555         return (nodeType == LeafNode);
556     }
557
558     boolean isRoot() {
559         return (nodeType == RootNode);
560     }
561
562     /**
563      * Places the contents of the buffer into the fields.
564      * Subclasses should implement and call super.
565      */
566     protected void extractValues(Field f) throws ObjectStoreException {
567         super.extractValues(f);
568         anchorAddress = new ObjectAddress(f.get(AnchorAddress));
569         parentAddress = new ObjectAddress(f.get(ParentAddress));
570         nextAddress = new ObjectAddress(f.get(NextAddress));
571         previousAddress = new ObjectAddress(f.get(PreviousAddress));
572         nodeType = f.getInt(NodeType);
573         numberOfEntries = f.getInt(NumberOfEntries);
574         usedSpace = f.getInt(UsedSpace);
575         usedSpaceMax = f.getInt(UsedSpaceMax);
576         entriesField = new Field(f.get(EntriesField));
577     }
578
579     /**
580      * Removes a cursor that is registered with this node.
581      */
582     void removeCursor(IndexCursor cursor) {
583         cursors.remove(cursor);
584     }
585
586     /**
587      * Removes the descriptor and key/value pair at the entry number given. This may
588      * result in the node becoming empty. The caller will need to take steps to plan for this.
589      */
590     void removeEntry(int i) throws IndexedStoreException {
591
592         /* remove the (key,value) entry */
593         byte[] key = getKey(i);
594         Field f = getKeyValueField(i);
595         f.clear();
596         usedSpace -= f.length();
597
598         /* remove the descriptor */
599         getDescriptorArray().remove(i);
600         numberOfEntries--;
601
602         /* if the 0th entry was removed, need to update the parent node with the new "low key" */
603         if (i == 0 && !parentAddress.isNull()) {
604             IndexNode parent = acquireNode(parentAddress);
605             if (numberOfEntries > 0) {
606                 parent.updateKeyForChild(key, address, getKey(0));
607             } else {
608                 parent.removeKeyForChild(address);
609             }
610             parent.release();
611         }
612
613         /* Notify any cursors and the anchor */
614         Object JavaDoc[] cursorArray = cursors.toArray();
615         for (int j = 0; j < cursorArray.length; j++) {
616             IndexCursor cursor = (IndexCursor) cursorArray[j];
617             cursor.entryRemoved(i);
618         }
619         IndexAnchor anchor = acquireAnchor(anchorAddress);
620         anchor.entryRemoved(this);
621         anchor.release();
622         setChanged();
623     }
624
625     /**
626      * Removes a child node address reference from a non-leaf node.
627      */
628     private void removeKeyForChild(ObjectAddress childAddress) throws IndexedStoreException {
629         Field childAddressField = new Field(childAddress);
630         int i = 0;
631         while (i < numberOfEntries) {
632             if (getValueField(i).compareTo(childAddressField) == 0)
633                 break;
634             i++;
635         }
636         if (i < numberOfEntries)
637             removeEntry(i);
638     }
639
640     private void setNextAddress(ObjectAddress address) {
641         nextAddress = address;
642         setChanged();
643     }
644
645     private void setNodeType(int nodeType) {
646         this.nodeType = nodeType;
647         setChanged();
648     }
649
650     private void setNumberOfEntries(int numberOfEntries) {
651         this.numberOfEntries = numberOfEntries;
652         setChanged();
653     }
654
655     private void setParentAddress(ObjectAddress address) {
656         parentAddress = address;
657         setChanged();
658     }
659
660     private void setPreviousAddress(ObjectAddress address) {
661         previousAddress = address;
662         setChanged();
663     }
664
665     private void setUsedSpace(int usedSpace) {
666         this.usedSpace = usedSpace;
667         setChanged();
668     }
669
670     private void setUsedSpaceMax(int usedSpaceMax) {
671         this.usedSpaceMax = usedSpaceMax;
672         setChanged();
673     }
674
675     /**
676      * Splits an index node. This split results in a new "low key" being placed in the parent. This may
677      * cause a parent node to split as well. Splits eventually propagate to the root node, cause it
678      * to split and a new root node to be created.
679      */
680     private ObjectAddress split() throws IndexedStoreException {
681
682         /* Nodes can only be split if there are at least 2 entries */
683         int n = numberOfEntries;
684         if (n < 2) {
685             throw new IndexedStoreException(IndexedStoreException.IndexNodeNotSplit);
686         }
687
688         /*
689          If this is a root node, need to make it an interior node and create a new parent root node.
690          Also need to modify the index anchor to indicate the new root node, and place this node (the old root node)
691          into the new root node. The new root node can always accept its first entry without splitting.
692          */
693         if (isRoot()) {
694             ObjectAddress newRootNodeAddress = insertObject(new IndexNode(anchorAddress));
695             parentAddress = newRootNodeAddress;
696             nodeType = InteriorNode;
697             IndexNode newRootNode = acquireNode(newRootNodeAddress);
698             newRootNode.insertKeyForChild(address, getLowKey());
699             newRootNode.release();
700             IndexAnchor anchor = acquireAnchor(anchorAddress);
701             anchor.setRootNodeAddress(newRootNodeAddress);
702             anchor.release();
703         }
704
705         /*
706          Get a new node, fill it with half the entries from this node, then compress this node. The
707          new node is created with current parent. However, the node at the current parentAddress may
708          split when the key is added to it for the new node. Non-leaf nodes compensate for this
709          by updating the newNode's parentAddress during the insertion.
710          */
711         ObjectAddress newNodeAddress = insertObject(new IndexNode(anchorAddress, parentAddress));
712         IndexNode newNode = acquireNode(newNodeAddress);
713         Field f1 = entriesField;
714         Field f2 = newNode.getEntriesField();
715         int k = n / 2;
716         newNode.setUsedSpace(copyEntries(f1, n - k, k, f2));
717         newNode.setUsedSpaceMax(newNode.getUsedSpace());
718         newNode.setNumberOfEntries(k);
719         usedSpace = usedSpace - newNode.getUsedSpace();
720         numberOfEntries = n - k;
721         compress();
722
723         /*
724          If this was a leaf node, need to set the previous and next pointers of the this node,
725          the new node, and the old "next" node.
726          */
727         if (isLeaf()) {
728             newNode.setNodeType(LeafNode);
729             newNode.setNextAddress(nextAddress);
730             newNode.setPreviousAddress(address);
731             if (!nextAddress.isNull()) {
732                 IndexNode nextNode = acquireNode(nextAddress);
733                 nextNode.setPreviousAddress(newNodeAddress);
734                 nextNode.release();
735             }
736             nextAddress = newNodeAddress;
737         }
738
739         /*
740          If this is a non-leaf node, need to update the parent addresses of any child nodes
741          of the new node. k is the number of entries in the new node.
742          */
743         if (!isLeaf()) {
744             for (int i = 0; i < k; i++) {
745                 ObjectAddress childAddress = new ObjectAddress(newNode.getValue(i));
746                 IndexNode childNode = acquireNode(childAddress);
747                 childNode.setParentAddress(newNodeAddress);
748                 childNode.release();
749             }
750         }
751
752         /*
753          Need to insert the new node's low key and address into the parent. This may
754          result in the parent splitting and having to update the parent address of this node.
755          */
756         IndexNode parentNode = acquireNode(parentAddress);
757         parentNode.insertKeyForChild(newNodeAddress, newNode.getLowKey());
758         parentNode.release();
759
760         /* Clean up. */
761         newNode.release();
762
763         /* Notify any cursors and the anchor */
764         Object JavaDoc[] cursorArray = cursors.toArray();
765         for (int j = 0; j < cursorArray.length; j++) {
766             IndexCursor cursor = (IndexCursor) cursorArray[j];
767             cursor.nodeSplit();
768         }
769         setChanged();
770         return newNodeAddress;
771     }
772
773     /**
774      * Unlinks a node from its parent and siblings. This does not modify the current node, but
775      * does modify all the nodes and anchors pointing to it.
776      */
777     void unlink() throws IndexedStoreException {
778         if (isRoot()) {
779             IndexAnchor anchor = acquireAnchor(anchorAddress);
780             anchor.setRootNodeAddress(ObjectAddress.Null);
781             anchor.release();
782         }
783         if (!parentAddress.isNull()) {
784             IndexNode parent = acquireNode(parentAddress);
785             parent.removeKeyForChild(address);
786             parent.release();
787         }
788         if (!nextAddress.isNull()) {
789             IndexNode next = acquireNode(nextAddress);
790             next.setPreviousAddress(previousAddress);
791             next.release();
792         }
793         if (!previousAddress.isNull()) {
794             IndexNode previous = acquireNode(previousAddress);
795             previous.setNextAddress(nextAddress);
796             previous.release();
797         }
798     }
799
800     /**
801      * Update the key and value at this entry to a new key and value. This may result in a node split.
802      * The caller must be able to recognize that the node has split and compensate for that.
803      */
804     private void updateEntry(int i, byte[] key, byte[] value) throws IndexedStoreException {
805
806         /*
807          If the node needs to be split, split it and then attempt the update again. Note that if
808          this is a non-leaf node the value is a child address. Unlike the insert of a key/value
809          pair, the child is already in the node, thus a split will update its parent address properly
810          and there is no need to handle that special case.
811          */
812         Field entries = entriesField;
813         int entriesLength = entries.length();
814         int newKeyValueLength = key.length + value.length;
815         int oldKeyValueLength = getKeyValueField(i).length();
816         int neededSpace = newKeyValueLength - oldKeyValueLength;
817         int freeSpace = entriesLength - ((numberOfEntries * DescriptorLength) + usedSpace);
818         if (freeSpace < neededSpace) {
819             ObjectAddress newNodeAddress = split();
820             if (i >= numberOfEntries) {
821                 IndexNode newNode = acquireNode(newNodeAddress);
822                 newNode.updateEntry(i - getNumberOfEntries(), key, value);
823                 newNode.release();
824             } else {
825                 updateEntry(i, key, value);
826             }
827             return;
828         }
829
830         /*
831          The node has enough free space to do the update.
832          Remove the old value and key fields from the space.
833          Clear the space used by the old value.
834          We can do this just by modifying the descriptor.
835          */
836         Field keyValueField = getKeyValueField(i);
837         keyValueField.clear();
838         Field descriptor = getDescriptor(i);
839         descriptor.clear();
840         usedSpace -= oldKeyValueLength;
841         compress(newKeyValueLength);
842
843         /* place the value and key fields into the space */
844         Pointer p = entries.pointTo(entriesLength - usedSpaceMax);
845         p.dec(value.length).put(value);
846         p.dec(key.length).put(key);
847         usedSpaceMax += newKeyValueLength;
848         usedSpace += newKeyValueLength;
849
850         /* update the descriptor */
851         descriptor.subfield(0, 2).put(entriesLength - usedSpaceMax);
852         descriptor.subfield(2, 2).put(key.length);
853         descriptor.subfield(4, 2).put(value.length);
854         setChanged();
855     }
856
857     /**
858      * Sets the key at this entry to a new key. This may result in a node split.
859      * The caller must be able to recognize that the node has split and compensate for that if necessary.
860      */
861     private void updateKeyAt(int i, byte[] key) throws IndexedStoreException {
862         updateEntry(i, key, getValue(i));
863     }
864
865     /**
866      * Updates the key of an (key,address) entry in a non-leaf node. The key must still be in order with respect
867      * to the other keys of the node.
868      */
869     private void updateKeyForChild(byte[] key, ObjectAddress childAddress, byte[] newKey) throws IndexedStoreException {
870         Field childAddressField = new Field(childAddress.toByteArray());
871         int i = findLastEntryLT(key) + 1;
872         while (i < numberOfEntries) {
873             if (getValueField(i).compareTo(childAddressField) == 0)
874                 break;
875             i++;
876         }
877         if (i < numberOfEntries) {
878             updateKeyAt(i, newKey);
879             if (i == 0 && !parentAddress.isNull()) {
880                 IndexNode parent = acquireNode(parentAddress);
881                 parent.updateKeyForChild(key, address, newKey);
882                 parent.release();
883             }
884         }
885     }
886
887     /**
888      * Sets the value at this entry to a new value. This may result in a node split.
889      * The caller must be able to recognize that the node has split and compensate for that.
890      */
891     void updateValueAt(int i, byte[] value) throws IndexedStoreException {
892         updateEntry(i, getKey(i), value);
893     }
894
895     public String JavaDoc toString() {
896         StringBuffer JavaDoc b = new StringBuffer JavaDoc();
897         if (isLeaf())
898             b.append("LeafNode"); //$NON-NLS-1$
899 if (isRoot())
900             b.append("RootNode"); //$NON-NLS-1$
901 if (isInterior())
902             b.append("InteriorNode"); //$NON-NLS-1$
903 b.append("\n Address = "); //$NON-NLS-1$
904 b.append(address);
905         b.append("\n AnchorAddress = "); //$NON-NLS-1$
906 b.append(anchorAddress);
907         b.append("\n ParentAddress = "); //$NON-NLS-1$
908 b.append(parentAddress);
909         b.append("\n PreviousAddress = "); //$NON-NLS-1$
910 b.append(previousAddress);
911         b.append("\n NextAddress = "); //$NON-NLS-1$
912 b.append(nextAddress);
913         b.append("\n NumberOfEntries = "); //$NON-NLS-1$
914 b.append(numberOfEntries);
915         b.append("\n UsedSpace = "); //$NON-NLS-1$
916 b.append(usedSpace);
917         b.append("\n UsedSpaceMax = "); //$NON-NLS-1$
918 b.append(usedSpaceMax);
919         return b.toString();
920     }
921
922 }
923
Popular Tags