1 /**
2 * JDBM LICENSE v1.00
3 *
4 * Redistribution and use of this software and associated documentation
5 * ("Software"), with or without modification, are permitted provided
6 * that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain copyright
9 * statements and notices. Redistributions must also contain a
10 * copy of this document.
11 *
12 * 2. Redistributions in binary form must reproduce the
13 * above copyright notice, this list of conditions and the
14 * following disclaimer in the documentation and/or other
15 * materials provided with the distribution.
16 *
17 * 3. The name "JDBM" must not be used to endorse or promote
18 * products derived from this Software without prior written
19 * permission of Cees de Groot. For written permission,
20 * please contact cg@cdegroot.com.
21 *
22 * 4. Products derived from this Software may not be called "JDBM"
23 * nor may "JDBM" appear in their names without prior written
24 * permission of Cees de Groot.
25 *
26 * 5. Due credit should be given to the JDBM Project
27 * (http://jdbm.sourceforge.net/).
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
30 * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
31 * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
32 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
33 * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
34 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
35 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
36 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
38 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
39 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
40 * OF THE POSSIBILITY OF SUCH DAMAGE.
41 *
42 * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
43 * Contributions are Copyright (C) 2000 by their associated contributors.
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 * Hashtable directory page.
64 *
65 * @author <a href="mailto:boisvert@exoffice.com">Alex Boisvert</a>
66 * @version $Id: HashDirectory.java,v 1.5 2005/06/25 23:12:32 doomdark Exp $
67 */
68 final class HashDirectory
69 extends HashNode
70 implements Externalizable
71 {
72
73 static final long serialVersionUID = 1L;
74
75
76 /**
77 * Maximum number of children in a directory.
78 *
79 * (Must be a power of 2 -- if you update this value, you must also
80 * update BIT_SIZE and MAX_DEPTH.)
81 */
82 static final int MAX_CHILDREN = 256;
83
84
85 /**
86 * Number of significant bits per directory level.
87 */
88 static final int BIT_SIZE = 8; // log2(256) = 8
89
90
91 /**
92 * Maximum number of levels (zero-based)
93 *
94 * (4 * 8 bits = 32 bits, which is the size of an "int", and as
95 * you know, hashcodes in Java are "ints")
96 */
97 static final int MAX_DEPTH = 3; // 4 levels
98
99
100 /**
101 * Record ids of children pages.
102 */
103 private long[] _children;
104
105
106 /**
107 * Depth of this directory page, zero-based
108 */
109 private byte _depth;
110
111
112 /**
113 * PageManager used to persist changes in directory and buckets
114 */
115 private transient RecordManager _recman;
116
117
118 /**
119 * This directory's record ID in the PageManager. (transient)
120 */
121 private transient long _recid;
122
123
124 /**
125 * Public constructor used by serialization
126 */
127 public HashDirectory() {
128 // empty
129 }
130
131 /**
132 * Construct a HashDirectory
133 *
134 * @param depth Depth of this directory page.
135 */
136 HashDirectory(byte depth) {
137 _depth = depth;
138 _children = new long[MAX_CHILDREN];
139 }
140
141
142 /**
143 * Sets persistence context. This method must be called before any
144 * persistence-related operation.
145 *
146 * @param recman RecordManager which stores this directory
147 * @param recid Record id of this directory.
148 */
149 void setPersistenceContext( RecordManager recman, long recid )
150 {
151 this._recman = recman;
152 this._recid = recid;
153 }
154
155
156 /**
157 * Get the record identifier used to load this hashtable.
158 */
159 long getRecid() {
160 return _recid;
161 }
162
163
164 /**
165 * Returns whether or not this directory is empty. A directory
166 * is empty when it no longer contains buckets or sub-directories.
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 * Returns the value which is associated with the given key. Returns
179 * <code>null</code> if there is not association for this key.
180 *
181 * @param key key whose associated value is to be returned
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 // not bucket/page --> not found
190 return null;
191 } else {
192 HashNode node = (HashNode) _recman.fetch( child_recid );
193 // System.out.println("HashDirectory.get() child is : "+node);
194
195 if ( node instanceof HashDirectory ) {
196 // recurse into next directory level
197 HashDirectory dir = (HashDirectory) node;
198 dir.setPersistenceContext( _recman, child_recid );
199 return dir.get( key );
200 } else {
201 // node is a bucket
202 HashBucket bucket = (HashBucket) node;
203 return bucket.getValue( key );
204 }
205 }
206 }
207
208
209 /**
210 * Associates the specified value with the specified key.
211 *
212 * @param key key with which the specified value is to be assocated.
213 * @param value value to be associated with the specified key.
214 * @return object which was previously associated with the given key,
215 * or <code>null</code> if no association existed.
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 // no bucket/page here yet, let's create a bucket
226 HashBucket bucket = new HashBucket(_depth+1);
227
228 // insert (key,value) pair in bucket
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 // System.out.println("Added: "+bucket);
237 return existing;
238 } else {
239 HashNode node = (HashNode) _recman.fetch( child_recid );
240
241 if ( node instanceof HashDirectory ) {
242 // recursive insert in next directory level
243 HashDirectory dir = (HashDirectory) node;
244 dir.setPersistenceContext( _recman, child_recid );
245 return dir.put( key, value );
246 } else {
247 // node is a bucket
248 HashBucket bucket = (HashBucket)node;
249 if (bucket.hasRoom()) {
250 Object existing = bucket.addElement(key, value);
251 _recman.update(child_recid, bucket);
252 // System.out.println("Added: "+bucket);
253 return existing;
254 } else {
255 // overflow, so create a new directory
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 // discard overflown bucket
268 _recman.delete( child_recid );
269
270 // migrate existing bucket elements
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 // (finally!) insert new element
279 return dir.put( key, value );
280 }
281 }
282 }
283 }
284
285
286 /**
287 * Remove the value which is associated with the given key. If the
288 * key does not exist, this method simply ignores the operation.
289 *
290 * @param key key whose associated value is to be removed
291 * @return object which was associated with the given key, or
292 * <code>null</code> if no association existed with given key.
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 // not bucket/page --> not found
299 return null;
300 } else {
301 HashNode node = (HashNode) _recman.fetch( child_recid );
302 // System.out.println("HashDirectory.remove() child is : "+node);
303
304 if (node instanceof HashDirectory) {
305 // recurse into next directory level
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 // delete empty directory
312 _recman.delete(child_recid);
313 _children[hash] = 0;
314 _recman.update(_recid, this);
315 }
316 }
317 return existing;
318 } else {
319 // node is a bucket
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 // delete bucket, it's empty
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 * Calculates the hashcode of a key, based on the current directory
339 * depth.
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 System.out.println("HashDirectory.hashCode() is: 0x"
349 +Integer.toHexString(hash)
350 +" for object hashCode() 0x"
351 +Integer.toHexString(key.hashCode()));
352 */
353 return hash;
354 }
355
356 /**
357 * Calculates the hashmask of this directory. The hashmask is the
358 * bit mask applied to a hashcode to retain only bits that are
359 * relevant to this directory level.
360 */
361 int hashMask() {
362 int bits = MAX_CHILDREN-1;
363 int hashMask = bits << ((MAX_DEPTH - _depth) * BIT_SIZE);
364 /*
365 System.out.println("HashDirectory.hashMask() is: 0x"
366 +Integer.toHexString(hashMask));
367 */
368 return hashMask;
369 }
370
371 /**
372 * Returns an enumeration of the keys contained in this
373 */
374 FastIterator keys()
375 throws IOException
376 {
377 return new HDIterator( true );
378 }
379
380 /**
381 * Returns an enumeration of the values contained in this
382 */
383 FastIterator values()
384 throws IOException
385 {
386 return new HDIterator( false );
387 }
388
389
390 /**
391 * Implement Externalizable interface
392 */
393 public void writeExternal(ObjectOutput out)
394 throws IOException {
395 out.writeByte(_depth);
396 out.writeObject(_children);
397 }
398
399
400 /**
401 * Implement Externalizable interface
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 // INNER CLASS
412 ////////////////////////////////////////////////////////////////////////
413
414 /**
415 * Utility class to enumerate keys/values in a HTree
416 */
417 public class HDIterator
418 extends FastIterator
419 {
420
421 /**
422 * True if we're iterating on keys, False if enumerating on values.
423 */
424 private boolean _iterateKeys;
425
426 /**
427 * Stacks of directories & last enumerated child position
428 */
429 private ArrayList _dirStack;
430 private ArrayList _childStack;
431
432 /**
433 * Current HashDirectory in the hierarchy
434 */
435 private HashDirectory _dir;
436
437 /**
438 * Current child position
439 */
440 private int _child;
441
442 /**
443 * Current bucket iterator
444 */
445 private Iterator _iter;
446
447
448 /**
449 * Construct an iterator on this directory.
450 *
451 * @param iterateKeys True if iteration supplies keys, False
452 * if iterateKeys supplies values.
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 * Returns the next object.
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 * Prepare internal state so we can answer <code>hasMoreElements</code>
491 *
492 * Actually, this code prepares an Enumeration on the next
493 * Bucket to enumerate. If no following bucket is found,
494 * the next Enumeration is set to <code>null</code>.
495 */
496 private void prepareNext() throws IOException {
497 long child_recid = 0;
498
499 // find next bucket/directory to enumerate
500 do {
501 _child++;
502 if (_child >= MAX_CHILDREN) {
503
504 if (_dirStack.isEmpty()) {
505 // no more directory in the stack, we're finished
506 return;
507 }
508
509 // try next page
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 // System.out.println("HDEnumeration.get() child is : "+node);
523
524 if ( node instanceof HashDirectory ) {
525 // save current position
526 _dirStack.add( _dir );
527 _childStack.add( new Integer( _child ) );
528
529 _dir = (HashDirectory)node;
530 _child = -1;
531
532 // recurse into
533 _dir.setPersistenceContext( _recman, child_recid );
534 prepareNext();
535 } else {
536 // node is a bucket
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