001: /*
002: * The Apache Software License, Version 1.1
003: *
004: *
005: * Copyright (c) 2001, 2002 The Apache Software Foundation. All rights
006: * reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Apache Software Foundation (http://www.apache.org/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Xerces" and "Apache Software Foundation" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact apache@apache.org.
031: *
032: * 5. Products derived from this software may not be called "Apache",
033: * nor may "Apache" appear in their name, without prior written
034: * permission of the Apache Software Foundation.
035: *
036: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
037: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
038: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
039: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
040: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
041: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
042: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
043: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
044: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
045: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
046: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
047: * SUCH DAMAGE.
048: * ====================================================================
049: *
050: * This software consists of voluntary contributions made by many
051: * individuals on behalf of the Apache Software Foundation and was
052: * originally based on software copyright (c) 2001, International
053: * Business Machines, Inc., http://www.apache.org. For more
054: * information on the Apache Software Foundation, please see
055: * <http://www.apache.org/>.
056: */
057:
058: package com.sun.xml.stream.xerces.util;
059:
060: /**
061: * This class is an unsynchronized hash table primary used for String
062: * to Object mapping.
063: * <p>
064: * The hash code uses the same algorithm as SymbolTable class.
065: *
066: * @author Elena Litani
067: * @version $Id: SymbolHash.java,v 1.2 2006/04/01 06:01:41 jeffsuttor Exp $
068: */
069: public class SymbolHash {
070:
071: //
072: // Constants
073: //
074:
075: /** Default table size. */
076: protected int fTableSize = 101;
077:
078: //
079: // Data
080: //
081:
082: /** Buckets. */
083: protected Entry[] fBuckets;
084:
085: /** Number of elements. */
086: protected int fNum = 0;
087:
088: //
089: // Constructors
090: //
091:
092: /** Constructs a key table with the default size. */
093: public SymbolHash() {
094: fBuckets = new Entry[fTableSize];
095: }
096:
097: /**
098: * Constructs a key table with a given size.
099: *
100: * @param size the size of the key table.
101: */
102: public SymbolHash(int size) {
103: fTableSize = size;
104: fBuckets = new Entry[fTableSize];
105: }
106:
107: //
108: // Public methods
109: //
110:
111: /**
112: * Adds the key/value mapping to the key table. If the key already exists,
113: * the previous value associated with this key is overwritten by the new
114: * value.
115: *
116: * @param key
117: * @param value
118: */
119: public void put(Object key, Object value) {
120: int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
121: Entry entry = search(key, bucket);
122:
123: // replace old value
124: if (entry != null) {
125: entry.value = value;
126: }
127: // create new entry
128: else {
129: entry = new Entry(key, value, fBuckets[bucket]);
130: fBuckets[bucket] = entry;
131: fNum++;
132: }
133: }
134:
135: /**
136: * Get the value associated with the given key.
137: *
138: * @param key
139: * @return
140: */
141: public Object get(Object key) {
142: int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
143: Entry entry = search(key, bucket);
144: if (entry != null) {
145: return entry.value;
146: }
147: return null;
148: }
149:
150: /**
151: * Get the number of key/value pairs stored in this table.
152: *
153: * @return
154: */
155: public int getLength() {
156: return fNum;
157: }
158:
159: /**
160: * Add all values to the given array. The array must have enough entry.
161: *
162: * @param elements the array to store the elements
163: * @param from where to start store element in the array
164: * @return number of elements copied to the array
165: */
166: public int getValues(Object[] elements, int from) {
167: for (int i = 0, j = 0; i < fTableSize && j < fNum; i++) {
168: for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
169: elements[from + j] = entry.value;
170: j++;
171: }
172: }
173: return fNum;
174: }
175:
176: /**
177: * Make a clone of this object.
178: */
179: public SymbolHash makeClone() {
180: SymbolHash newTable = new SymbolHash(fTableSize);
181: newTable.fNum = fNum;
182: for (int i = 0; i < fTableSize; i++) {
183: if (fBuckets[i] != null)
184: newTable.fBuckets[i] = fBuckets[i].makeClone();
185: }
186: return newTable;
187: }
188:
189: /**
190: * Remove all key/value assocaition. This tries to save a bit of GC'ing
191: * by at least keeping the fBuckets array around.
192: */
193: public void clear() {
194: for (int i = 0; i < fTableSize; i++) {
195: fBuckets[i] = null;
196: }
197: fNum = 0;
198: } // clear(): void
199:
200: protected Entry search(Object key, int bucket) {
201: // search for identical key
202: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
203: if (key.equals(entry.key))
204: return entry;
205: }
206: return null;
207: }
208:
209: //
210: // Classes
211: //
212:
213: /**
214: * This class is a key table entry. Each entry acts as a node
215: * in a linked list.
216: */
217: protected static final class Entry {
218: // key/value
219: public Object key;
220: public Object value;
221: /** The next entry. */
222: public Entry next;
223:
224: public Entry() {
225: key = null;
226: value = null;
227: next = null;
228: }
229:
230: public Entry(Object key, Object value, Entry next) {
231: this .key = key;
232: this .value = value;
233: this .next = next;
234: }
235:
236: public Entry makeClone() {
237: Entry entry = new Entry();
238: entry.key = key;
239: entry.value = value;
240: if (next != null)
241: entry.next = next.makeClone();
242: return entry;
243: }
244: } // entry
245:
246: } // class SymbolHash
|