|
1 package com.jofti.btree;
2
3 import java.io.Serializable  ;
4
5 import org.apache.commons.logging.Log;
6 import org.apache.commons.logging.LogFactory;
7
8 import com.jofti.core.IStoreKey;
9 import com.jofti.core.IStoreManager;
10 import com.jofti.exception.JoftiException;
11 import com.jofti.store.Page;
12 import com.jofti.store.StoreWrapper;
13
14
27 public class PagedLeafNode extends AbstractLeafNode implements Leaf,
28 Serializable
29 {
30
31
34 private static final long serialVersionUID = -5295978203948185278L;
35
36 Page pageData = null;
37
38 private static Log log = LogFactory.getLog(PagedLeafNode.class);
39
40 transient IStoreManager manager = null;
41
42 IStoreKey key = null;
43
44 private boolean dirty = false;
45
46 public PagedLeafNode(IStoreManager manager, IStoreKey key)
47 {
48
49 this.manager = manager;
50 this.key = key;
51
52 }
53
54
57 public void setEntries(Object [] temp)
58 {
59
60
62 }
63
64
68 public void setPageEntries(IPage temp)
69 {
70
71 try {
72 dirty = true;
73
74 key.setNumber(entryNumber);
75 setPage(temp);
76
77 } catch (Throwable e) {
78
79 throw new RuntimeException (e);
80
81 }
82
83 }
84
85
88 protected void removeEntries()
89 {
90
91 try {
92
93 manager.remove(key, null);
94 dirty = false;
95 } catch (JoftiException e) {
96
97 log.error("Unable to remove for node", e);
98
99 }
100
101 }
102
103 protected void setPage(IPage page) throws JoftiException
104 {
105 if (dirty) {
106
107 key.setNumber(entryNumber);
108 manager.store(key, page);
109 dirty = false;
110 key.setNewKey(false);
111 }
112 }
113
114 protected void removePage(IPage page)
115 {
116
117 key.setNumber(entryNumber);
118
119 try {
120 manager.remove(key, page);
121 } catch (Throwable t) {
122 System.out.println("unable to remove " + page);
123 }
124 dirty = false;
125 key.setNewKey(false);
126 }
127
128 protected IPage getPage()
129 {
130
131 StoreWrapper wrapper = null;
132 try {
133 wrapper = manager.retrieve(key);
134
135 } catch (Throwable e) {
136 while (e.getCause() != null) {
137 System.err.println(e);
138 e = e.getCause();
139 }
140
141 throw new RuntimeException (e);
142 }
143 key = wrapper.key;
144
145 return wrapper.page;
146
147 }
148
149 public LeafNodeEntry getEntry(Comparable value)
150 {
151 if (entryNumber == 0) {
152 return null;
153 }
154
155 IPage page = getPage();
157 LeafNodeEntry entry = indexedBinaryRetrieve(page, value);
158 manager.releasePage(key, page);
159 return entry;
160
161 }
162
163 protected Object [] realGetEntries()
164 {
165
166 if (dirty) {
167 log.error("Dirty node retrieval - Unable to get entries for node");
170 return null;
171 }
172 Object [] entries = null;
173
174 try {
175
176 StoreWrapper wrapper = manager.retrieve(key);
177 key = wrapper.key;
178 if (entries == null) {
180 throw new JoftiException("null returned for entries");
181 }
182 if (entryNumber != 0 && entries[entryNumber - 1] == null) {
183 int tempCount = 0;
184 for (int i = entryNumber - 1; i >= 0; i--) {
185 if (entries[i] != null) {
186 tempCount = i;
187 break;
188 }
189 }
190 throw new JoftiException("expected " + entryNumber + " got "
191 + tempCount + " for " + key);
192 }
193
194 } catch (JoftiException e) {
195
196 log.error("Unable to get entries for node", e);
197
198 }
199
200 return entries;
201
202 }
203
204
205
206 public boolean equals(Object obj)
207 {
208 try {
209 PagedLeafNode temp = (PagedLeafNode) obj;
210 return key.equals(temp.key);
211 } catch (Exception e) {
212 }
214 return false;
215 }
216
217 public int hashCode()
218 {
219 return key.hashCode();
220 }
221
222 protected LeafNodeEntry indexedBinaryRetrieve(IPage page, Object obj)
223 {
224 int i = 0;
225 int size = entryNumber;
226 for (int j = size - 1; i <= j;) {
227 int k = i + j >> 1;
228 LeafNodeEntry obj1 = page.getEntry(k);
229
230
231 int l = obj1.getValue().compareTo(obj);
232 if (l < 0)
233 i = k + 1;
234 else if (l > 0)
235 j = k - 1;
236 else
237 return obj1;
238 }
239
240 return null;
241 }
242
243 protected int indexedBinaryLocate(IPage page, Object obj)
244 {
245
246 int low = 0;
247 int high = entryNumber - 1;
248
249 LeafNodeEntry entry = null;
250 while (low <= high) {
251 int mid = (low + high) >> 1;
252
253 entry = page.getEntry(mid);
254
255 int cmp = entry.compareTo(obj);
256
257 if (cmp < 0)
258 low = mid + 1;
259 else if (cmp > 0)
260 high = mid - 1;
261 else
262 return mid; }
264 return -(low + 1);
266 }
267
268 public boolean deleteEntry(NodeEntry entry)
269 {
270 resetNextNode();
271 IPage page = getPage();
272 if (entry == null || entry.getValue() == null) {
273 return false;
274 }
275 if (entryNumber == 0) {
276 return false;
277 } else {
278 int result = indexedBinaryLocate(page, entry);
279 if (result >= 0) {
280 LeafNodeEntry listEntry = page.getEntry(result);
281
282 listEntry
283 .removeAllIds(((LeafNodeEntry) entry).getUniqueIdSet());
284
285 if (listEntry.getUniqueIdSize() == 0) {
286
287
288 page.removeEntry(result);
289 entryNumber--;
291 if (entryNumber == 0) {
293 rightValue = BTree.MIN_RIGHT_VALUE;
294 removePage(page);
295
296 } else {
297
298 LeafNodeEntry tempEntry = page
299 .getEntry(entryNumber - 1);
300
301 rightValue = tempEntry.getValue();
302 dirty = true;
303 try {
304 setPage(page);
305 } catch (JoftiException e) {
306 throw new RuntimeException (e);
307 }
308 }
309
310 return true;
311 } else {
312 try {
313
314 page.updateEntry(result, listEntry);
315 dirty = true;
316 setPage(page);
317 } catch (JoftiException e) {
318 throw new RuntimeException ("Unable to remove entry ", e);
319 }
320 }
321 }
322 }
323
324 return false;
325
326 }
327
328 public Object [] insertEntry(NodeEntry entry) throws JoftiException
329 {
330
331 LeafNodeEntry leafEntry = (LeafNodeEntry) entry;
332 IPage page = getPage();
333
334 if (entry == null || entry.getValue() == null) {
335 throw new JoftiException("Null node entry cannot be inserted");
336 }
337
338 resetNextNode();
339 if (entryNumber == 0) {
340 entryNumber++;
341 rightValue = entry.getValue();
342 dirty = true;
343
344 page.setEntry(0, leafEntry);
345
346 setPage(page);
347
348 return null;
349 } else if (rightValue.compareTo(entry.getValue()) >= 0) {
350
351 int result = indexedBinaryLocate(page, entry);
352
353 if (result < 0) {
354 int index = (-result) - 1;
356
357 page.setEntry(index, leafEntry);
358 entryNumber++;
359 dirty = true;
360 setPage(page);
361 return null;
362 } else {
363 LeafNodeEntry listEntry = page.getEntry(result);
364
365 listEntry.addUniqueIdSet(((LeafNodeEntry) entry)
366 .getUniqueIdSet());
367
368 page.updateEntry(result, listEntry);
369
370 dirty = true;
371 setPage(page);
372 return null;
373 }
374
375 }
376 throw new JoftiException("unable to insert " + entry.getValue()
377 + "as is bigger than current right value");
378
379 }
380
381 public Object [] getEntries()
382 {
383 Object [] objArr = null;
384 try {
385 IPage page = getPage();
386 objArr = new Object [entryNumber];
387 for (int i = 0; i < entryNumber; i++) {
388 LeafNodeEntry entry = page.getEntry(i);
389
390 objArr[i] = entry;
391
392 }
393 } catch (Throwable t) {
394 log.fatal("Error getting entries from node " + key + t);
395
396 }
397 return objArr;
398
399 }
400
401 public boolean contains(Comparable value)
402 {
403 if (rightValue == null) {
404 return false;
405 }
406
407 return rightValue.compareTo(value) >= 0;
408
409 }
410
411 public Node splitNode(Object [] entries) throws JoftiException
412 {
413
415 IPage page = getPage();
416
417 EntrySplitWrapper[] entriesList = manager.split(page, entryNumber);
418 Node newNode = NodeFactory.getInstance(manager).createLeafNode();
420 Comparable currentRight = rightValue;
422 EntrySplitWrapper newEntries = entriesList[1];
425 newNode.entryNumber = newEntries.size;
427
428 newNode.setRightValue(currentRight);
429 ((PagedLeafNode) newNode).setPageEntries((IPage) newEntries.entries);
430 newNode.setLinkNode(getLinkNode());
431
432 EntrySplitWrapper replacements = (EntrySplitWrapper) entriesList[0];
436 entryNumber = replacements.size;
440 IPage replacementPage = (IPage) replacements.entries;
441
442
443 setRightValue(replacementPage.getEntry(entryNumber - 1).getValue());
444
445 setPageEntries(replacementPage);
446 return newNode;
447 }
448
449 public boolean isLeaf()
450 {
451 return true;
452 }
453
454 public synchronized IStoreKey getKey()
455 {
456 return key;
457 }
458
459
460 public synchronized void setKey(IStoreKey key)
461 {
462 this.key = key;
463 }
464
465
466 }
467 |
Popular Tags |
Java API By Example, From Geeks To Geeks.