LongKeyMap


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 LongKeyMap provides a simple hashmap from longs to values.  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 LongKeyMap {
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    private final static int DELETED = 0x1;
45    private final static long DEAD_KEY = 0xdeadbeeffeedcafeL;
46    private long []keys;
47    private Object   []values;
48    private byte []flags;
49    private int size;
50    private int mask;
51  
52    /**
53     * Create a new LongKeyMap.  Default size is 16.
54     */
55    public LongKeyMap()
56    {
57      keys = new long[16];
58      values = new Object  [16];
59      flags = new byte[16];
60  
61      mask = keys.length - 1;
62      size = 0;
63  
64      clear();
65    }
66  
67    /**
68     * Create a new IntMap for cloning.
69     */
70    private LongKeyMap(boolean dummy)
71    {
72    }
73  
74    /**
75     * Clear the hashmap.
76     */
77    public void clear()
78    {
79      for (int i = 0; i < values.length; i++) {
80        keys[i] = DEAD_KEY;
81        flags[i] = 0;
82        values[i] = null;
83      }
84      size = 0;
85    }
86    /**
87     * Returns the current number of entries in the map.
88     */
89    public int size() 
90    { 
91      return size;
92    }
93  
94    /**
95     * Puts a new value in the property table with the appropriate flags
96     */
97    public Object   get(long key)
98    {
99      int hash = (int) (key & mask);
100 
101     while (true) {
102       long mapKey = keys[hash];
103 
104       if (mapKey == key)
105     return values[hash];
106       else if (mapKey == DEAD_KEY) {
107     if ((flags[hash] & DELETED) == 0)
108       return null;
109       }
110 
111       hash = (hash + 1) & mask;
112     }
113   }
114 
115   /**
116    * Expands the property table
117    */
118   private void resize(int newSize)
119   {
120     long []newKeys = new long[newSize];
121     Object   []newValues = new Object  [newSize];
122     byte []newFlags = new byte[newSize];
123 
124     for (int i = 0; i < newSize; i++)
125       newKeys[i] = DEAD_KEY;
126 
127     mask = newKeys.length - 1;
128 
129     for (int i = 0; i < keys.length; i++) {
130       if (keys[i] == DEAD_KEY || (flags[i] & DELETED) != 0)
131     continue;
132 
133       int hash = (int) keys[i] & mask;
134 
135       while (true) {
136     if (newKeys[hash] == DEAD_KEY) {
137       newKeys[hash] = keys[i];
138       newValues[hash] = values[i];
139       newFlags[hash] = flags[i];
140       break;
141     }
142     hash = (hash + 1) & mask;
143       }
144     }
145 
146     keys = newKeys;
147     values = newValues;
148     flags = newFlags;
149   }
150 
151   /**
152    * Puts a new value in the property table with the appropriate flags
153    */
154   public Object   put(long key, Object   value)
155   {
156     int hash = (int) (key & mask);
157     int count = size;
158 
159     while (count-- >= 0) {
160       long testKey = keys[hash];
161 
162       if (testKey == DEAD_KEY || (flags[hash] & DELETED) != 0) {
163     keys[hash] = key;
164     values[hash] = value;
165     flags[hash] = 0;
166 
167     size++;
168 
169     if (keys.length <= 2 * size)
170       resize(2 * keys.length);
171 
172     return null;
173       }
174       else if (key != testKey) {
175     hash = (hash + 1) & mask;
176     continue;
177       }
178       else {
179     Object   old = values[hash];
180 
181     values[hash] = value;
182 
183     return old;
184       }
185     }
186 
187     return null;
188   }
189 
190   /**
191    * Deletes the entry.  Returns true if successful.
192    */
193   public Object   remove(long key)
194   {
195     int hash = (int) (key & mask);
196 
197     while (true) {
198       long mapKey = keys[hash];
199 
200       if (mapKey == DEAD_KEY)
201     return null;
202       else if (mapKey == key) {
203     flags[hash] |= DELETED;
204 
205     size--;
206 
207     keys[hash] = DEAD_KEY;
208 
209     return values[hash];
210       }
211 
212       hash = (hash + 1) & mask;
213     }
214   }
215   /**
216    * Returns an iterator of the keys.
217    */
218   public Iterator   iterator()
219   {
220     return new LongKeyMapIterator();
221   }
222 
223   public Object   clone()
224   {
225     LongKeyMap clone = new LongKeyMap(true);
226 
227     clone.keys = new long[keys.length];
228     System.arraycopy(keys, 0, clone.keys, 0, keys.length);
229     
230     clone.values = new Object  [values.length];
231     System.arraycopy(values, 0, clone.values, 0, values.length);
232     
233     clone.flags = new byte[flags.length];
234     System.arraycopy(flags, 0, clone.flags, 0, flags.length);
235 
236     clone.mask = mask;
237     clone.size = size;
238 
239     return clone;
240   }
241 
242   public String   toString()
243   {
244     StringBuffer   sbuf = new StringBuffer  ();
245 
246     sbuf.append("LongKeyMap[");
247     boolean isFirst = true;
248     for (int i = 0; i <= mask; i++) {
249       if ((flags[i] & DELETED) == 0 && keys[i] != DEAD_KEY) {
250     if (! isFirst)
251       sbuf.append(", ");
252     isFirst = false;
253     sbuf.append(keys[i]);
254     sbuf.append(":");
255     sbuf.append(values[i]);
256       }
257     }
258     sbuf.append("]");
259     return sbuf.toString();
260   }
261 
262   class LongKeyMapIterator implements Iterator   {
263     int index;
264 
265     public boolean hasNext()
266     {
267       for (; index < keys.length; index++)
268     if (keys[index] != DEAD_KEY && (flags[index] & DELETED) == 0)
269       return true;
270 
271       return false;
272     }
273 
274     public Object   next()
275     {
276       for (; index < keys.length; index++)
277     if (keys[index] != DEAD_KEY && (flags[index] & DELETED) == 0)
278       return new Long  (keys[index++]);
279 
280       return null;
281     }
282 
283     public void remove()
284     {
285       throw new RuntimeException  ();
286     }
287   }
288 }
289
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags