Data Structures/Trees/Hashing Memory Checking Example

Java implementation of a basic persistent database index using the linear hash algorithm

package linearhashmap;
 
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
 
/**
 * 
 * @author S.Tan
 * 
 * @param <K>
 *            key type , must implement equals() and hashCode()
 * @param <V>
 *            value type
 * 
 * 
 */
public class LHMap2<K, V> implements Map<K, V>, Serializable {
 
	/**
	 * 
	 */
	private static final long serialVersionUID = 3095071852466632996L;
 
	/**
	 * 
	 */
 
	public static interface BlockListener<K, V> {
		public void blockRequested(int block, LHMap2<K, V> map);
	}
 
	List<BlockListener<K, V>> listeners = new ArrayList<BlockListener<K, V>>();
 
	// int savedBlocks;
	int N;
	int level = 0;
	int split = 0;
	int blockSize;
	long totalWrites = 0;
 
	List<Block<K, V>> blockList = new ArrayList<Block<K, V>>();
 
	public void addBlockListener(BlockListener<K, V> listener) {
		listeners.add(listener);
	}
 
	void notifyBlockRequested(int block) {
		for (BlockListener<K, V> l : listeners) {
			l.blockRequested(block, this);
		}
	}
 
	public LHMap2(int blockSize, int nStartingBlocks) {
		this.blockSize = blockSize;
		this.N = nStartingBlocks;
		for (int i = 0; i < nStartingBlocks; ++i) {
			addBlock();
		}
 
		Runtime.getRuntime().addShutdownHook(new Thread(new Runnable() {
 
			@Override
			public void run() {
				showStructure();
 
			}
		}));
	}
 
	public static class Block<K, V> implements Externalizable {
		/**
		 * 
		 */
 
		int j = 0;
 
		Block<K, V> overflow = null;
		LinkedList<K> keyList = new LinkedList<K>();
		LinkedList<V> valueList = new LinkedList<V>();
		transient private LHMap2<K, V> owner;
		transient private Map<K, V> shadow = new TreeMap<K, V>();
 
		private boolean changed = false;
 
		private int size = 0;
 
		public LHMap2<K, V> getOwner() {
			return owner;
		}
 
		public void setOwner(LHMap2<K, V> owner) {
			this.owner = owner;
			Block<K, V> ov = overflow;
			while (ov != null) {
				overflow.setOwner(owner);
				ov = ov.overflow;
			}
		}
 
		public Block() {
			super();
		}
 
		public Block(LHMap2<K, V> map) {
			setOwner(map);
		}
 
		public V put(K k, V v) {
			setChanged(true);
 
			V v2 = replace(k, v);
			if (v2 == null) {
				++size;
				if (keyList.size() == getOwner().blockSize) {
 
					if (overflow == null) {
						getOwner().blockOverflowed(this, k, v);
					} else {
						overflow.put(k, v);
					}
 
				} else {
					keyList.addFirst(k);
					valueList.addFirst(v);
				}
 
			}
 
			return v2;
		}
 
		void setChanged(boolean b) {
			changed = b;
		}
 
		public Map<K, V> drainToMap(Map<K, V> map) {
 
			while (!keyList.isEmpty()) {
				K k = keyList.removeLast();
				V v = valueList.removeLast();
				map.put(k, v);
 
			}
 
			if (overflow != null)
 
				map = overflow.drainToMap(map);
 
			garbageCollectionOverflow();
 
			return map;
		}
 
		public void updateMap(Map<K, V> map) {
			Iterator<K> ik = keyList.descendingIterator();
			Iterator<V> iv = valueList.descendingIterator();
			while (ik.hasNext() && iv.hasNext()) {
				map.put(ik.next(), iv.next());
			}
 
			if (overflow != null)
				overflow.updateMap(map);
 
		}
 
		private void garbageCollectionOverflow() {
			if (overflow != null) {
				overflow.garbageCollectionOverflow();
				overflow = null;
 
			}
		}
 
		public void addOverflowBucket() {
 
			// assert overflow is needed
			if (keyList.size() < getOwner().blockSize)
				return;
 
			if (overflow == null) {
				overflow = new Block<K, V>(getOwner());
			} else {
				overflow.addOverflowBucket();
			}
		}
 
		public V replace(K key, V v2) {
 
			if (overflow != null) {
				V v = (V) overflow.replace(key, v2);
				if (v != null)
					return v;
			}
 
			Iterator<K> i = keyList.listIterator();
 
			int j = 0;
 
			while (i.hasNext()) {
 
				if (key.equals(i.next())) {
 
					V v = valueList.get(j);
 
					if (v2 != null) {
 
						valueList.set(j, v2);
 
					}
 
					return v;
				}
				++j;
			}
 
			return null;
		}
 
		public boolean isChanged() {
			return changed;
		}
 
		@Override
		public void readExternal(ObjectInput arg0) throws IOException,
				ClassNotFoundException {
			int sz = arg0.readInt();
			for (int i = 0; i < sz; ++i) {
				K k = (K) arg0.readObject();
				V v = (V) arg0.readObject();
				shadow.put(k, v);
			}
		}
 
		public void loadFromShadow(LHMap2<K, V> owner) {
			setOwner(owner);
			Block<K, V> b = this;
			for (K k : shadow.keySet()) {
				if (b.keyList.size() == owner.blockSize) {
					Block<K, V> overflow = new Block<K, V>(owner);
					b.overflow = overflow;
					b = overflow;
				}
				b.keyList.add(k);
				b.valueList.add(shadow.get(k));
 
			}
			shadow.clear();
		}
 
		@Override
		public void writeExternal(ObjectOutput arg0) throws IOException {
			if (!changed)
				return;
			Map<K, V> map = new TreeMap<K, V>();
 
			// this is destructive of the block
			updateMap(map);
			int sz = map.size();
			arg0.writeInt(sz);
			for (K k : map.keySet()) {
				arg0.writeObject(k);
				arg0.writeObject(map.get(k));
			}
			setChanged(false);
 
		}
 
	}
 
	void init() {
 
		for (int i = 0; i < N; ++i) {
			addBlock();
		}
	}
 
	/**
	 * @param hashValue
	 * @return a bucket number.
	 */
	int getDynamicHash(int hashValue) {
 
		long unsignedHash = (long) ((long) hashValue << 32) >>> 32;
		// ^^ this long cast needed
		int h = (int) (unsignedHash % (N << level));
		// System.err.println("h = " + h);
		if (h < split) {
 
			h = (int) (unsignedHash % (N << (level + 1)));
			// System.err.println("h < split, new h = " + h);
		}
		return h;
 
	}
 
	public V put(K k, V v) {
		++totalWrites;
		int h = getDynamicHash(k.hashCode());
		Block<K, V> b = getBlock(h);
 
		b.put(k, v);
 
		return v;
 
	}
 
	public long getTotalWrites() {
		return totalWrites;
	}
 
	private Block<K, V> getBlock(int h) {
		notifyBlockRequested(h);
		return blockList.get(h);
	}
 
	void blockOverflowed(Block<K, V> b, K k, V v) {
 
		splitNextBucket();
 
		b.addOverflowBucket();
		b.put(k, v);
	}
 
	private void splitNextBucket() {
		Block<K, V> b = getBlock(split);
		TreeMap<K, V> map = new TreeMap<K, V>();
		b.drainToMap(map);
		addBlock();
		System.err.printf("split N LEVEL  %d %d %d \n", split, N, level);
		if (++split >= (N << level)) {
			++level;
 
			split = 0;
		}
 
		for (K k : map.keySet()) {
			V v = map.get(k);
			int h = getDynamicHash(k.hashCode());
			System.err.println(h + " ");
			Block<K, V> b2 = getBlock(h);
			b2.put(k, v);
		}
	}
 
	private Block<K, V> addBlock() {
		Block<K, V> b = new Block<K, V>(this);
		blockList.add(b);
 
		return b;
	}
 
	@Override
	public void clear() {
		blockList = new ArrayList<Block<K, V>>();
		split = 0;
		level = 0;
		totalWrites = 0;// savedBlocks = 0;
 
	}
 
	@Override
	public boolean containsKey(Object key) {
		return get(key) != null;
	}
 
	@Override
	public boolean containsValue(Object value) {
		return values().contains(value);
	}
 
	@Override
	public Set<java.util.Map.Entry<K, V>> entrySet() {
		TreeSet<Map.Entry<K, V>> set = new TreeSet<Map.Entry<K, V>>();
		Set<K> kk = keySet();
		for (K k : kk) {
			final K k2 = k;
			set.add(new Entry<K, V>() {
 
				@Override
				public K getKey() {
					return k2;
				}
 
				@Override
				public V getValue() {
					return get(k2);
				}
 
				@Override
				public V setValue(V value) {
					return put(k2, value);
				}
			});
		}
		return set;
	}
 
	@Override
	public V get(Object key) {
		int h = getDynamicHash(key.hashCode());
		Block<K, V> b = getBlock(h);
		return b.replace((K) key, null);
	}
 
	@Override
	public boolean isEmpty() {
		return size() == 0;
	}
 
	@Override
	public Set<K> keySet() {
		TreeSet<K> kk = new TreeSet<K>();
		for (int i = 0; i < blockList.size(); ++i) {
			Block<K, V> b = getBlock(i);
			kk.addAll(b.keyList);
			Block<K, V> ov = b.overflow;
			while (ov != null) {
				kk.addAll(ov.keyList);
				ov = ov.overflow;
			}
		}
		return kk;
	}
 
	@Override
	public void putAll(Map<? extends K, ? extends V> m) {
		for (K k : m.keySet()) {
			put(k, m.get(k));
		}
	}
 
	@Override
	public V remove(Object key) {
		return null;
	}
 
	@Override
	public int size() {
		long sz = longSize();
		return (int) ((long) sz > (long) Integer.MAX_VALUE ? Integer.MAX_VALUE
				: sz);
	}
 
	public long longSize() {
		long sz = 0;
		for (Block<K, V> b : blockList) {
			Block<K, V> b1 = b;
			while (b1 != null) {
				sz += b1.size;
				b1 = b.overflow;
			}
		}
		return sz;
	}
 
	@Override
	public Collection<V> values() {
		ArrayList<V> list = new ArrayList<V>();
		Set<K> kk = keySet();
		for (K k : kk) {
			list.add(get(k));
		}
		return list;
	}
 
	private void showStructure() {
		for (int i = 0; i < blockList.size(); ++i) {
 
			Block<K, V> b = getBlock(i);
			Block<K, V> ov = b.overflow;
			int k = 0;
			while (ov != null) {
				ov = ov.overflow;
				++k;
			}
 
			System.out.println("Block " + i + " size " + b.keyList.size()
					+ " overflow blocks = " + k);
 
		}
	}
 
}
 
 
 
package linearhashmap;
 
import java.io.File;
import java.io.Serializable;
import java.util.List;
import java.util.Random;
 
public class LHMap2BlockFileManagerData implements  Serializable{
	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	public byte[] buf;
	public Random r;
	public File baseDir;
	public File home;
	public int maxBlocks;
	public int retired;
	public double unloadRatio;
	public List<Integer> retirees;
	public int avgBlockSize;
	public long avgCount;
 
	public LHMap2BlockFileManagerData(byte[] buf, Random r, int retired,
			List<Integer> retirees, long avgCount) {
		this.buf = buf;
		this.r = r;
		this.retired = retired;
		this.retirees = retirees;
		this.avgCount = avgCount;
	}
 
 
}
 
package linearhashmap;
 
 
 
import java.io.ByteArrayInputStream;
 
import java.io.ByteArrayOutputStream;
 
import java.io.File;
 
import java.io.FileInputStream;
 
import java.io.FileNotFoundException;
 
import java.io.FileOutputStream;
 
import java.io.IOException;
 
import java.io.ObjectInputStream;
 
import java.io.ObjectOutputStream;
 
import java.io.Serializable;
 
import java.util.ArrayList;
 
import java.util.Random;
 
 
 
/**
 
 * This class manages the LHMap2 class block disk swapping, and saves and load
 
 * an instance of the LHMap2 class. It has been used to externally index a
 
 * legacy file based database of 100,000 record master table, and 1,000,000
 
 * record sized child tables, and accounts for heap space available in the java
 
 * virtual machine, so that OutOfMemory errors are avoided when the heap space
 
 * is low by putting blocks back on files, and garbage collecting them. The main
 
 * performance bottleneck appeared when loading a million record table for an
 
 * index , on initial creation of the index.
 
 * 
 
 * @author doctor
 
 * 
 
 * @param <K>
 
 * @param <V>
 
 */
 
public class LHMap2BlockFileManager<K, V> implements
 
		LHMap2.BlockListener<K, V>, Serializable {
 
 
 
	/**
 
	 * 
 
	 */
 
	private static final long serialVersionUID = 2615265603397988894L;
 
	LHMap2BlockFileManagerData data = new LHMap2BlockFileManagerData(
 
			new byte[10000], new Random(), 0, new ArrayList<Integer>(), 0);
 
 
 
	public LHMap2BlockFileManager(File baseDir, String name, int maxBlocks,
 
			double unloadRatio) {
 
		data.home = new File(baseDir, name);
 
		if (!data.home.exists())
 
			data.home.mkdir();
 
		this.data.maxBlocks = maxBlocks;
 
		this.data.unloadRatio = unloadRatio;
 
	}
 
 
 
	@Override
 
	public void blockRequested(int block, LHMap2<K, V> map) {
 
		LHMap2.Block<K, V> b = map.blockList.get(block);
 
 
 
		if (b == null) {
 
			int tries = 3; // for some reason, the File constructor can be
 
							// asynchronous occasionally, so need to try again
 
							// after delay
 
			File f = new File(data.home, Integer.toString(block));
 
			do {
 
 
 
				if (f.exists())
 
					break;
 
 
 
				if (!f.exists()) {
 
					if (--tries >= 0)
 
						fatal(block);
 
					try {
 
 
 
						Thread.sleep(100);
 
					} catch (InterruptedException e) {
 
						e.printStackTrace();
 
					}
 
 
 
				}
 
 
 
			} while (true);
 
			try {
 
				ByteArrayInputStream bis = new ByteArrayInputStream(data.buf);
 
				FileInputStream fis = new FileInputStream(f);
 
				int sz = fis.read(data.buf);
 
				fis.close();
 
				addByteStats(sz);
 
				ObjectInputStream ois = new ObjectInputStream(bis);
 
				b = new LHMap2.Block<K, V>();
 
 
 
				b.readExternal(ois);
 
				ois.close();
 
				b.loadFromShadow(map);
 
 
 
				map.blockList.set(block, b);
 
				--data.retired;
 
 
 
			} catch (FileNotFoundException e) {
 
				e.printStackTrace();
 
				fatal(block);
 
			} catch (IOException e) {
 
				e.printStackTrace();
 
				fatal(block);
 
			} catch (ClassNotFoundException e) {
 
				e.printStackTrace();
 
				fatal(block);
 
			}
 
 
 
		}
 
		int size = map.blockList.size();
 
 
 
		try {
 
			long freeMemory = Runtime.getRuntime().freeMemory();
 
 
 
			long limitMemory = (long) (data.avgBlockSize * data.unloadRatio * size);
 
 
 
			if (block % 30 == 0)
 
				System.err.println("free memory =" + freeMemory + " limit "
 
						+ limitMemory);
 
 
 
			if (map.split % 20 == 19) {
 
				// this is just to add statistics before really needing to
 
				// retire
 
				retireActiveBlock(map, block);
 
				++data.retired;
 
 
 
			} else if (freeMemory < limitMemory) {
 
				for (int i = 0; i < map.blockList.size() / 4; ++i) {
 
					retireActiveBlock(map, block);
 
					++data.retired;
 
				}
 
				System.runFinalization();
 
				System.gc();
 
			}
 
 
 
		} catch (FileNotFoundException e) {
 
			e.printStackTrace();
 
		} catch (IOException e) {
 
			e.printStackTrace();
 
		}
 
 
 
	}
 
 
 
	private void addByteStats(int sz) {
 
		++data.avgCount;
 
		data.avgBlockSize = (int) ((data.avgBlockSize * (data.avgCount - 1) + sz) / data.avgCount);
 
	}
 
 
 
	public void retireActiveBlock(LHMap2<K, V> map, int notThisOne)
 
			throws FileNotFoundException, IOException {
 
		int pick = 0;
 
		int size = map.blockList.size();
 
 
 
		for (pick = 0; pick < size
 
				&& (pick == notThisOne || (map.blockList.get(pick)) == null); ++pick)
 
			;
 
		if (pick < size)
 
			retireBlock(map, pick);
 
 
 
	}
 
 
 
	private void retireBlock(LHMap2<K, V> map, int pick) throws IOException,
 
			FileNotFoundException {
 
		LHMap2.Block<K, V> b = map.blockList.get(pick);
 
		if (b == null)
 
			return;
 
 
 
		if (b.isChanged()) {
 
			File f = new File(data.home, Integer.toString(pick));
 
			ByteArrayOutputStream bos = new ByteArrayOutputStream();
 
 
 
			ObjectOutputStream oos = new ObjectOutputStream(bos);
 
			b.writeExternal(oos);
 
			oos.flush();
 
			oos.close();
 
			FileOutputStream fos = new FileOutputStream(f);
 
			byte[] bb = bos.toByteArray();
 
 
 
			fos.write(bb);
 
			fos.flush();
 
			fos.close();
 
			if (bb.length > data.buf.length) {
 
				data.buf = bb;
 
			}
 
		}
 
		map.blockList.set(pick, null);
 
 
 
	}
 
 
 
	private void fatal(int block) {
 
		Exception e = new Exception();
 
		try {
 
			throw e;
 
		} catch (Exception e2) {
 
			e2.printStackTrace();
 
		}
 
		System.err.println("block " + block
 
				+ " requested and it is not in blocklist and not a file");
 
		for (int i : data.retirees) {
 
			System.err.print(i + " ");
 
		}
 
		System.err.println(" were retired");
 
		System.exit(-2);
 
	}
 
 
 
	public static boolean metaExists(File indexDir, String name) {
 
		File home = new File(indexDir, name);
 
		return new File(home, "LinearMap2").exists();
 
	}
 
 
 
	public static <K, V> LHMap2<K, V> load(File baseDir, String name)
 
			throws FileNotFoundException, IOException, ClassNotFoundException {
 
		File home = new File(baseDir, name);
 
 
 
		File f2 = new File(home, "LinearMap2");
 
		ObjectInputStream ois = new ObjectInputStream(new FileInputStream(f2));
 
		LHMap2<K, V> map = (LHMap2<K, V>) ois.readObject();
 
		ois.close();
 
		loadBlocks(map);
 
 
 
		return map;
 
	}
 
 
 
	private static <K, V> void loadBlocks(LHMap2<K, V> map) {
 
		LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(map);
 
		int size = map.blockList.size();
 
		for (int i = 0; i < size; ++i) {
 
			mgr.blockRequested(i, map);
 
		}
 
	}
 
 
 
	public static <K, V> LHMap2BlockFileManager<K, V> getBlockManagerListener(
 
			LHMap2<K, V> map) {
 
		LHMap2BlockFileManager<K, V> mgr = (LHMap2BlockFileManager<K, V>) map.listeners
 
				.get(0);
 
		return mgr;
 
	}
 
 
 
	public static void save(File indexDir, String name,
 
			LHMap2<?, ?> offsetMap) throws FileNotFoundException, IOException {
 
		retireAllBlocks(offsetMap);
 
 
 
		File home = new File(indexDir, name);
 
		File f2 = new File(home, "LinearMap2");
 
		ObjectOutputStream oos = new ObjectOutputStream(
 
				new FileOutputStream(f2));
 
		oos.writeObject(offsetMap);
 
		oos.close();
 
	}
 
 
 
	private static <K, V> void retireAllBlocks(LHMap2<K, V> offsetMap)
 
			throws FileNotFoundException, IOException {
 
		LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(offsetMap);
 
		int sz = offsetMap.blockList.size();
 
		for (int i = 0; i < sz; ++i) {
 
			LHMap2.Block<K, V> b = offsetMap.blockList.get(i);
 
 
 
			if (b != null) {
 
				mgr.retireBlock(offsetMap, i);
 
			}
 
 
 
		}
 
	}
 
}
Last modified on 28 May 2011, at 00:51