001: /**
002: * JDBM LICENSE v1.00
003: *
004: * Redistribution and use of this software and associated documentation
005: * ("Software"), with or without modification, are permitted provided
006: * that the following conditions are met:
007: *
008: * 1. Redistributions of source code must retain copyright
009: * statements and notices. Redistributions must also contain a
010: * copy of this document.
011: *
012: * 2. Redistributions in binary form must reproduce the
013: * above copyright notice, this list of conditions and the
014: * following disclaimer in the documentation and/or other
015: * materials provided with the distribution.
016: *
017: * 3. The name "JDBM" must not be used to endorse or promote
018: * products derived from this Software without prior written
019: * permission of Cees de Groot. For written permission,
020: * please contact cg@cdegroot.com.
021: *
022: * 4. Products derived from this Software may not be called "JDBM"
023: * nor may "JDBM" appear in their names without prior written
024: * permission of Cees de Groot.
025: *
026: * 5. Due credit should be given to the JDBM Project
027: * (http://jdbm.sourceforge.net/).
028: *
029: * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
030: * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
031: * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
032: * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
033: * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
034: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
035: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
036: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
037: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
038: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
039: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
040: * OF THE POSSIBILITY OF SUCH DAMAGE.
041: *
042: * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
043: * Contributions are Copyright (C) 2000 by their associated contributors.
044: *
045: */package jdbm.htree;
046:
047: import java.io.Externalizable;
048: import java.io.IOException;
049: import java.io.ObjectInput;
050: import java.io.ObjectOutput;
051:
052: import java.util.ArrayList;
053:
054: /**
055: * A bucket is a placeholder for multiple (key, value) pairs. Buckets
056: * are used to store collisions (same hash value) at all levels of an
057: * H*tree.
058: *
059: * There are two types of buckets: leaf and non-leaf.
060: *
061: * Non-leaf buckets are buckets which hold collisions which happen
062: * when the H*tree is not fully expanded. Keys in a non-leaf buckets
063: * can have different hash codes. Non-leaf buckets are limited to an
064: * arbitrary size. When this limit is reached, the H*tree should create
065: * a new Directory page and distribute keys of the non-leaf buckets into
066: * the newly created Directory.
067: *
068: * A leaf bucket is a bucket which contains keys which all have
069: * the same <code>hashCode()</code>. Leaf buckets stand at the
070: * bottom of an H*tree because the hashing algorithm cannot further
071: * discriminate between different keys based on their hash code.
072: *
073: * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
074: * @version $Id: HashBucket.java,v 1.2 2005/06/25 23:12:32 doomdark Exp $
075: */
076: final class HashBucket extends HashNode implements Externalizable {
077:
078: final static long serialVersionUID = 1L;
079:
080: /**
081: * The maximum number of elements (key, value) a non-leaf bucket
082: * can contain.
083: */
084: public static final int OVERFLOW_SIZE = 8;
085:
086: /**
087: * Depth of this bucket.
088: */
089: private int _depth;
090:
091: /**
092: * Keys in this bucket. Keys are ordered to match their respective
093: * value in <code>_values</code>.
094: */
095: private ArrayList _keys;
096:
097: /**
098: * Values in this bucket. Values are ordered to match their respective
099: * key in <code>_keys</code>.
100: */
101: private ArrayList _values;
102:
103: /**
104: * Public constructor for serialization.
105: */
106: public HashBucket() {
107: // empty
108: }
109:
110: /**
111: * Construct a bucket with a given depth level. Depth level is the
112: * number of <code>HashDirectory</code> above this bucket.
113: */
114: public HashBucket(int level) {
115: if (level > HashDirectory.MAX_DEPTH + 1) {
116: throw new IllegalArgumentException(
117: "Cannot create bucket with depth > MAX_DEPTH+1. "
118: + "Depth=" + level);
119: }
120: _depth = level;
121: _keys = new ArrayList(OVERFLOW_SIZE);
122: _values = new ArrayList(OVERFLOW_SIZE);
123: }
124:
125: /**
126: * Returns the number of elements contained in this bucket.
127: */
128: public int getElementCount() {
129: return _keys.size();
130: }
131:
132: /**
133: * Returns whether or not this bucket is a "leaf bucket".
134: */
135: public boolean isLeaf() {
136: return (_depth > HashDirectory.MAX_DEPTH);
137: }
138:
139: /**
140: * Returns true if bucket can accept at least one more element.
141: */
142: public boolean hasRoom() {
143: if (isLeaf()) {
144: return true; // leaf buckets are never full
145: } else {
146: // non-leaf bucket
147: return (_keys.size() < OVERFLOW_SIZE);
148: }
149: }
150:
151: /**
152: * Add an element (key, value) to this bucket. If an existing element
153: * has the same key, it is replaced silently.
154: *
155: * @return Object which was previously associated with the given key
156: * or <code>null</code> if no association existed.
157: */
158: public Object addElement(Object key, Object value) {
159: int existing = _keys.indexOf(key);
160: if (existing != -1) {
161: // replace existing element
162: Object before = _values.get(existing);
163: _values.set(existing, value);
164: return before;
165: } else {
166: // add new (key, value) pair
167: _keys.add(key);
168: _values.add(value);
169: return null;
170: }
171: }
172:
173: /**
174: * Remove an element, given a specific key.
175: *
176: * @param key Key of the element to remove
177: *
178: * @return Removed element value, or <code>null</code> if not found
179: */
180: public Object removeElement(Object key) {
181: int existing = _keys.indexOf(key);
182: if (existing != -1) {
183: Object obj = _values.get(existing);
184: _keys.remove(existing);
185: _values.remove(existing);
186: return obj;
187: } else {
188: // not found
189: return null;
190: }
191: }
192:
193: /**
194: * Returns the value associated with a given key. If the given key
195: * is not found in this bucket, returns <code>null</code>.
196: */
197: public Object getValue(Object key) {
198: int existing = _keys.indexOf(key);
199: if (existing != -1) {
200: return _values.get(existing);
201: } else {
202: // key not found
203: return null;
204: }
205: }
206:
207: /**
208: * Obtain keys contained in this buckets. Keys are ordered to match
209: * their values, which be be obtained by calling <code>getValues()</code>.
210: *
211: * As an optimization, the Vector returned is the instance member
212: * of this class. Please don't modify outside the scope of this class.
213: */
214: ArrayList getKeys() {
215: return this ._keys;
216: }
217:
218: /**
219: * Obtain values contained in this buckets. Values are ordered to match
220: * their keys, which be be obtained by calling <code>getKeys()</code>.
221: *
222: * As an optimization, the Vector returned is the instance member
223: * of this class. Please don't modify outside the scope of this class.
224: */
225: ArrayList getValues() {
226: return this ._values;
227: }
228:
229: /**
230: * Implement Externalizable interface.
231: */
232: public void writeExternal(ObjectOutput out) throws IOException {
233: out.writeInt(_depth);
234:
235: int entries = _keys.size();
236: out.writeInt(entries);
237:
238: // write keys
239: for (int i = 0; i < entries; i++) {
240: out.writeObject(_keys.get(i));
241: }
242: // write values
243: for (int i = 0; i < entries; i++) {
244: out.writeObject(_values.get(i));
245: }
246: }
247:
248: /**
249: * Implement Externalizable interface.
250: */
251: public void readExternal(ObjectInput in) throws IOException,
252: ClassNotFoundException {
253: _depth = in.readInt();
254:
255: int entries = in.readInt();
256:
257: // prepare array lists
258: int size = Math.max(entries, OVERFLOW_SIZE);
259: _keys = new ArrayList(size);
260: _values = new ArrayList(size);
261:
262: // read keys
263: for (int i = 0; i < entries; i++) {
264: _keys.add(in.readObject());
265: }
266: // read values
267: for (int i = 0; i < entries; i++) {
268: _values.add(in.readObject());
269: }
270: }
271:
272: public String toString() {
273: StringBuffer buf = new StringBuffer();
274: buf.append("HashBucket {depth=");
275: buf.append(_depth);
276: buf.append(", keys=");
277: buf.append(_keys);
278: buf.append(", values=");
279: buf.append(_values);
280: buf.append("}");
281: return buf.toString();
282: }
283: }
|