1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree;
21
22
23 import java.io.IOException;
24 import java.lang.reflect.Array;
25
26 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
27 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
28
29
30
31
32
33
34
35
36
37
38
39 abstract class AbstractPage<K, V> implements Page<K, V>
40 {
41
42 protected transient BTree<K, V> btree;
43
44
45 protected KeyHolder<K>[] keys;
46
47
48 protected PageHolder<K, V>[] children;
49
50
51 protected int nbElems;
52
53
54 protected long revision;
55
56
57 protected long offset = -1L;
58
59
60 protected long lastOffset = -1L;
61
62
63
64
65
66
67
68 protected AbstractPage( BTree<K, V> btree )
69 {
70 this.btree = btree;
71 }
72
73
74
75
76
77 @SuppressWarnings("unchecked")
78
79 protected AbstractPage( BTree<K, V> btree, long revision, int nbElems )
80 {
81 this.btree = btree;
82 this.revision = revision;
83 this.nbElems = nbElems;
84 this.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, nbElems );
85 }
86
87
88
89
90
91 public int getNbElems()
92 {
93 return nbElems;
94 }
95
96
97
98
99
100
101 void setNbElems( int nbElems )
102 {
103 this.nbElems = nbElems;
104 }
105
106
107
108
109
110 public K getKey( int pos )
111 {
112 if ( ( pos < nbElems ) && ( keys[pos] != null ) )
113 {
114 return keys[pos].getKey();
115 }
116 else
117 {
118 return null;
119 }
120 }
121
122
123
124
125
126 @Override
127 public boolean hasKey( K key ) throws IOException
128 {
129 int pos = findPos( key );
130
131 if ( pos < 0 )
132 {
133
134
135 return children[-pos].getValue().hasKey( key );
136 }
137 else
138 {
139 Page<K, V> page = children[pos].getValue();
140
141 return page.hasKey( key );
142 }
143 }
144
145
146
147
148
149 Page<K, V> getReference( int pos ) throws IOException
150 {
151 if ( pos < nbElems + 1 )
152 {
153 if ( children[pos] != null )
154 {
155 return children[pos].getValue();
156 }
157 else
158 {
159 return null;
160 }
161 }
162 else
163 {
164 return null;
165 }
166 }
167
168
169
170
171
172 public TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
173 throws IOException
174 {
175 int pos = findPos( key );
176
177 if ( pos < 0 )
178 {
179 pos = -pos;
180 }
181
182
183 stack[depth++] = new ParentPos<K, V>( this, pos );
184
185 Page<K, V> page = children[pos].getValue();
186
187 return page.browse( key, transaction, stack, depth );
188 }
189
190
191
192
193
194 @Override
195 public boolean contains( K key, V value ) throws IOException
196 {
197 int pos = findPos( key );
198
199 if ( pos < 0 )
200 {
201
202
203 return children[-pos].getValue().contains( key, value );
204 }
205 else
206 {
207 return children[pos].getValue().contains( key, value );
208 }
209 }
210
211
212
213
214
215 public DeleteResult<K, V> delete( K key, V value, long revision ) throws IOException
216 {
217 return delete( key, value, revision, null, -1 );
218 }
219
220
221
222
223
224
225
226
227
228
229
230
231
232 abstract DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent,
233 int parentPos )
234 throws IOException;
235
236
237
238
239
240 public V get( K key ) throws IOException, KeyNotFoundException
241 {
242 int pos = findPos( key );
243
244 if ( pos < 0 )
245 {
246
247
248 return children[-pos].getValue().get( key );
249 }
250 else
251 {
252 return children[pos].getValue().get( key );
253 }
254 }
255
256
257
258
259
260 Page<K, V> getPage( int pos )
261 {
262 if ( ( pos >= 0 ) && ( pos < children.length ) )
263 {
264 if ( children[pos] != null )
265 {
266 return children[pos].getValue();
267 }
268 else
269 {
270 return null;
271 }
272 }
273 else
274 {
275 return null;
276 }
277 }
278
279
280
281
282
283
284
285
286 void setPageHolder( int pos, PageHolder<K, V> pageHolder )
287 {
288 if ( ( pos >= 0 ) && ( pos < children.length ) )
289 {
290 children[pos] = pageHolder;
291 }
292 }
293
294
295
296
297
298 @Override
299 public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
300 {
301 int pos = findPos( key );
302
303 if ( pos < 0 )
304 {
305
306
307 return children[-pos].getValue().getValues( key );
308 }
309 else
310 {
311 return children[pos].getValue().getValues( key );
312 }
313 }
314
315
316
317
318
319
320
321 void setValue( int pos, ValueHolder<V> value )
322 {
323
324 }
325
326
327
328
329
330 public TupleCursor<K, V> browse( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
331 throws IOException
332 {
333 stack[depth++] = new ParentPos<K, V>( this, 0 );
334
335 Page<K, V> page = children[0].getValue();
336
337 return page.browse( transaction, stack, depth );
338 }
339
340
341
342
343
344 public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
345 throws IOException
346 {
347 stack[depth++] = new ParentPos( this, 0 );
348
349 Page<K, V> page = children[0].getValue();
350
351 return page.browseKeys( transaction, stack, depth );
352 }
353
354
355
356
357
358
359
360
361
362
363
364 protected int selectSibling( Page<K, V> parent, int parentPos ) throws IOException
365 {
366 if ( parentPos == 0 )
367 {
368
369
370 return 1;
371 }
372
373 if ( parentPos == parent.getNbElems() )
374 {
375
376
377 return parentPos - 1;
378 }
379
380 Page<K, V> prevPage = ( ( AbstractPage<K, V> ) parent ).getPage( parentPos - 1 );
381 Page<K, V> nextPage = ( ( AbstractPage<K, V> ) parent ).getPage( parentPos + 1 );
382
383 int prevPageSize = prevPage.getNbElems();
384 int nextPageSize = nextPage.getNbElems();
385
386 if ( prevPageSize >= nextPageSize )
387 {
388 return parentPos - 1;
389 }
390 else
391 {
392 return parentPos + 1;
393 }
394 }
395
396
397
398
399
400 public K getLeftMostKey()
401 {
402 return keys[0].getKey();
403 }
404
405
406
407
408
409 public K getRightMostKey()
410 {
411 return keys[nbElems - 1].getKey();
412 }
413
414
415
416
417
418 long getOffset()
419 {
420 return offset;
421 }
422
423
424
425
426
427 void setOffset( long offset )
428 {
429 this.offset = offset;
430 }
431
432
433
434
435
436 long getLastOffset()
437 {
438 return lastOffset;
439 }
440
441
442
443
444
445 void setLastOffset( long lastOffset )
446 {
447 this.lastOffset = lastOffset;
448 }
449
450
451
452
453
454 KeyHolder<K>[] getKeys()
455 {
456 return keys;
457 }
458
459
460
461
462
463
464
465
466 void setKey( int pos, KeyHolder<K> key )
467 {
468 keys[pos] = key;
469 }
470
471
472
473
474
475 void setKeys( KeyHolder<K>[] keys )
476 {
477 this.keys = keys;
478 }
479
480
481
482
483
484 ValueHolder<V> getValue( int pos )
485 {
486
487 return null;
488 }
489
490
491
492
493
494 public long getRevision()
495 {
496 return revision;
497 }
498
499
500
501
502
503 void setRevision( long revision )
504 {
505 this.revision = revision;
506 }
507
508
509
510
511
512
513
514
515
516
517 protected final int compare( K key1, K key2 )
518 {
519 if ( key1 == key2 )
520 {
521 return 0;
522 }
523
524 if ( key1 == null )
525 {
526 return 1;
527 }
528
529 if ( key2 == null )
530 {
531 return -1;
532 }
533
534 return btree.getKeyComparator().compare( key1, key2 );
535 }
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574 public int findPos( K key )
575 {
576
577 if ( nbElems == 0 )
578 {
579 return 0;
580 }
581
582 int min = 0;
583 int max = nbElems - 1;
584
585
586 while ( min < max )
587 {
588 int middle = ( min + max + 1 ) >> 1;
589
590 int comp = compare( keys[middle].getKey(), key );
591
592 if ( comp < 0 )
593 {
594 min = middle + 1;
595 }
596 else if ( comp > 0 )
597 {
598 max = middle - 1;
599 }
600 else
601 {
602
603
604
605 return -( middle + 1 );
606 }
607 }
608
609
610 int comp = compare( keys[max].getKey(), key );
611
612 if ( comp == 0 )
613 {
614 return -( max + 1 );
615 }
616 else
617 {
618 if ( comp < 0 )
619 {
620 return max + 1;
621 }
622 else
623 {
624 return max;
625 }
626 }
627 }
628
629
630
631
632
633 public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
634 {
635 return children[0].getValue().findLeftMost();
636 }
637
638
639
640
641
642 public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
643 {
644 return children[nbElems].getValue().findRightMost();
645 }
646
647
648
649
650
651 public BTree<K, V> getBtree()
652 {
653 return btree;
654 }
655
656
657
658
659
660 public String dumpPage( String tabs )
661 {
662 StringBuilder sb = new StringBuilder();
663
664 if ( nbElems > 0 )
665 {
666
667 sb.append( children[0].getValue().dumpPage( tabs + " " ) );
668
669 for ( int i = 0; i < nbElems; i++ )
670 {
671 sb.append( tabs );
672 sb.append( "<" );
673 sb.append( getKey( i ) ).append( ">\n" );
674 sb.append( children[i + 1].getValue().dumpPage( tabs + " " ) );
675 }
676 }
677
678 return sb.toString();
679 }
680
681
682
683
684
685 public String toString()
686 {
687 StringBuilder sb = new StringBuilder();
688
689 sb.append( "r" ).append( revision );
690 sb.append( ", nbElems:" ).append( nbElems );
691
692 if ( offset > 0 )
693 {
694 sb.append( ", offset:" ).append( offset );
695 }
696
697 return sb.toString();
698 }
699 }