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;
052:
053: /**
054: * A simple hashtable, not synchronized, with fixed load factor.
055: * Keys are Strings and values are ints.
056: *
057: * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
058: * @version $Id$
059: */
060: public class StringIntMap {
061:
062: /**
063: * The underlying array
064: */
065: protected Entry[] table;
066:
067: /**
068: * The number of entries
069: */
070: protected int count;
071:
072: /**
073: * Creates a new table.
074: * @param c The capacity of the table.
075: */
076: public StringIntMap(int c) {
077: table = new Entry[((c * 3) >>> 2) + 1];
078: }
079:
080: /**
081: * Gets the value corresponding to the given string.
082: * @return the value or -1.
083: */
084: public int get(String key) {
085: int hash = key.hashCode() & 0x7FFFFFFF;
086: int index = hash % table.length;
087:
088: for (Entry e = table[index]; e != null; e = e.next) {
089: if ((e.hash == hash) && e.key.equals(key)) {
090: return e.value;
091: }
092: }
093: return -1;
094: }
095:
096: /**
097: * Sets a new value for the given variable
098: */
099: public void put(String key, int value) {
100: int hash = key.hashCode() & 0x7FFFFFFF;
101: int index = hash % table.length;
102:
103: for (Entry e = table[index]; e != null; e = e.next) {
104: if ((e.hash == hash) && e.key.equals(key)) {
105: e.value = value;
106: return;
107: }
108: }
109:
110: // The key is not in the hash table
111: int len = table.length;
112: if (count++ >= (len * 3) >>> 2) {
113: rehash();
114: index = hash % table.length;
115: }
116:
117: Entry e = new Entry(hash, key, value, table[index]);
118: table[index] = e;
119: }
120:
121: /**
122: * Rehash the table
123: */
124: protected void rehash() {
125: Entry[] oldTable = table;
126:
127: table = new Entry[oldTable.length * 2 + 1];
128:
129: for (int i = oldTable.length - 1; i >= 0; i--) {
130: for (Entry old = oldTable[i]; old != null;) {
131: Entry e = old;
132: old = old.next;
133:
134: int index = e.hash % table.length;
135: e.next = table[index];
136: table[index] = e;
137: }
138: }
139: }
140:
141: /**
142: * To manage collisions
143: */
144: protected static class Entry {
145: /**
146: * The hash code
147: */
148: public int hash;
149:
150: /**
151: * The key
152: */
153: public String key;
154:
155: /**
156: * The value
157: */
158: public int value;
159:
160: /**
161: * The next entry
162: */
163: public Entry next;
164:
165: /**
166: * Creates a new entry
167: */
168: public Entry(int hash, String key, int value, Entry next) {
169: this.hash = hash;
170: this.key = key;
171: this.value = value;
172: this.next = next;
173: }
174: }
175: }
|