tikhomirov@304: /*
tikhomirov@304:  * Copyright (c) 2011 TMate Software Ltd
tikhomirov@304:  *  
tikhomirov@304:  * This program is free software; you can redistribute it and/or modify
tikhomirov@304:  * it under the terms of the GNU General Public License as published by
tikhomirov@304:  * the Free Software Foundation; version 2 of the License.
tikhomirov@304:  *
tikhomirov@304:  * This program is distributed in the hope that it will be useful,
tikhomirov@304:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@304:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@304:  * GNU General Public License for more details.
tikhomirov@304:  *
tikhomirov@304:  * For information on how to redistribute this software under
tikhomirov@304:  * the terms of a license other than GNU General Public License
tikhomirov@304:  * contact TMate Software at support@hg4j.com
tikhomirov@304:  */
tikhomirov@304: package org.tmatesoft.hg.util;
tikhomirov@304: 
tikhomirov@304: import org.tmatesoft.hg.internal.Experimental;
tikhomirov@304: 
tikhomirov@304: /**
tikhomirov@304:  * Memory-friendly alternative to HashSet. With slightly worse performance than that of HashSet, uses n * sizeof(HashMap.Entry) less memory 
tikhomirov@304:  * (i.e. for set of 50k elements saves more than 1 Mb of memory). Besides, elements of this set can be obtained (not only queried for presence) -  
tikhomirov@304:  * the option essential for canonical mappings (aka Pool)
tikhomirov@304:  * 
tikhomirov@304:  * @author Artem Tikhomirov
tikhomirov@304:  * @author TMate Software Ltd.
tikhomirov@304:  */
tikhomirov@304: @Experimental
tikhomirov@304: public class DirectHashSet<T> {
tikhomirov@304: 	
tikhomirov@304: 	private Object[] table;
tikhomirov@304: 	private int size;
tikhomirov@304: 	private int threshold;
tikhomirov@304: 
tikhomirov@304: 	public DirectHashSet() {
tikhomirov@304: 		this (16);
tikhomirov@304: 	}
tikhomirov@304: 
tikhomirov@304: 	public DirectHashSet(int capacity) {
tikhomirov@304:         int result = 2;
tikhomirov@304:         while (result < capacity) {
tikhomirov@304:         	result <<= 1;
tikhomirov@304:         }
tikhomirov@304: 		table = new Object[result];
tikhomirov@304: 		threshold = result - (result >>> 2);
tikhomirov@304: 	}
tikhomirov@304: 
tikhomirov@304: 	/**
tikhomirov@304: 	 * Add element to the set.
tikhomirov@304: 	 * @param o element, shall not be <code>null</code>
tikhomirov@304: 	 * @return previous element from the set equal to the argument
tikhomirov@304: 	 */
tikhomirov@304: 	@SuppressWarnings("unchecked")
tikhomirov@304: 	public T put(T o) {
tikhomirov@304: 		final int h = hash(o);
tikhomirov@304: 		final int mask = table.length - 1;
tikhomirov@304: 		int i = h & mask;
tikhomirov@304: 		Object t;
tikhomirov@304: 		while ((t = table[i]) != null) {
tikhomirov@304: 			if (t.equals(o)) {
tikhomirov@304: 				table[i] = o;
tikhomirov@304: 				return (T) t;
tikhomirov@304: 			}
tikhomirov@304: 			i = (i+1) & mask;
tikhomirov@304: 		}
tikhomirov@304: 		table[i] = o;
tikhomirov@304: 		if (++size >= threshold) {
tikhomirov@304: 			resize();
tikhomirov@304: 		}
tikhomirov@304: 		return null;
tikhomirov@304: 	}
tikhomirov@304: 	
tikhomirov@304: 	/**
tikhomirov@304: 	 * Query set for the element.
tikhomirov@304: 	 * @param o element, shall not be <code>null</code>
tikhomirov@304: 	 * @return element from the set, if present
tikhomirov@304: 	 */
tikhomirov@304: 	@SuppressWarnings("unchecked")
tikhomirov@304: 	public T get(T o) {
tikhomirov@304: 		final int h = hash(o);
tikhomirov@304: 		final int mask = table.length - 1;
tikhomirov@304: 		int i = h & mask;
tikhomirov@304: 		Object t;
tikhomirov@304: 		while ((t = table[i]) != null) {
tikhomirov@304: 			if (t == o || t.equals(o)) {
tikhomirov@304: 				return (T) t;
tikhomirov@304: 			}
tikhomirov@304: 			i = (i+1) & mask;
tikhomirov@304: 		}
tikhomirov@304: 		return null;
tikhomirov@304: 	}
tikhomirov@304: 	
tikhomirov@304: 	public int size() {
tikhomirov@304: 		return size;
tikhomirov@304: 	}
tikhomirov@304: 	
tikhomirov@304: 	public void clear() {
tikhomirov@304: 		Object[] t = table;
tikhomirov@304: 		for (int i = 0, top = t.length; i < top; i++) {
tikhomirov@304: 			t[i] = null;
tikhomirov@304: 		}
tikhomirov@304: 		size = 0;
tikhomirov@304: 	}
tikhomirov@304: 	
tikhomirov@304: 	private void resize() {
tikhomirov@304: 		final int newSize = table.length << 1;
tikhomirov@304: 		final int newMask = newSize - 1;
tikhomirov@304: 		Object[] newTable = new Object[newSize];
tikhomirov@304: 		for (int i = 0, size = table.length; i < size; i++) {
tikhomirov@304: 			Object t = table[i];
tikhomirov@304: 			if (t != null) {
tikhomirov@304: 				table[i] = null;
tikhomirov@304: 				int x = hash(t) & newMask;
tikhomirov@304: 				while (newTable[x] != null) {
tikhomirov@304: 					x = (x+1) & newMask;
tikhomirov@304: 				}
tikhomirov@304: 				newTable[x] = t;
tikhomirov@304: 			}
tikhomirov@304: 		}
tikhomirov@304: 		table = newTable;
tikhomirov@304: 		threshold = newSize - (newSize >>> 2);
tikhomirov@304: 	}
tikhomirov@304: 
tikhomirov@304: 	private static int hash(Object o) {
tikhomirov@304: 		int h = o.hashCode();
tikhomirov@304: //		return h;
tikhomirov@304: 		// HashMap.newHash()
tikhomirov@304: 		h ^= (h >>> 20) ^ (h >>> 12);
tikhomirov@304:         return h ^ (h >>> 7) ^ (h >>> 4);
tikhomirov@304: 	}
tikhomirov@304: 
tikhomirov@304: }