l2j-server-game/L2J_Server_BETA/java/com/l2jserver/gameserver/util/L2ObjectHashSet.java

/*
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 */
package com.l2jserver.gameserver.util;

import java.util.Iterator;
import java.util.NoSuchElementException;

import com.l2jserver.gameserver.model.L2Object;

/**
 * This class is a highly optimized hash table, where keys are integers.<br>
 * The main goal of this class is to allow concurrent read/iterate and write access to this table, plus minimal used memory.<br>
 * This class uses plain array as the table of values, and keys are used to get position in the table.<br>
 * If the position is already busy, we iterate to the next position, until we find the needed element or null.<br>
 * To iterate over the table (read access) we may simply iterate through table array.<br>
 * In case we remove an element from the table, we check - if the next position is null, we reset table's slot to null, otherwise we assign it to a dummy value.
 * @author mkizub
 * @param <T> type of values stored in this hash table.
 */
public final class L2ObjectHashSet<T extends L2Object> extends L2ObjectSet<T>
{
	private static final boolean TRACE = false;
	private static final boolean DEBUG = false;
	
	private static final int[] PRIMES =
	{
		5,
		7,
		11,
		17,
		23,
		29,
		37,
		47,
		59,
		71,
		89,
		107,
		131,
		163,
		197,
		239,
		293,
		353,
		431,
		521,
		631,
		761,
		919,
		1103,
		1327,
		1597,
		1931,
		2333,
		2801,
		3371,
		4049,
		4861,
		5839,
		7013,
		8419,
		10103,
		12143,
		14591,
		17519,
		21023,
		25229,
		30293,
		36353,
		43627,
		52361,
		62851,
		75431,
		90523,
		108631,
		130363,
		156437,
		187751,
		225307,
		270371,
		324449,
		389357,
		467237,
		560689,
		672827,
		807403,
		968897,
		1162687,
		1395263,
		1674319,
		2009191,
		2411033,
		2893249,
		3471899,
		4166287,
		4999559,
		5999471,
		7199369
	};
	
	private T[] _table;
	private int[] _collisions;
	private int _count;
	
	private static int getPrime(int min)
	{
		for (int element : PRIMES)
		{
			if (element >= min)
			{
				return element;
			}
		}
		throw new OutOfMemoryError();
	}
	
	@SuppressWarnings("unchecked")
	public L2ObjectHashSet()
	{
		int size = PRIMES[0];
		_table = (T[]) new L2Object[size];
		_collisions = new int[(size + 31) >> 5];
		if (DEBUG)
		{
			check();
		}
	}
	
	@Override
	public int size()
	{
		return _count;
	}
	
	@Override
	public boolean isEmpty()
	{
		return _count == 0;
	}
	
	@Override
	@SuppressWarnings("unchecked")
	public synchronized void clear()
	{
		int size = PRIMES[0];
		_table = (T[]) new L2Object[size];
		_collisions = new int[(size + 31) >> 5];
		_count = 0;
		if (DEBUG)
		{
			check();
		}
	}
	
	private void check()
	{
		if (DEBUG)
		{
			int cnt = 0;
			assert _collisions.length == ((_table.length + 31) >> 5);
			for (T obj : _table)
			{
				if (obj != null)
				{
					cnt++;
				}
			}
			assert cnt == _count;
		}
	}
	
	@Override
	public synchronized void put(T obj)
	{
		if (obj == null)
		{
			return;
		}
		if (contains(obj))
		{
			return;
		}
		if (_count >= (_table.length / 2))
		{
			expand();
		}
		final int hashcode = obj.getObjectId();
		assert hashcode > 0;
		int seed = hashcode;
		int incr = 1 + (((seed >> 5) + 1) % (_table.length - 1));
		int ntry = 0;
		int slot = -1; // keep last found slot
		do
		{
			int pos = (seed % _table.length) & 0x7FFFFFFF;
			if (_table[pos] == null)
			{
				if (slot < 0)
				{
					slot = pos;
				}
				if ((_collisions[pos >> 5] & (1 << (pos & 31))) == 0)
				{
					// found an empty slot without previous collisions,
					// but use previously found slot
					_table[slot] = obj;
					_count++;
					if (TRACE)
					{
						System.err.println("ht: put obj id=" + hashcode + " at slot=" + slot);
					}
					if (DEBUG)
					{
						check();
					}
					return;
				}
			}
			else
			{
				// check if we are adding the same object
				if (_table[pos] == obj)
				{
					return;
				}
				// this should never happen
				assert obj.getObjectId() != _table[pos].getObjectId();
				// if there was no collisions at this slot, and we found a free
				// slot previously - use found slot
				if ((slot >= 0) && ((_collisions[pos >> 5] & (1 << (pos & 31))) == 0))
				{
					_table[slot] = obj;
					_count++;
					if (TRACE)
					{
						System.err.println("ht: put obj id=" + hashcode + " at slot=" + slot);
					}
					if (DEBUG)
					{
						check();
					}
					return;
				}
			}
			
			// set collision bit
			_collisions[pos >> 5] |= 1 << (pos & 31);
			// calculate next slot
			seed += incr;
		}
		while (++ntry < _table.length);
		if (DEBUG)
		{
			check();
		}
		throw new IllegalStateException();
	}
	
	@Override
	public synchronized void remove(T obj)
	{
		if (obj == null)
		{
			return;
		}
		if (!contains(obj))
		{
			return;
		}
		int hashcode = obj.getObjectId();
		assert hashcode > 0;
		int seed = hashcode;
		int incr = 1 + (((seed >> 5) + 1) % (_table.length - 1));
		int ntry = 0;
		do
		{
			int pos = (seed % _table.length) & 0x7FFFFFFF;
			if (_table[pos] == obj)
			{
				// found the object
				_table[pos] = null;
				_count--;
				if (TRACE)
				{
					System.err.println("ht: remove obj id=" + hashcode + " from slot=" + pos);
				}
				if (DEBUG)
				{
					check();
				}
				return;
			}
			// check for collision (if we previously deleted element)
			if ((_table[pos] == null) && ((_collisions[pos >> 5] & (1 << (pos & 31))) == 0))
			{
				if (DEBUG)
				{
					check();
				}
				return; // throw new IllegalArgumentException();
			}
			// calculate next slot
			seed += incr;
		}
		while (++ntry < _table.length);
		if (DEBUG)
		{
			check();
		}
		throw new IllegalStateException();
	}
	
	@Override
	public boolean contains(T obj)
	{
		final int size = _table.length;
		if (size <= 11)
		{
			// for small tables linear check is fast
			for (int i = 0; i < size; i++)
			{
				if (_table[i] == obj)
				{
					return true;
				}
			}
			return false;
		}
		int hashcode = obj.getObjectId();
		assert hashcode > 0;
		int seed = hashcode;
		int incr = 1 + (((seed >> 5) + 1) % (size - 1));
		int ntry = 0;
		do
		{
			int pos = (seed % size) & 0x7FFFFFFF;
			if (_table[pos] == obj)
			{
				return true;
			}
			// check for collision (if we previously deleted element)
			if ((_table[pos] == null) && ((_collisions[pos >> 5] & (1 << (pos & 31))) == 0))
			{
				return false;
			}
			// calculate next slot
			seed += incr;
		}
		while (++ntry < size);
		return false;
	}
	
	@SuppressWarnings("unchecked")
	private/* already synchronized in put() */void expand()
	{
		int newSize = getPrime(_table.length + 1);
		L2Object[] newTable = new L2Object[newSize];
		int[] newCollisions = new int[(newSize + 31) >> 5];
		
		// over all old entries
		next_entry:
		for (int i = 0; i < _table.length; i++)
		{
			L2Object obj = _table[i];
			if (obj == null)
			{
				continue;
			}
			final int hashcode = obj.getObjectId();
			int seed = hashcode;
			int incr = 1 + (((seed >> 5) + 1) % (newSize - 1));
			int ntry = 0;
			do
			{
				int pos = (seed % newSize) & 0x7FFFFFFF;
				if (newTable[pos] == null)
				{
					// found an empty slot without previous collisions,
					// but use previously found slot
					newTable[pos] = obj;
					if (TRACE)
					{
						System.err.println("ht: move obj id=" + hashcode + " from slot=" + i + " to slot=" + pos);
					}
					continue next_entry;
				}
				// set collision bit
				newCollisions[pos >> 5] |= 1 << (pos & 31);
				// calculate next slot
				seed += incr;
			}
			while (++ntry < newSize);
			throw new IllegalStateException();
		}
		_table = (T[]) newTable;
		_collisions = newCollisions;
		if (DEBUG)
		{
			check();
		}
	}
	
	@Override
	public Iterator<T> iterator()
	{
		return new Itr(_table);
	}
	
	class Itr implements Iterator<T>
	{
		private final T[] _array;
		private int _nextIdx;
		private T _nextObj;
		private T _lastRet;
		
		Itr(T[] pArray)
		{
			this._array = pArray;
			for (; _nextIdx < _array.length; _nextIdx++)
			{
				_nextObj = _array[_nextIdx];
				if (_nextObj != null)
				{
					return;
				}
			}
		}
		
		@Override
		public boolean hasNext()
		{
			return _nextObj != null;
		}
		
		@Override
		public T next()
		{
			if (_nextObj == null)
			{
				throw new NoSuchElementException();
			}
			_lastRet = _nextObj;
			for (_nextIdx++; _nextIdx < _array.length; _nextIdx++)
			{
				_nextObj = _array[_nextIdx];
				if (_nextObj != null)
				{
					break;
				}
			}
			if (_nextIdx >= _array.length)
			{
				_nextObj = null;
			}
			return _lastRet;
		}
		
		@Override
		public void remove()
		{
			if (_lastRet == null)
			{
				throw new IllegalStateException();
			}
			L2ObjectHashSet.this.remove(_lastRet);
		}
	}
}