diff options
10 files changed, 866 insertions, 404 deletions
diff --git a/src/main/java/net/minecraft/server/ChunkProviderServer.java b/src/main/java/net/minecraft/server/ChunkProviderServer.java index 3242f440..6a5fe5b3 100644 --- a/src/main/java/net/minecraft/server/ChunkProviderServer.java +++ b/src/main/java/net/minecraft/server/ChunkProviderServer.java @@ -11,20 +11,20 @@ import java.util.Set; import java.util.Random; import org.bukkit.Server; -import org.bukkit.craftbukkit.util.LongHashset; -import org.bukkit.craftbukkit.util.LongHashtable; +import org.bukkit.craftbukkit.util.LongHashSet; +import org.bukkit.craftbukkit.util.LongObjectHashMap; import org.bukkit.event.world.ChunkUnloadEvent; // CraftBukkit end public class ChunkProviderServer implements IChunkProvider { // CraftBukkit start - public LongHashset unloadQueue = new LongHashset(); + public LongHashSet unloadQueue = new LongHashSet(); public Chunk emptyChunk; public IChunkProvider chunkProvider; // CraftBukkit private IChunkLoader e; public boolean forceChunkLoad = false; // true -> false - public LongHashtable<Chunk> chunks = new LongHashtable<Chunk>(); + public LongObjectHashMap<Chunk> chunks = new LongObjectHashMap<Chunk>(); public List chunkList = new ArrayList(); public WorldServer world; // CraftBukkit end diff --git a/src/main/java/net/minecraft/server/SpawnerCreature.java b/src/main/java/net/minecraft/server/SpawnerCreature.java index a4846225..c9870fd1 100644 --- a/src/main/java/net/minecraft/server/SpawnerCreature.java +++ b/src/main/java/net/minecraft/server/SpawnerCreature.java @@ -7,33 +7,14 @@ import java.util.List; import java.util.Random; // CraftBukkit start -import org.bukkit.craftbukkit.util.LongBaseHashtable; -import org.bukkit.craftbukkit.util.EntryBase; +import org.bukkit.craftbukkit.util.LongObjectHashMap; import org.bukkit.craftbukkit.util.LongHash; import org.bukkit.event.entity.CreatureSpawnEvent.SpawnReason; // CraftBukkit end public final class SpawnerCreature { - // CraftBukkit start - // private static HashMap b = new HashMap(); // Moved local to spawnEntities - static private class ChunkEntry extends EntryBase { - public boolean spawn; - - public ChunkEntry(int x, int z, boolean spawn) { - super(LongHash.toLong(x, z)); - this.spawn = spawn; - } - - int getX() { - return LongHash.msw(key); - } - - int getZ() { - return LongHash.lsw(key); - } - } - // CraftBukkit end + private static LongObjectHashMap b = new LongObjectHashMap(); // CraftBukkit - HashMap -> LongObjectHashMap protected static final Class[] a = new Class[] { EntitySpider.class, EntityZombie.class, EntitySkeleton.class}; protected static ChunkPosition getRandomPosition(World world, int i, int j) { @@ -49,10 +30,7 @@ public final class SpawnerCreature { if (!flag && !flag1) { return 0; } else { - // CraftBukkit start - // b.clear(); - LongBaseHashtable chunkCoords = new LongBaseHashtable(); - // CraftBukkit end + b.clear(); int i; int j; @@ -67,13 +45,14 @@ public final class SpawnerCreature { for (int l = -b0; l <= b0; ++l) { for (int i1 = -b0; i1 <= b0; ++i1) { boolean flag2 = l == -b0 || l == b0 || i1 == -b0 || i1 == b0; + // CraftBukkit start - long chunkCoord = LongHash.toLong(l + k, i1 + j); + long chunkCoords = LongHash.toLong(l + k, i1 + j); if (!flag2) { - chunkCoords.put(new ChunkEntry(l + k, i1 + j, false)); - } else if (!chunkCoords.containsKey(chunkCoord)) { - chunkCoords.put(new ChunkEntry(l + k, i1 + j, true)); + b.put(chunkCoords, false); + } else if (!b.containsKey(chunkCoords)) { + b.put(chunkCoords, true); } // CraftBukkit end } @@ -82,7 +61,6 @@ public final class SpawnerCreature { i = 0; ChunkCoordinates chunkcoordinates = worldserver.getSpawn(); - java.util.ArrayList<EntryBase> b = chunkCoords.entries(); // CraftBukkit EnumCreatureType[] aenumcreaturetype = EnumCreatureType.values(); j = aenumcreaturetype.length; @@ -110,13 +88,15 @@ public final class SpawnerCreature { // CraftBukkit end if ((!enumcreaturetype.d() || flag1) && (enumcreaturetype.d() || flag) && worldserver.a(enumcreaturetype.a()) <= limit * b.size() / 256) { // CraftBukkit - use per-world limits + Iterator iterator = b.keySet().iterator(); - // CraftBukkit start label108: - for (EntryBase base : b) { - ChunkEntry entry = (SpawnerCreature.ChunkEntry) base; - if (!entry.spawn) { - ChunkPosition chunkposition = getRandomPosition(worldserver, entry.getX(), entry.getZ()); + while (iterator.hasNext()) { + // CraftBukkit start + long key = ((Long) iterator.next()).longValue(); + + if (!((Boolean) b.get(key)).booleanValue()) { + ChunkPosition chunkposition = getRandomPosition(worldserver, LongHash.msw(key), LongHash.lsw(key)); // CraftBukkit end int k1 = chunkposition.x; int l1 = chunkposition.y; diff --git a/src/main/java/net/minecraft/server/World.java b/src/main/java/net/minecraft/server/World.java index ae3dda73..3a1bdc1f 100644 --- a/src/main/java/net/minecraft/server/World.java +++ b/src/main/java/net/minecraft/server/World.java @@ -9,7 +9,7 @@ import java.util.concurrent.Callable; // CraftBukkit start import org.bukkit.Bukkit; -import org.bukkit.craftbukkit.util.LongHashset; +import org.bukkit.craftbukkit.util.LongHashSet; import org.bukkit.craftbukkit.util.UnsafeList; import org.bukkit.generator.ChunkGenerator; import org.bukkit.craftbukkit.CraftServer; @@ -60,7 +60,7 @@ public abstract class World implements IBlockAccess { // CraftBukkit start - public, longhashset public boolean allowMonsters = true; public boolean allowAnimals = true; - protected LongHashset chunkTickList = new LongHashset(); + protected LongHashSet chunkTickList = new LongHashSet(); public long ticksPerAnimalSpawns; public long ticksPerMonsterSpawns; // CraftBukkit end @@ -1057,12 +1057,12 @@ public abstract class World implements IBlockAccess { for (i = 0; i < this.j.size(); ++i) { entity = (Entity) this.j.get(i); // CraftBukkit start - fixed an NPE, don't process entities in chunks queued for unload - ChunkProviderServer chunkProviderServer = ((WorldServer) entity.world).chunkProviderServer; - if (chunkProviderServer.unloadQueue.containsKey(MathHelper.floor(entity.locX) >> 4, MathHelper.floor(entity.locZ) >> 4)) { + if (entity == null) { continue; } - if (entity == null) { + ChunkProviderServer chunkProviderServer = ((WorldServer) entity.world).chunkProviderServer; + if (chunkProviderServer.unloadQueue.contains(MathHelper.floor(entity.locX) >> 4, MathHelper.floor(entity.locZ) >> 4)) { continue; } // CraftBukkit end @@ -1103,7 +1103,7 @@ public abstract class World implements IBlockAccess { // CraftBukkit start - don't tick entities in chunks queued for unload ChunkProviderServer chunkProviderServer = ((WorldServer) entity.world).chunkProviderServer; - if (chunkProviderServer.unloadQueue.containsKey(MathHelper.floor(entity.locX) >> 4, MathHelper.floor(entity.locZ) >> 4)) { + if (chunkProviderServer.unloadQueue.contains(MathHelper.floor(entity.locX) >> 4, MathHelper.floor(entity.locZ) >> 4)) { continue; } // CraftBukkit end @@ -1147,7 +1147,7 @@ public abstract class World implements IBlockAccess { // CraftBukkit start - don't tick entities in chunks queued for unload ChunkProviderServer chunkProviderServer = ((WorldServer) tileentity.world).chunkProviderServer; - if (chunkProviderServer.unloadQueue.containsKey(tileentity.x >> 4, tileentity.z >> 4)) { + if (chunkProviderServer.unloadQueue.contains(tileentity.x >> 4, tileentity.z >> 4)) { continue; } // CraftBukkit end @@ -1819,7 +1819,7 @@ public abstract class World implements IBlockAccess { for (int i1 = -b0; i1 <= b0; ++i1) { // CraftBukkit start - don't tick chunks queued for unload ChunkProviderServer chunkProviderServer = ((WorldServer) entityhuman.world).chunkProviderServer; - if (chunkProviderServer.unloadQueue.containsKey(l + j, i1 + k)) { + if (chunkProviderServer.unloadQueue.contains(l + j, i1 + k)) { continue; } // CraftBukkit end diff --git a/src/main/java/org/bukkit/craftbukkit/util/EntryBase.java b/src/main/java/org/bukkit/craftbukkit/util/EntryBase.java deleted file mode 100644 index 4f71657b..00000000 --- a/src/main/java/org/bukkit/craftbukkit/util/EntryBase.java +++ /dev/null @@ -1,9 +0,0 @@ -package org.bukkit.craftbukkit.util; - -public class EntryBase { - protected long key; - - public EntryBase(long key) { - this.key = key; - } -} diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongBaseHashtable.java b/src/main/java/org/bukkit/craftbukkit/util/LongBaseHashtable.java deleted file mode 100644 index 8732597c..00000000 --- a/src/main/java/org/bukkit/craftbukkit/util/LongBaseHashtable.java +++ /dev/null @@ -1,112 +0,0 @@ -package org.bukkit.craftbukkit.util; - -import static org.bukkit.craftbukkit.util.Java15Compat.Arrays_copyOf; - -import java.util.ArrayList; - -public class LongBaseHashtable extends LongHash { - - EntryBase[][][] values = new EntryBase[256][][]; - EntryBase cache = null; - - public void put(int msw, int lsw, EntryBase entry) { - put(entry); - } - - public EntryBase getEntry(int msw, int lsw) { - return getEntry(toLong(msw, lsw)); - } - - public synchronized void put(EntryBase entry) { - int mainIdx = (int) (entry.key & 255); - EntryBase[][] outer = this.values[mainIdx]; - if (outer == null) this.values[mainIdx] = outer = new EntryBase[256][]; - - int outerIdx = (int) ((entry.key >> 32) & 255); - EntryBase[] inner = outer[outerIdx]; - - if (inner == null) { - outer[outerIdx] = inner = new EntryBase[5]; - inner[0] = this.cache = entry; - } else { - int i; - for (i = 0; i < inner.length; i++) { - if (inner[i] == null || inner[i].key == entry.key) { - inner[i] = this.cache = entry; - return; - } - } - - outer[outerIdx] = inner = Arrays_copyOf(inner, i + i); - inner[i] = entry; - } - } - - public synchronized EntryBase getEntry(long key) { - return containsKey(key) ? cache : null; - } - - public synchronized boolean containsKey(long key) { - if (this.cache != null && cache.key == key) return true; - - int outerIdx = (int) ((key >> 32) & 255); - EntryBase[][] outer = this.values[(int) (key & 255)]; - if (outer == null) return false; - - EntryBase[] inner = outer[outerIdx]; - if (inner == null) return false; - - for (int i = 0; i < inner.length; i++) { - EntryBase e = inner[i]; - if (e == null) { - return false; - } else if (e.key == key) { - this.cache = e; - return true; - } - } - return false; - } - - public synchronized void remove(long key) { - EntryBase[][] outer = this.values[(int) (key & 255)]; - if (outer == null) return; - - EntryBase[] inner = outer[(int) ((key >> 32) & 255)]; - if (inner == null) return; - - for (int i = 0; i < inner.length; i++) { - if (inner[i] == null) continue; - - if (inner[i].key == key) { - for (i++; i < inner.length; i++) { - if (inner[i] == null) break; - inner[i - 1] = inner[i]; - } - - inner[i-1] = null; - this.cache = null; - return; - } - } - } - - public synchronized ArrayList<EntryBase> entries() { - ArrayList<EntryBase> ret = new ArrayList<EntryBase>(); - - for (EntryBase[][] outer : this.values) { - if (outer == null) continue; - - for (EntryBase[] inner : outer) { - if (inner == null) continue; - - for (EntryBase entry : inner) { - if (entry == null) break; - - ret.add(entry); - } - } - } - return ret; - } -} diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongHash.java b/src/main/java/org/bukkit/craftbukkit/util/LongHash.java index 5cb09ed7..691cafd0 100644 --- a/src/main/java/org/bukkit/craftbukkit/util/LongHash.java +++ b/src/main/java/org/bukkit/craftbukkit/util/LongHash.java @@ -1,6 +1,6 @@ package org.bukkit.craftbukkit.util; -public abstract class LongHash { +public class LongHash { public static long toLong(int msw, int lsw) { return ((long) msw << 32) + lsw - Integer.MIN_VALUE; } @@ -12,16 +12,4 @@ public abstract class LongHash { public static int lsw(long l) { return (int) (l & 0xFFFFFFFF) + Integer.MIN_VALUE; } - - public boolean containsKey(int msw, int lsw) { - return containsKey(toLong(msw, lsw)); - } - - public void remove(int msw, int lsw) { - remove(toLong(msw, lsw)); - } - - public abstract boolean containsKey(long key); - - public abstract void remove(long key); } diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongHashSet.java b/src/main/java/org/bukkit/craftbukkit/util/LongHashSet.java new file mode 100644 index 00000000..22c96c5a --- /dev/null +++ b/src/main/java/org/bukkit/craftbukkit/util/LongHashSet.java @@ -0,0 +1,301 @@ +/* + Based on CompactHashSet Copyright 2011 Ontopia Project + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +*/ + +package org.bukkit.craftbukkit.util; + +import java.util.Iterator; +import java.util.ConcurrentModificationException; +import java.util.NoSuchElementException; + +public class LongHashSet { + private final static int INITIAL_SIZE = 3; + private final static double LOAD_FACTOR = 0.75; + + private final static long FREE = 0; + private final static long REMOVED = Long.MIN_VALUE; + + private int freeEntries; + private int elements; + private long[] values; + private int modCount; + + public LongHashSet() { + this(INITIAL_SIZE); + } + + public LongHashSet(int size) { + values = new long[(size==0 ? 1 : size)]; + elements = 0; + freeEntries = values.length; + modCount = 0; + } + + public Iterator iterator() { + return new Itr(); + } + + public int size() { + return elements; + } + + public boolean isEmpty() { + return elements == 0; + } + + public boolean contains(int msw, int lsw) { + return contains(LongHash.toLong(msw, lsw)); + } + + public boolean contains(long value) { + int hash = hash(value); + int index = (hash & 0x7FFFFFFF) % values.length; + int offset = 1; + + // search for the object (continue while !null and !this object) + while(values[index] != FREE && !(hash(values[index]) == hash && values[index] == value)) { + index = ((index + offset) & 0x7FFFFFFF) % values.length; + offset = offset * 2 + 1; + + if (offset == -1) { + offset = 2; + } + } + + return values[index] != FREE; + } + + public boolean add(int msw, int lsw) { + return add(LongHash.toLong(msw, lsw)); + } + + public boolean add(long value) { + int hash = hash(value); + int index = (hash & 0x7FFFFFFF) % values.length; + int offset = 1; + int deletedix = -1; + + // search for the object (continue while !null and !this object) + while(values[index] != FREE && !(hash(values[index]) == hash && values[index] == value)) { + // if there's a deleted object here we can put this object here, + // provided it's not in here somewhere else already + if (values[index] == REMOVED) { + deletedix = index; + } + + index = ((index + offset) & 0x7FFFFFFF) % values.length; + offset = offset * 2 + 1; + + if (offset == -1) { + offset = 2; + } + } + + if (values[index] == FREE) { + if (deletedix != -1) { // reusing a deleted cell + index = deletedix; + } else { + freeEntries--; + } + + modCount++; + elements++; + values[index] = value; + + if (1 - (freeEntries / (double) values.length) > LOAD_FACTOR) { + rehash(); + } + + return true; + } else { + return false; + } + } + + public void remove(int msw, int lsw) { + remove(LongHash.toLong(msw, lsw)); + } + + public boolean remove(long value) { + int hash = hash(value); + int index = (hash & 0x7FFFFFFF) % values.length; + int offset = 1; + + // search for the object (continue while !null and !this object) + while(values[index] != FREE && !(hash(values[index]) == hash && values[index] == value)) { + index = ((index + offset) & 0x7FFFFFFF) % values.length; + offset = offset * 2 + 1; + + if (offset == -1) { + offset = 2; + } + } + + if (values[index] != FREE) { + values[index] = REMOVED; + modCount++; + elements--; + return true; + } else { + return false; + } + } + + public void clear() { + elements = 0; + for (int ix = 0; ix < values.length; ix++) { + values[ix] = FREE; + } + + freeEntries = values.length; + modCount++; + } + + public long[] toArray() { + long[] result = new long[elements]; + long[] values = Java15Compat.Arrays_copyOf(this.values, this.values.length); + int pos = 0; + + for (long value : values) { + if (value != FREE && value != REMOVED) { + result[pos++] = value; + } + } + + return result; + } + + public long popFirst() { + for (long value : values) { + if (value != FREE && value != REMOVED) { + remove(value); + return value; + } + } + + return 0; + } + + public long[] popAll() { + long[] ret = toArray(); + clear(); + return ret; + } + + // This method copied from Murmur3, written by Austin Appleby released under Public Domain + private int hash(long value) { + value ^= value >>> 33; + value *= 0xff51afd7ed558ccdL; + value ^= value >>> 33; + value *= 0xc4ceb9fe1a85ec53L; + value ^= value >>> 33; + return (int) value; + } + + private void rehash() { + int gargagecells = values.length - (elements + freeEntries); + if (gargagecells / (double) values.length > 0.05) { + rehash(values.length); + } else { + rehash(values.length * 2 + 1); + } + } + + private void rehash(int newCapacity) { + long[] newValues = new long[newCapacity]; + + for (long value : values) { + if (value == FREE || value == REMOVED) { + continue; + } + + int hash = hash(value); + int index = (hash & 0x7FFFFFFF) % newCapacity; + int offset = 1; + + // search for the object + while (newValues[index] != FREE) { + index = ((index + offset) & 0x7FFFFFFF) % newCapacity; + offset = offset * 2 + 1; + + if (offset == -1) { + offset = 2; + } + } + + newValues[index] = value; + } + + values = newValues; + freeEntries = values.length - elements; + } + + private class Itr implements Iterator { + private int index; + private int lastReturned = -1; + private int expectedModCount; + + public Itr() { + for (index = 0; index < values.length && (values[index] == FREE || values[index] == REMOVED); index++) { + // This is just to drive the index forward to the first valid entry + } + expectedModCount = modCount; + } + + public boolean hasNext() { + return index != values.length; + } + + public Long next() { + if (modCount != expectedModCount) { + throw new ConcurrentModificationException(); + } + + int length = values.length; + if (index >= length) { + lastReturned = -2; + throw new NoSuchElementException(); + } + + lastReturned = index; + for (index += 1; index < length && (values[index] == FREE || values[index] == REMOVED); index++) { + // This is just to drive the index forward to the next valid entry + } + + if (values[lastReturned] == FREE) { + return FREE; + } else { + return values[lastReturned]; + } + } + + public void remove() { + if (modCount != expectedModCount) { + throw new ConcurrentModificationException(); + } + + if (lastReturned == -1 || lastReturned == -2) { + throw new IllegalStateException(); + } + + if (values[lastReturned] != FREE && values[lastReturned] != REMOVED) { + values[lastReturned] = REMOVED; + elements--; + modCount++; + expectedModCount = modCount; + } + } + } +} diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongHashset.java b/src/main/java/org/bukkit/craftbukkit/util/LongHashset.java deleted file mode 100644 index e5847c35..00000000 --- a/src/main/java/org/bukkit/craftbukkit/util/LongHashset.java +++ /dev/null @@ -1,178 +0,0 @@ -package org.bukkit.craftbukkit.util; - -import static org.bukkit.craftbukkit.util.Java15Compat.Arrays_copyOf; -import java.util.concurrent.locks.ReentrantReadWriteLock; -import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock; -import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock; - -public class LongHashset extends LongHash { - long[][][] values = new long[256][][]; - int count = 0; - ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(); - ReadLock rl = rwl.readLock(); - WriteLock wl = rwl.writeLock(); - - public boolean isEmpty() { - rl.lock(); - try { - return this.count == 0; - } finally { - rl.unlock(); - } - } - - public int size() { - return count; - } - - public void add(int msw, int lsw) { - add(toLong(msw, lsw)); - } - - public void add(long key) { - wl.lock(); - try { - int mainIdx = (int) (key & 255); - long outer[][] = this.values[mainIdx]; - if (outer == null) this.values[mainIdx] = outer = new long[256][]; - - int outerIdx = (int) ((key >> 32) & 255); - long inner[] = outer[outerIdx]; - - if (inner == null) { - synchronized (this) { - outer[outerIdx] = inner = new long[1]; - inner[0] = key; - this.count++; - } - } else { - int i; - for (i = 0; i < inner.length; i++) { - if (inner[i] == key) { - return; - } - } - inner = Arrays_copyOf(inner, i + 1); - outer[outerIdx] = inner; - inner[i] = key; - this.count++; - } - } finally { - wl.unlock(); - } - } - - public boolean containsKey(long key) { - rl.lock(); - try { - long[][] outer = this.values[(int) (key & 255)]; - if (outer == null) return false; - - long[] inner = outer[(int) ((key >> 32) & 255)]; - if (inner == null) return false; - - for (long entry : inner) { - if (entry == key) return true; - } - return false; - } finally { - rl.unlock(); - } - } - - public void remove(long key) { - wl.lock(); - try { - long[][] outer = this.values[(int) (key & 255)]; - if (outer == null) return; - - long[] inner = outer[(int) ((key >> 32) & 255)]; - if (inner == null) return; - - int max = inner.length - 1; - for (int i = 0; i <= max; i++) { - if (inner[i] == key) { - this.count--; - if (i != max) { - inner[i] = inner[max]; - } - - outer[(int) ((key >> 32) & 255)] = (max == 0 ? null : Arrays_copyOf(inner, max)); - return; - } - } - } finally { - wl.unlock(); - } - } - - public long popFirst() { - wl.lock(); - try { - for (long[][] outer: this.values) { - if (outer == null) continue; - - for (int i = 0; i < outer.length; i++) { - long[] inner = outer[i]; - if (inner == null || inner.length == 0) continue; - - this.count--; - long ret = inner[inner.length - 1]; - outer[i] = Arrays_copyOf(inner, inner.length - 1); - - return ret; - } - } - } finally { - wl.unlock(); - } - return 0; - } - - public long[] popAll() { - int index = 0; - wl.lock(); - try { - long[] ret = new long[this.count]; - for (long[][] outer : this.values) { - if (outer == null) continue; - - for (int oIdx = outer.length - 1; oIdx >= 0; oIdx--) { - long[] inner = outer[oIdx]; - if (inner == null) continue; - - for (long entry: inner) { - ret[index++] = entry; - } - outer[oIdx] = null; - } - } - count = 0; - return ret; - } finally { - wl.unlock(); - } - } - - public long[] keys() { - int index = 0; - rl.lock(); - try { - long[] ret = new long[this.count]; - for (long[][] outer : this.values) { - if (outer == null) continue; - - for (long[] inner : outer) { - if (inner == null) continue; - - for (long entry : inner) { - ret[index++] = entry; - } - } - } - return ret; - } finally { - rl.unlock(); - } - } -} diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongHashtable.java b/src/main/java/org/bukkit/craftbukkit/util/LongHashtable.java deleted file mode 100644 index 2b89cf94..00000000 --- a/src/main/java/org/bukkit/craftbukkit/util/LongHashtable.java +++ /dev/null @@ -1,45 +0,0 @@ -package org.bukkit.craftbukkit.util; - -import java.util.ArrayList; - -public class LongHashtable<V> extends LongBaseHashtable { - - public void put(int msw, int lsw, V value) { - put(toLong(msw, lsw), value); - } - - public V get(int msw, int lsw) { - return get(toLong(msw, lsw)); - } - - public synchronized void put(long key, V value) { - put(new Entry(key, value)); - } - - @SuppressWarnings("unchecked") - public synchronized V get(long key) { - Entry entry = ((Entry) getEntry(key)); - return entry != null ? entry.value : null; - } - - @SuppressWarnings("unchecked") - public synchronized ArrayList<V> values() { - ArrayList<V> ret = new ArrayList<V>(); - - ArrayList<EntryBase> entries = entries(); - - for (EntryBase entry : entries) { - ret.add(((Entry) entry).value); - } - return ret; - } - - private class Entry extends EntryBase { - V value; - - Entry(long k, V v) { - super(k); - this.value = v; - } - } -} diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java b/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java new file mode 100644 index 00000000..34cc0a6e --- /dev/null +++ b/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java @@ -0,0 +1,537 @@ +/* +Based on OpenLongObjectHashMap from colt. Original copyright follows: + +Copyright © 1999 CERN - European Organization for Nuclear Research. +Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose +is hereby granted without fee, provided that the above copyright notice appear in all copies and +that both that copyright notice and this permission notice appear in supporting documentation. +CERN makes no representations about the suitability of this software for any purpose. +It is provided "as is" without expressed or implied warranty. +*/ + +package org.bukkit.craftbukkit.util; + +import java.util.AbstractCollection; +import java.util.AbstractSet; +import java.util.Arrays; +import java.util.Collection; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Map.Entry; +import java.util.NoSuchElementException; +import java.util.Set; + +public class LongObjectHashMap<V> implements Cloneable { + private long keys[]; + private V values[]; + + private int freeEntries; + private int elements; + + private int highWaterMark; + private int lowWaterMark; + private final double minLoadFactor; + private final double maxLoadFactor; + + private final long FREE = 0; + private final long REMOVED = Long.MIN_VALUE; + + private static final int defaultCapacity = 277; + private static final double defaultMinLoadFactor = 0.2; + private static final double defaultMaxLoadFactor = 0.5; + + private static final int largestPrime = Integer.MAX_VALUE; + private static final int[] primeCapacities = { + largestPrime, + + 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 102877, 205759, + 411527, 823117, 1646237, 3292489, 6584983, 13169977, 26339969, 52679969, 105359939, + 210719881, 421439783, 842879579, 1685759167, + + 433, 877, 1759, 3527, 7057, 14143, 28289, 56591, 113189, 226379, 452759, 905551, 1811107, + 3622219, 7244441, 14488931, 28977863, 57955739, 115911563, 231823147, 463646329, 927292699, + 1854585413, + + 953, 1907, 3821, 7643, 15287, 30577, 61169, 122347, 244703, 489407, 978821, 1957651, 3915341, + 7830701, 15661423, 31322867, 62645741, 125291483, 250582987, 501165979, 1002331963, + 2004663929, + + 1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853, 267713, 535481, 1070981, 2141977, 4283963, + 8567929, 17135863, 34271747, 68543509, 137087021, 274174111, 548348231, 1096696463, + + 31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741, 143483, 286973, 573953, + 1147921, 2295859, 4591721, 9183457, 18366923, 36733847, 73467739, 146935499, 293871013, + 587742049, 1175484103, + + 599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027, 310081, 620171, 1240361, 2480729, + 4961459, 9922933, 19845871, 39691759, 79383533, 158767069, 317534141, 635068283, 1270136683, + + 311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037, 164089, 328213, 656429, 1312867, + 2625761, 5251529, 10503061, 21006137, 42012281, 84024581, 168049163, 336098327, 672196673, + 1344393353, + + 3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899, + 701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557, + 359339171, 718678369, 1437356741, + + 43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159, 46327, 92657, 185323, 370661, 741337, + 1482707, 2965421, 5930887, 11861791, 23723597, 47447201, 94894427, 189788857, 379577741, + 759155483, 1518310967, + + 379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649, 195311, 390647, 781301, 1562611, + 3125257, 6250537, 12501169, 25002389, 50004791, 100009607, 200019221, 400038451, 800076929, + 1600153859 + }; + + static { + java.util.Arrays.sort(primeCapacities); + } + + public LongObjectHashMap() { + this(defaultCapacity); + } + + public LongObjectHashMap(int initialCapacity) { + this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor); + } + + @SuppressWarnings("unchecked") + public LongObjectHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) { + int capacity = initialCapacity; + capacity = nextPrime(capacity); + if (capacity == 0) capacity = 1; + + keys = new long[capacity]; + values = (V[]) new Object[capacity]; + + this.minLoadFactor = minLoadFactor; + if (maxLoadFactor == largestPrime) { + this.maxLoadFactor = 1.0; + } else { + this.maxLoadFactor = maxLoadFactor; + } + + elements = 0; + freeEntries = capacity; + + lowWaterMark = 0; + highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor); + } + + public void clear() { + Arrays.fill(keys, FREE); + Arrays.fill(values, null); + + elements = 0; + freeEntries = keys.length; + trimToSize(); + } + + @SuppressWarnings("unchecked") + public Set<Long> keySet() { + return new KeySet(); + } + + @SuppressWarnings("unchecked") + public Collection<V> values() { + return new ValueCollection(); + } + + /** + * Returns a Set of Entry objects for the HashMap. This is not how the internal + * implementation is laid out so this constructs the entire Set when called. For + * this reason it should be avoided if at all possible. + * @deprecated + * @return Set of Entry objects + */ + @Deprecated + public Set<Entry<Long, V>> entrySet() { + HashSet<Entry<Long, V>> set = new HashSet<Entry<Long, V>>(); + + for (int i = 0; i < keys.length; i++) { + if (keys[i] != FREE && keys[i] != REMOVED) { + set.add(new LongObjectEntry(keys[i], values[i])); + } + } + + return set; + } + + public boolean containsKey(int msw, int lsw) { + return containsKey(LongHash.toLong(msw, lsw)); + } + + public boolean containsKey(long key) { + return indexOfKey(key) >= 0; + } + + public boolean containsValue(V value) { + return indexOfValue(value) >= 0; + } + + public int size() { + return elements; + } + + public boolean isEmpty() { + return elements == 0; + } + + public V get(int msw, int lsw) { + return get(LongHash.toLong(msw, lsw)); + } + + public V get(long key) { + int i = indexOfKey(key); + if (i < 0) { + return null; + } + return values[i]; + } + + public V put(int msw, int lsw, V value) { + return put(LongHash.toLong(msw, lsw), value); + } + + public V put(long key, V value) { + int i = indexOfInsertion(key); + if (i < 0) { + i = -i - 1; + V oldValue = values[i]; + values[i] = value; + return oldValue; + } + + if (elements > highWaterMark) { + int newCapacity = chooseGrowCapacity(elements + 1, minLoadFactor, maxLoadFactor); + rehash(newCapacity); + return put(key, value); + } + + if (keys[i] == FREE) { + freeEntries--; + } + + keys[i] = key; + values[i] = value; + elements++; + + if (freeEntries < 1) { + int newCapacity = chooseGrowCapacity(elements + 1, minLoadFactor, maxLoadFactor); + rehash(newCapacity); + } + + return null; + } + + public V remove(int msw, int lsw) { + return remove(LongHash.toLong(msw, lsw)); + } + + public V remove(long key) { + int i = indexOfKey(key); + if (i < 0) { + return null; + } + + V oldValue = values[i]; + keys[i] = REMOVED; + values[i] = null; + elements--; + + if (elements < lowWaterMark) { + int newCapacity = chooseShrinkCapacity(elements, minLoadFactor, maxLoadFactor); + rehash(newCapacity); + } + + return oldValue; + } + + public void ensureCapacity(int minCapacity) { + if (keys.length < minCapacity) { + int newCapacity = nextPrime(minCapacity); + rehash(newCapacity); + } + } + + public void trimToSize() { + int newCapacity = nextPrime((int) (1 + 1.2 * size())); + if (keys.length > newCapacity) { + rehash(newCapacity); + } + } + + public Object clone() throws CloneNotSupportedException { + LongObjectHashMap copy = (LongObjectHashMap) super.clone(); + copy.keys = keys.clone(); + copy.values = values.clone(); + return copy; + } + + /** + * @param key the key to be added to the receiver. + * @return the index where the key would need to be inserted, if it is not already contained. + * Returns -index-1 if the key is already contained at slot index. + * Therefore, if the returned index < 0, then it is already contained at slot -index-1. + * If the returned index >= 0, then it is NOT already contained and should be inserted at slot index. + */ + private int indexOfInsertion(long key) { + final int length = keys.length; + + final int hash = hash(key) & 0x7FFFFFFF; + int i = hash % length; + int decrement = hash % (length - 2); + if (decrement == 0) { + decrement = 1; + } + + while ((keys[i] != FREE && keys[i] != REMOVED) && keys[i] != key) { + i -= decrement; + if (i < 0) { + i += length; + } + } + + if (keys[i] == REMOVED) { + int j = i; + while (keys[i] != FREE && (keys[i] == REMOVED || keys[i] != key)) { + i -= decrement; + if (i < 0) { + i += length; + } + } + if (keys[i] == FREE) { + i = j; + } + } + + + if (keys[i] != FREE && keys[i] != REMOVED) { + // key already contained at slot i. + // return a negative number identifying the slot. + return -i - 1; + } + // not already contained, should be inserted at slot i. + // return a number >= 0 identifying the slot. + return i; + } + + private int indexOfKey(long key) { + final int length = keys.length; + + final int hash = hash(key) & 0x7FFFFFFF; + int i = hash % length; + int decrement = hash % (length - 2); + if (decrement == 0) decrement = 1; + + while (keys[i] != FREE && (keys[i] == REMOVED || keys[i] != key)) { + i -= decrement; + if (i < 0) i += length; + } + + if (keys[i] == FREE) { + return -1; + } + + return i; + } + + private int indexOfValue(Object value) { + for (int i = keys.length; --i >= 0; ) { + if ((keys[i] != FREE && keys[i] != REMOVED) && values[i] == value) { + return i; + } + } + + return -1; + } + + @SuppressWarnings("unchecked") + private void rehash(int newCapacity) { + int oldCapacity = keys.length; + + long oldKeys[] = keys; + V oldValues[] = values; + + long newKeys[] = new long[newCapacity]; + V newValues[] = (V[]) new Object[newCapacity]; + + lowWaterMark = chooseLowWaterMark(newCapacity, minLoadFactor); + highWaterMark = chooseHighWaterMark(newCapacity, maxLoadFactor); + + keys = newKeys; + values = newValues; + freeEntries = newCapacity - elements; + + for (int i = oldCapacity; i-- > 0; ) { + if (oldKeys[i] != FREE && oldKeys[i] != REMOVED) { + long element = oldKeys[i]; + int index = indexOfInsertion(element); + newKeys[index] = element; + newValues[index] = oldValues[i]; + } + } + } + + private static int nextPrime(int desiredCapacity) { + int i = Arrays.binarySearch(primeCapacities, desiredCapacity); + if (i < 0) { + i = -i - 1; + } + + return primeCapacities[i]; + } + + private int chooseGrowCapacity(int size, double minLoad, double maxLoad) { + return nextPrime(Math.max(size + 1, (int) ((4 * size / (3 * minLoad + maxLoad))))); + } + + private int chooseShrinkCapacity(int size, double minLoad, double maxLoad) { + return nextPrime(Math.max(size + 1, (int) ((4 * size / (minLoad + 3 * maxLoad))))); + } + + private int chooseHighWaterMark(int capacity, double maxLoad) { + return Math.min(capacity - 2, (int) (capacity * maxLoad)); + } + + private int chooseLowWaterMark(int capacity, double minLoad) { + return (int) (capacity * minLoad); + } + + // This method copied from Murmur3, written by Austin Appleby released under Public Domain + private int hash(long value) { + value ^= value >>> 33; + value *= 0xff51afd7ed558ccdL; + value ^= value >>> 33; + value *= 0xc4ceb9fe1a85ec53L; + value ^= value >>> 33; + return (int) value; + } + + private class LongObjectEntry implements Entry<Long, V> { + private final long key; + private final V value; + + LongObjectEntry(long k, V v) { + key = k; + value = v; + } + + public Long getKey() { + return key; + } + + public V getValue() { + return value; + } + + public V setValue(V v) { + // Changes are not reflected in the main HashMap + return value; + } + } + + private class KeySet extends AbstractSet { + public int size() { + return elements; + } + + public boolean contains(long key) { + return containsKey(key); + } + + @SuppressWarnings("unchecked") + public Iterator<Long> iterator() { + return new KeyIterator(); + } + } + + private class KeyIterator implements Iterator { + private int ix; + + private KeyIterator() { + for (ix = 0; ix < keys.length; ix++) { + if (values[ix] != null && keys[ix] != REMOVED) { + break; + } + } + } + + public boolean hasNext() { + return ix < keys.length; + } + + public void remove() { + throw new UnsupportedOperationException("Collection is read-only"); + } + + public Long next() { + if (ix >= keys.length) { + throw new NoSuchElementException(); + } + + long key = keys[ix++]; + + for (; ix < keys.length; ix++) { + if (keys[ix] != FREE && keys[ix] != REMOVED) { + break; + } + } + + return key; + } + } + + private class ValueCollection extends AbstractCollection<V> { + public int size() { + return elements; + } + + @SuppressWarnings("unchecked") + public Iterator<V> iterator() { + return new ValueIterator(); + } + + @SuppressWarnings("unchecked") + public boolean contains(Object value) { + return containsValue((V) value); + } + } + + private class ValueIterator<V> implements Iterator<V> { + private int ix; + + private ValueIterator() { + for (ix = 0; ix < values.length; ix++) { + if (values[ix] != null) { + break; + } + } + } + + public boolean hasNext() { + return ix < values.length; + } + + public void remove() { + throw new UnsupportedOperationException("Collection is read-only"); + } + + @SuppressWarnings("unchecked") + public V next() { + if (ix >= values.length) { + throw new NoSuchElementException(); + } + + V value = (V) values[ix++]; + + for (; ix < values.length; ix++) { + if (values[ix] != null) { + break; + } + } + + return value; + } + } +} |