001: /*
002: * Copyright 2002-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: /*
018: * Note: originally released under the GNU LGPL v2.1,
019: * but rereleased by the original author under the ASF license (above).
020: */
021: package net.sf.thingamablog.xml;
022:
023: /**
024: * <p>A hash map that uses primitive ints for the key rather than objects.</p>
025: *
026: * <p>Note that this class is for internal optimization purposes only, and may
027: * not be supported in future releases of Jakarta Commons Lang. Utilities of
028: * this sort may be included in future releases of Jakarta Commons Collections.</p>
029: *
030: * @author Justin Couch
031: * @author Alex Chaffee (alex@apache.org)
032: * @author Stephen Colebourne
033: * @since 2.0
034: * @version $Revision: 1.1 $
035: * @see java.util.HashMap
036: */
037: class IntHashMap {
038:
039: /**
040: * The hash table data.
041: */
042: private transient Entry table[];
043:
044: /**
045: * The total number of entries in the hash table.
046: */
047: private transient int count;
048:
049: /**
050: * The table is rehashed when its size exceeds this threshold. (The
051: * value of this field is (int)(capacity * loadFactor).)
052: *
053: * @serial
054: */
055: private int threshold;
056:
057: /**
058: * The load factor for the hashtable.
059: *
060: * @serial
061: */
062: private float loadFactor;
063:
064: /**
065: * <p>Innerclass that acts as a datastructure to create a new entry in the
066: * table.</p>
067: */
068: private static class Entry {
069: int hash;
070: int key;
071: Object value;
072: Entry next;
073:
074: /**
075: * <p>Create a new entry with the given values.</p>
076: *
077: * @param hash The code used to hash the object with
078: * @param key The key used to enter this in the table
079: * @param value The value for this key
080: * @param next A reference to the next entry in the table
081: */
082: protected Entry(int hash, int key, Object value, Entry next) {
083: this .hash = hash;
084: this .key = key;
085: this .value = value;
086: this .next = next;
087: }
088: }
089:
090: /**
091: * <p>Constructs a new, empty hashtable with a default capacity and load
092: * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
093: */
094: public IntHashMap() {
095: this (20, 0.75f);
096: }
097:
098: /**
099: * <p>Constructs a new, empty hashtable with the specified initial capacity
100: * and default load factor, which is <code>0.75</code>.</p>
101: *
102: * @param initialCapacity the initial capacity of the hashtable.
103: * @throws IllegalArgumentException if the initial capacity is less
104: * than zero.
105: */
106: public IntHashMap(int initialCapacity) {
107: this (initialCapacity, 0.75f);
108: }
109:
110: /**
111: * <p>Constructs a new, empty hashtable with the specified initial
112: * capacity and the specified load factor.</p>
113: *
114: * @param initialCapacity the initial capacity of the hashtable.
115: * @param loadFactor the load factor of the hashtable.
116: * @throws IllegalArgumentException if the initial capacity is less
117: * than zero, or if the load factor is nonpositive.
118: */
119: public IntHashMap(int initialCapacity, float loadFactor) {
120: super ();
121: if (initialCapacity < 0) {
122: throw new IllegalArgumentException("Illegal Capacity: "
123: + initialCapacity);
124: }
125: if (loadFactor <= 0) {
126: throw new IllegalArgumentException("Illegal Load: "
127: + loadFactor);
128: }
129: if (initialCapacity == 0) {
130: initialCapacity = 1;
131: }
132:
133: this .loadFactor = loadFactor;
134: table = new Entry[initialCapacity];
135: threshold = (int) (initialCapacity * loadFactor);
136: }
137:
138: /**
139: * <p>Returns the number of keys in this hashtable.</p>
140: *
141: * @return the number of keys in this hashtable.
142: */
143: public int size() {
144: return count;
145: }
146:
147: /**
148: * <p>Tests if this hashtable maps no keys to values.</p>
149: *
150: * @return <code>true</code> if this hashtable maps no keys to values;
151: * <code>false</code> otherwise.
152: */
153: public boolean isEmpty() {
154: return count == 0;
155: }
156:
157: /**
158: * <p>Tests if some key maps into the specified value in this hashtable.
159: * This operation is more expensive than the <code>containsKey</code>
160: * method.</p>
161: *
162: * <p>Note that this method is identical in functionality to containsValue,
163: * (which is part of the Map interface in the collections framework).</p>
164: *
165: * @param value a value to search for.
166: * @return <code>true</code> if and only if some key maps to the
167: * <code>value</code> argument in this hashtable as
168: * determined by the <tt>equals</tt> method;
169: * <code>false</code> otherwise.
170: * @throws NullPointerException if the value is <code>null</code>.
171: * @see #containsKey(int)
172: * @see #containsValue(Object)
173: * @see java.util.Map
174: */
175: public boolean contains(Object value) {
176: if (value == null) {
177: throw new NullPointerException();
178: }
179:
180: Entry tab[] = table;
181: for (int i = tab.length; i-- > 0;) {
182: for (Entry e = tab[i]; e != null; e = e.next) {
183: if (e.value.equals(value)) {
184: return true;
185: }
186: }
187: }
188: return false;
189: }
190:
191: /**
192: * <p>Returns <code>true</code> if this HashMap maps one or more keys
193: * to this value.</p>
194: *
195: * <p>Note that this method is identical in functionality to contains
196: * (which predates the Map interface).</p>
197: *
198: * @param value value whose presence in this HashMap is to be tested.
199: * @see java.util.Map
200: * @since JDK1.2
201: */
202: public boolean containsValue(Object value) {
203: return contains(value);
204: }
205:
206: /**
207: * <p>Tests if the specified object is a key in this hashtable.</p>
208: *
209: * @param key possible key.
210: * @return <code>true</code> if and only if the specified object is a
211: * key in this hashtable, as determined by the <tt>equals</tt>
212: * method; <code>false</code> otherwise.
213: * @see #contains(Object)
214: */
215: public boolean containsKey(int key) {
216: Entry tab[] = table;
217: int hash = key;
218: int index = (hash & 0x7FFFFFFF) % tab.length;
219: for (Entry e = tab[index]; e != null; e = e.next) {
220: if (e.hash == hash) {
221: return true;
222: }
223: }
224: return false;
225: }
226:
227: /**
228: * <p>Returns the value to which the specified key is mapped in this map.</p>
229: *
230: * @param key a key in the hashtable.
231: * @return the value to which the key is mapped in this hashtable;
232: * <code>null</code> if the key is not mapped to any value in
233: * this hashtable.
234: * @see #put(int, Object)
235: */
236: public Object get(int key) {
237: Entry tab[] = table;
238: int hash = key;
239: int index = (hash & 0x7FFFFFFF) % tab.length;
240: for (Entry e = tab[index]; e != null; e = e.next) {
241: if (e.hash == hash) {
242: return e.value;
243: }
244: }
245: return null;
246: }
247:
248: /**
249: * <p>Increases the capacity of and internally reorganizes this
250: * hashtable, in order to accommodate and access its entries more
251: * efficiently.</p>
252: *
253: * <p>This method is called automatically when the number of keys
254: * in the hashtable exceeds this hashtable's capacity and load
255: * factor.</p>
256: */
257: protected void rehash() {
258: int oldCapacity = table.length;
259: Entry oldMap[] = table;
260:
261: int newCapacity = oldCapacity * 2 + 1;
262: Entry newMap[] = new Entry[newCapacity];
263:
264: threshold = (int) (newCapacity * loadFactor);
265: table = newMap;
266:
267: for (int i = oldCapacity; i-- > 0;) {
268: for (Entry old = oldMap[i]; old != null;) {
269: Entry e = old;
270: old = old.next;
271:
272: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
273: e.next = newMap[index];
274: newMap[index] = e;
275: }
276: }
277: }
278:
279: /**
280: * <p>Maps the specified <code>key</code> to the specified
281: * <code>value</code> in this hashtable. The key cannot be
282: * <code>null</code>. </p>
283: *
284: * <p>The value can be retrieved by calling the <code>get</code> method
285: * with a key that is equal to the original key.</p>
286: *
287: * @param key the hashtable key.
288: * @param value the value.
289: * @return the previous value of the specified key in this hashtable,
290: * or <code>null</code> if it did not have one.
291: * @throws NullPointerException if the key is <code>null</code>.
292: * @see #get(int)
293: */
294: public Object put(int key, Object value) {
295: // Makes sure the key is not already in the hashtable.
296: Entry tab[] = table;
297: int hash = key;
298: int index = (hash & 0x7FFFFFFF) % tab.length;
299: for (Entry e = tab[index]; e != null; e = e.next) {
300: if (e.hash == hash) {
301: Object old = e.value;
302: e.value = value;
303: return old;
304: }
305: }
306:
307: if (count >= threshold) {
308: // Rehash the table if the threshold is exceeded
309: rehash();
310:
311: tab = table;
312: index = (hash & 0x7FFFFFFF) % tab.length;
313: }
314:
315: // Creates the new entry.
316: Entry e = new Entry(hash, key, value, tab[index]);
317: tab[index] = e;
318: count++;
319: return null;
320: }
321:
322: /**
323: * <p>Removes the key (and its corresponding value) from this
324: * hashtable.</p>
325: *
326: * <p>This method does nothing if the key is not present in the
327: * hashtable.</p>
328: *
329: * @param key the key that needs to be removed.
330: * @return the value to which the key had been mapped in this hashtable,
331: * or <code>null</code> if the key did not have a mapping.
332: */
333: public Object remove(int key) {
334: Entry tab[] = table;
335: int hash = key;
336: int index = (hash & 0x7FFFFFFF) % tab.length;
337: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
338: if (e.hash == hash) {
339: if (prev != null) {
340: prev.next = e.next;
341: } else {
342: tab[index] = e.next;
343: }
344: count--;
345: Object oldValue = e.value;
346: e.value = null;
347: return oldValue;
348: }
349: }
350: return null;
351: }
352:
353: /**
354: * <p>Clears this hashtable so that it contains no keys.</p>
355: */
356: public synchronized void clear() {
357: Entry tab[] = table;
358: for (int index = tab.length; --index >= 0;) {
359: tab[index] = null;
360: }
361: count = 0;
362: }
363:
364: }
|