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 java.io.Externalizable;
50  import java.io.IOException;
51  import java.io.ObjectInput;
52  import java.io.ObjectOutput;
53  
54  import java.util.ArrayList;
55  
56  /**
57   * A bucket is a placeholder for multiple (key, value) pairs.  Buckets
58   * are used to store collisions (same hash value) at all levels of an
59   * H*tree.
60   *
61   * There are two types of buckets: leaf and non-leaf.
62   *
63   * Non-leaf buckets are buckets which hold collisions which happen
64   * when the H*tree is not fully expanded.   Keys in a non-leaf buckets
65   * can have different hash codes.  Non-leaf buckets are limited to an
66   * arbitrary size.  When this limit is reached, the H*tree should create
67   * a new Directory page and distribute keys of the non-leaf buckets into
68   * the newly created Directory.
69   *
70   * A leaf bucket is a bucket which contains keys which all have
71   * the same <code>hashCode()</code>.  Leaf buckets stand at the
72   * bottom of an H*tree because the hashing algorithm cannot further
73   * discriminate between different keys based on their hash code.
74   *
75   *  @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
76   *  @version $Id: HashBucket.java,v 1.2 2005/06/25 23:12:32 doomdark Exp $
77   */
78  final class HashBucket
79      extends HashNode
80      implements Externalizable
81  {
82  
83      final static long serialVersionUID = 1L;
84  
85      /**
86       * The maximum number of elements (key, value) a non-leaf bucket
87       * can contain.
88       */
89      public static final int OVERFLOW_SIZE = 8;
90  
91  
92      /**
93       * Depth of this bucket.
94       */
95      private int _depth;
96  
97  
98      /**
99       * Keys in this bucket.  Keys are ordered to match their respective
100      * value in <code>_values</code>.
101      */
102     private ArrayList _keys;
103 
104 
105     /**
106      * Values in this bucket.  Values are ordered to match their respective
107      * key in <code>_keys</code>.
108      */
109     private ArrayList _values;
110 
111 
112     /**
113      * Public constructor for serialization.
114      */
115     public HashBucket() {
116         // empty
117     }
118 
119 
120     /**
121      * Construct a bucket with a given depth level.  Depth level is the
122      * number of <code>HashDirectory</code> above this bucket.
123      */
124     public HashBucket( int level )
125     {
126         if ( level > HashDirectory.MAX_DEPTH+1 ) {
127             throw new IllegalArgumentException(
128                             "Cannot create bucket with depth > MAX_DEPTH+1. "
129                             + "Depth=" + level );
130         }
131         _depth = level;
132         _keys = new ArrayList( OVERFLOW_SIZE );
133         _values = new ArrayList( OVERFLOW_SIZE );
134     }
135 
136 
137     /**
138      * Returns the number of elements contained in this bucket.
139      */
140     public int getElementCount()
141     {
142         return _keys.size();
143     }
144 
145 
146     /**
147      * Returns whether or not this bucket is a "leaf bucket".
148      */
149     public boolean isLeaf()
150     {
151         return ( _depth > HashDirectory.MAX_DEPTH );
152     }
153 
154 
155     /**
156      * Returns true if bucket can accept at least one more element.
157      */
158     public boolean hasRoom()
159     {
160         if ( isLeaf() ) {
161             return true;  // leaf buckets are never full
162         } else {
163             // non-leaf bucket
164             return ( _keys.size() < OVERFLOW_SIZE );
165         }
166     }
167 
168 
169     /**
170      * Add an element (key, value) to this bucket.  If an existing element
171      * has the same key, it is replaced silently.
172      *
173      * @return Object which was previously associated with the given key
174      *          or <code>null</code> if no association existed.
175      */
176     public Object addElement( Object key, Object value )
177     {
178         int existing = _keys.indexOf(key);
179         if ( existing != -1 ) {
180             // replace existing element
181             Object before = _values.get( existing );
182             _values.set( existing, value );
183             return before;
184         } else {
185             // add new (key, value) pair
186             _keys.add( key );
187             _values.add( value );
188             return null;
189         }
190     }
191 
192 
193     /**
194      * Remove an element, given a specific key.
195      *
196      * @param key Key of the element to remove
197      *
198      * @return Removed element value, or <code>null</code> if not found
199      */
200     public Object removeElement( Object key )
201     {
202         int existing = _keys.indexOf(key);
203         if ( existing != -1 ) {
204             Object obj = _values.get( existing );
205             _keys.remove( existing );
206             _values.remove( existing );
207             return obj;
208         } else {
209             // not found
210             return null;
211         }
212     }
213 
214 
215     /**
216      * Returns the value associated with a given key.  If the given key
217      * is not found in this bucket, returns <code>null</code>.
218      */
219     public Object getValue( Object key )
220     {
221         int existing = _keys.indexOf(key);
222         if ( existing != -1 ) {
223             return _values.get( existing );
224         } else {
225             // key not found
226             return null;
227         }
228     }
229 
230 
231     /**
232      * Obtain keys contained in this buckets.  Keys are ordered to match
233      * their values, which be be obtained by calling <code>getValues()</code>.
234      *
235      * As an optimization, the Vector returned is the instance member
236      * of this class.  Please don't modify outside the scope of this class.
237      */
238     ArrayList getKeys()
239     {
240         return this._keys;
241     }
242 
243 
244     /**
245      * Obtain values contained in this buckets.  Values are ordered to match
246      * their keys, which be be obtained by calling <code>getKeys()</code>.
247      *
248      * As an optimization, the Vector returned is the instance member
249      * of this class.  Please don't modify outside the scope of this class.
250      */
251     ArrayList getValues()
252     {
253         return this._values;
254     }
255 
256 
257     /**
258      * Implement Externalizable interface.
259      */
260     public void writeExternal( ObjectOutput out )
261         throws IOException
262     {
263         out.writeInt( _depth );
264 
265         int entries = _keys.size();
266         out.writeInt( entries );
267 
268         // write keys
269         for (int i=0; i<entries; i++) {
270             out.writeObject( _keys.get( i ) );
271         }
272         // write values
273         for (int i=0; i<entries; i++) {
274             out.writeObject( _values.get( i ) );
275         }
276     }
277 
278 
279     /**
280      * Implement Externalizable interface.
281      */
282     public void readExternal(ObjectInput in)
283     throws IOException, ClassNotFoundException {
284         _depth = in.readInt();
285 
286         int entries = in.readInt();
287 
288         // prepare array lists
289         int size = Math.max( entries, OVERFLOW_SIZE );
290         _keys = new ArrayList( size );
291         _values = new ArrayList( size );
292 
293         // read keys
294         for ( int i=0; i<entries; i++ ) {
295             _keys.add( in.readObject() );
296         }
297         // read values
298         for ( int i=0; i<entries; i++ ) {
299             _values.add( in.readObject() );
300         }
301     }
302 
303     public String toString() {
304         StringBuffer buf = new StringBuffer();
305         buf.append("HashBucket {depth=");
306         buf.append(_depth);
307         buf.append(", keys=");
308         buf.append(_keys);
309         buf.append(", values=");
310         buf.append(_values);
311         buf.append("}");
312         return buf.toString();
313     }
314 }