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 }