001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package org.apache.xerces.util;
019:
020: /**
021: * This class is an unsynchronized hash table primary used for String
022: * to Object mapping.
023: * <p>
024: * The hash code uses the same algorithm as SymbolTable class.
025: *
026: * @author Elena Litani
027: * @version $Id: SymbolHash.java 447241 2006-09-18 05:12:57Z mrglavas $
028: */
029: public class SymbolHash {
030:
031: //
032: // Constants
033: //
034:
035: /** Default table size. */
036: protected int fTableSize = 101;
037:
038: //
039: // Data
040: //
041:
042: /** Buckets. */
043: protected Entry[] fBuckets;
044:
045: /** Number of elements. */
046: protected int fNum = 0;
047:
048: //
049: // Constructors
050: //
051:
052: /** Constructs a key table with the default size. */
053: public SymbolHash() {
054: fBuckets = new Entry[fTableSize];
055: }
056:
057: /**
058: * Constructs a key table with a given size.
059: *
060: * @param size the size of the key table.
061: */
062: public SymbolHash(int size) {
063: fTableSize = size;
064: fBuckets = new Entry[fTableSize];
065: }
066:
067: //
068: // Public methods
069: //
070:
071: /**
072: * Adds the key/value mapping to the key table. If the key already exists,
073: * the previous value associated with this key is overwritten by the new
074: * value.
075: *
076: * @param key
077: * @param value
078: */
079: public void put(Object key, Object value) {
080: int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
081: Entry entry = search(key, bucket);
082:
083: // replace old value
084: if (entry != null) {
085: entry.value = value;
086: }
087: // create new entry
088: else {
089: entry = new Entry(key, value, fBuckets[bucket]);
090: fBuckets[bucket] = entry;
091: fNum++;
092: }
093: }
094:
095: /**
096: * Get the value associated with the given key.
097: *
098: * @param key
099: * @return the value associated with the given key.
100: */
101: public Object get(Object key) {
102: int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
103: Entry entry = search(key, bucket);
104: if (entry != null) {
105: return entry.value;
106: }
107: return null;
108: }
109:
110: /**
111: * Get the number of key/value pairs stored in this table.
112: *
113: * @return the number of key/value pairs stored in this table.
114: */
115: public int getLength() {
116: return fNum;
117: }
118:
119: /**
120: * Add all values to the given array. The array must have enough entry.
121: *
122: * @param elements the array to store the elements
123: * @param from where to start store element in the array
124: * @return number of elements copied to the array
125: */
126: public int getValues(Object[] elements, int from) {
127: for (int i = 0, j = 0; i < fTableSize && j < fNum; i++) {
128: for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
129: elements[from + j] = entry.value;
130: j++;
131: }
132: }
133: return fNum;
134: }
135:
136: /**
137: * Make a clone of this object.
138: */
139: public SymbolHash makeClone() {
140: SymbolHash newTable = new SymbolHash(fTableSize);
141: newTable.fNum = fNum;
142: for (int i = 0; i < fTableSize; i++) {
143: if (fBuckets[i] != null)
144: newTable.fBuckets[i] = fBuckets[i].makeClone();
145: }
146: return newTable;
147: }
148:
149: /**
150: * Remove all key/value assocaition. This tries to save a bit of GC'ing
151: * by at least keeping the fBuckets array around.
152: */
153: public void clear() {
154: for (int i = 0; i < fTableSize; i++) {
155: fBuckets[i] = null;
156: }
157: fNum = 0;
158: } // clear(): void
159:
160: protected Entry search(Object key, int bucket) {
161: // search for identical key
162: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
163: if (key.equals(entry.key))
164: return entry;
165: }
166: return null;
167: }
168:
169: //
170: // Classes
171: //
172:
173: /**
174: * This class is a key table entry. Each entry acts as a node
175: * in a linked list.
176: */
177: protected static final class Entry {
178: // key/value
179: public Object key;
180: public Object value;
181: /** The next entry. */
182: public Entry next;
183:
184: public Entry() {
185: key = null;
186: value = null;
187: next = null;
188: }
189:
190: public Entry(Object key, Object value, Entry next) {
191: this .key = key;
192: this .value = value;
193: this .next = next;
194: }
195:
196: public Entry makeClone() {
197: Entry entry = new Entry();
198: entry.key = key;
199: entry.value = value;
200: if (next != null)
201: entry.next = next.makeClone();
202: return entry;
203: }
204: } // entry
205:
206: } // class SymbolHash
|