1 package com.jofti.util; 2 3 import java.util.AbstractSet ; 4 import java.util.Collection ; 5 import java.util.ConcurrentModificationException ; 6 import java.util.HashMap ; 7 import java.util.Iterator ; 8 import java.util.LinkedHashMap ; 9 import java.util.LinkedHashSet ; 10 import java.util.Map ; 11 import java.util.NoSuchElementException ; 12 13 14 15 16 17 import java.io.Serializable ; 18 import java.lang.ref.SoftReference ; 19 20 21 22 23 36 public class FastSet extends AbstractSet 37 implements Cloneable , Serializable 38 { 39 transient SoftReference lookupArray = null; 40 41 44 static final int DEFAULT_INITIAL_CAPACITY = 2; 45 46 51 static final int MAXIMUM_CAPACITY = 1 << 30; 52 53 56 static final float DEFAULT_LOAD_FACTOR = 0.75f; 57 58 61 transient Entry[] table; 62 63 66 transient int size; 67 68 72 int threshold; 73 74 79 float loadFactor; 80 81 88 transient volatile int modCount; 89 90 91 92 98 public FastSet() { 99 this.loadFactor = DEFAULT_LOAD_FACTOR; 100 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 101 table = new Entry[DEFAULT_INITIAL_CAPACITY]; 102 } 103 104 107 static final Object NULL_KEY = new Object (); 108 109 static Object maskNull(Object key) { 110 return (key == null ? NULL_KEY : key); 111 } 112 113 116 static Object unmaskNull(Object key) { 117 return (key == NULL_KEY ? null : key); 118 } 119 120 static class Entry { 121 Object value; 122 final int hash; 123 Entry next; 124 125 128 Entry(int h, Object k, Entry n) { 129 next = n; 130 value = k; 131 hash = h; 132 } 133 134 public Object getValue() { 135 return unmaskNull(value); 136 } 137 138 139 public Object setValue(Object newValue) { 140 Object oldValue = value; 141 value = newValue; 142 return oldValue; 143 } 144 145 public boolean equals(Object o) { 146 if (!(o instanceof Map.Entry )) 147 return false; 148 Entry e = (Entry)o; 149 Object k1 = value; 150 Object k2 = e.value; 151 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 152 return true; 153 } 154 return false; 155 } 156 157 public int hashCode() { 158 return (value==NULL_KEY ? 0 : value.hashCode()); 159 } 160 161 public String toString() { 162 return getValue().toString(); 163 } 164 165 170 void recordAccess(HashMap m) { 171 } 172 173 177 void recordRemoval(HashMap m) { 178 } 179 } 180 181 public Iterator iterator() { 182 return new KeyIterator(); 183 } 184 185 public int size() { 186 return size; 187 } 188 public boolean isEmpty() { 189 return size == 0; 190 } 191 192 193 static int hash(Object x) { 194 int h = x.hashCode(); 195 196 h += ~(h << 9); 197 h ^= (h >>> 14); 198 h += (h << 4); 199 h ^= (h >>> 10); 200 return h; 201 } 202 203 206 static boolean eq(Object x, Object y) { 207 return x == y || x.equals(y); 208 } 209 210 213 static int indexFor(int h, int length) { 214 return h & (length-1); 215 } 216 217 public boolean contains(Object o) { 218 219 220 Object k = maskNull(o); 221 int hash = hash(k); 222 int i = indexFor(hash, table.length); 223 Entry e = table[i]; 224 while (e != null) { 225 if (e.hash == hash && eq(k, e.value)) 226 return true; 227 e = e.next; 228 } 229 return false; 230 } 231 232 private void clearCache(){ 233 lookupArray = new SoftReference (null); 234 235 236 } 237 public boolean add(Object o) { 238 clearCache(); 240 241 Object k = maskNull(o); 242 int hash = hash(k); 243 int i = indexFor(hash, table.length); 244 245 for (Entry e = table[i]; e != null; e = e.next) { 246 if (e.hash == hash && eq(k, e.value)) { 247 Object oldValue = e.value; 248 e.value = k; 249 250 return oldValue ==null; 251 } 252 } 253 254 modCount++; 255 addEntry(hash, k, i); 256 return false; 257 258 259 } 260 261 public boolean remove(Object o) { 262 263 Entry e = removeEntryForKey(o); 264 return (e == null ? false : true); 265 } 266 267 268 273 Entry removeEntryForKey(Object value) { 274 Object k = maskNull(value); 275 int hash = hash(k); 276 int i = indexFor(hash, table.length); 277 Entry prev = table[i]; 278 Entry e = prev; 279 280 while (e != null) { 281 Entry next = e.next; 282 if (e.hash == hash && eq(k, e.value)) { 283 modCount++; 284 size--; 285 if (prev == e) 286 table[i] = next; 287 else 288 prev.next = next; 289 return e; 290 } 291 prev = e; 292 e = next; 293 } 294 if (e != null){ 295 clearCache(); 296 } 297 return e; 298 } 299 300 public void clear() { 301 clearCache(); 303 modCount++; 304 Entry tab[] = table; 305 for (int i = 0; i < tab.length; i++) 306 tab[i] = null; 307 size = 0; 308 } 309 public boolean removeAll(Collection c) { 310 boolean modified =false; 311 clearCache(); 312 if (size() > c.size()) { 313 for (Iterator i = c.iterator(); i.hasNext(); ) 314 modified |= remove(i.next()); 315 } else { 316 for (Iterator i = iterator(); i.hasNext(); ) { 317 if(c.contains(i.next())) { 318 i.remove(); 319 modified = true; 320 } 321 } 322 } 323 return modified; 324 325 } 326 333 void addEntry(int hash, Object value, int bucketIndex) { 334 table[bucketIndex] = new Entry(hash, value, table[bucketIndex]); 335 if (size++ >= threshold) 336 resize(2 * table.length); 337 } 338 339 void resize(int newCapacity) { 340 Entry[] oldTable = table; 341 int oldCapacity = oldTable.length; 342 if (oldCapacity == MAXIMUM_CAPACITY) { 343 threshold = Integer.MAX_VALUE; 344 return; 345 } 346 347 Entry[] newTable = new Entry[newCapacity]; 348 transfer(newTable); 349 table = newTable; 350 threshold = (int)(newCapacity * loadFactor); 351 } 352 353 356 void transfer(Entry[] newTable) { 357 Entry[] src = table; 358 int newCapacity = newTable.length; 359 for (int j = 0; j < src.length; j++) { 360 Entry e = src[j]; 361 if (e != null) { 362 src[j] = null; 363 do { 364 Entry next = e.next; 365 int i = indexFor(e.hash, newCapacity); 366 e.next = newTable[i]; 367 newTable[i] = e; 368 e = next; 369 } while (e != null); 370 } 371 } 372 } 373 374 375 376 377 public Object [] toArray() { 378 Object [] result = null; 379 if (lookupArray != null){ 380 result =(Object [])lookupArray.get(); 381 } 382 383 if (result ==null){ 384 result= new Object [size]; 385 int resultCounter =0; 386 Entry n = null; 387 int length = table.length-1; 388 for (int i = length; i >= 0 ; i--){ 389 n = table[i]; 390 while (n != null){ 391 result[resultCounter++]= n.value; 392 n = n.next; 393 } 394 395 } 396 lookupArray = new SoftReference (result); 397 } 398 return result; 399 } 400 401 402 403 404 public boolean containsAll(Collection c) { 405 Iterator e = c.iterator(); 406 while (e.hasNext()) 407 if(!contains(e.next())) 408 return false; 409 410 return true; 411 } 412 413 private class KeyIterator extends HashIterator { 414 public Object next() { 415 return nextEntry().getValue(); 416 } 417 } 418 419 private abstract class HashIterator implements Iterator { 420 Entry next; int expectedModCount; int index; Entry current; 425 HashIterator() { 426 expectedModCount = modCount; 427 Entry[] t = table; 428 if (t ==null){ 429 430 } 431 int i = t.length; 432 Entry n = null; 433 if (size != 0) { while (i > 0 && (n = t[--i]) == null) 435 ; 436 } 437 next = n; 438 index = i; 439 } 440 441 public boolean hasNext() { 442 return next != null; 443 } 444 445 Entry nextEntry() { 446 if (modCount != expectedModCount) 447 throw new ConcurrentModificationException (); 448 Entry e = next; 449 if (e == null) 450 throw new NoSuchElementException (); 451 452 Entry n = e.next; 453 Entry[] t = table; 454 int i = index; 455 while (n == null && i > 0) 456 n = t[--i]; 457 index = i; 458 next = n; 459 return current = e; 460 } 461 462 public void remove() { 463 464 if (current == null) 465 throw new IllegalStateException (); 466 if (modCount != expectedModCount) 467 throw new ConcurrentModificationException (); 468 clearCache(); 470 Object k = current.value; 471 current = null; 472 removeEntryForKey(k); 473 expectedModCount = modCount; 474 } 475 476 } 477 478 private void writeObject(java.io.ObjectOutputStream s) 479 throws java.io.IOException { 480 s.defaultWriteObject(); 482 483 s.writeFloat(loadFactor); 485 486 s.writeInt(size); 488 489 for (Iterator i=new KeyIterator(); i.hasNext(); ) 491 s.writeObject(i.next()); 492 } 493 494 498 private void readObject(java.io.ObjectInputStream s) 499 throws java.io.IOException , ClassNotFoundException { 500 s.defaultReadObject(); 502 503 float loadFactor = s.readFloat(); 505 506 this.loadFactor = DEFAULT_LOAD_FACTOR; 507 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 508 table = new Entry[DEFAULT_INITIAL_CAPACITY]; 509 510 511 int size = s.readInt(); 513 514 for (int i=0; i<size; i++) { 516 Object e = s.readObject(); 517 add(e); 518 } 519 } 520 521 } 522 523 524 | Popular Tags |