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 }