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&lt;WeakEntity&lt;Player&gt;, Integer&gt; 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&lt;Player&gt; 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&lt;Bat&gt; 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&lt;WeakEntity&lt;Entity&gt;, Object&gt; 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&lt;Player&gt; 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&lt;Player&gt; 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&lt;WeakEntity&lt;Player&gt;&gt; list = Lists.newArrayList();
297     *
298     *     for (WeakEntity&lt;Player&gt; 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}