1 /*
2
3 Licensed to the Apache Software Foundation (ASF) under one or more
4 contributor license agreements. See the NOTICE file distributed with
5 this work for additional information regarding copyright ownership.
6 The ASF licenses this file to You under the Apache License, Version 2.0
7 (the "License"); you may not use this file except in compliance with
8 the License. You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17
18 */
19 package org.apache.batik.css.engine.value;
20
21 /**
22 * A simple hashtable, not synchronized, with fixed load factor and with
23 * equality test made with '=='.
24 *
25 * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
26 * @version $Id: StringMap.java 1733416 2016-03-03 07:07:13Z gadams $
27 */
28 public class StringMap {
29
30 /**
31 * The initial capacity
32 */
33 protected static final int INITIAL_CAPACITY = 11;
34
35 /**
36 * The underlying array
37 */
38 protected Entry[] table;
39
40 /**
41 * The number of entries
42 */
43 protected int count;
44
45 /**
46 * Creates a new table.
47 */
48 public StringMap() {
49 table = new Entry[INITIAL_CAPACITY];
50 }
51
52 /**
53 * Creates a copy of the given StringMap object.
54 * @param t The table to copy.
55 */
56 public StringMap( StringMap t ) {
57 count = t.count;
58 table = new Entry[t.table.length];
59 for ( int i = 0; i < table.length; i++ ) {
60 Entry e = t.table[ i ];
61 Entry n = null;
62 if ( e != null ) {
63 n = new Entry( e.hash, e.key, e.value, null );
64 table[ i ] = n;
65 e = e.next;
66 while ( e != null ) {
67 n.next = new Entry( e.hash, e.key, e.value, null );
68 n = n.next;
69 e = e.next;
70 }
71 }
72 }
73 }
74
75 /**
76 * Gets the value corresponding to the given string.
77 * @return the value or null
78 */
79 public Object get( String key ) {
80 int hash = key.hashCode() & 0x7FFFFFFF;
81 int index = hash % table.length;
82
83 for ( Entry e = table[ index ]; e != null; e = e.next ) {
84 if ( ( e.hash == hash ) && e.key == key ) {
85 return e.value;
86 }
87 }
88 return null;
89 }
90
91 /**
92 * Sets a new value for the given variable
93 * @return the old value or null
94 */
95 public Object put( String key, Object value ) {
96 int hash = key.hashCode() & 0x7FFFFFFF;
97 int index = hash % table.length;
98
99 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 }
175