001 /*
002 * Copyright (c) 2001-2008 Caucho Technology, Inc. All rights reserved.
003 *
004 * The Apache Software License, Version 1.1
005 *
006 * Redistribution and use in source and binary forms, with or without
007 * modification, are permitted provided that the following conditions
008 * are met:
009 *
010 * 1. Redistributions of source code must retain the above copyright
011 * notice, this list of conditions and the following disclaimer.
012 *
013 * 2. Redistributions in binary form must reproduce the above copyright
014 * notice, this list of conditions and the following disclaimer in
015 * the documentation and/or other materials provided with the
016 * distribution.
017 *
018 * 3. The end-user documentation included with the redistribution, if
019 * any, must include the following acknowlegement:
020 * "This product includes software developed by the
021 * Caucho Technology (http://www.caucho.com/)."
022 * Alternately, this acknowlegement may appear in the software itself,
023 * if and wherever such third-party acknowlegements normally appear.
024 *
025 * 4. The names "Burlap", "Resin", and "Caucho" must not be used to
026 * endorse or promote products derived from this software without prior
027 * written permission. For written permission, please contact
028 * info@caucho.com.
029 *
030 * 5. Products derived from this software may not be called "Resin"
031 * nor may "Resin" appear in their names without prior written
032 * permission of Caucho Technology.
033 *
034 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
035 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
036 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
037 * DISCLAIMED. IN NO EVENT SHALL CAUCHO TECHNOLOGY OR ITS CONTRIBUTORS
038 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
039 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
040 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
041 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
042 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
043 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
044 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
045 *
046 * @author Scott Ferguson
047 */
048
049 package com.caucho.hessian.util;
050
051 /**
052 * The IntMap provides a simple hashmap from keys to integers. The API is
053 * an abbreviation of the HashMap collection API.
054 *
055 * <p>The convenience of IntMap is avoiding all the silly wrapping of
056 * integers.
057 */
058 public class IdentityIntMap {
059 /**
060 * Encoding of a null entry. Since NULL is equal to Integer.MIN_VALUE,
061 * it's impossible to distinguish between the two.
062 */
063 public final static int NULL = 0xdeadbeef; // Integer.MIN_VALUE + 1;
064
065 private Object []_keys;
066 private int []_values;
067
068 private int _size;
069 private int _prime;
070
071 /**
072 * Create a new IntMap. Default size is 16.
073 */
074 public IdentityIntMap(int capacity)
075 {
076 _keys = new Object[capacity];
077 _values = new int[capacity];
078
079 _prime = getBiggestPrime(_keys.length);
080 _size = 0;
081 }
082
083 /**
084 * Clear the hashmap.
085 */
086 public void clear()
087 {
088 final Object []keys = _keys;
089 final int []values = _values;
090
091 for (int i = keys.length - 1; i >= 0; i--) {
092 keys[i] = null;
093 values[i] = 0;
094 }
095
096 _size = 0;
097 }
098 /**
099 * Returns the current number of entries in the map.
100 */
101 public final int size()
102 {
103 return _size;
104 }
105
106 /**
107 * Puts a new value in the property table with the appropriate flags
108 */
109 public final int get(Object key)
110 {
111 int prime = _prime;
112 int hash = System.identityHashCode(key) % prime;
113 // int hash = key.hashCode() & mask;
114
115 final Object []keys = _keys;
116
117 while (true) {
118 Object mapKey = keys[hash];
119
120 if (mapKey == null)
121 return NULL;
122 else if (mapKey == key)
123 return _values[hash];
124
125 hash = (hash + 1) % prime;
126 }
127 }
128
129 /**
130 * Puts a new value in the property table with the appropriate flags
131 */
132 public final int put(Object key, int value, boolean isReplace)
133 {
134 int prime = _prime;
135 int hash = Math.abs(System.identityHashCode(key) % prime);
136 // int hash = key.hashCode() % prime;
137
138 Object []keys = _keys;
139
140 while (true) {
141 Object testKey = keys[hash];
142
143 if (testKey == null) {
144 keys[hash] = key;
145 _values[hash] = value;
146
147 _size++;
148
149 if (keys.length <= 4 * _size)
150 resize(4 * keys.length);
151
152 return value;
153 }
154 else if (key != testKey) {
155 hash = (hash + 1) % prime;
156
157 continue;
158 }
159 else if (isReplace){
160 int old = _values[hash];
161
162 _values[hash] = value;
163
164 return old;
165 }
166 else {
167 return _values[hash];
168 }
169 }
170 }
171
172 /**
173 * Removes a value in the property table.
174 */
175 public final void remove(Object key)
176 {
177 if (put(key, NULL, true) != NULL) {
178 _size--;
179 }
180 }
181
182 /**
183 * Expands the property table
184 */
185 private void resize(int newSize)
186 {
187 Object []keys = _keys;
188 int values[] = _values;
189
190 _keys = new Object[newSize];
191 _values = new int[newSize];
192 _size = 0;
193
194 _prime = getBiggestPrime(_keys.length);
195
196 for (int i = keys.length - 1; i >= 0; i--) {
197 Object key = keys[i];
198 int value = values[i];
199
200 if (key != null && value != NULL) {
201 put(key, value, true);
202 }
203 }
204 }
205
206 protected int hashCode(Object value)
207 {
208 return System.identityHashCode(value);
209 }
210
211 public String toString()
212 {
213 StringBuffer sbuf = new StringBuffer();
214
215 sbuf.append("IntMap[");
216 boolean isFirst = true;
217
218 for (int i = 0; i <= _keys.length; i++) {
219 if (_keys[i] != null) {
220 if (! isFirst)
221 sbuf.append(", ");
222
223 isFirst = false;
224 sbuf.append(_keys[i]);
225 sbuf.append(":");
226 sbuf.append(_values[i]);
227 }
228 }
229 sbuf.append("]");
230
231 return sbuf.toString();
232 }
233
234 public static final int []PRIMES =
235 {
236 1, /* 1<< 0 = 1 */
237 2, /* 1<< 1 = 2 */
238 3, /* 1<< 2 = 4 */
239 7, /* 1<< 3 = 8 */
240 13, /* 1<< 4 = 16 */
241 31, /* 1<< 5 = 32 */
242 61, /* 1<< 6 = 64 */
243 127, /* 1<< 7 = 128 */
244 251, /* 1<< 8 = 256 */
245 509, /* 1<< 9 = 512 */
246 1021, /* 1<<10 = 1024 */
247 2039, /* 1<<11 = 2048 */
248 4093, /* 1<<12 = 4096 */
249 8191, /* 1<<13 = 8192 */
250 16381, /* 1<<14 = 16384 */
251 32749, /* 1<<15 = 32768 */
252 65521, /* 1<<16 = 65536 */
253 131071, /* 1<<17 = 131072 */
254 262139, /* 1<<18 = 262144 */
255 524287, /* 1<<19 = 524288 */
256 1048573, /* 1<<20 = 1048576 */
257 2097143, /* 1<<21 = 2097152 */
258 4194301, /* 1<<22 = 4194304 */
259 8388593, /* 1<<23 = 8388608 */
260 16777213, /* 1<<24 = 16777216 */
261 33554393, /* 1<<25 = 33554432 */
262 67108859, /* 1<<26 = 67108864 */
263 134217689, /* 1<<27 = 134217728 */
264 268435399, /* 1<<28 = 268435456 */
265 };
266
267 public static int getBiggestPrime(int value)
268 {
269 for (int i = PRIMES.length - 1; i >= 0; i--) {
270 if (PRIMES[i] <= value)
271 return PRIMES[i];
272 }
273
274 return 2;
275 }
276 }