# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1314648912 -7200
# Node ID 6355ecda1f0861f5956c8594b55b00872336fa44
# Parent  6d1804fe0ed744e129c5b45e863456b142107c34
Tailored Map implementation with int keys

diff -r 6d1804fe0ed7 -r 6355ecda1f08 src/org/tmatesoft/hg/internal/IntMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/org/tmatesoft/hg/internal/IntMap.java	Mon Aug 29 22:15:12 2011 +0200
@@ -0,0 +1,151 @@
+/*
+ * Copyright (c) 2011 TMate Software Ltd
+ *  
+ * 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; version 2 of the License.
+ *
+ * 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.
+ *
+ * For information on how to redistribute this software under
+ * the terms of a license other than GNU General Public License
+ * contact TMate Software at support@hg4j.com
+ */
+package org.tmatesoft.hg.internal;
+
+import java.util.NoSuchElementException;
+
+
+/**
+ * Map implementation that uses plain int keys and performs with log n effectiveness.
+ * 
+ * @author Artem Tikhomirov
+ * @author TMate Software Ltd.
+ */
+public class IntMap<V> {
+
+	private int[] keys;
+	private Object[] values;
+	private int size;
+	
+	public IntMap(int size) {
+		keys = new int[size <= 0 ? 16 : size];
+		values = new Object[keys.length];
+	}
+	
+	public int size() {
+		return size;
+	}
+	
+	public int firstKey() {
+		if (size == 0) {
+			throw new NoSuchElementException();
+		}
+		return keys[0];
+	}
+
+	public int lastKey() {
+		if (size == 0) {
+			throw new NoSuchElementException();
+		}
+		return keys[size-1];
+	}
+	
+	public void trimToSize() {
+		if (size < keys.length) {
+			int[] newKeys = new int[size];
+			Object[] newValues = new Object[size];
+			System.arraycopy(keys, 0, newKeys, 0, size);
+			System.arraycopy(values, 0, newValues, 0, size);
+			keys = newKeys;
+			values = newValues;
+		}
+	}
+
+	public void put(int key, V value) {
+		int ix = binarySearch(keys, size, key);
+		if (ix < 0) {
+			final int insertPoint = -ix - 1;
+			assert insertPoint <= size; // can't be greater, provided binarySearch didn't malfunction.
+			if (size == keys.length) {
+				int newCapacity = size + (size >>> 2);
+				int[] newKeys = new int[newCapacity];
+				Object[] newValues = new Object[newCapacity];
+				System.arraycopy(keys, 0, newKeys, 0, insertPoint);
+				System.arraycopy(keys, insertPoint, newKeys, insertPoint+1, keys.length - insertPoint);
+				System.arraycopy(values, 0, newValues, 0, insertPoint);
+				System.arraycopy(values, insertPoint, newValues, insertPoint+1, values.length - insertPoint);
+				keys = newKeys;
+				values = newValues;
+			} else {
+				// arrays got enough capacity
+				if (insertPoint != size) {
+					System.arraycopy(keys, insertPoint, keys, insertPoint+1, keys.length - insertPoint - 1);
+					System.arraycopy(values, insertPoint, values, insertPoint+1, values.length - insertPoint - 1);
+				}
+				// else insertPoint is past known elements, no need to copy arrays
+			}
+			keys[insertPoint] = key;
+			values[insertPoint] = value;
+			size++;
+		} else {
+			values[ix] = value;
+		}
+	}
+	
+	public boolean containsKey(int key) {
+		return binarySearch(keys, size, key) >= 0;
+	}
+
+	@SuppressWarnings("unchecked")
+	public V get(int key) {
+		int ix = binarySearch(keys, size, key);
+		if (ix >= 0) {
+			return (V) values[ix];
+		}
+		return null;
+	}
+
+	// copy of Arrays.binarySearch, with upper search limit as argument
+	private static int binarySearch(int[] a, int high, int key) {
+		int low = 0;
+		high--;
+
+		while (low <= high) {
+			int mid = (low + high) >> 1;
+			int midVal = a[mid];
+
+			if (midVal < key)
+				low = mid + 1;
+			else if (midVal > key)
+				high = mid - 1;
+			else
+				return mid; // key found
+		}
+		return -(low + 1); // key not found.
+	}
+
+	public static void main(String[] args) {
+		IntMap<String> m = new IntMap<String>(-1);
+		m.put(18, "18");
+		m.put(1, "1");
+		m.put(9, "9");
+		m.put(20, "20");
+		m.put(2, "2");
+		m.put(3, "3");
+		m.put(21, "21");
+		m.put(15, "15");
+		m.put(12, "12");
+		m.put(11, "11");
+		m.put(31, "31");
+		System.out.printf("%d  [%d..%d]\n", m.size(), m.firstKey(), m.lastKey());
+		for (int i = m.firstKey(); i <= m.lastKey(); i++) {
+			if (m.containsKey(i)) {
+				System.out.printf("@%02d:%s\n", i, m.get(i));
+			}
+		}
+	}
+}
diff -r 6d1804fe0ed7 -r 6355ecda1f08 src/org/tmatesoft/hg/repo/HgDataFile.java
--- a/src/org/tmatesoft/hg/repo/HgDataFile.java	Thu Aug 25 21:35:03 2011 +0200
+++ b/src/org/tmatesoft/hg/repo/HgDataFile.java	Mon Aug 29 22:15:12 2011 +0200
@@ -28,13 +28,13 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.TreeMap;
 
 import org.tmatesoft.hg.core.HgDataStreamException;
 import org.tmatesoft.hg.core.HgException;
 import org.tmatesoft.hg.core.Nodeid;
 import org.tmatesoft.hg.internal.DataAccess;
 import org.tmatesoft.hg.internal.FilterByteChannel;
+import org.tmatesoft.hg.internal.IntMap;
 import org.tmatesoft.hg.internal.RevlogStream;
 import org.tmatesoft.hg.util.ByteChannel;
 import org.tmatesoft.hg.util.CancelSupport;
@@ -347,52 +347,60 @@
 	}
 
 	private static class Metadata {
+		private static class Record {
+			public final int offset;
+			public final MetadataEntry[] entries;
+			
+			public Record(int off, MetadataEntry[] entr) {
+				offset = off;
+				entries = entr;
+			}
+		}
 		// XXX sparse array needed
-		private final TreeMap<Integer, Integer> offsets = new TreeMap<Integer, Integer>();
-		private final TreeMap<Integer, MetadataEntry[]> entries = new TreeMap<Integer, MetadataEntry[]>();
+		private final IntMap<Record> entries = new IntMap<Record>(5);
 		
-		private final Integer NONE = new Integer(-1); // do not duplicate -1 integers at least within single file (don't want statics)
+		private final Record NONE = new Record(-1, null); // don't want statics
 
 		// true when there's metadata for given revision
 		boolean known(int revision) {
-			Integer i = offsets.get(revision);
+			Record i = entries.get(revision);
 			return i != null && NONE != i;
 		}
 
 		// true when revision has been checked for metadata presence.
 		public boolean checked(int revision) {
-			return offsets.containsKey(revision);
+			return entries.containsKey(revision);
 		}
 
 		// true when revision has been checked and found not having any metadata
 		boolean none(int revision) {
-			Integer i = offsets.get(revision);
+			Record i = entries.get(revision);
 			return i == NONE;
 		}
 
 		// mark revision as having no metadata.
 		void recordNone(int revision) {
-			Integer i = offsets.get(revision);
+			Record i = entries.get(revision);
 			if (i == NONE) {
 				return; // already there
 			} 
 			if (i != null) {
 				throw new IllegalStateException(String.format("Trying to override Metadata state for revision %d (known offset: %d)", revision, i));
 			}
-			offsets.put(revision, NONE);
+			entries.put(revision, NONE);
 		}
 
 		// since this is internal class, callers are supposed to ensure arg correctness (i.e. ask known() before)
 		int dataOffset(int revision) {
-			return offsets.get(revision);
+			return entries.get(revision).offset;
 		}
 		void add(int revision, int dataOffset, Collection<MetadataEntry> e) {
-			assert !offsets.containsKey(revision);
-			offsets.put(revision, dataOffset);
-			entries.put(revision, e.toArray(new MetadataEntry[e.size()]));
+			assert !entries.containsKey(revision);
+			entries.put(revision, new Record(dataOffset, e.toArray(new MetadataEntry[e.size()])));
 		}
+
 		String find(int revision, String key) {
-			for (MetadataEntry me : entries.get(revision)) {
+			for (MetadataEntry me : entries.get(revision).entries) {
 				if (me.matchKey(key)) {
 					return me.value();
 				}
@@ -466,7 +474,6 @@
 					bos.write(b);
 				}
 			}
-			_metadata.trimToSize();
 			metadata.add(revisionNumber, lastEntryStart, _metadata);
 			if (da.isEmpty() || !byteOne) {
 				throw new HgDataStreamException(fname, String.format("Metadata for revision %d is not closed properly", revisionNumber), null);