View Javadoc

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