LongMap


1   /*
2    * Copyright (c) 1998-2006 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   *   Free SoftwareFoundation, Inc.
23   *   59 Temple Place, Suite 330
24   *   Boston, MA 02111-1307  USA
25   *
26   * @author Scott Ferguson
27   */
28  
29  package com.caucho.util;
30  
31  import java.util.Iterator  ;
32  /**
33   * The IntMap provides a simple hashmap from keys to integers.  The API is
34   * an abbreviation of the HashMap collection API.
35   *
36   * <p>The convenience of IntMap is avoiding all the silly wrapping of
37   * integers.
38   */
39  public class LongMap<K> {
40    /**
41     * Encoding of a null entry.  Since NULL is equal to Integer.MIN_VALUE, 
42     * it's impossible to distinguish between the two.
43     */
44    public final static long NULL = 0xffffffffffffffedL;
45    private static int DELETED = 0x1;
46    private K []_keys;
47    private long _nullValue;
48    private long []_values;
49    private byte []_flags;
50    private int _size;
51    private int _mask;
52  
53    /**
54     * Create a new LongMap.  Default size is 16.
55     */
56    public LongMap()
57    {
58      _keys = (K []) new Object  [16];
59      _values = new long[16];
60      _flags = new byte[16];
61  
62      _mask = _keys.length - 1;
63      _size = 0;
64  
65      _nullValue = NULL;
66    }
67  
68    /**
69     * Create a new IntMap for cloning.
70     */
71    private LongMap(boolean dummy)
72    {
73    }
74  
75    /**
76     * Clear the hashmap.
77     */
78    public void clear()
79    {
80      _nullValue = NULL;
81      
82      for (int i = 0; i < _values.length; i++) {
83        _keys[i] = null;
84        _flags[i] = 0;
85        _values[i] = 0;
86      }
87      
88      _size = 0;
89    }
90    /**
91     * Returns the current number of entries in the map.
92     */
93    public int size() 
94    { 
95      return _size;
96    }
97  
98    /**
99     * Puts a new value in the property table with the appropriate flags
100    */
101   public long get(K key)
102   {
103     if (key == null)
104       return _nullValue;
105 
106     int hash = key.hashCode() & _mask;
107 
108     while (true) {
109       K mapKey = _keys[hash];
110 
111       if (mapKey == key)
112     return _values[hash];
113       else if (mapKey == null) {
114     if ((_flags[hash] & DELETED) == 0)
115       return NULL;
116       }
117       else if (mapKey.equals(key))
118     return _values[hash];
119 
120       hash = (hash + 1) & _mask;
121     }
122   }
123 
124   /**
125    * Expands the property table
126    */
127   private void resize(int newSize)
128   {
129     K []newKeys = (K []) new Object  [newSize];
130     long []newValues = new long[newSize];
131     byte []newFlags = new byte[newSize];
132 
133     _mask = newKeys.length - 1;
134 
135     for (int i = 0; i < _keys.length; i++) {
136       if (_keys[i] == null || (_flags[i] & DELETED) != 0)
137     continue;
138 
139       int hash = _keys[i].hashCode() & _mask;
140 
141       while (true) {
142     if (newKeys[hash] == null) {
143       newKeys[hash] = _keys[i];
144       newValues[hash] = _values[i];
145       newFlags[hash] = _flags[i];
146       break;
147     }
148     hash = (hash + 1) & _mask;
149       }
150     }
151 
152     _keys = newKeys;
153     _values = newValues;
154     _flags = newFlags;
155   }
156 
157   /**
158    * Puts a new value in the property table with the appropriate flags
159    */
160   public long put(K key, long value)
161   {
162     return put(key, value, false);
163   }
164 
165   /**
166    * Puts a new value in the property table with the appropriate flags
167    */
168   public long putIfNew(K key, long value)
169   {
170     return put(key, value, true);
171   }
172 
173   /**
174    * Puts a new value in the property table with the appropriate flags
175    */
176   private long put(K key, long value, boolean ifNew)
177   {
178     if (key == null) {
179       long old = _nullValue;
180       _nullValue = value;
181       return old;
182     }
183 
184     int hash = key.hashCode() & _mask;
185 
186     while (true) {
187       K testKey = _keys[hash];
188 
189       if (testKey == null || (_flags[hash] & DELETED) != 0) {
190     _keys[hash] = key;
191     _values[hash] = value;
192     _flags[hash] = 0;
193 
194     _size++;
195 
196     if (_keys.length <= 2 * _size)
197       resize(2 * _keys.length);
198 
199     return NULL;
200       }
201       else if (key != testKey && ! testKey.equals(key)) {
202     hash = (hash + 1) & _mask;
203     continue;
204       }
205       else if (ifNew) {
206     return _values[hash];
207       }
208       else {
209     long old = _values[hash];
210 
211     _values[hash] = value;
212 
213     return old;
214       }
215     }
216   }
217 
218   /**
219    * Deletes the entry.  Returns true if successful.
220    */
221   public long remove(K key)
222   {
223     if (key == null) {
224       long old = _nullValue;
225       _nullValue = NULL;
226       return old;
227     }
228 
229     int hash = key.hashCode() & _mask;
230 
231     while (true) {
232       Object   mapKey = _keys[hash];
233 
234       if (mapKey == null)
235     return NULL;
236       else if (mapKey.equals(key)) {
237     _flags[hash] |= DELETED;
238 
239     _size--;
240 
241     _keys[hash] = null;
242 
243     return _values[hash];
244       }
245 
246       hash = (hash + 1) & _mask;
247     }
248   }
249   /**
250    * Returns an iterator of the keys.
251    */
252   public Iterator   iterator()
253   {
254     return new LongMapIterator();
255   }
256 
257   public Object   clone()
258   {
259     LongMap clone = new LongMap(true);
260 
261     clone._keys = new Object  [_keys.length];
262     System.arraycopy(_keys, 0, clone._keys, 0, _keys.length);
263     
264     clone._values = new long[_values.length];
265     System.arraycopy(_values, 0, clone._values, 0, _values.length);
266     
267     clone._flags = new byte[_flags.length];
268     System.arraycopy(_flags, 0, clone._flags, 0, _flags.length);
269 
270     clone._mask = _mask;
271     clone._size = _size;
272 
273     clone._nullValue = _nullValue;
274 
275     return clone;
276   }
277 
278   public String   toString()
279   {
280     StringBuffer   sbuf = new StringBuffer  ();
281 
282     sbuf.append("LongMap[");
283     
284     boolean isFirst = true;
285     
286     for (int i = 0; i <= _mask; i++) {
287       if ((_flags[i] & DELETED) == 0 && _keys[i] != null) {
288     if (! isFirst)
289       sbuf.append(", ");
290     isFirst = false;
291     sbuf.append(_keys[i]);
292     sbuf.append(":");
293     sbuf.append(_values[i]);
294       }
295     }
296     sbuf.append("]");
297     
298     return sbuf.toString();
299   }
300 
301   class LongMapIterator implements Iterator   {
302     int _index;
303 
304     public boolean hasNext()
305     {
306       for (; _index < _keys.length; _index++)
307     if (_keys[_index] != null && (_flags[_index] & DELETED) == 0)
308       return true;
309 
310       return false;
311     }
312 
313     public Object   next()
314     {
315       for (; _index < _keys.length; _index++)
316     if (_keys[_index] != null && (_flags[_index] & DELETED) == 0)
317       return _keys[_index++];
318 
319       return null;
320     }
321 
322     public void remove()
323     {
324       throw new RuntimeException  ();
325     }
326   }
327 }
328
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags