001: /*
002:
003: Licensed to the Apache Software Foundation (ASF) under one or more
004: contributor license agreements. See the NOTICE file distributed with
005: this work for additional information regarding copyright ownership.
006: The ASF licenses this file to You under the Apache License, Version 2.0
007: (the "License"); you may not use this file except in compliance with
008: the License. You may obtain a copy of the License at
009:
010: http://www.apache.org/licenses/LICENSE-2.0
011:
012: Unless required by applicable law or agreed to in writing, software
013: distributed under the License is distributed on an "AS IS" BASIS,
014: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: See the License for the specific language governing permissions and
016: limitations under the License.
017:
018: */
019: package org.apache.batik.css.engine.value;
020:
021: /**
022: * A simple hashtable, not synchronized, with fixed load factor and with
023: * equality test made with '=='.
024: *
025: * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
026: * @version $Id: StringMap.java 489226 2006-12-21 00:05:36Z cam $
027: */
028: public class StringMap {
029:
030: /**
031: * The initial capacity
032: */
033: protected static final int INITIAL_CAPACITY = 11;
034:
035: /**
036: * The underlying array
037: */
038: protected Entry[] table;
039:
040: /**
041: * The number of entries
042: */
043: protected int count;
044:
045: /**
046: * Creates a new table.
047: */
048: public StringMap() {
049: table = new Entry[INITIAL_CAPACITY];
050: }
051:
052: /**
053: * Creates a copy of the given StringMap object.
054: * @param t The table to copy.
055: */
056: public StringMap(StringMap t) {
057: count = t.count;
058: table = new Entry[t.table.length];
059: for (int i = 0; i < table.length; i++) {
060: Entry e = t.table[i];
061: Entry n = null;
062: if (e != null) {
063: n = new Entry(e.hash, e.key, e.value, null);
064: table[i] = n;
065: e = e.next;
066: while (e != null) {
067: n.next = new Entry(e.hash, e.key, e.value, null);
068: n = n.next;
069: e = e.next;
070: }
071: }
072: }
073: }
074:
075: /**
076: * Gets the value corresponding to the given string.
077: * @return the value or null
078: */
079: public Object get(String key) {
080: int hash = key.hashCode() & 0x7FFFFFFF;
081: int index = hash % table.length;
082:
083: for (Entry e = table[index]; e != null; e = e.next) {
084: if ((e.hash == hash) && e.key == key) {
085: return e.value;
086: }
087: }
088: return null;
089: }
090:
091: /**
092: * Sets a new value for the given variable
093: * @return the old value or null
094: */
095: public Object put(String key, Object value) {
096: int hash = key.hashCode() & 0x7FFFFFFF;
097: int index = hash % table.length;
098:
099: for (Entry e = table[index]; e != null; e = e.next) {
100: if ((e.hash == hash) && e.key == key) {
101: Object old = e.value;
102: e.value = value;
103: return old;
104: }
105: }
106:
107: // The key is not in the hash table
108: int len = table.length;
109: if (count++ >= (len - (len >> 2))) {
110: // more than 75% loaded: grow
111: rehash();
112: index = hash % table.length;
113: }
114:
115: Entry e = new Entry(hash, key, value, table[index]);
116: table[index] = e;
117: return null;
118: }
119:
120: /**
121: * Rehash the table
122: */
123: protected void rehash() {
124: Entry[] oldTable = table;
125:
126: table = new Entry[oldTable.length * 2 + 1];
127:
128: for (int i = oldTable.length - 1; i >= 0; i--) {
129: for (Entry old = oldTable[i]; old != null;) {
130: Entry e = old;
131: old = old.next;
132:
133: int index = e.hash % table.length;
134: e.next = table[index];
135: table[index] = e;
136: }
137: }
138: }
139:
140: /**
141: * To manage collisions
142: */
143: protected static class Entry {
144: /**
145: * The hash code
146: */
147: public int hash;
148:
149: /**
150: * The key
151: */
152: public String key;
153:
154: /**
155: * The value
156: */
157: public Object value;
158:
159: /**
160: * The next entry
161: */
162: public Entry next;
163:
164: /**
165: * Creates a new entry
166: */
167: public Entry(int hash, String key, Object value, Entry next) {
168: this.hash = hash;
169: this.key = key;
170: this.value = value;
171: this.next = next;
172: }
173: }
174: }
|