1 28 29 package com.caucho.util; 30 31 import java.util.ArrayList ; 32 33 38 public class LongKeyClockCache<E extends ClockCacheItem> { 39 private long []_keys; 41 42 private E []_values; 44 45 private int _capacity; 47 private int _size; 49 private int _mask; 50 51 private int _clock; 52 53 58 public LongKeyClockCache(int initialCapacity) 59 { 60 int capacity; 61 62 for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) { 63 } 64 65 _keys = new long[capacity]; 66 _values = (E []) new ClockCacheItem[capacity]; 67 _mask = capacity - 1; 68 69 _capacity = initialCapacity; 70 } 71 72 75 public int size() 76 { 77 return _size; 78 } 79 80 83 public void clear() 84 { 85 ArrayList <E> listeners = null; 86 87 synchronized (this) { 88 for (int i = 0; i < _values.length; i++) { 89 E item = _values[i]; 90 91 if (item != null) { 92 if (listeners == null) 93 listeners = new ArrayList <E>(); 94 listeners.add(item); 95 } 96 97 _values[i] = null; 98 } 99 100 _size = 0; 101 } 102 103 for (int i = listeners == null ? -1 : listeners.size() - 1; i >= 0; i--) { 104 E listener = listeners.get(i); 105 listener.removeEvent(); 106 } 107 } 108 109 115 public E get(long key) 116 { 117 int hash = getHash(key); 118 int count = _size + 1; 119 120 synchronized (this) { 121 for (; count > 0; count--) { 122 E item = _values[hash]; 123 124 if (item == null) 125 return null; 126 127 if (_keys[hash] == key) { 128 item.setUsed(); 129 130 return item; 131 } 132 133 hash = (hash + 1) & _mask; 134 } 135 } 136 137 return null; 138 } 139 140 149 public E put(long key, E value) 150 { 151 freeSpace(); 152 153 E item = putImpl(key, value); 154 155 if (3 * _values.length <= 4 * _size) { 157 synchronized (this) { 158 long []oldKeys = _keys; 159 E []oldValues = _values; 160 161 _keys = new long[2 * oldKeys.length]; 162 _values = (E []) new Object [2 * oldValues.length]; 163 164 _mask = _values.length - 1; 165 _size = 0; 166 167 for (int i = oldValues.length - 1; i >= 0; i--) { 168 long oldKey = oldKeys[i]; 169 E oldValue = oldValues[i]; 170 171 if (oldValue != null) 172 putImpl(oldKey, oldValue); 173 } 174 } 175 } 176 177 if (item != null) 178 item.removeEvent(); 179 180 return item; 181 } 182 183 private E putImpl(long key, E value) 184 { 185 E item = null; 186 187 int hash = getHash(key); 188 int count = _size + 1; 189 190 synchronized (this) { 191 for (; count > 0; count--) { 192 item = _values[hash]; 193 194 if (item == null) { 196 _keys[hash] = key; 197 _values[hash] = value; 198 _size++; 199 200 return null; 201 } 202 203 if (_keys[hash] == key) { 205 item.setUsed(); 206 207 _values[hash] = value; 208 209 return item; 210 } 211 212 hash = (hash + 1) & _mask; 213 } 214 } 215 216 throw new IllegalStateException (); 217 } 218 219 private void freeSpace() 220 { 221 int i = _size - _capacity; 222 if (i > 16) 223 i = 16; 224 while (i-- > 0 && removeItem()) { 226 } 227 } 228 229 232 private boolean removeItem() 233 { 234 int length = _values.length; 235 int clock = _clock; 236 ClockCacheItem item = null; 237 238 for (int i = 0; i < length; i++) { 239 synchronized (this) { 240 item = _values[clock]; 241 242 if (item != null && ! item.isUsed()) { 243 _clock = clock; 244 _values[clock] = null; 245 _size--; 246 247 refillEntries(clock); 248 249 break; 250 } 251 } 252 253 if (item != null) 254 item.clearUsed(); 255 256 clock = (clock + 1) % length; 257 item = null; 258 } 259 260 _clock = clock; 261 262 if (item != null) { 263 item.removeEvent(); 264 return true; 265 } 266 else 267 return false; 268 } 269 270 277 public ClockCacheItem remove(long key) 278 { 279 int hash = getHash(key); 280 int count = _size + 1; 281 282 ClockCacheItem item = null; 283 284 synchronized (this) { 285 for (; count > 0; count--) { 286 item = _values[hash]; 287 288 if (item == null) 289 return null; 290 291 if (_keys[hash] == key) { 292 _values[hash] = null; 293 _size--; 294 295 refillEntries(hash); 296 break; 297 } 298 299 hash = (hash + 1) & _mask; 300 } 301 } 302 303 if (count < 0) 304 throw new RuntimeException ("internal cache error"); 305 306 item.removeEvent(); 307 308 return item; 309 } 310 311 314 private void refillEntries(int hash) 315 { 316 for (int count = _size; count >= 0; count--) { 317 hash = (hash + 1) & _mask; 318 319 if (_values[hash] == null) 320 return; 321 322 refillEntry(hash); 323 } 324 } 325 326 329 private void refillEntry(int baseHash) 330 { 331 long key = _keys[baseHash]; 332 E value = _values[baseHash]; 333 334 _values[baseHash] = null; 335 336 int hash = getHash(key); 337 338 for (int count = _size; count >= 0; count--) { 339 if (_values[hash] == null) { 340 _keys[hash] = key; 341 _values[hash] = value; 342 return; 343 } 344 345 hash = (hash + 1) & _mask; 346 } 347 } 348 349 352 private int getHash(long key) 353 { 354 long hash = key; 355 hash = hash * 0x5deece66dl + 0xbl + (hash >>> 32) * 137; 356 357 return (int) hash & _mask; 358 } 359 } 360 | Popular Tags |