001: /*
002: * Copyright (c) 2000-2005, Dennis M. Sosnoski. All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer. Redistributions in binary
009: * form must reproduce the above copyright notice, this list of conditions and
010: * the following disclaimer in the documentation and/or other materials provided
011: * with the distribution. Neither the name of JiBX nor the names of its
012: * contributors may be used to endorse or promote products derived from this
013: * software without specific prior written permission.
014: *
015: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
016: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
017: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
018: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
019: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
020: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
021: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
022: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
023: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
024: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
025: * POSSIBILITY OF SUCH DAMAGE.
026: */
027:
028: package org.jibx.runtime.impl;
029:
030: /**
031: * Hash map using <code>String</code> values as keys mapped to primitive
032: * <code>int</code> values. This implementation is unsynchronized in order to
033: * provide the best possible performance for typical usage scenarios, so
034: * explicit synchronization must be implemented by a wrapper class or directly
035: * by the application in cases where instances are modified in a multithreaded
036: * environment. The map implementation is not very efficient when resizing, but
037: * works well when the size of the map is known in advance.
038: *
039: * @author Dennis M. Sosnoski
040: * @version 1.1
041: */
042: public class StringIntHashMap {
043: /** Default value returned when key not found in table. */
044: public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;
045:
046: /** Default fill fraction allowed before growing table. */
047: protected static final double DEFAULT_FILL = 0.3d;
048:
049: /** Minimum size used for hash table. */
050: protected static final int MINIMUM_SIZE = 31;
051:
052: /** Fill fraction allowed for this hash table. */
053: protected final double m_fillFraction;
054:
055: /** Number of entries present in table. */
056: protected int m_entryCount;
057:
058: /** Entries allowed before growing table. */
059: protected int m_entryLimit;
060:
061: /** Size of array used for keys. */
062: protected int m_arraySize;
063:
064: /** Offset added (modulo table size) to slot number on collision. */
065: protected int m_hitOffset;
066:
067: /** Array of key table slots. */
068: protected String[] m_keyTable;
069:
070: /** Array of value table slots. */
071: protected int[] m_valueTable;
072:
073: /** Value returned when key not found in table. */
074: protected int m_notFoundValue;
075:
076: /**
077: * Constructor with full specification.
078: *
079: * @param count number of values to assume in initial sizing of table
080: * @param fill fraction full allowed for table before growing
081: * @param miss value returned when key not found in table
082: */
083: public StringIntHashMap(int count, double fill, int miss) {
084:
085: // check the passed in fill fraction
086: if (fill <= 0.0d || fill >= 1.0d) {
087: throw new IllegalArgumentException(
088: "fill value out of range");
089: }
090: m_fillFraction = fill;
091:
092: // compute initial table size (ensuring odd)
093: m_arraySize = Math.max((int) (count / m_fillFraction),
094: MINIMUM_SIZE);
095: m_arraySize += (m_arraySize + 1) % 2;
096:
097: // initialize the table information
098: m_entryLimit = (int) (m_arraySize * m_fillFraction);
099: m_hitOffset = m_arraySize / 2;
100: m_keyTable = new String[m_arraySize];
101: m_valueTable = new int[m_arraySize];
102: m_notFoundValue = miss;
103: }
104:
105: /**
106: * Constructor with size and fill fraction specified. Uses default hash
107: * technique and value returned when key not found in table.
108: *
109: * @param count number of values to assume in initial sizing of table
110: * @param fill fraction full allowed for table before growing
111: */
112: public StringIntHashMap(int count, double fill) {
113: this (count, fill, DEFAULT_NOT_FOUND);
114: }
115:
116: /**
117: * Constructor with only size supplied. Uses default hash technique and
118: * values for fill fraction and value returned when key not found in table.
119: *
120: * @param count number of values to assume in initial sizing of table
121: */
122: public StringIntHashMap(int count) {
123: this (count, DEFAULT_FILL);
124: }
125:
126: /**
127: * Default constructor.
128: */
129: public StringIntHashMap() {
130: this (0, DEFAULT_FILL);
131: }
132:
133: /**
134: * Copy (clone) constructor.
135: *
136: * @param base instance being copied
137: */
138: public StringIntHashMap(StringIntHashMap base) {
139:
140: // copy the basic occupancy information
141: m_fillFraction = base.m_fillFraction;
142: m_entryCount = base.m_entryCount;
143: m_entryLimit = base.m_entryLimit;
144: m_arraySize = base.m_arraySize;
145: m_hitOffset = base.m_hitOffset;
146: m_notFoundValue = base.m_notFoundValue;
147:
148: // copy table of items
149: m_keyTable = new String[m_arraySize];
150: System
151: .arraycopy(base.m_keyTable, 0, m_keyTable, 0,
152: m_arraySize);
153: m_valueTable = new int[m_arraySize];
154: System.arraycopy(base.m_valueTable, 0, m_valueTable, 0,
155: m_arraySize);
156: }
157:
158: /**
159: * Step the slot number for an entry. Adds the collision offset (modulo
160: * the table size) to the slot number.
161: *
162: * @param slot slot number to be stepped
163: * @return stepped slot number
164: */
165: private final int stepSlot(int slot) {
166: return (slot + m_hitOffset) % m_arraySize;
167: }
168:
169: /**
170: * Find free slot number for entry. Starts at the slot based directly
171: * on the hashed key value. If this slot is already occupied, it adds
172: * the collision offset (modulo the table size) to the slot number and
173: * checks that slot, repeating until an unused slot is found.
174: *
175: * @param slot initial slot computed from key
176: * @return slot at which entry was added
177: */
178: private final int freeSlot(int slot) {
179: while (m_keyTable[slot] != null) {
180: slot = stepSlot(slot);
181: }
182: return slot;
183: }
184:
185: /**
186: * Standard base slot computation for a key.
187: *
188: * @param key key value to be computed
189: * @return base slot for key
190: */
191: private final int standardSlot(Object key) {
192: return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
193: }
194:
195: /**
196: * Standard find key in table. This method may be used directly for key
197: * lookup using either the <code>hashCode()</code> method defined for the
198: * key objects or the <code>System.identityHashCode()</code> method, and
199: * either the <code>equals()</code> method defined for the key objects or
200: * the <code>==</code> operator, as selected by the hash technique
201: * constructor parameter. To implement a hash class based on some other
202: * methods of hashing and/or equality testing, define a separate method in
203: * the subclass with a different name and use that method instead. This
204: * avoids the overhead caused by overrides of a very heavily used method.
205: *
206: * @param key to be found in table
207: * @return index of matching key, or <code>-index-1</code> of slot to be
208: * used for inserting key in table if not already present (always negative)
209: */
210: private int standardFind(Object key) {
211:
212: // find the starting point for searching table
213: int slot = standardSlot(key);
214:
215: // scan through table to find target key
216: while (m_keyTable[slot] != null) {
217:
218: // check if we have a match on target key
219: if (m_keyTable[slot].equals(key)) {
220: return slot;
221: } else {
222: slot = stepSlot(slot);
223: }
224:
225: }
226: return -slot - 1;
227: }
228:
229: /**
230: * Reinsert an entry into the hash map. This is used when the table is being
231: * directly modified, and does not adjust the count present or check the
232: * table capacity.
233: *
234: * @param slot position of entry to be reinserted into hash map
235: * @return <code>true</code> if the slot number used by the entry has has
236: * changed, <code>false</code> if not
237: */
238: private boolean reinsert(int slot) {
239: String key = m_keyTable[slot];
240: m_keyTable[slot] = null;
241: return assignSlot(key, m_valueTable[slot]) != slot;
242: }
243:
244: /**
245: * Internal remove pair from the table. Removes the pair from the table
246: * by setting the key entry to <code>null</code> and adjusting the count
247: * present, then chains through the table to reinsert any other pairs
248: * which may have collided with the removed pair. If the associated value
249: * is an object reference, it should be set to <code>null</code> before
250: * this method is called.
251: *
252: * @param slot index number of pair to be removed
253: */
254: protected void internalRemove(int slot) {
255:
256: // delete pair from table
257: m_keyTable[slot] = null;
258: m_entryCount--;
259: while (m_keyTable[(slot = stepSlot(slot))] != null) {
260:
261: // reinsert current entry in table to fill holes
262: reinsert(slot);
263:
264: }
265: }
266:
267: /**
268: * Restructure the table. This is used when the table is increasing or
269: * decreasing in size, and works directly with the old table representation
270: * arrays. It inserts pairs from the old arrays directly into the table
271: * without adjusting the count present or checking the table size.
272: *
273: * @param keys array of keys
274: * @param values array of values
275: */
276: private void restructure(String[] keys, int[] values) {
277: for (int i = 0; i < keys.length; i++) {
278: if (keys[i] != null) {
279: assignSlot(keys[i], values[i]);
280: }
281: }
282: }
283:
284: /**
285: * Assign slot for entry. Starts at the slot found by the hashed key value.
286: * If this slot is already occupied, it steps the slot number and checks the
287: * resulting slot, repeating until an unused slot is found. This method does
288: * not check for duplicate keys, so it should only be used for internal
289: * reordering of the tables.
290: *
291: * @param key to be added to table
292: * @param value associated value for key
293: * @return slot at which entry was added
294: */
295: private int assignSlot(String key, int value) {
296: int offset = freeSlot(standardSlot(key));
297: m_keyTable[offset] = key;
298: m_valueTable[offset] = value;
299: return offset;
300: }
301:
302: /**
303: * Add an entry to the table. If the key is already present in the table,
304: * this replaces the existing value associated with the key.
305: *
306: * @param key key to be added to table (non- <code>null</code>)
307: * @param value associated value for key
308: * @return value previously associated with key, or reserved not found value
309: * if key not previously present in table
310: */
311: public int add(String key, int value) {
312:
313: // first validate the parameters
314: if (key == null) {
315: throw new IllegalArgumentException("null key not supported");
316: } else if (value == m_notFoundValue) {
317: throw new IllegalArgumentException(
318: "value matching not found return not supported");
319: } else {
320:
321: // check space available
322: int min = m_entryCount + 1;
323: if (min > m_entryLimit) {
324:
325: // find the array size required
326: int size = m_arraySize;
327: int limit = m_entryLimit;
328: while (limit < min) {
329: size = size * 2 + 1;
330: limit = (int) (size * m_fillFraction);
331: }
332:
333: // set parameters for new array size
334: m_arraySize = size;
335: m_entryLimit = limit;
336: m_hitOffset = size / 2;
337:
338: // restructure for larger arrays
339: String[] keys = m_keyTable;
340: m_keyTable = new String[m_arraySize];
341: int[] values = m_valueTable;
342: m_valueTable = new int[m_arraySize];
343: restructure(keys, values);
344: }
345:
346: // find slot of table
347: int offset = standardFind(key);
348: if (offset >= 0) {
349:
350: // replace existing value for key
351: int prior = m_valueTable[offset];
352: m_valueTable[offset] = value;
353: return prior;
354:
355: } else {
356:
357: // add new pair to table
358: m_entryCount++;
359: offset = -offset - 1;
360: m_keyTable[offset] = key;
361: m_valueTable[offset] = value;
362: return m_notFoundValue;
363:
364: }
365: }
366: }
367:
368: /**
369: * Check if an entry is present in the table. This method is supplied to
370: * support the use of values matching the reserved not found value.
371: *
372: * @param key key for entry to be found
373: * @return <code>true</code> if key found in table, <code>false</code>
374: * if not
375: */
376: public final boolean containsKey(String key) {
377: return standardFind(key) >= 0;
378: }
379:
380: /**
381: * Find an entry in the table.
382: *
383: * @param key key for entry to be returned
384: * @return value for key, or reserved not found value if key not found
385: */
386: public final int get(String key) {
387: int slot = standardFind(key);
388: if (slot >= 0) {
389: return m_valueTable[slot];
390: } else {
391: return m_notFoundValue;
392: }
393: }
394:
395: /**
396: * Remove an entry from the table. If multiple entries are present with the
397: * same key value, only the first one found will be removed.
398: *
399: * @param key key to be removed from table
400: * @return value associated with removed key, or reserved not found value if
401: * key not found in table
402: */
403: public int remove(String key) {
404: int slot = standardFind(key);
405: if (slot >= 0) {
406: int value = m_valueTable[slot];
407: internalRemove(slot);
408: return value;
409: } else {
410: return m_notFoundValue;
411: }
412: }
413:
414: /**
415: * Construct a copy of the table.
416: *
417: * @return shallow copy of table
418: */
419: public Object clone() {
420: return new StringIntHashMap(this);
421: }
422: }
|