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.htree;
48
49 import jdbm.RecordManager;
50
51 import jdbm.helper.FastIterator;
52 import jdbm.helper.IterationException;
53
54 import java.io.Externalizable;
55 import java.io.IOException;
56 import java.io.ObjectInput;
57 import java.io.ObjectOutput;
58
59 import java.util.ArrayList;
60 import java.util.Iterator;
61
62
63
64
65
66
67
68 final class HashDirectory
69 extends HashNode
70 implements Externalizable
71 {
72
73 static final long serialVersionUID = 1L;
74
75
76
77
78
79
80
81
82 static final int MAX_CHILDREN = 256;
83
84
85
86
87
88 static final int BIT_SIZE = 8;
89
90
91
92
93
94
95
96
97 static final int MAX_DEPTH = 3;
98
99
100
101
102
103 private long[] _children;
104
105
106
107
108
109 private byte _depth;
110
111
112
113
114
115 private transient RecordManager _recman;
116
117
118
119
120
121 private transient long _recid;
122
123
124
125
126
127 public HashDirectory() {
128
129 }
130
131
132
133
134
135
136 HashDirectory(byte depth) {
137 _depth = depth;
138 _children = new long[MAX_CHILDREN];
139 }
140
141
142
143
144
145
146
147
148
149 void setPersistenceContext( RecordManager recman, long recid )
150 {
151 this._recman = recman;
152 this._recid = recid;
153 }
154
155
156
157
158
159 long getRecid() {
160 return _recid;
161 }
162
163
164
165
166
167
168 boolean isEmpty() {
169 for (int i=0; i<_children.length; i++) {
170 if (_children[i] != 0) {
171 return false;
172 }
173 }
174 return true;
175 }
176
177
178
179
180
181
182
183 Object get(Object key)
184 throws IOException
185 {
186 int hash = hashCode( key );
187 long child_recid = _children[ hash ];
188 if ( child_recid == 0 ) {
189
190 return null;
191 } else {
192 HashNode node = (HashNode) _recman.fetch( child_recid );
193
194
195 if ( node instanceof HashDirectory ) {
196
197 HashDirectory dir = (HashDirectory) node;
198 dir.setPersistenceContext( _recman, child_recid );
199 return dir.get( key );
200 } else {
201
202 HashBucket bucket = (HashBucket) node;
203 return bucket.getValue( key );
204 }
205 }
206 }
207
208
209
210
211
212
213
214
215
216
217 Object put(Object key, Object value)
218 throws IOException {
219 if (value == null) {
220 return remove(key);
221 }
222 int hash = hashCode(key);
223 long child_recid = _children[hash];
224 if (child_recid == 0) {
225
226 HashBucket bucket = new HashBucket(_depth+1);
227
228
229 Object existing = bucket.addElement(key, value);
230
231 long b_recid = _recman.insert(bucket);
232 _children[hash] = b_recid;
233
234 _recman.update(_recid, this);
235
236
237 return existing;
238 } else {
239 HashNode node = (HashNode) _recman.fetch( child_recid );
240
241 if ( node instanceof HashDirectory ) {
242
243 HashDirectory dir = (HashDirectory) node;
244 dir.setPersistenceContext( _recman, child_recid );
245 return dir.put( key, value );
246 } else {
247
248 HashBucket bucket = (HashBucket)node;
249 if (bucket.hasRoom()) {
250 Object existing = bucket.addElement(key, value);
251 _recman.update(child_recid, bucket);
252
253 return existing;
254 } else {
255
256 if (_depth == MAX_DEPTH) {
257 throw new RuntimeException( "Cannot create deeper directory. "
258 + "Depth=" + _depth );
259 }
260 HashDirectory dir = new HashDirectory( (byte) (_depth+1) );
261 long dir_recid = _recman.insert( dir );
262 dir.setPersistenceContext( _recman, dir_recid );
263
264 _children[hash] = dir_recid;
265 _recman.update( _recid, this );
266
267
268 _recman.delete( child_recid );
269
270
271 ArrayList keys = bucket.getKeys();
272 ArrayList values = bucket.getValues();
273 int entries = keys.size();
274 for ( int i=0; i<entries; i++ ) {
275 dir.put( keys.get( i ), values.get( i ) );
276 }
277
278
279 return dir.put( key, value );
280 }
281 }
282 }
283 }
284
285
286
287
288
289
290
291
292
293
294 Object remove(Object key) throws IOException {
295 int hash = hashCode(key);
296 long child_recid = _children[hash];
297 if (child_recid == 0) {
298
299 return null;
300 } else {
301 HashNode node = (HashNode) _recman.fetch( child_recid );
302
303
304 if (node instanceof HashDirectory) {
305
306 HashDirectory dir = (HashDirectory)node;
307 dir.setPersistenceContext( _recman, child_recid );
308 Object existing = dir.remove(key);
309 if (existing != null) {
310 if (dir.isEmpty()) {
311
312 _recman.delete(child_recid);
313 _children[hash] = 0;
314 _recman.update(_recid, this);
315 }
316 }
317 return existing;
318 } else {
319
320 HashBucket bucket = (HashBucket)node;
321 Object existing = bucket.removeElement(key);
322 if (existing != null) {
323 if (bucket.getElementCount() >= 1) {
324 _recman.update(child_recid, bucket);
325 } else {
326
327 _recman.delete(child_recid);
328 _children[hash] = 0;
329 _recman.update(_recid, this);
330 }
331 }
332 return existing;
333 }
334 }
335 }
336
337
338
339
340
341 private int hashCode(Object key) {
342 int hashMask = hashMask();
343 int hash = key.hashCode();
344 hash = hash & hashMask;
345 hash = hash >>> ((MAX_DEPTH - _depth) * BIT_SIZE);
346 hash = hash % MAX_CHILDREN;
347
348
349
350
351
352
353 return hash;
354 }
355
356
357
358
359
360
361 int hashMask() {
362 int bits = MAX_CHILDREN-1;
363 int hashMask = bits << ((MAX_DEPTH - _depth) * BIT_SIZE);
364
365
366
367
368 return hashMask;
369 }
370
371
372
373
374 FastIterator keys()
375 throws IOException
376 {
377 return new HDIterator( true );
378 }
379
380
381
382
383 FastIterator values()
384 throws IOException
385 {
386 return new HDIterator( false );
387 }
388
389
390
391
392
393 public void writeExternal(ObjectOutput out)
394 throws IOException {
395 out.writeByte(_depth);
396 out.writeObject(_children);
397 }
398
399
400
401
402
403 public synchronized void readExternal(ObjectInput in)
404 throws IOException, ClassNotFoundException {
405 _depth = in.readByte();
406 _children = (long[])in.readObject();
407 }
408
409
410
411
412
413
414
415
416
417 public class HDIterator
418 extends FastIterator
419 {
420
421
422
423
424 private boolean _iterateKeys;
425
426
427
428
429 private ArrayList _dirStack;
430 private ArrayList _childStack;
431
432
433
434
435 private HashDirectory _dir;
436
437
438
439
440 private int _child;
441
442
443
444
445 private Iterator _iter;
446
447
448
449
450
451
452
453
454 HDIterator( boolean iterateKeys )
455 throws IOException
456 {
457 _dirStack = new ArrayList();
458 _childStack = new ArrayList();
459 _dir = HashDirectory.this;
460 _child = -1;
461 _iterateKeys = iterateKeys;
462
463 prepareNext();
464 }
465
466
467
468
469
470 public Object next()
471 {
472 Object next = null;
473 if( _iter != null && _iter.hasNext() ) {
474 next = _iter.next();
475 } else {
476 try {
477 prepareNext();
478 } catch ( IOException except ) {
479 throw new IterationException( except );
480 }
481 if ( _iter != null && _iter.hasNext() ) {
482 return next();
483 }
484 }
485 return next;
486 }
487
488
489
490
491
492
493
494
495
496 private void prepareNext() throws IOException {
497 long child_recid = 0;
498
499
500 do {
501 _child++;
502 if (_child >= MAX_CHILDREN) {
503
504 if (_dirStack.isEmpty()) {
505
506 return;
507 }
508
509
510 _dir = (HashDirectory) _dirStack.remove( _dirStack.size()-1 );
511 _child = ( (Integer) _childStack.remove( _childStack.size()-1 ) ).intValue();
512 continue;
513 }
514 child_recid = _dir._children[_child];
515 } while (child_recid == 0);
516
517 if (child_recid == 0) {
518 throw new Error("child_recid cannot be 0");
519 }
520
521 HashNode node = (HashNode) _recman.fetch( child_recid );
522
523
524 if ( node instanceof HashDirectory ) {
525
526 _dirStack.add( _dir );
527 _childStack.add( new Integer( _child ) );
528
529 _dir = (HashDirectory)node;
530 _child = -1;
531
532
533 _dir.setPersistenceContext( _recman, child_recid );
534 prepareNext();
535 } else {
536
537 HashBucket bucket = (HashBucket)node;
538 if ( _iterateKeys ) {
539 _iter = bucket.getKeys().iterator();
540 } else {
541 _iter = bucket.getValues().iterator();
542 }
543 }
544 }
545 }
546
547 }
548