001: package com.jofti.btree;
002:
003: import java.io.Serializable;
004:
005: import org.apache.commons.logging.Log;
006: import org.apache.commons.logging.LogFactory;
007:
008: import com.jofti.core.IStoreKey;
009: import com.jofti.core.IStoreManager;
010: import com.jofti.exception.JoftiException;
011: import com.jofti.store.Page;
012: import com.jofti.store.StoreWrapper;
013:
014: /**
015: * <p>
016: * A version of a {@link LeafNode} that pages its entries to and from disk. The entries are managed in an {@link IPage}
017: * which has operations performed upon it. Storage and retrieval is performed by an {@link IStoreManager}. This object uses the IPage as
018: * its transfer object.
019: * </p>
020: * <p>
021: * The Node does not keep a reference to the IPage inbetween operations and so a retrieval from the {@link IStoreManager} is required
022: * each time. The Manager is free to cache these objects in order to make this operation more performant.
023: * </p>
024: * @author steve Woodcock
025: * @version 1.36
026: */
027: public class PagedLeafNode extends AbstractLeafNode implements Leaf,
028: Serializable {
029:
030: /**
031: *
032: */
033: private static final long serialVersionUID = -5295978203948185278L;
034:
035: Page pageData = null;
036:
037: private static Log log = LogFactory.getLog(PagedLeafNode.class);
038:
039: transient IStoreManager manager = null;
040:
041: IStoreKey key = null;
042:
043: private boolean dirty = false;
044:
045: public PagedLeafNode(IStoreManager manager, IStoreKey key) {
046:
047: this .manager = manager;
048: this .key = key;
049:
050: }
051:
052: /* (non-Javadoc)
053: * @see com.jofti.btree.INode#setEntries(java.lang.Object[])
054: */
055: public void setEntries(Object[] temp) {
056:
057: // not used in paged node
058:
059: }
060:
061: /**
062: * Sets this node's page entries to be the IPage passed in.
063: * @param temp
064: */
065: public void setPageEntries(IPage temp) {
066:
067: try {
068: dirty = true;
069:
070: key.setNumber(entryNumber);
071: setPage(temp);
072:
073: } catch (Throwable e) {
074:
075: throw new RuntimeException(e);
076:
077: }
078:
079: }
080:
081: /**
082: * Removes all the entries in the node and propogate this to the underlying {@link IStoreManager}.
083: */
084: protected void removeEntries() {
085:
086: try {
087:
088: manager.remove(key, null);
089: dirty = false;
090: } catch (JoftiException e) {
091:
092: log.error("Unable to remove for node", e);
093:
094: }
095:
096: }
097:
098: protected void setPage(IPage page) throws JoftiException {
099: if (dirty) {
100:
101: key.setNumber(entryNumber);
102: manager.store(key, page);
103: dirty = false;
104: key.setNewKey(false);
105: }
106: }
107:
108: protected void removePage(IPage page) {
109:
110: key.setNumber(entryNumber);
111:
112: try {
113: manager.remove(key, page);
114: } catch (Throwable t) {
115: System.out.println("unable to remove " + page);
116: }
117: dirty = false;
118: key.setNewKey(false);
119: }
120:
121: protected IPage getPage() {
122:
123: StoreWrapper wrapper = null;
124: try {
125: wrapper = manager.retrieve(key);
126:
127: } catch (Throwable e) {
128: while (e.getCause() != null) {
129: System.err.println(e);
130: e = e.getCause();
131: }
132:
133: throw new RuntimeException(e);
134: }
135: key = wrapper.key;
136:
137: return wrapper.page;
138:
139: }
140:
141: public LeafNodeEntry getEntry(Comparable value) {
142: if (entryNumber == 0) {
143: return null;
144: }
145:
146: // look through list and see if we have a match
147: IPage page = getPage();
148: LeafNodeEntry entry = indexedBinaryRetrieve(page, value);
149: manager.releasePage(key, page);
150: return entry;
151:
152: }
153:
154: protected Object[] realGetEntries() {
155:
156: if (dirty) {
157: // we have a read before we have re-written - this is a problem
158: // and should not happen with the locking
159: log
160: .error("Dirty node retrieval - Unable to get entries for node");
161: return null;
162: }
163: Object[] entries = null;
164:
165: try {
166:
167: StoreWrapper wrapper = manager.retrieve(key);
168: key = wrapper.key;
169: // entries = wrapper.entries;
170: if (entries == null) {
171: throw new JoftiException("null returned for entries");
172: }
173: if (entryNumber != 0 && entries[entryNumber - 1] == null) {
174: int tempCount = 0;
175: for (int i = entryNumber - 1; i >= 0; i--) {
176: if (entries[i] != null) {
177: tempCount = i;
178: break;
179: }
180: }
181: throw new JoftiException("expected " + entryNumber
182: + " got " + tempCount + " for " + key);
183: }
184:
185: } catch (JoftiException e) {
186:
187: log.error("Unable to get entries for node", e);
188:
189: }
190:
191: return entries;
192:
193: }
194:
195: public boolean equals(Object obj) {
196: try {
197: PagedLeafNode temp = (PagedLeafNode) obj;
198: return key.equals(temp.key);
199: } catch (Exception e) {
200: // intentional
201: }
202: return false;
203: }
204:
205: public int hashCode() {
206: return key.hashCode();
207: }
208:
209: protected LeafNodeEntry indexedBinaryRetrieve(IPage page, Object obj) {
210: int i = 0;
211: int size = entryNumber;
212: for (int j = size - 1; i <= j;) {
213: int k = i + j >> 1;
214: LeafNodeEntry obj1 = page.getEntry(k);
215:
216: int l = obj1.getValue().compareTo(obj);
217: if (l < 0)
218: i = k + 1;
219: else if (l > 0)
220: j = k - 1;
221: else
222: return obj1;
223: }
224:
225: return null;
226: }
227:
228: protected int indexedBinaryLocate(IPage page, Object obj) {
229:
230: int low = 0;
231: int high = entryNumber - 1;
232:
233: LeafNodeEntry entry = null;
234: while (low <= high) {
235: int mid = (low + high) >> 1;
236:
237: entry = page.getEntry(mid);
238:
239: int cmp = entry.compareTo(obj);
240:
241: if (cmp < 0)
242: low = mid + 1;
243: else if (cmp > 0)
244: high = mid - 1;
245: else
246: return mid; // key found
247: }
248: return -(low + 1); // key not found
249:
250: }
251:
252: public boolean deleteEntry(NodeEntry entry) {
253: resetNextNode();
254: IPage page = getPage();
255: if (entry == null || entry.getValue() == null) {
256: return false;
257: }
258: if (entryNumber == 0) {
259: return false;
260: } else {
261: int result = indexedBinaryLocate(page, entry);
262: if (result >= 0) {
263: LeafNodeEntry listEntry = page.getEntry(result);
264:
265: listEntry.removeAllIds(((LeafNodeEntry) entry)
266: .getUniqueIdSet());
267:
268: if (listEntry.getUniqueIdSize() == 0) {
269:
270: page.removeEntry(result);
271: // Let gc do its work
272: entryNumber--;
273: // update the right value if we need to
274: if (entryNumber == 0) {
275: rightValue = BTree.MIN_RIGHT_VALUE;
276: removePage(page);
277:
278: } else {
279:
280: LeafNodeEntry tempEntry = page
281: .getEntry(entryNumber - 1);
282:
283: rightValue = tempEntry.getValue();
284: dirty = true;
285: try {
286: setPage(page);
287: } catch (JoftiException e) {
288: throw new RuntimeException(e);
289: }
290: }
291:
292: return true;
293: } else {
294: try {
295:
296: page.updateEntry(result, listEntry);
297: dirty = true;
298: setPage(page);
299: } catch (JoftiException e) {
300: throw new RuntimeException(
301: "Unable to remove entry ", e);
302: }
303: }
304: }
305: }
306:
307: return false;
308:
309: }
310:
311: public Object[] insertEntry(NodeEntry entry) throws JoftiException {
312:
313: LeafNodeEntry leafEntry = (LeafNodeEntry) entry;
314: IPage page = getPage();
315:
316: if (entry == null || entry.getValue() == null) {
317: throw new JoftiException(
318: "Null node entry cannot be inserted");
319: }
320:
321: resetNextNode();
322: if (entryNumber == 0) {
323: entryNumber++;
324: rightValue = entry.getValue();
325: dirty = true;
326:
327: page.setEntry(0, leafEntry);
328:
329: setPage(page);
330:
331: return null;
332: } else if (rightValue.compareTo(entry.getValue()) >= 0) {
333:
334: int result = indexedBinaryLocate(page, entry);
335:
336: if (result < 0) {
337: // we need to insert it
338: int index = (-result) - 1;
339:
340: page.setEntry(index, leafEntry);
341: entryNumber++;
342: dirty = true;
343: setPage(page);
344: return null;
345: } else {
346: LeafNodeEntry listEntry = page.getEntry(result);
347:
348: listEntry.addUniqueIdSet(((LeafNodeEntry) entry)
349: .getUniqueIdSet());
350:
351: page.updateEntry(result, listEntry);
352:
353: dirty = true;
354: setPage(page);
355: return null;
356: }
357:
358: }
359: throw new JoftiException("unable to insert " + entry.getValue()
360: + "as is bigger than current right value");
361:
362: }
363:
364: public Object[] getEntries() {
365: Object[] objArr = null;
366: try {
367: IPage page = getPage();
368: objArr = new Object[entryNumber];
369: for (int i = 0; i < entryNumber; i++) {
370: LeafNodeEntry entry = page.getEntry(i);
371:
372: objArr[i] = entry;
373:
374: }
375: } catch (Throwable t) {
376: log.fatal("Error getting entries from node " + key + t);
377:
378: }
379: return objArr;
380:
381: }
382:
383: public boolean contains(Comparable value) {
384: if (rightValue == null) {
385: return false;
386: }
387:
388: return rightValue.compareTo(value) >= 0;
389:
390: }
391:
392: public Node splitNode(Object[] entries) throws JoftiException {
393: // first insert the entry
394:
395: IPage page = getPage();
396:
397: EntrySplitWrapper[] entriesList = manager.split(page,
398: entryNumber);
399: //
400: Node newNode = NodeFactory.getInstance(manager)
401: .createLeafNode();
402: //
403: Comparable currentRight = rightValue;
404: //
405: //
406: EntrySplitWrapper newEntries = entriesList[1];
407: //
408: newNode.entryNumber = newEntries.size;
409:
410: newNode.setRightValue(currentRight);
411: ((PagedLeafNode) newNode)
412: .setPageEntries((IPage) newEntries.entries);
413: newNode.setLinkNode(getLinkNode());
414:
415: //
416: //// replace values in current node
417: //
418: EntrySplitWrapper replacements = (EntrySplitWrapper) entriesList[0];
419: //
420: //
421: //
422: entryNumber = replacements.size;
423: IPage replacementPage = (IPage) replacements.entries;
424:
425: setRightValue(replacementPage.getEntry(entryNumber - 1)
426: .getValue());
427:
428: setPageEntries(replacementPage);
429: return newNode;
430: }
431:
432: public boolean isLeaf() {
433: return true;
434: }
435:
436: public synchronized IStoreKey getKey() {
437: return key;
438: }
439:
440: public synchronized void setKey(IStoreKey key) {
441: this.key = key;
442: }
443:
444: }
|