IdentityIntMap


1   /*
2    * Copyright (c) 1998-1999 Caucho Technology -- all rights reserved
3    *
4    * This file is part of Resin(R) Open Source
5    *
6    * Each copy or derived work must preserve the copyright notice and this
7    * notice unmodified.
8    *
9    * Resin Open Source is free software; you can redistribute it and/or modify
10   * it under the terms of the GNU General Public License as published by
11   * the Free Software Foundation; either version 2 of the License, or
12   * (at your option) any later version.
13   *
14   * Resin Open Source is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17   * of NON-INFRINGEMENT.  See the GNU General Public License for more
18   * details.
19   *
20   * You should have received a copy of the GNU General Public License
21   * along with Resin Open Source; if not, write to the
22   *
23   *   Free SoftwareFoundation, Inc.
24   *   59 Temple Place, Suite 330
25   *   Boston, MA 02111-1307  USA
26   *
27   * @author Scott Ferguson
28   */
29  
30  package com.caucho.util;
31  
32  import java.util.Iterator  ;
33  /**
34   * The IntMap provides a simple hashmap from keys to integers.  The API is
35   * an abbreviation of the HashMap collection API.
36   *
37   * <p>The convenience of IntMap is avoiding all the silly wrapping of
38   * integers.
39   */
40  public class IdentityIntMap {
41    /**
42     * Encoding of a null entry.  Since NULL is equal to Integer.MIN_VALUE, 
43     * it's impossible to distinguish between the two.
44     */
45    public final static int NULL = Integer.MIN_VALUE;
46    private static int DELETED = 0x1;
47    private Object   []keys;
48    private int nullValue;
49    private int []values;
50    private byte []flags;
51    private int size;
52    private int mask;
53  
54    /**
55     * Create a new IntMap.  Default size is 16.
56     */
57    public IdentityIntMap()
58    {
59      keys = new Object  [16];
60      values = new int[16];
61      flags = new byte[16];
62  
63      mask = keys.length - 1;
64      size = 0;
65  
66      nullValue = NULL;
67    }
68  
69    /**
70     * Clear the hashmap.
71     */
72    public void clear()
73    {
74      nullValue = NULL;
75      for (int i = 0; i < values.length; i++) {
76        keys[i] = null;
77        flags[i] = 0;
78        values[i] = 0;
79      }
80      size = 0;
81    }
82    /**
83     * Returns the current number of entries in the map.
84     */
85    public int size() 
86    { 
87      return size;
88    }
89  
90    /**
91     * Puts a new value in the property table with the appropriate flags
92     */
93    public int get(Object   key)
94    {
95      if (key == null)
96        return nullValue;
97  
98      int hash = System.identityHashCode(key) & mask;
99  
100     while (true) {
101       Object   mapKey = keys[hash];
102 
103       if (mapKey == key)
104     return values[hash];
105       else if (mapKey == null) {
106     if ((flags[hash] & DELETED) == 0)
107       return NULL;
108       }
109       else if (mapKey.equals(key))
110     return values[hash];
111 
112       hash = (hash + 1) & mask;
113     }
114   }
115 
116   /**
117    * Expands the property table
118    */
119   private void resize(int newSize)
120   {
121     Object   []newKeys = new Object  [newSize];
122     int []newValues = new int[newSize];
123     byte []newFlags = new byte[newSize];
124 
125     mask = newKeys.length - 1;
126 
127     for (int i = 0; i < keys.length; i++) {
128       if (keys[i] == null || (flags[i] & DELETED) != 0)
129     continue;
130 
131       int hash = System.identityHashCode(keys[i]) & mask;
132 
133       while (true) {
134     if (newKeys[hash] == null) {
135       newKeys[hash] = keys[i];
136       newValues[hash] = values[i];
137       newFlags[hash] = flags[i];
138       break;
139     }
140     hash = (hash + 1) & mask;
141       }
142     }
143 
144     keys = newKeys;
145     values = newValues;
146     flags = newFlags;
147   }
148 
149   /**
150    * Puts a new value in the property table with the appropriate flags
151    */
152   public int put(Object   key, int value)
153   {
154     if (key == null) {
155       int old = nullValue;
156       nullValue = value;
157       return old;
158     }
159 
160     int hash = System.identityHashCode(key) & mask;
161 
162     while (true) {
163       Object   testKey = keys[hash];
164 
165       if (testKey == null || (flags[hash] & DELETED) != 0) {
166     keys[hash] = key;
167     values[hash] = value;
168     flags[hash] = 0;
169 
170     size++;
171 
172     if (keys.length <= 2 * size)
173       resize(2 * keys.length);
174 
175     return NULL;
176       }
177       else if (key != testKey && ! testKey.equals(key)) {
178     hash = (hash + 1) & mask;
179     continue;
180       }
181       else {
182     int old = values[hash];
183 
184     values[hash] = value;
185 
186     return old;
187       }
188     }
189   }
190 
191   /**
192    * Deletes the entry.  Returns true if successful.
193    */
194   public int remove(Object   key)
195   {
196     if (key == null) {
197       int old = nullValue;
198       nullValue = NULL;
199       return old;
200     }
201 
202     int hash = System.identityHashCode(key) & mask;
203 
204     while (true) {
205       Object   mapKey = keys[hash];
206 
207       if (mapKey == null)
208     return NULL;
209       else if (mapKey.equals(key)) {
210     flags[hash] |= DELETED;
211 
212     size--;
213 
214     keys[hash] = null;
215 
216     return values[hash];
217       }
218 
219       hash = (hash + 1) & mask;
220     }
221   }
222   /**
223    * Returns an iterator of the keys.
224    */
225   public Iterator   iterator()
226   {
227     return new IntMapIterator();
228   }
229 
230   public String   toString()
231   {
232     StringBuffer   sbuf = new StringBuffer  ();
233 
234     sbuf.append("IntMap[");
235     boolean isFirst = true;
236     for (int i = 0; i <= mask; i++) {
237       if ((flags[i] & DELETED) == 0 && keys[i] != null) {
238     if (! isFirst)
239       sbuf.append(", ");
240     isFirst = false;
241     sbuf.append(keys[i]);
242     sbuf.append(":");
243     sbuf.append(values[i]);
244       }
245     }
246     sbuf.append("]");
247     return sbuf.toString();
248   }
249 
250   class IntMapIterator implements Iterator   {
251     int index;
252 
253     public boolean hasNext()
254     {
255       for (; index < keys.length; index++)
256     if (keys[index] != null && (flags[index] & DELETED) == 0)
257       return true;
258 
259       return false;
260     }
261 
262     public Object   next()
263     {
264       for (; index < keys.length; index++)
265     if (keys[index] != null && (flags[index] & DELETED) == 0)
266       return keys[index++];
267 
268       return null;
269     }
270 
271     public void remove()
272     {
273       throw new RuntimeException  ();
274     }
275   }
276 }
277
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags