IntMap


1   /*
2    * Copyright (c) 2001-2006 Caucho Technology, Inc.  All rights reserved.
3    *
4    * The Apache Software License, Version 1.1
5    *
6    * Redistribution and use in source and binary forms, with or without
7    * modification, are permitted provided that the following conditions
8    * are met:
9    *
10   * 1. Redistributions of source code must retain the above copyright
11   *    notice, this list of conditions and the following disclaimer.
12   *
13   * 2. Redistributions in binary form must reproduce the above copyright
14   *    notice, this list of conditions and the following disclaimer in
15   *    the documentation and/or other materials provided with the
16   *    distribution.
17   *
18   * 3. The end-user documentation included with the redistribution, if
19   *    any, must include the following acknowlegement:
20   *       "This product includes software developed by the
21   *        Caucho Technology (http://www.caucho.com/)."
22   *    Alternately, this acknowlegement may appear in the software itself,
23   *    if and wherever such third-party acknowlegements normally appear.
24   *
25   * 4. The names "Burlap", "Resin", and "Caucho" must not be used to
26   *    endorse or promote products derived from this software without prior
27   *    written permission. For written permission, please contact
28   *    info@caucho.com.
29   *
30   * 5. Products derived from this software may not be called "Resin"
31   *    nor may "Resin" appear in their names without prior written
32   *    permission of Caucho Technology.
33   *
34   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
35   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
36   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
37   * DISCLAIMED.  IN NO EVENT SHALL CAUCHO TECHNOLOGY OR ITS CONTRIBUTORS
38   * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
39   * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
40   * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
41   * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
42   * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
43   * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
44   * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45   *
46   * @author Scott Ferguson
47   */
48  
49  package com.caucho.hessian.util;
50  
51  /**
52   * The IntMap provides a simple hashmap from keys to integers.  The API is
53   * an abbreviation of the HashMap collection API.
54   *
55   * <p>The convenience of IntMap is avoiding all the silly wrapping of
56   * integers.
57   */
58  public class IntMap {
59    /**
60     * Encoding of a null entry.  Since NULL is equal to Integer.MIN_VALUE, 
61     * it's impossible to distinguish between the two.
62     */
63    public final static int NULL = 0xdeadbeef; // Integer.MIN_VALUE + 1;
64  
65    private static final Object   DELETED = new Object  ();
66  
67    private Object   []_keys;
68    private int []_values;
69  
70    private int _size;
71    private int _mask;
72  
73    /**
74     * Create a new IntMap.  Default size is 16.
75     */
76    public IntMap()
77    {
78      _keys = new Object  [256];
79      _values = new int[256];
80  
81      _mask = _keys.length - 1;
82      _size = 0;
83    }
84  
85    /**
86     * Clear the hashmap.
87     */
88    public void clear()
89    {
90      Object   []keys = _keys;
91      int []values = _values;
92  
93      for (int i = keys.length - 1; i >= 0; i--) {
94        keys[i] = null;
95        values[i] = 0;
96      }
97  
98      _size = 0;
99    }
100   /**
101    * Returns the current number of entries in the map.
102    */
103   public int size()
104   {
105     return _size;
106   }
107 
108   /**
109    * Puts a new value in the property table with the appropriate flags
110    */
111   public int get(Object   key)
112   {
113     int mask = _mask;
114     int hash = key.hashCode() % mask & mask;
115 
116     Object   []keys = _keys;
117 
118     while (true) {
119       Object   mapKey = keys[hash];
120 
121       if (mapKey == null)
122         return NULL;
123       else if (mapKey == key || mapKey.equals(key))
124         return _values[hash];
125 
126       hash = (hash + 1) % mask;
127     }
128   }
129 
130   /**
131    * Expands the property table
132    */
133   private void resize(int newSize)
134   {
135     Object   []newKeys = new Object  [newSize];
136     int []newValues = new int[newSize];
137 
138     int mask = _mask = newKeys.length - 1;
139 
140     Object   []keys = _keys;
141     int values[] = _values;
142 
143     for (int i = keys.length - 1; i >= 0; i--) {
144       Object   key = keys[i];
145 
146       if (key == null || key == DELETED)
147         continue;
148 
149       int hash = key.hashCode() % mask & mask;
150 
151       while (true) {
152         if (newKeys[hash] == null) {
153           newKeys[hash] = key;
154           newValues[hash] = values[i];
155           break;
156         }
157 
158         hash = (hash + 1) % mask;
159       }
160     }
161 
162     _keys = newKeys;
163     _values = newValues;
164   }
165 
166   /**
167    * Puts a new value in the property table with the appropriate flags
168    */
169   public int put(Object   key, int value)
170   {
171     int mask = _mask;
172     int hash = key.hashCode() % mask & mask;
173 
174     Object   []keys = _keys;
175 
176     while (true) {
177       Object   testKey = keys[hash];
178 
179       if (testKey == null || testKey == DELETED) {
180         keys[hash] = key;
181         _values[hash] = value;
182 
183         _size++;
184 
185         if (keys.length <= 4 * _size)
186           resize(4 * keys.length);
187 
188         return NULL;
189       }
190       else if (key != testKey && ! key.equals(testKey)) {
191         hash = (hash + 1) % mask;
192 
193         continue;
194       }
195       else {
196         int old = _values[hash];
197 
198         _values[hash] = value;
199 
200         return old;
201       }
202     }
203   }
204 
205   /**
206    * Deletes the entry.  Returns true if successful.
207    */
208   public int remove(Object   key)
209   {
210     int mask = _mask;
211     int hash = key.hashCode() % mask & mask;
212 
213     while (true) {
214       Object   mapKey = _keys[hash];
215 
216       if (mapKey == null)
217         return NULL;
218       else if (mapKey == key) {
219         _keys[hash] = DELETED;
220 
221         _size--;
222 
223         return _values[hash];
224       }
225 
226       hash = (hash + 1) % mask;
227     }
228   }
229 
230   public String   toString()
231   {
232     StringBuffer   sbuf = new StringBuffer  ();
233 
234     sbuf.append("IntMap[");
235     boolean isFirst = true;
236 
237     for (int i = 0; i <= _mask; i++) {
238       if (_keys[i] != null && _keys[i] != DELETED) {
239         if (! isFirst)
240           sbuf.append(", ");
241 
242         isFirst = false;
243         sbuf.append(_keys[i]);
244         sbuf.append(":");
245         sbuf.append(_values[i]);
246       }
247     }
248     sbuf.append("]");
249 
250     return sbuf.toString();
251   }
252 }
253
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags