/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.db.procore.cluster;

import gnu.trove.impl.PrimeFinder;

public class LongHash {
	static final int HeaderSize = 2;
	static private final int UsedAndRealSize = -2; // Number of allocated slots.
	static private final int MaxAndFreeSize = -1; // Number of used slots.
	static private final int MinRealSize = 3;
	static private final int MinRealSizeMinusOne = MinRealSize - 1; 
	private static final long FREE = 0;
	private static final long REMOVED = -1;

	static final boolean isFree(long a) {
		return FREE == a;
	}

	static final boolean isFull(long a) {
		return a > FREE;
	}

	static final boolean isRemoved(long a) {
		return REMOVED == a;
	}

	static final long setFree() {
		return FREE;
	}

	static final long setFull(long a) {
		return a;
	}

	static final long setRemoved() {
		return REMOVED;
	}

	static public int getRealSize(long[] longs, int hashBase) {
		long desc = longs[hashBase + UsedAndRealSize];
		assert(desc < 0);
		int realSize = (int)desc & 0x7FFFFFFF;
		assert (realSize > MinRealSizeMinusOne);
		return realSize;
	}

//	private static void setRealSize(long[] longs, int hashBase, int realSize) {
//		assert (realSize > MinRealSizeMinusOne); 
//		long desc = longs[hashBase + UsedAndRealSize];
//		assert(desc < 0);
//		assert((int)desc < 0);
//		desc = (desc & 0xFFFFFFFF80000000L) | realSize;
//		longs[hashBase + UsedAndRealSize] = desc;
//	}

    private static void setUsedAndRealSize(long[] longs, int hashBase, int usedSize, int realSize) {
		assert(usedSize >= 0);
		assert(realSize > MinRealSizeMinusOne);
        int index = hashBase + UsedAndRealSize;
        long desc = longs[index];
        assert(desc <= 0); // memory is initialized to zero
        desc = (long)usedSize << 32 | realSize | 0x8000000080000000L;
        longs[index] = desc;
    }

    public static int getUsedSize(long[] longs, int hashBase) {
    	long desc = longs[hashBase + UsedAndRealSize];
    	assert(desc < 0);
    	assert((int)desc < 0);
    	return (int)(desc >> 32) & 0x7FFFFFFF;
    }

	static void setUsedSize(long[] longs, int hashBase, int usedSize) {
		assert (usedSize >= 0);
        int index = hashBase + UsedAndRealSize;
        long desc = longs[index];
        assert(desc < 0);
		assert((int)desc < 0);
        desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
        longs[index] = desc;
	}

	// return value after decrement
	static int decUsedSize(long[] longs, int hashBase) {
        int index = hashBase + UsedAndRealSize;
        long desc = longs[index];
        assert(desc < 0);
        int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) - 1;
		assert(usedSize >= 0);
        desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
        longs[index] = desc;
        return usedSize;
	}

	// return value after increment
	static int incUsedSize(long[] longs, int hashBase) {
        int index = hashBase + UsedAndRealSize;
        long desc = longs[index];
        assert(desc < 0);
        int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) + 1;
		assert(usedSize > 0);
        desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
        longs[index] = desc;
        return usedSize;
	}

	static int getFreeSize(long[] longs, int hashBase) {
		long desc = longs[hashBase + MaxAndFreeSize];
		assert(desc > 0);
		int freeSize = (int)desc;
		assert (freeSize >= 0); 
		return freeSize;
	}

	static void setFreeSize(long[] longs, int hashBase, int freeSize) {
		assert (freeSize >= 0);
		long desc = longs[hashBase + MaxAndFreeSize];
		assert(desc > 0);
		assert((int)desc >= 0);
		desc = (desc & 0xFFFFFFFF00000000L) | freeSize;
		longs[hashBase + MaxAndFreeSize] = desc;
	}

	static void decFreeSize(long[] longs, int hashBase) {
		long desc = longs[hashBase + MaxAndFreeSize];
		assert(desc > 0);
		int freeSize = (int)desc;
		assert(freeSize > 0);
		desc = (desc & 0xFFFFFFFF00000000L) | --freeSize;
		longs[hashBase + MaxAndFreeSize] = desc;
	}
	
    private static void setMaxAndFreeSize(long[] longs, int hashBase, int maxSize, int freeSize) {
		assert (maxSize > 0);
		assert (freeSize >= 0);
        int index = hashBase + MaxAndFreeSize;
        long desc = longs[index];
        assert(desc >= 0); // memory is initialized to zero
        desc = ((long)maxSize << 32) | freeSize;
        longs[index] = desc;
    }

	static int getMaxSize(long[] longs, int hashBase) {
    	long desc = longs[hashBase + MaxAndFreeSize];
    	assert(desc > 0);
    	assert((int)desc >= 0);
    	return (int)(desc >> 32);
	}

	static void setMaxSize(long[] longs, int hashBase, int maxSize) {
		assert (maxSize > 0);
        int index = hashBase + MaxAndFreeSize;
        long desc = longs[index];
        assert(desc > 0);
		assert((int)desc >= 0);
        desc = (desc & 0x00000000FFFFFFFFL) | (long)maxSize << 32;
        longs[index] = desc;
	}

	public static boolean add(AllocatorI allocator, long a) {
		long[] longs = allocator.getLongs();
		int hashBase = allocator.getHashBase();
		int index = insertionIndex(longs, hashBase, a);
		if (index < 0)
			return false; // already present in set, nothing to add
		long previousState = longs[index];
		assert(LongHash.isFull(a));
		longs[index] = a;
		postInsertHook(longs, hashBase, LongHash.isFree(previousState), allocator);
		return true; // yes, we added something
	}

    public static boolean remove(long[] longs, int hashBase, long a) {
        int index = LongHash.index(longs, hashBase, a);
        if (index >= 0) {
        	longs[index] = setRemoved();
        	decUsedSize(longs, hashBase);
            return true;
        }
        return false;
    }

    public static boolean contains(long[] longs, int hashBase,long a) {
        return index(longs, hashBase, a) >= 0;
    }

    public static boolean isEmpty(long[] longs, int hashBase) {
		return 0 == getUsedSize(longs, hashBase);
	}

    public static void clear(long[] longs, int hashBase) {
        long[] set = longs;
        long free = setFree();
        int capacity = getRealSize(longs, hashBase);
        for (int i = capacity; i-- > 0;) {
            set[hashBase + i] = free;
        }
        setUsedSize(longs, hashBase, 0);
        setFreeSize(longs, hashBase, capacity);
    }
    
	/**
	 * Ensure that this hashtable has sufficient capacity to hold
	 * <tt>desiredCapacity<tt> <b>additional</b> elements without
	 * requiring a rehash.  This is a tuning method you can call
	 * before doing a large insert.
	 *
	 * @param desiredSize an <code>int</code> value
	 */
	public static boolean ensureSize(AllocatorI allocator, int desiredSize) {
		long[] longs = allocator.getLongs();
		int hashBase = allocator.getHashBase();
		int size = getUsedSize(longs, hashBase);
		if (desiredSize > (getMaxSize(longs, hashBase) - size)) {
			int newCapacity = ((desiredSize + size) << 1) + 1;
			rehash(longs, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);
			return true;
		}
		return false;
	}

	/**
	 * Compresses the hashtable to the minimum prime size (as defined by
	 * PrimeFinder) that will hold all of the elements currently in the table.
	 * If you have done a lot of <tt>remove</tt> operations and plan to do a
	 * lot of queries or insertions or iteration, it is a good idea to invoke
	 * this method. Doing so will accomplish two things:
	 * 
	 * <ol>
	 * <li> You'll free memory allocated to the table but no longer needed
	 * because of the remove()s.</li>
	 * 
	 * <li> You'll get better query/insert/iterator performance because there
	 * won't be any <tt>REMOVED</tt> slots to skip over when probing for
	 * indices in the table.</li>
	 * </ol>
	 */
	public static void compact(AllocatorI allocator) {
		long[] longs = allocator.getLongs();
		int hashBase = allocator.getHashBase();
		// need at least one free spot for open addressing
		rehash(longs, hashBase, PrimeFinder.nextPrime((getUsedSize(longs, hashBase) << 1) + 1), allocator);
	}

	public static int setUp(AllocatorI allocator, int initialCapacity) {
		int capacity = PrimeFinder.nextPrime(initialCapacity << 1);
		int hashBase = allocator.allocate(capacity);
		assert(hashBase == allocator.getHashBase());
		long[] longs = allocator.getLongs();
		setUsedAndRealSize(longs, hashBase, 0, capacity);
		setMaxAndFreeSize(longs, hashBase, capacity >> 1, capacity);
		return hashBase;
	}

	/**
	 * Expands the set to accomodate new values.
	 * 
	 * @param newCapacity
	 *            an <code>int</code> value
	 */
	static final void rehash(long[] oldLongs, int oldHashBase, int newCapacity,
			AllocatorI allocator) {
		assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);
		int oldCapacity = getRealSize(oldLongs, oldHashBase);
		int oldSize = getUsedSize(oldLongs, oldHashBase);
		// new hash base is initialized to LongHash.freeSet()
		int newHashBase = allocator.allocate(newCapacity);
		long[] newLongs = allocator.getLongs();
		setUsedAndRealSize(newLongs, newHashBase, oldSize, newCapacity);
		setMaxAndFreeSize(newLongs, newHashBase, newCapacity>>1, newCapacity - oldSize);
		
		for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {
			long o = oldLongs[i];
			if (isFull(o)) {
				int index = insertionIndex(newLongs, newHashBase, o);
				newLongs[index] = o;
			}
		}
	}

	/**
	 * After an insert, this hook is called to adjust the size/free values of
	 * the set and to perform rehashing if necessary.
	 */
	protected static final void postInsertHook(long[] longs, int hashBase,
			boolean usedFreeSlot, AllocatorI allocator) {
		if (usedFreeSlot) {
			decFreeSize(longs, hashBase);
		}

		// rehash whenever we exhaust the available space in the table
		if (incUsedSize(longs, hashBase) > getMaxSize(longs, hashBase)
				|| getFreeSize(longs, hashBase) == 0) {
			// choose a new capacity suited to the new state of the table
			// if we've grown beyond our maximum size, double capacity;
			// if we've exhausted the free spots, rehash to the same capacity,
			// which will free up any stale removed slots for reuse.
			int newCapacity = getUsedSize(longs, hashBase) > getMaxSize(longs,
					hashBase) ? PrimeFinder.nextPrime(getRealSize(longs,
					hashBase) << 1) : getRealSize(longs, hashBase);
			rehash(longs, hashBase, newCapacity, allocator);
		}
	}

	/**
	 * Locates the index of <tt>val</tt>.
	 * 
	 * @param val
	 *            an <code>long</code> value
	 * @return the index of <tt>val</tt> or -1 if it isn't in the set.
	 */
	static int index(long[] longs, int hashBase, long a) {
		int hash, probe, index, length, hashIndex;
		long[] set = longs;
		length = getRealSize(longs, hashBase);
		hash = computeHashCode(a);
		index = hash % length;
		hashIndex = hashBase + index;

		if (!LongHash.isFree(set[hashIndex])
				&& (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
			// see Knuth, p. 529
			probe = 1 + (hash % (length - 2));

			do {
				index -= probe;
				if (index < 0) {
					index += length;
				}
				hashIndex = hashBase + index;
			} while (!LongHash.isFree(set[hashIndex])
					&& (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a));
		}

		return LongHash.isFree(set[hashIndex]) ? -1  : hashIndex;
	}

	/**
	 * Locates the index at which <tt>val</tt> can be inserted. if there is
	 * already a value equal()ing <tt>val</tt> in the set, returns that value
	 * as a negative integer.
	 * 
	 * @param val
	 *            an <code>long</code> value
	 * @return an <code>int</code> value
	 */
	static final int insertionIndex(long[] longs, int hashBase, long a) {
		int hash, probe, index, length, hashIndex;
		long[] set = longs;
		length = getRealSize(longs, hashBase);
		hash = computeHashCode(a);
		index = hash % length;
		assert(0 != hashBase);
		hashIndex = hashBase + index;
		
		if (LongHash.isFree(set[hashIndex])) {
			return hashIndex; // empty, all done
		} else if (LongHash.isFull(set[hashIndex]) && set[hashIndex] == a) {
			return -hashIndex; // already stored
		} else { // already FULL or REMOVED, must probe
			// compute the double hash
			probe = 1 + (hash % (length - 2));

			// if the slot we landed on is FULL (but not removed), probe
			// until we find an empty slot, a REMOVED slot, or an element
			// equal to the one we are trying to insert.
			// finding an empty slot means that the value is not present
			// and that we should use that slot as the insertion point;
			// finding a REMOVED slot means that we need to keep searching,
			// however we want to remember the offset of that REMOVED slot
			// so we can reuse it in case a "new" insertion (i.e. not an update)
			// is possible.
			// finding a matching value means that we've found that our desired
			// key is already in the table

			if (!LongHash.isRemoved(set[hashIndex])) {
				// starting at the natural offset, probe until we find an
				// offset that isn't full.
				do {
					index -= probe;
					if (index < 0) {
						index += length;
					}
					hashIndex = hashBase + index;
				} while (LongHash.isFull(set[hashIndex]) && set[hashIndex] != a);
			}

			// if the index we found was removed: continue probing until we
			// locate a free location or an element which equal()s the
			// one we have.
			if (LongHash.isRemoved(set[hashIndex])) {
				int firstRemoved = hashIndex;
				while (!LongHash.isFree(set[hashIndex])
						&& (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
					index -= probe;
					if (index < 0) {
						index += length;
					}
					hashIndex = hashBase + index;
				}
				return LongHash.isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
			}
			// if it's full, the key is already stored
			return LongHash.isFull(set[hashIndex]) ? -hashIndex : hashIndex;
		}
	}

	static final int computeHashCode(long aKey) {
		int hash = ((int) (aKey ^ (aKey >> 32))) * 31;
		return hash & 0x7fffffff; // Top bit reserved.
	}

	interface AllocatorI {
		int allocate(int size); // return base address of hash table, allocates also hash header
		long[] getLongs(); // return base address of allocator memory
		int getHashBase(); // return base address of hash table
	}
}

class LongIterator {
	private long[] longs;
	private int hashBase;
	private int index;
	// for reset
	private int size; // number of elements in the set
	private final LongHash.AllocatorI allocator;

	public LongIterator(LongHash.AllocatorI allocator) {
		this.allocator = allocator;
		this.reset();
    }
	public int size() {
		return this.size; 
	}
	public void reset() {
		if (longs == null ||
				LongHash.getUsedSize(longs, hashBase) != this.size ||
				longs != allocator.getLongs() ||
				hashBase != allocator.getHashBase()) {
			this.longs = allocator.getLongs();
			this.hashBase = allocator.getHashBase();
			this.size = LongHash.getUsedSize(longs, hashBase);
		}
		this.index = LongHash.getRealSize(longs, hashBase);
	}
	public long next() {
    	if (moveToNextIndex())
    		return longs[hashBase + index];
    	return LongHash.setFree();
    }
    protected final boolean moveToNextIndex() {
        // doing the assignment && < 0 in one line saves 3 opcodes...
        if ((index = nextIndex()) < 0) {
            return false;
        }
        return true;
    }
    protected final int nextIndex() {
        long[] states = longs;
        int i = index;
        while (i-- > 0 && (!LongHash.isFull(states[hashBase + i])))
        		;
        return i;
    }
    public boolean hasNext() {
        return nextIndex() >= 0;
    }
}