001: /*
002:
003: ============================================================================
004: The Apache Software License, Version 1.1
005: ============================================================================
006:
007: Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
008:
009: Redistribution and use in source and binary forms, with or without modifica-
010: tion, are permitted provided that the following conditions are met:
011:
012: 1. Redistributions of source code must retain the above copyright notice,
013: this list of conditions and the following disclaimer.
014:
015: 2. Redistributions in binary form must reproduce the above copyright notice,
016: this list of conditions and the following disclaimer in the documentation
017: and/or other materials provided with the distribution.
018:
019: 3. The end-user documentation included with the redistribution, if any, must
020: include the following acknowledgment: "This product includes software
021: developed by the Apache Software Foundation (http://www.apache.org/)."
022: Alternately, this acknowledgment may appear in the software itself, if
023: and wherever such third-party acknowledgments normally appear.
024:
025: 4. The names "Batik" and "Apache Software Foundation" must not be
026: used to endorse or promote products derived from this software without
027: prior written permission. For written permission, please contact
028: apache@apache.org.
029:
030: 5. Products derived from this software may not be called "Apache", nor may
031: "Apache" appear in their name, without prior written permission of the
032: Apache Software Foundation.
033:
034: THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
035: INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
036: FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
037: APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
038: INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
039: DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
040: OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
041: ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
042: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
043: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
044:
045: This software consists of voluntary contributions made by many individuals
046: on behalf of the Apache Software Foundation. For more information on the
047: Apache Software Foundation, please see <http://www.apache.org/>.
048:
049: */
050:
051: package org.apache.batik.css.engine.value;
052:
053: /**
054: * A simple hashtable, not synchronized, with fixed load factor and with
055: * equality test made with '=='.
056: *
057: * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
058: * @version $Id$
059: */
060: public class StringMap {
061:
062: /**
063: * The initial capacity
064: */
065: protected final static int INITIAL_CAPACITY = 11;
066:
067: /**
068: * The underlying array
069: */
070: protected Entry[] table;
071:
072: /**
073: * The number of entries
074: */
075: protected int count;
076:
077: /**
078: * Creates a new table.
079: */
080: public StringMap() {
081: table = new Entry[INITIAL_CAPACITY];
082: }
083:
084: /**
085: * Creates a copy of the given StringMap object.
086: * @param t The table to copy.
087: */
088: public StringMap(StringMap t) {
089: count = t.count;
090: table = new Entry[t.table.length];
091: for (int i = 0; i < table.length; i++) {
092: Entry e = t.table[i];
093: Entry n = null;
094: if (e != null) {
095: n = new Entry(e.hash, e.key, e.value, null);
096: table[i] = n;
097: e = e.next;
098: while (e != null) {
099: n.next = new Entry(e.hash, e.key, e.value, null);
100: n = n.next;
101: e = e.next;
102: }
103: }
104: }
105: }
106:
107: /**
108: * Gets the value corresponding to the given string.
109: * @return the value or null
110: */
111: public Object get(String key) {
112: int hash = key.hashCode() & 0x7FFFFFFF;
113: int index = hash % table.length;
114:
115: for (Entry e = table[index]; e != null; e = e.next) {
116: if ((e.hash == hash) && e.key == key) {
117: return e.value;
118: }
119: }
120: return null;
121: }
122:
123: /**
124: * Sets a new value for the given variable
125: * @return the old value or null
126: */
127: public Object put(String key, Object value) {
128: int hash = key.hashCode() & 0x7FFFFFFF;
129: int index = hash % table.length;
130:
131: for (Entry e = table[index]; e != null; e = e.next) {
132: if ((e.hash == hash) && e.key == key) {
133: Object old = e.value;
134: e.value = value;
135: return old;
136: }
137: }
138:
139: // The key is not in the hash table
140: int len = table.length;
141: if (count++ >= (len * 3) >>> 2) {
142: rehash();
143: index = hash % table.length;
144: }
145:
146: Entry e = new Entry(hash, key, value, table[index]);
147: table[index] = e;
148: return null;
149: }
150:
151: /**
152: * Rehash the table
153: */
154: protected void rehash() {
155: Entry[] oldTable = table;
156:
157: table = new Entry[oldTable.length * 2 + 1];
158:
159: for (int i = oldTable.length - 1; i >= 0; i--) {
160: for (Entry old = oldTable[i]; old != null;) {
161: Entry e = old;
162: old = old.next;
163:
164: int index = e.hash % table.length;
165: e.next = table[index];
166: table[index] = e;
167: }
168: }
169: }
170:
171: /**
172: * To manage collisions
173: */
174: protected static class Entry {
175: /**
176: * The hash code
177: */
178: public int hash;
179:
180: /**
181: * The key
182: */
183: public String key;
184:
185: /**
186: * The value
187: */
188: public Object value;
189:
190: /**
191: * The next entry
192: */
193: public Entry next;
194:
195: /**
196: * Creates a new entry
197: */
198: public Entry(int hash, String key, Object value, Entry next) {
199: this .hash = hash;
200: this .key = key;
201: this .value = value;
202: this .next = next;
203: }
204: }
205:
206: // BEGIN RAVE MODIFICATIONS
207: // I need to be able to iterate over these StringMaps
208: public java.util.Iterator keys() {
209: return new It(true);
210: }
211:
212: public java.util.Iterator values() {
213: return new It(false);
214: }
215:
216: public int size() {
217: return count;
218: }
219:
220: private class It implements java.util.Iterator {
221: /** @param keys If true iterate keyset else valueset */
222: private It(boolean keys) {
223: this .keys = keys;
224: findNext();
225: }
226:
227: public boolean hasNext() {
228: return entry != null;
229: }
230:
231: public Object next() {
232: Entry e = entry;
233: findNext();
234: return keys ? e.key : e.value;
235: }
236:
237: public void remove() {
238: throw new UnsupportedOperationException();
239: }
240:
241: private int index = -1;
242: private Entry entry = null;
243: private boolean keys;
244:
245: private void findNext() {
246: if (entry != null) {
247: entry = entry.next;
248: if (entry != null) {
249: return;
250: }
251: }
252: if (index == table.length) {
253: return;
254: }
255: index++;
256: while (index < table.length) {
257: if (table[index] != null) {
258: entry = table[index];
259: return;
260: }
261: index++;
262: }
263: }
264: }
265: // END RAVE MODIFICATIONS
266:
267: }
|