Sort Config entries and use O(log N) lookup

Decrease running time for getStringList (and all other get methods) by
looking for configuration entries using binary search rather than
linear search through the configuration file.

Configuration lines are sorted by section, subsection, name in a
sorted list whenever the snapshot is rebuilt. Binary search is used to
locate an index in the middle of the values, then walk backwards to
find the first value in the range.

Given a configuration of file of 5000 distinct section/subsection/name
triplets (e.g. a Gerrit Code Review project.config configuration file
with 5000 unique access control rules), this new code is faster to
lookup each rule individually using getStringList():

  old setStringList() 194 usec avg
      getStringList() 196 usec avg

  new setStringList() 188 usec avg
      getStringList()  24 usec avg

Change-Id: Ic8907231868c18eb946b72f341a6b58666b70324

2 files changed, 123 insertions, 39 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java
index cf166d5b9c..58a03bf8bf 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java
@@ -456,22 +456,22 @@ public class Config {
 	 */
 	public String[] getStringList(final String section, String subsection,
 			final String name) {
-		final String[] baseList;
+		String[] base;
 		if (baseConfig != null)
-			baseList = baseConfig.getStringList(section, subsection, name);
+			base = baseConfig.getStringList(section, subsection, name);
 		else
-			baseList = EMPTY_STRING_ARRAY;
-
-		final List<String> lst = getRawStringList(section, subsection, name);
-		if (lst != null) {
-			final String[] res = new String[baseList.length + lst.size()];
-			int idx = baseList.length;
-			System.arraycopy(baseList, 0, res, 0, idx);
-			for (final String val : lst)
-				res[idx++] = val;
-			return res;
-		}
-		return baseList;
+			base = EMPTY_STRING_ARRAY;
+
+		String[] self = getRawStringList(section, subsection, name);
+		if (self == null)
+			return base;
+		if (base.length == 0)
+			return self;
+		String[] res = new String[base.length + self.length];
+		int n = base.length;
+		System.arraycopy(base, 0, res, 0, n);
+		System.arraycopy(self, 0, res, n, self.length);
+		return res;
 	}
 
 	/**
@@ -588,36 +588,18 @@ public class Config {
 
 	private String getRawString(final String section, final String subsection,
 			final String name) {
-		final List<String> lst = getRawStringList(section, subsection, name);
+		String[] lst = getRawStringList(section, subsection, name);
 		if (lst != null)
-			return lst.get(0);
+			return lst[0];
 		else if (baseConfig != null)
 			return baseConfig.getRawString(section, subsection, name);
 		else
 			return null;
 	}
 
-	private List<String> getRawStringList(final String section,
-			final String subsection, final String name) {
-		List<String> r = null;
-		for (final ConfigLine e : state.get().entryList) {
-			if (e.match(section, subsection, name))
-				r = add(r, e.value);
-		}
-		return r;
-	}
-
-	private static List<String> add(final List<String> curr, final String value) {
-		if (curr == null)
-			return Collections.singletonList(value);
-		if (curr.size() == 1) {
-			final List<String> r = new ArrayList<String>(2);
-			r.add(curr.get(0));
-			r.add(value);
-			return r;
-		}
-		curr.add(value);
-		return curr;
+	private String[] getRawStringList(String section, String subsection,
+			String name) {
+		return state.get().get(section, subsection, name);
 	}
 
 	private ConfigSnapshot getState() {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java
index 61e4e0c93e..5527267b86 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java
@@ -2,8 +2,7 @@
  * Copyright (C) 2010, Mathias Kinzler <mathias.kinzler@sap.com>
  * Copyright (C) 2009, Constantine Plotnikov <constantine.plotnikov@gmail.com>
  * Copyright (C) 2007, Dave Watson <dwatson@mimvista.com>
- * Copyright (C) 2008-2010, Google Inc.
- * Copyright (C) 2009, Google, Inc.
+ * Copyright (C) 2008-2012, Google Inc.
  * Copyright (C) 2009, JetBrains s.r.o.
  * Copyright (C) 2007-2008, Robin Rosenberg <robin.rosenberg@dewire.com>
  * Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org>
@@ -51,6 +50,12 @@
 
 package org.eclipse.jgit.lib;
 
+import static org.eclipse.jgit.util.StringUtils.compareIgnoreCase;
+import static org.eclipse.jgit.util.StringUtils.compareWithCase;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
@@ -59,10 +64,107 @@ class ConfigSnapshot {
 	final List<ConfigLine> entryList;
 	final Map<Object, Object> cache;
 	final ConfigSnapshot baseState;
+	volatile List<ConfigLine> sorted;
 
 	ConfigSnapshot(List<ConfigLine> entries, ConfigSnapshot base) {
 		entryList = entries;
 		cache = new ConcurrentHashMap<Object, Object>(16, 0.75f, 1);
 		baseState = base;
 	}
+
+	String[] get(String section, String subsection, String name) {
+		List<ConfigLine> s = sorted();
+		int idx = find(s, section, subsection, name);
+		if (idx < 0)
+			return null;
+		int end = end(s, idx, section, subsection, name);
+		String[] r = new String[end - idx];
+		for (int i = 0; idx < end;)
+			r[i++] = s.get(idx++).value;
+		return r;
+	}
+
+	private int find(List<ConfigLine> s, String s1, String s2, String name) {
+		int low = 0;
+		int high = s.size();
+		while (low < high) {
+			int mid = (low + high) >>> 1;
+			ConfigLine e = s.get(mid);
+			int cmp = compare2(
+					s1, s2, name,
+					e.section, e.subsection, e.name);
+			if (cmp < 0)
+				high = mid;
+			else if (cmp == 0)
+				return first(s, mid, s1, s2, name);
+			else
+				low = mid + 1;
+		}
+		return -(low + 1);
+	}
+
+	private int first(List<ConfigLine> s, int i, String s1, String s2, String n) {
+		while (0 < i) {
+			if (s.get(i - 1).match(s1, s2, n))
+				i--;
+			else
+				return i;
+		}
+		return i;
+	}
+
+	private int end(List<ConfigLine> s, int i, String s1, String s2, String n) {
+		while (i < s.size()) {
+			if (s.get(i).match(s1, s2, n))
+				i++;
+			else
+				return i;
+		}
+		return i;
+	}
+
+	private List<ConfigLine> sorted() {
+		List<ConfigLine> r = sorted;
+		if (r == null)
+			sorted = r = sort(entryList);
+		return r;
+	}
+
+	private static List<ConfigLine> sort(List<ConfigLine> in) {
+		List<ConfigLine> sorted = new ArrayList<ConfigLine>(in.size());
+		for (ConfigLine line : in) {
+			if (line.section != null && line.name != null)
+				sorted.add(line);
+		}
+		Collections.sort(sorted, new LineComparator());
+		return sorted;
+	}
+
+	private static int compare2(
+			String aSection, String aSubsection, String aName,
+			String bSection, String bSubsection, String bName) {
+		int c = compareIgnoreCase(aSection, bSection);
+		if (c != 0)
+			return c;
+
+		if (aSubsection == null && bSubsection != null)
+			return -1;
+		if (aSubsection != null && bSubsection == null)
+			return 1;
+		if (aSubsection != null) {
+			c = compareWithCase(aSubsection, bSubsection);
+			if (c != 0)
+				return c;
+		}
+
+		return compareIgnoreCase(aName, bName);
+	}
+
+	private static class LineComparator implements Comparator<ConfigLine> {
+		public int compare(ConfigLine a, ConfigLine b) {
+			return compare2(
+					a.section, a.subsection, a.name,
+					b.section, b.subsection, b.name);
+		}
+	}
 }