001/* 002 * Trident - A Multithreaded Server Alternative 003 * Copyright 2014 The TridentSDK Team 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018package net.tridentsdk.util; 019 020import com.google.common.collect.Sets; 021import com.google.common.reflect.TypeToken; 022import net.tridentsdk.Trident; 023import net.tridentsdk.base.BoundingBox; 024import net.tridentsdk.base.Position; 025import net.tridentsdk.docs.InternalUseOnly; 026import net.tridentsdk.entity.Entity; 027import net.tridentsdk.entity.traits.EntityProperties; 028import net.tridentsdk.entity.types.EntityType; 029import net.tridentsdk.world.World; 030 031import javax.annotation.concurrent.GuardedBy; 032import javax.annotation.concurrent.NotThreadSafe; 033import javax.annotation.concurrent.ThreadSafe; 034import java.lang.ref.WeakReference; 035import java.lang.reflect.ParameterizedType; 036import java.lang.reflect.Type; 037import java.util.*; 038import java.util.concurrent.locks.Condition; 039import java.util.concurrent.locks.Lock; 040import java.util.concurrent.locks.ReentrantLock; 041import java.util.stream.Collectors; 042 043/** 044 * A reference to an entity 045 * 046 * <p>Three constructors are provided. In the case that the stored value comes from an <em>alien-source</em>, or any 047 * general situation where the value to be held by the WeakEntity is unknown and unspecified, the recommended factory 048 * method to use is {@link #orEmpty(net.tridentsdk.entity.Entity)}. This prevents the creation of unnecessary instances 049 * of WeakEntity where the value is always going to {@code null}. Because this method always returns the same instance 050 * of a {@code null} holding WeakEntity, registration does not need to be executed, where registration means to place 051 * the reference into a queue which will be cleared once the entity has been removed. In this context, and alien method 052 * is: <em>"A method you call for which you have no control over the code, and further don’t even know what the code 053 * does, other than the method signature</em> [...] <em>it could refer to calls to third party libraries</em>."</p> 054 * 055 * <p>Because entities are loaded with all of their data and AI, the removal of them entirely depends on the references 056 * left held to it. If the entity is technically removed by the server, but still held by a plugin, for example, then 057 * a memory leak will occur because the entity will never actually be removed. It is not updated for players, but the 058 * reference stays in memory, wasting computing power on a non-existent entity.</p> 059 * 060 * <p>Use this class to store a link or bridge to the reference of an entity. The storage of an instance of this class 061 * will only hold this class only, and the reference to the entity in this class may become {@code null} at any time, 062 * in which case is indicated by {@link #isNull()} returning {@code true}.</p> 063 * 064 * <p>Much thought was put into the design of this class, especially if it should be made thread-safe. Because this is 065 * an internal change, it can be easily done without breaking the API. However, the decision was made to make this 066 * class 067 * thread-safe in order to preserve the fact that both the users of this API, including plugins and the server itself 068 * is concurrent. It would decrease the burden to handle this safely using the internal implementation rather than 069 * having the client code execute awkward constructs in order to keep consistency. This is OK for the implementation to 070 * perform, but because plugin authors may not always think about the concurrent nature of this API, it was done at the 071 * cost of performance to reduce bugs which are often difficult to find.</p> 072 * 073 * <p>This is the equivalent of {@link com.google.common.base.Optional} but for entities specifically, much like an 074 * optional which stores a {@link java.lang.ref.WeakReference} of the specified property. While this class does use 075 * WeakReference to manage the references, other methods to safeguard the reference is also implemented, such as 076 * removal 077 * listeners.</p> 078 * 079 * <p>Internally, this class manages a queue of references which, in turn, are polled by a thread called 080 * {@code Trident - Reference Handler}. Every call to clear a specific reference also runs the mark/sweep collector, 081 * although it is invoked directly rather than using {@link #runMarkSweep()}. The implementation of the collector may 082 * be 083 * found in the documentation for {@link #runMarkSweep()}. Entities call 084 * {@link #clearReferencesTo(net.tridentsdk.entity.Entity)} when they are removed to purge old references to that 085 * entity 086 * after it has finished despawning. This method also runs the mark/sweep collector. This is only implemented as a 087 * safeguard behind {@link java.lang.ref.WeakReference}, which is used to store the actual instance of the entity to be 088 * weakly referenced. The reference handling thread cleans up the entity after all the references have been cleared, as 089 * well as collecting any other obsolete references. This was done because WeakReference may allow the reference to be 090 * held longer than it has lived, in the case that the GC does not run, the reference handler will perform the 091 * necessary actions to make sure the entity is correctly nulled.</p> 092 * 093 * <p>Here are examples on the usage of this class.</p> 094 * 095 * <p>WeakEntity can and should be used when storing entities, such as players inside a collection or reference.</p> 096 * <pre><code> 097 * private final Map<WeakEntity<Player>, Integer> score = 098 * Maps.newHashMap(); 099 * 100 * // Add player 101 * Player player = ... 102 * int playerScore = ... 103 * score.put(WeakEntity.of(player), playerScore); 104 * 105 * // Checking player 106 * for (WeakEntity<Player> weakEntity : score.keySet()) { 107 * // This is simply proof of concept, don't check if it is null 108 * // then try to obtain it 109 * // Or try to hide the player from himself/herself 110 * if (weakEntity.isNull()) 111 * continue; 112 * weakEntity.obtain().hide(weakEntity); 113 * } 114 * </code></pre> 115 * 116 * <p>WeakEntity acts like an optional which can be used to eliminate the need to check for {@code null}.</p> 117 * <pre><code> 118 * // Finding the player 119 * // Don't do this in production-stage code, it doesn't work the way the name implies! 120 * public WeakEntity<Bat> findClosest(Player player, int range) { 121 * for (Entity entity : player.withinRange(range)) { 122 * if (entity instanceof Bat) { 123 * // Unable to be null, so we use of(Entity) 124 * // Instead of orEmpty(Entity) 125 * return WeakEntity.of(entity); 126 * } 127 * } 128 * 129 * // No bats near the player, it's empty 130 * return WeakEntity.empty(); 131 * } 132 * 133 * // Find a Bat closest to the player, or spawn a new one, and accelerate it upwards (just because) 134 * findClosest(player, 69) 135 * .or(EntityBuilder.create().build(TridentBat.class)) 136 * .setVelocity(new Vector(0, 10, 0)); 137 * </code></pre> 138 * 139 * <p>WeakEntity does not need to be instantiated to find in a collection.</p> 140 * <pre><code> 141 * Map<WeakEntity<Entity>, Object> map = Maps.newHashMap(); 142 * ... 143 * Object o = map.get(WeakEntity.searchFor(entity)); 144 * </code></pre> 145 * 146 * <p>Finally, WeakEntity can be used to find and prevent bugs which would otherwise cause NullPointerExceptions.</p> 147 * <pre><code> 148 * // Using it to find bugs 149 * // Oh, leave it here for a while until I implement a different method, then I'll come back to it 150 * WeakEntity<Player> weakEntity = WeakEntity.of(null); 151 * ... 152 * // I was smart and used obtain() instead of entity() 153 * weakEntity.obtain().hide(); 154 * 155 * // Code errors 156 * 157 * // Go back to the line you found in the stacktrace 158 * // Looks like it was on the line that tried to obtain the entity 159 * // from a WeakEntity 160 * // We remember that we implemented a find player method later on 161 * 162 * // Final code 163 * WeakEntity<Player> weakEntity = WeakEntity.of(player()); 164 * </code></pre> 165 * 166 * @author The TridentSDK Team 167 * @since 0.3-alpha-DP 168 */ 169@ThreadSafe 170public final class WeakEntity<T extends Entity> { 171 private static final WeakEntity<?> NULL_ENTITY = new WeakEntity<>(new SafeReference<>(null)); 172 private static final CleaningRefCollection REFERENCE_QUEUE = CleaningRefCollection.newQueue(); 173 174 // Not automatically instantiated by the server, won't be started if it is not needed 175 static { 176 Thread thread = new Thread(REFERENCE_QUEUE, "Trident - Reference Handler"); 177 thread.setDaemon(true); 178 thread.setPriority(Thread.MAX_PRIORITY); 179 thread.start(); 180 } 181 182 private final SafeReference<T> referencedEntity; 183 private volatile Object finder; 184 185 private WeakEntity(SafeReference<T> referencedEntity) { 186 this.referencedEntity = referencedEntity; 187 } 188 189 /** 190 * Obtains a WeakEntity which holds a {@code null} referenced entity 191 * 192 * <p>This method does not produce a new object. The instance of an empty WeakEntity is held in a {@code static} 193 * field inside this class.</p> 194 * 195 * @param <T> the type of entity to hold {@code null} for 196 * @return a WeakEntity which holds {@code null} 197 */ 198 public static <T extends Entity> WeakEntity<T> empty() { 199 return (WeakEntity<T>) NULL_ENTITY; 200 } 201 202 /** 203 * Obtains a WeakEntity which holds the specified entity 204 * 205 * <p>The entity which is specified will become {@code null} when it is dereferenced from the server.</p> 206 * 207 * <p>This may be used in the place of {@link #orEmpty(net.tridentsdk.entity.Entity)} if creation of a new 208 * WeakEntity for a {@code null} entity is OK. In other words, this is a fast-path (albeit the fact that the 209 * difference in performance is negligible in comparison with creation overhead and memory) for the 210 * {@link #orEmpty(net.tridentsdk.entity.Entity)}.</p> 211 * 212 * @param referencedEntity the entity to hold until it is removed 213 * @param <T> the type of entity to hold 214 * @return a WeakEntity which holds the entity until it becomes {@code null} 215 */ 216 public static <T extends Entity> WeakEntity<T> of(T referencedEntity) { 217 WeakEntity<T> weakEntity = new WeakEntity<>(new SafeReference<>(referencedEntity)); 218 REFERENCE_QUEUE.put(weakEntity); 219 return weakEntity; 220 } 221 222 /** 223 * Obtains a WeakEntity which is either a {@link #empty()} reference or a reference 224 * {@link #of(net.tridentsdk.entity.Entity)}, depending on if the specified entity is {@code null} or 225 * non-{@code null}, respectively 226 * 227 * <p>If the returned WeakEntity holds {@code null}, and is equivalent to {@link #empty()}, then no instance of 228 * WeakEntity was created.</p> 229 * 230 * <p>If the referenced entity is <em>known</em> to be {@code null}, then do not use this method. Although it is 231 * still correct, if it is not possible for it to be {@code null}, use an {@link #empty()} WeakEntity.</p> 232 * 233 * @param referencedEntity the entity to obtain the reference for 234 * @param <T> the type of entity to hold 235 * @return a WeakEntity which holds the specified entity, or {@link #empty()} if the specified entity to reference 236 * is {@code null} 237 */ 238 public static <T extends Entity> WeakEntity<T> orEmpty(T referencedEntity) { 239 if (referencedEntity == null) 240 return empty(); 241 return of(referencedEntity); 242 } 243 244 /** 245 * Removes the references of the entity from any WeakEntity instances which are non-null 246 * 247 * <p>This method was meant to be used only for the implementation. The calling of this method by a non-Trident 248 * class has no effect.</p> 249 * 250 * @param entity the entity to dereference and clear from WeakEntity 251 * @throws IllegalAccessException when the caller is not Trident 252 */ 253 @InternalUseOnly 254 public static void clearReferencesTo(Entity entity) throws IllegalAccessException { 255 if (!Trident.isTrident()) 256 throw new IllegalAccessException("WeakEntities may only be cleared by a Trident class"); 257 REFERENCE_QUEUE.clearReference(entity); 258 } 259 260 /** 261 * Provides an object which possesses the matching properties for a WeakEntity 262 * 263 * <p>This is needed when obtaining a WeakEntity from a collection. The returned object overrides equals and 264 * hashCode, as well as toString to mimic the actual referenced entity. If the reference is {@code null}, then no 265 * new object is created and the method returns a cached version of the object. Because the WeakEntity's original 266 * implementation also delegates the same identifying functions to the reference, this is the preferred way to find 267 * a WeakEntity from a collection or to match with a stored version.</p> 268 * 269 * <p>This method never returns null. If there is no entity which is known to exist with a WeakEntity, then the 270 * returned object {@code searchFor(null).equals(null)}.</p> 271 * 272 * @param entity the entity to get the finder for 273 * @return an object that possesses the properties of the entity so that they match up with an WeakEntity containing 274 * the same entity 275 */ 276 public static Object searchFor(Entity entity) { 277 if (entity == null) 278 return RefList.NULL; 279 return REFERENCE_QUEUE.finderOf(entity); 280 } 281 282 /** 283 * Obtains an iterator which cleans elements in a collection which holds {@link net.tridentsdk.util.WeakEntity} 284 * instances 285 * 286 * <p>This method is recommended for usage with any collection which holds instances of 287 * {@link net.tridentsdk.util.WeakEntity}, as although it may reduce memory leaks caused by resources being held 288 * after a referencing class is not fully unloaded, one WeakEntity is referenced is several places internally.</p> 289 * 290 * <p>This supports all collections that are part of the Java Collections Framework. In particular, collections 291 * which have 2 keys and obtain entry sets with a {@link net.tridentsdk.util.WeakEntity} in the key, value, or both 292 * are supported by this iterator.</p> 293 * 294 * <p>Normal use case: 295 * <pre><code> 296 * List<WeakEntity<Player>> list = Lists.newArrayList(); 297 * 298 * for (WeakEntity<Player> weakEntity : WeakEntity.iterate(list)) { 299 * // Obtain can be used here 300 * } 301 * </code></pre></p> 302 * 303 * <p>No support is provided for iteration-then-remove, as the semantics of the iterator precede checks for nullity 304 * before the element is returned.</p> 305 * 306 * @param collect the collection to clean of nulled references 307 * @param <E> the element type for the iterator 308 * @return the iterator which cleans a collection possibly containing {@code null} references to weak entities 309 */ 310 public static <E> CleaningIterator<E> iterate(Collection<E> collect) { 311 Type type = ((ParameterizedType) collect.getClass().getGenericSuperclass()).getActualTypeArguments()[0]; 312 TypeToken token = TypeToken.of(type); 313 CleaningIterator<E> iterator; 314 315 // The collection is an entry set 316 if (Map.Entry.class.isAssignableFrom(token.getRawType())) { 317 iterator = new CleaningIterator<E>(collect.iterator()) { 318 @Override 319 boolean shouldRemove(E entry) { 320 Map.Entry e = (Map.Entry) entry; 321 322 Object key = e.getKey(); 323 if (key instanceof WeakEntity) { 324 WeakEntity entity = (WeakEntity) key; 325 if (entity.isNull()) { 326 return true; 327 } 328 } 329 330 Object value = e.getValue(); 331 if (value instanceof WeakEntity) { 332 WeakEntity entity = (WeakEntity) value; 333 if (entity.isNull()) { 334 return true; 335 } 336 } 337 338 return false; 339 } 340 }; 341 } 342 // The collection has weak entities 343 else { 344 iterator = new CleaningIterator<E>(collect.iterator()) { 345 @Override 346 boolean shouldRemove(E entry) { 347 if (entry instanceof WeakEntity) { 348 WeakEntity entity = (WeakEntity) entry; 349 if (entity.isNull()) { 350 return true; 351 } 352 } 353 354 // We do not skip if the first element(s) are not WeakEntities 355 // as we cannot assume the collection isn't <Object> 356 return false; 357 } 358 }; 359 } 360 361 return iterator; 362 } 363 364 /** 365 * Forces the reference handler thread to run the {@code null} or garbage reference collection cycle and reclaim 366 * memory lost by those references 367 * 368 * <p>This runs the mark sweeping strategy employed by the reference handler. Previous references are swept from 369 * the session and the thread continues to mark the {@code null} references. They are placed into a collection 370 * until the sweeping completes. When this step does complete, the collection is checked, then the references are 371 * purged from the reference queue.</p> 372 * 373 * <p>Unlike Java's default GC implementation, this method is strongly bound. This always succeeds in running the 374 * collection cycle.</p> 375 */ 376 public static void runMarkSweep() { 377 REFERENCE_QUEUE.beginSweep(); 378 } 379 380 /** 381 * Observes the reference to see if the entity is {@code null} or not accessible via the server anymore 382 * 383 * @return {@code true} to indicate the entity is removed and cannot be further referenced, in which case the 384 * instance of this object should also become {@code null} 385 */ 386 public boolean isNull() { 387 return entity() == null; 388 } 389 390 /** 391 * Obtains the instance of the referenced entity, or, if it {@link #isNull()}, then this method will return the 392 * specified fallback object, which must match the type of this object 393 * 394 * <p>The provided fallback should not be {@code null}. This is allowed, and is still correct, however, a more 395 * effective strategy is to use {@link #entity()} instead.</p> 396 * 397 * @param fallback the entity to return in place of the reference in the case that the reference is {@code null} 398 * @return the entity if non-{@code null}, or the fallback if it is 399 */ 400 public T or(T fallback) { 401 T ref = this.referencedEntity.get(); 402 return ref == null ? fallback : ref; 403 } 404 405 /** 406 * Obtains the instance of the referenced entity, or {@code null} if it has been dereferenced 407 * 408 * @return the entity which this reference points to, or {@code null} if the entity no longer exists on the server 409 */ 410 public T entity() { 411 return this.referencedEntity.get(); 412 } 413 414 /** 415 * Obtains the referenced entity, but is fail-fast 416 * 417 * <p>This method will throw an {@link java.lang.IllegalStateException} if the referenced entity is {@code null}. 418 * Usually, this should be used for debugging purposes, but can be used as a marker in the case that something 419 * within the code goes wrong.</p> 420 * 421 * @return the referenced entity, can <strong>never</strong> be {@code null} 422 */ 423 public T obtain() { 424 T ref = this.referencedEntity.get(); 425 if (ref == null) 426 throw new IllegalStateException("Obtained entity is null"); 427 return ref; 428 } 429 430 /** 431 * This removes the reference to the entity in this particular instance of WeakEntity 432 * 433 * <p>If the referenced entity is {@code null} already, no changes will take effect. The call of this method also 434 * has <em>happens-before</em> consistency to any subsequent inspection calls to this WeakEntity.</p> 435 */ 436 public void clear() { 437 this.referencedEntity.clear(); 438 } 439 440 /** 441 * Instance method of {@link #searchFor(net.tridentsdk.entity.Entity)}. See that method for the documentation and 442 * implementation. 443 * 444 * <p>This method still internally polls the reference queue for the entity's cached finder.</p> 445 * 446 * @return an Object which can be used to find WeakEntities in a collection 447 */ 448 public Object finder() { 449 return finder; 450 } 451 452 /** 453 * {@inheritDoc} 454 */ 455 @Override 456 public boolean equals(Object obj) { 457 Object o = referencedEntity.get(); 458 return obj == null ? o == null : obj.equals(o); 459 } 460 461 /** 462 * {@inheritDoc} 463 */ 464 @Override 465 public int hashCode() { 466 Object o = referencedEntity.get(); 467 return o == null ? 0 : o.hashCode(); 468 } 469 470 /** 471 * {@inheritDoc} 472 */ 473 @Override 474 public String toString() { 475 return getClass().getName() + "{referencedEntity = " + referencedEntity.get() + "}@" + hashCode(); 476 } 477 478 // Thread-visible version of WeakReference 479 private static class SafeReference<T> extends WeakReference<T> { 480 private volatile int fence = 0; 481 482 public SafeReference(T referent) { 483 super(referent); 484 } 485 486 @Override 487 public T get() { 488 int barrier = fence; 489 return super.get(); 490 } 491 492 @Override 493 public void clear() { 494 super.clear(); 495 fence = 0; 496 } 497 } 498 499 // Stores references and collects/cleans up null references 500 private static class CleaningRefCollection implements Runnable { 501 @GuardedBy("lock") 502 private RefEntry[] entries = new RefEntry[16]; 503 504 @GuardedBy("lock") 505 private int length; 506 507 // Locking mechanisms 508 private final Lock lock = new ReentrantLock(); 509 private final Condition hasNodes = lock.newCondition(); 510 511 // INVARIANT: MODIFIED THREAD-LOCALLY ONLY 512 private final Set<WeakEntity> marked = Sets.newHashSet(); 513 514 private CleaningRefCollection() { 515 } 516 517 public static CleaningRefCollection newQueue() { 518 return new CleaningRefCollection(); 519 } 520 521 public void put(WeakEntity<?> weakEntity) { 522 if (weakEntity.isNull()) return; // Don't bother with trying 523 RefList node = RefList.newNode(weakEntity, get(weakEntity.entity())); 524 add(node.finder(), node); 525 } 526 527 // Clears references to the entity, forcing the sweep to run 528 // this leaves the empty node to be collected by the sweeper 529 public void clearReference(Entity entity) { 530 RefList entities = get(entity); 531 532 if (entities == null) 533 return; 534 for (WeakEntity<?> e : entities) 535 e.clear(); 536 537 // Clear unused reference 538 beginSweep(); 539 } 540 541 public Object finderOf(Entity entity) { 542 RefList node = get(entity); 543 if (node == null) 544 return RefList.NULL; 545 546 return node.finder(); 547 } 548 549 public void beginSweep() { 550 lock.lock(); 551 try { 552 hasNodes.signal(); 553 } finally { 554 lock.unlock(); 555 } 556 } 557 558 @Override 559 public void run() { 560 while (true) { 561 try { 562 lock.lockInterruptibly(); 563 while (marked.isEmpty()) 564 hasNodes.await(); 565 566 // Step 1: find nodes 567 Set<RefEntry> entries = entries(); 568 569 // Step 2: mark 570 for (RefEntry entry : entries) { 571 Set<WeakEntity> weakRefs = entry.val().refs(); 572 573 marked.addAll(weakRefs.stream().filter(WeakEntity::isNull).collect(Collectors.toList())); 574 } 575 576 // Step 3: sweep 577 for (RefEntry entry : entries) { 578 Set<WeakEntity> refs = entry.val().refs(); 579 refs.removeAll(marked); 580 581 if (refs.isEmpty()) { 582 remove(entry.val()); 583 } 584 } 585 586 // Remove marked entries 587 marked.clear(); 588 } catch (InterruptedException ignored) { 589 // Run by a daemon thread, doesn't matter if it was interrupted 590 } finally { 591 lock.unlock(); 592 } 593 } 594 } 595 596 // Collection ops 597 private void add(Object key, RefList value) { 598 lock.lock(); 599 try { 600 int hash = hash(key); 601 RefEntry toSet = this.search(key, value, hash); 602 toSet.setHash(hash); 603 toSet.setVal(value); 604 } finally { 605 lock.unlock(); 606 } 607 } 608 609 private RefList get(Object key) { 610 lock.lock(); 611 try { 612 int hash = hash(key); 613 RefEntry node = this.loop(key, this.entries[hash]); 614 if (node == null) 615 return null; 616 else 617 return node.val(); 618 } finally { 619 lock.unlock(); 620 } 621 } 622 623 private void remove(Object key) { 624 try { 625 RefEntry head = this.entries[hash(key)]; 626 if (head == null) 627 return; 628 629 this.remove(key, head); 630 } finally { 631 lock.unlock(); 632 } 633 } 634 635 private Set<RefEntry> entries() { 636 Set<RefEntry> set = Sets.newHashSet(); 637 for (RefEntry entry : entries) { 638 if (entry == null) 639 continue; 640 set.add(entry); 641 } 642 return set; 643 } 644 645 private void resize() { 646 lock.lock(); 647 try { 648 if (this.length > entries.length - 2) { 649 int newLen = entries.length * 2; 650 651 RefEntry[] resize = new RefEntry[newLen]; 652 System.arraycopy(entries, 0, resize, 0, length); 653 this.entries = resize; 654 } 655 } finally { 656 lock.unlock(); 657 } 658 } 659 660 private int hash(Object key) { 661 long h = key.hashCode(); 662 h = (h >> 16 ^ h) * 0x33L; 663 h = (h >> 16 ^ h) * 0x33L; 664 h = h >> 16 ^ h; 665 666 return (int) (h & ((long) entries.length - 1)); 667 } 668 669 private RefEntry loop(Object key, RefEntry head) { 670 RefEntry tail = head; 671 while (tail != null) { 672 if (tail.key().equals(key)) 673 return tail; 674 tail = tail.next(); 675 } 676 677 return null; 678 } 679 680 private RefEntry search(Object k, RefList v, int hash) { 681 RefEntry head = this.entries[hash]; 682 RefEntry tail = this.loop(k, head); 683 if (tail != null) 684 return tail; 685 else 686 return this.create(k, null, v, hash); 687 } 688 689 private RefEntry create(Object k, RefEntry previous, RefList v, int hash) { 690 RefEntry node = new RefEntry(k, v, hash); 691 if (previous == null) { 692 this.entries[hash] = node; 693 this.length++; 694 this.resize(); 695 return node; 696 } 697 698 previous.setNext(node); 699 this.length++; 700 this.resize(); 701 return node; 702 } 703 704 private void remove(Object k, RefEntry head) { 705 RefEntry leading = head; 706 RefEntry tail = leading == null ? null : leading.next(); 707 708 while (tail != null) { 709 if (tail.key().equals(k)) { 710 leading.setNext(tail.next()); 711 this.length--; 712 return; 713 } 714 715 tail = tail.next(); 716 leading = leading.next(); 717 } 718 719 if (leading != null && leading.key().equals(k)) 720 this.entries[leading.hash()] = null; 721 722 this.length--; 723 } 724 } 725 726 private static class RefEntry { 727 private final Object key; 728 729 @GuardedBy("RefList.lock") 730 private RefList list; 731 @GuardedBy("RefList.lock") 732 private int hash; 733 @GuardedBy("RefList.lock") 734 private RefEntry next; 735 736 private RefEntry(Object key, RefList entity, int hash) { 737 this.key = key; 738 this.list = entity; 739 this.hash = hash; 740 } 741 742 public static RefEntry newEntry(Object key, RefList entity, int hash) { 743 return new RefEntry(key, entity, hash); 744 } 745 746 public Object key() { 747 return this.key; 748 } 749 750 public RefList val() { 751 return this.list; 752 } 753 754 public void setVal(RefList list) { 755 this.list = list; 756 } 757 758 public int hash() { 759 return this.hash; 760 } 761 762 public void setHash(int hash) { 763 this.hash = hash; 764 } 765 766 public RefEntry next() { 767 return this.next; 768 } 769 770 public void setNext(RefEntry next) { 771 this.next = next; 772 } 773 } 774 775 // A set of references assigned to a particular entity 776 private static class RefList implements Iterable<WeakEntity> { 777 private static final Entity NULL = new Entity() { 778 @Override public void teleport(double x, double y, double z) {} 779 @Override public void teleport(Entity entity) {} 780 781 @Override 782 public void teleport(Position position) { 783 } 784 @Override public World world() {return null;} 785 @Override public Position position() {return null;} 786 @Override public Vector velocity() {return null;} 787 @Override public void setVelocity(Vector vector) {} 788 @Override public boolean onGround() {return false;} 789 @Override public Set<Entity> withinRange(double radius) {return null;} 790 @Override public String displayName() {return null;} 791 @Override public void setDisplayName(String name) {} 792 @Override public boolean isNameVisible() {return false;} 793 @Override public boolean isSilent() {return false;} 794 @Override public int entityId() {return 0;} 795 @Override public UUID uniqueId() {return null;} 796 @Override public void remove() {} 797 @Override public Entity passenger() {return null;} 798 @Override public void setPassenger(Entity entity) {} 799 @Override public void eject() {} 800 @Override public EntityType type() {return null;} 801 @Override public void applyProperties(EntityProperties properties) {} 802 @Override public void setSize(float width, float height) {} 803 @Override public BoundingBox boundingBox() {return null;} 804 805 @Override 806 public int hashCode() { 807 return 0; 808 } 809 810 @Override 811 public boolean equals(Object obj) { 812 return obj == null; 813 } 814 }; 815 816 @GuardedBy("lock") 817 private final Set<WeakEntity> weakEntities; 818 private final Object finder; 819 private final Object lock = new Object(); 820 821 private RefList(final WeakEntity entity, RefList node) { 822 entity.finder = this.finder = new Object() { 823 @Override 824 public int hashCode() { 825 return entity.hashCode(); 826 } 827 828 @Override 829 public boolean equals(Object obj) { 830 return entity.equals(obj); 831 } 832 }; 833 834 Set<WeakEntity> original; 835 if (node == null) 836 original = Sets.newHashSet(); 837 else 838 original = node.weakEntities; 839 840 if (original == null) 841 original = Sets.newHashSet(); 842 original.add(entity); 843 844 weakEntities = original; 845 } 846 847 public static RefList newNode(WeakEntity entity, RefList node) { 848 return new RefList(entity, node); 849 } 850 851 // Removes the references which are empty 852 public void clean() throws InterruptedException { 853 synchronized (lock) { 854 weakEntities.stream().filter(WeakEntity::isNull).forEach(weakEntities::remove); 855 } 856 } 857 858 // Removes a specified entity 859 public void clear(WeakEntity entity) { 860 synchronized (lock) { 861 weakEntities.remove(entity); 862 } 863 } 864 865 public Set<WeakEntity> refs() { 866 synchronized (lock) { 867 return weakEntities; 868 } 869 } 870 871 @Override 872 public Iterator<WeakEntity> iterator() { 873 synchronized (lock) { 874 return weakEntities.iterator(); 875 } 876 } 877 878 // Used to reference the entity without actually using it 879 public Object finder() { 880 return this.finder; 881 } 882 } 883 884 /** 885 * An iterator for a collection holding {@link net.tridentsdk.util.WeakEntity}s. 886 * 887 * <p>Before iterating, this method makes sure {@link WeakEntity#isNull()} returns {@code false}. In the case that 888 * it is {@code true}, the iterator removes that entry from the collection being iterated.</p> 889 * 890 * <p>This iterator is not shareable between concurrent. It is designed for single-threaded iteration. The changes 891 * made in this iterator do not necessarily reflect to the changes to different iterators of the same collection. 892 * This will only become a problem in concurrent iteration, depending on the iterator implementation, as specified 893 * by the collection class.</p> 894 * 895 * @param <E> the element type iterated by this iterator 896 */ 897 @NotThreadSafe 898 // An iterator which clears entries based on their WeakEntity nullstate 899 public static abstract class CleaningIterator<E> implements Iterator<E>, Iterable<E> { 900 private final Iterator<E> iterator; 901 private E object; 902 903 abstract boolean shouldRemove(E entry); 904 905 CleaningIterator(Iterator<E> iterator) { 906 this.iterator = iterator; 907 } 908 909 /** 910 * This method also advances the iterator index 911 * 912 * {@inheritDoc} 913 */ 914 @Override 915 public boolean hasNext() { 916 while (iterator.hasNext()) { 917 E entry = iterator.next(); 918 if (entry == null) { 919 continue; 920 } 921 922 if (shouldRemove(entry)) { 923 iterator.remove(); 924 } else { 925 object = entry; 926 return true; 927 } 928 } 929 930 return false; 931 } 932 933 @Override 934 public E next() { 935 E o = object; 936 if (o == null) { 937 if (!hasNext()) { 938 throw new NoSuchElementException(); 939 } 940 } 941 942 object = null; 943 return o; 944 } 945 946 @Override 947 public void remove() { 948 iterator.remove(); 949 } 950 951 @Override 952 public Iterator<E> iterator() { 953 return this; 954 } 955 } 956}