1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 package jdbm.btree;
48
49 import jdbm.RecordManager;
50
51 import jdbm.helper.Serializer;
52 import jdbm.helper.Tuple;
53 import jdbm.helper.TupleBrowser;
54
55 import java.io.Externalizable;
56 import java.io.IOException;
57 import java.io.ObjectInput;
58 import java.io.ObjectOutput;
59 import java.io.Serializable;
60
61 import java.util.Comparator;
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 public class BTree
91 implements Externalizable
92 {
93
94 private static final boolean DEBUG = false;
95
96
97
98
99 final static long serialVersionUID = 1L;
100
101
102
103
104
105 public static final int DEFAULT_SIZE = 16;
106
107
108
109
110
111 protected transient RecordManager _recman;
112
113
114
115
116
117 private transient long _recid;
118
119
120
121
122
123 protected Comparator _comparator;
124
125
126
127
128
129 protected Serializer _keySerializer;
130
131
132
133
134
135 protected Serializer _valueSerializer;
136
137
138
139
140
141
142 private int _height;
143
144
145
146
147
148 private transient long _root;
149
150
151
152
153
154 protected int _pageSize;
155
156
157
158
159
160 protected int _entries;
161
162
163
164
165
166 private transient BPage _bpageSerializer;
167
168
169
170
171
172 public BTree()
173 {
174
175 }
176
177
178
179
180
181
182
183
184 public static BTree createInstance( RecordManager recman,
185 Comparator comparator )
186 throws IOException
187 {
188 return createInstance( recman, comparator, null, null, DEFAULT_SIZE );
189 }
190
191
192
193
194
195
196
197
198
199
200 public static BTree createInstance( RecordManager recman,
201 Comparator comparator,
202 Serializer keySerializer,
203 Serializer valueSerializer )
204 throws IOException
205 {
206 return createInstance( recman, comparator, keySerializer,
207 valueSerializer, DEFAULT_SIZE );
208 }
209
210
211
212
213
214
215
216
217
218
219
220 public static BTree createInstance( RecordManager recman,
221 Comparator comparator,
222 Serializer keySerializer,
223 Serializer valueSerializer,
224 int pageSize )
225 throws IOException
226 {
227 BTree btree;
228
229 if ( recman == null ) {
230 throw new IllegalArgumentException( "Argument 'recman' is null" );
231 }
232
233 if ( comparator == null ) {
234 throw new IllegalArgumentException( "Argument 'comparator' is null" );
235 }
236
237 if ( ! ( comparator instanceof Serializable ) ) {
238 throw new IllegalArgumentException( "Argument 'comparator' must be serializable" );
239 }
240
241 if ( keySerializer != null && ! ( keySerializer instanceof Serializable ) ) {
242 throw new IllegalArgumentException( "Argument 'keySerializer' must be serializable" );
243 }
244
245 if ( valueSerializer != null && ! ( valueSerializer instanceof Serializable ) ) {
246 throw new IllegalArgumentException( "Argument 'valueSerializer' must be serializable" );
247 }
248
249
250 if ( ( pageSize & 1 ) != 0 ) {
251 throw new IllegalArgumentException( "Argument 'pageSize' must be even" );
252 }
253
254 btree = new BTree();
255 btree._recman = recman;
256 btree._comparator = comparator;
257 btree._keySerializer = keySerializer;
258 btree._valueSerializer = valueSerializer;
259 btree._pageSize = pageSize;
260 btree._bpageSerializer = new BPage();
261 btree._bpageSerializer._btree = btree;
262 btree._recid = recman.insert( btree );
263 return btree;
264 }
265
266
267
268
269
270
271
272
273 public static BTree load( RecordManager recman, long recid )
274 throws IOException
275 {
276 BTree btree = (BTree) recman.fetch( recid );
277 btree._recid = recid;
278 btree._recman = recman;
279 btree._bpageSerializer = new BPage();
280 btree._bpageSerializer._btree = btree;
281 return btree;
282 }
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297 public synchronized Object insert( Object key, Object value,
298 boolean replace )
299 throws IOException
300 {
301 if ( key == null ) {
302 throw new IllegalArgumentException( "Argument 'key' is null" );
303 }
304 if ( value == null ) {
305 throw new IllegalArgumentException( "Argument 'value' is null" );
306 }
307
308 BPage rootPage = getRoot();
309
310 if ( rootPage == null ) {
311
312 if (DEBUG) {
313 System.out.println( "BTree.insert() new root BPage" );
314 }
315 rootPage = new BPage( this, key, value );
316 _root = rootPage._recid;
317 _height = 1;
318 _entries = 1;
319 _recman.update( _recid, this );
320 return null;
321 } else {
322 BPage.InsertResult insert = rootPage.insert( _height, key, value, replace );
323 boolean dirty = false;
324 if ( insert._overflow != null ) {
325
326 if ( DEBUG ) {
327 System.out.println( "BTree.insert() replace root BPage due to overflow" );
328 }
329 rootPage = new BPage( this, rootPage, insert._overflow );
330 _root = rootPage._recid;
331 _height += 1;
332 dirty = true;
333 }
334 if ( insert._existing == null ) {
335 _entries++;
336 dirty = true;
337 }
338 if ( dirty ) {
339 _recman.update( _recid, this );
340 }
341
342 return insert._existing;
343 }
344 }
345
346
347
348
349
350
351
352
353
354 public synchronized Object remove( Object key )
355 throws IOException
356 {
357 if ( key == null ) {
358 throw new IllegalArgumentException( "Argument 'key' is null" );
359 }
360
361 BPage rootPage = getRoot();
362 if ( rootPage == null ) {
363 return null;
364 }
365 boolean dirty = false;
366 BPage.RemoveResult remove = rootPage.remove( _height, key );
367 if ( remove._underflow && rootPage.isEmpty() ) {
368 _height -= 1;
369 dirty = true;
370
371
372 if ( _height == 0 ) {
373 _root = 0;
374 } else {
375 _root = rootPage.childBPage( _pageSize-1 )._recid;
376 }
377 }
378 if ( remove._value != null ) {
379 _entries--;
380 dirty = true;
381 }
382 if ( dirty ) {
383 _recman.update( _recid, this );
384 }
385 return remove._value;
386 }
387
388
389
390
391
392
393
394
395 public synchronized Object find( Object key )
396 throws IOException
397 {
398 if ( key == null ) {
399 throw new IllegalArgumentException( "Argument 'key' is null" );
400 }
401 BPage rootPage = getRoot();
402 if ( rootPage == null ) {
403 return null;
404 }
405
406 Tuple tuple = new Tuple( null, null );
407 TupleBrowser browser = rootPage.find( _height, key );
408
409 if ( browser.getNext( tuple ) ) {
410
411
412 if ( _comparator.compare( key, tuple.getKey() ) != 0 ) {
413 return null;
414 } else {
415 return tuple.getValue();
416 }
417 } else {
418 return null;
419 }
420 }
421
422
423
424
425
426
427
428
429
430
431 public synchronized Tuple findGreaterOrEqual( Object key )
432 throws IOException
433 {
434 Tuple tuple;
435 TupleBrowser browser;
436
437 if ( key == null ) {
438
439
440 return null;
441 }
442
443 tuple = new Tuple( null, null );
444 browser = browse( key );
445 if ( browser.getNext( tuple ) ) {
446 return tuple;
447 } else {
448 return null;
449 }
450 }
451
452
453
454
455
456
457
458
459
460
461
462 public synchronized TupleBrowser browse()
463 throws IOException
464 {
465 BPage rootPage = getRoot();
466 if ( rootPage == null ) {
467 return EmptyBrowser.INSTANCE;
468 }
469 TupleBrowser browser = rootPage.findFirst();
470 return browser;
471 }
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486 public synchronized TupleBrowser browse( Object key )
487 throws IOException
488 {
489 BPage rootPage = getRoot();
490 if ( rootPage == null ) {
491 return EmptyBrowser.INSTANCE;
492 }
493 TupleBrowser browser = rootPage.find( _height, key );
494 return browser;
495 }
496
497
498
499
500
501 public synchronized int size()
502 {
503 return _entries;
504 }
505
506
507
508
509
510 public long getRecid()
511 {
512 return _recid;
513 }
514
515
516
517
518
519 private BPage getRoot()
520 throws IOException
521 {
522 if ( _root == 0 ) {
523 return null;
524 }
525 BPage root = (BPage) _recman.fetch( _root, _bpageSerializer );
526 root._recid = _root;
527 root._btree = this;
528 return root;
529 }
530
531
532
533
534 public void readExternal( ObjectInput in )
535 throws IOException, ClassNotFoundException
536 {
537 _comparator = (Comparator) in.readObject();
538 _keySerializer = (Serializer) in.readObject();
539 _valueSerializer = (Serializer) in.readObject();
540 _height = in.readInt();
541 _root = in.readLong();
542 _pageSize = in.readInt();
543 _entries = in.readInt();
544 }
545
546
547
548
549
550 public void writeExternal( ObjectOutput out )
551 throws IOException
552 {
553 out.writeObject( _comparator );
554 out.writeObject( _keySerializer );
555 out.writeObject( _valueSerializer );
556 out.writeInt( _height );
557 out.writeLong( _root );
558 out.writeInt( _pageSize );
559 out.writeInt( _entries );
560 }
561
562
563 public void setValueSerializer( Serializer valueSerializer )
564 {
565 _valueSerializer = valueSerializer;
566 }
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592 static class EmptyBrowser
593 extends TupleBrowser
594 {
595
596 static TupleBrowser INSTANCE = new EmptyBrowser();
597
598 public boolean getNext( Tuple tuple )
599 {
600 return false;
601 }
602
603 public boolean getPrevious( Tuple tuple )
604 {
605 return false;
606 }
607 }
608 }
609