Merge changes Ic8907231,I693148a5

* changes:
  Sort Config entries and use O(log N) lookup
  Extract inner classes from Config

4 files changed, 400 insertions, 176 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 7ea91ffafc..58a03bf8bf 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java
@@ -61,7 +61,6 @@ import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.atomic.AtomicReference;
 
 import org.eclipse.jgit.errors.ConfigInvalidException;
@@ -91,7 +90,7 @@ public class Config {
 	 * This state is copy-on-write. It should always contain an immutable list
 	 * of the configuration keys/values.
 	 */
-	private final AtomicReference<State> state;
+	private final AtomicReference<ConfigSnapshot> state;
 
 	private final Config baseConfig;
 
@@ -118,7 +117,7 @@ public class Config {
 	 */
 	public Config(Config defaultConfig) {
 		baseConfig = defaultConfig;
-		state = new AtomicReference<State>(newState());
+		state = new AtomicReference<ConfigSnapshot>(newState());
 	}
 
 	/**
@@ -457,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;
 	}
 
 	/**
@@ -527,7 +526,7 @@ public class Config {
 	 */
 	@SuppressWarnings("unchecked")
 	public <T> T get(final SectionParser<T> parser) {
-		final State myState = getState();
+		final ConfigSnapshot myState = getState();
 		T obj = (T) myState.cache.get(parser);
 		if (obj == null) {
 			obj = parser.parse(this);
@@ -589,51 +588,33 @@ 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 Entry e : state.get().entryList) {
-			if (e.match(section, subsection, name))
-				r = add(r, e.value);
-		}
-		return r;
+	private String[] getRawStringList(String section, String subsection,
+			String name) {
+		return state.get().get(section, subsection, name);
 	}
 
-	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 State getState() {
-		State cur, upd;
+	private ConfigSnapshot getState() {
+		ConfigSnapshot cur, upd;
 		do {
 			cur = state.get();
-			final State base = getBaseState();
+			final ConfigSnapshot base = getBaseState();
 			if (cur.baseState == base)
 				return cur;
-			upd = new State(cur.entryList, base);
+			upd = new ConfigSnapshot(cur.entryList, base);
 		} while (!state.compareAndSet(cur, upd));
 		return upd;
 	}
 
-	private State getBaseState() {
+	private ConfigSnapshot getBaseState() {
 		return baseConfig != null ? baseConfig.getState() : null;
 	}
 
@@ -792,20 +773,21 @@ public class Config {
 	 *            optional subsection value, e.g. a branch name
 	 */
 	public void unsetSection(String section, String subsection) {
-		State src, res;
+		ConfigSnapshot src, res;
 		do {
 			src = state.get();
 			res = unsetSection(src, section, subsection);
 		} while (!state.compareAndSet(src, res));
 	}
 
-	private State unsetSection(final State srcState, final String section,
+	private ConfigSnapshot unsetSection(final ConfigSnapshot srcState,
+			final String section,
 			final String subsection) {
 		final int max = srcState.entryList.size();
-		final ArrayList<Entry> r = new ArrayList<Entry>(max);
+		final ArrayList<ConfigLine> r = new ArrayList<ConfigLine>(max);
 
 		boolean lastWasMatch = false;
-		for (Entry e : srcState.entryList) {
+		for (ConfigLine e : srcState.entryList) {
 			if (e.match(section, subsection)) {
 				// Skip this record, it's for the section we are removing.
 				lastWasMatch = true;
@@ -839,7 +821,7 @@ public class Config {
 	 */
 	public void setStringList(final String section, final String subsection,
 			final String name, final List<String> values) {
-		State src, res;
+		ConfigSnapshot src, res;
 		do {
 			src = state.get();
 			res = replaceStringList(src, section, subsection, name, values);
@@ -848,10 +830,10 @@ public class Config {
 			fireConfigChangedEvent();
 	}
 
-	private State replaceStringList(final State srcState,
+	private ConfigSnapshot replaceStringList(final ConfigSnapshot srcState,
 			final String section, final String subsection, final String name,
 			final List<String> values) {
-		final List<Entry> entries = copy(srcState, values);
+		final List<ConfigLine> entries = copy(srcState, values);
 		int entryIndex = 0;
 		int valueIndex = 0;
 		int insertPosition = -1;
@@ -859,7 +841,7 @@ public class Config {
 		// Reset the first n Entry objects that match this input name.
 		//
 		while (entryIndex < entries.size() && valueIndex < values.size()) {
-			final Entry e = entries.get(entryIndex);
+			final ConfigLine e = entries.get(entryIndex);
 			if (e.match(section, subsection, name)) {
 				entries.set(entryIndex, e.forValue(values.get(valueIndex++)));
 				insertPosition = entryIndex + 1;
@@ -871,7 +853,7 @@ public class Config {
 		//
 		if (valueIndex == values.size() && entryIndex < entries.size()) {
 			while (entryIndex < entries.size()) {
-				final Entry e = entries.get(entryIndex++);
+				final ConfigLine e = entries.get(entryIndex++);
 				if (e.match(section, subsection, name))
 					entries.remove(--entryIndex);
 			}
@@ -891,14 +873,14 @@ public class Config {
 				// We didn't find any matching section header for this key,
 				// so we must create a new section header at the end.
 				//
-				final Entry e = new Entry();
+				final ConfigLine e = new ConfigLine();
 				e.section = section;
 				e.subsection = subsection;
 				entries.add(e);
 				insertPosition = entries.size();
 			}
 			while (valueIndex < values.size()) {
-				final Entry e = new Entry();
+				final ConfigLine e = new ConfigLine();
 				e.section = section;
 				e.subsection = subsection;
 				e.name = name;
@@ -910,20 +892,21 @@ public class Config {
 		return newState(entries);
 	}
 
-	private static List<Entry> copy(final State src, final List<String> values) {
+	private static List<ConfigLine> copy(final ConfigSnapshot src,
+			final List<String> values) {
 		// At worst we need to insert 1 line for each value, plus 1 line
 		// for a new section header. Assume that and allocate the space.
 		//
 		final int max = src.entryList.size() + values.size() + 1;
-		final ArrayList<Entry> r = new ArrayList<Entry>(max);
+		final ArrayList<ConfigLine> r = new ArrayList<ConfigLine>(max);
 		r.addAll(src.entryList);
 		return r;
 	}
 
-	private static int findSectionEnd(final List<Entry> entries,
+	private static int findSectionEnd(final List<ConfigLine> entries,
 			final String section, final String subsection) {
 		for (int i = 0; i < entries.size(); i++) {
-			Entry e = entries.get(i);
+			ConfigLine e = entries.get(i);
 			if (e.match(section, subsection, null)) {
 				i++;
 				while (i < entries.size()) {
@@ -944,7 +927,7 @@ public class Config {
 	 */
 	public String toText() {
 		final StringBuilder out = new StringBuilder();
-		for (final Entry e : state.get().entryList) {
+		for (final ConfigLine e : state.get().entryList) {
 			if (e.prefix != null)
 				out.append(e.prefix);
 			if (e.section != null && e.name == null) {
@@ -994,10 +977,10 @@ public class Config {
 	 *             made to {@code this}.
 	 */
 	public void fromText(final String text) throws ConfigInvalidException {
-		final List<Entry> newEntries = new ArrayList<Entry>();
+		final List<ConfigLine> newEntries = new ArrayList<ConfigLine>();
 		final StringReader in = new StringReader(text);
-		Entry last = null;
-		Entry e = new Entry();
+		ConfigLine last = null;
+		ConfigLine e = new ConfigLine();
 		for (;;) {
 			int input = in.read();
 			if (-1 == input)
@@ -1009,7 +992,7 @@ public class Config {
 				newEntries.add(e);
 				if (e.section != null)
 					last = e;
-				e = new Entry();
+				e = new ConfigLine();
 
 			} else if (e.suffix != null) {
 				// Everything up until the end-of-line is in the suffix.
@@ -1056,12 +1039,14 @@ public class Config {
 		state.set(newState(newEntries));
 	}
 
-	private State newState() {
-		return new State(Collections.<Entry> emptyList(), getBaseState());
+	private ConfigSnapshot newState() {
+		return new ConfigSnapshot(Collections.<ConfigLine> emptyList(),
+				getBaseState());
 	}
 
-	private State newState(final List<Entry> entries) {
-		return new State(Collections.unmodifiableList(entries), getBaseState());
+	private ConfigSnapshot newState(final List<ConfigLine> entries) {
+		return new ConfigSnapshot(Collections.unmodifiableList(entries),
+				getBaseState());
 	}
 
 	/**
@@ -1279,7 +1264,7 @@ public class Config {
 		public Set<String> parse(Config cfg) {
 			final Set<String> result = new LinkedHashSet<String>();
 			while (cfg != null) {
-				for (final Entry e : cfg.state.get().entryList) {
+				for (final ConfigLine e : cfg.state.get().entryList) {
 					if (e.subsection != null && e.name == null
 							&& StringUtils.equalsIgnoreCase(section, e.section))
 						result.add(e.subsection);
@@ -1332,7 +1317,7 @@ public class Config {
 		public Set<String> parse(Config cfg) {
 			final Map<String, String> m = new LinkedHashMap<String, String>();
 			while (cfg != null) {
-				for (final Entry e : cfg.state.get().entryList) {
+				for (final ConfigLine e : cfg.state.get().entryList) {
 					if (e.name == null)
 						continue;
 					if (!StringUtils.equalsIgnoreCase(section, e.section))
@@ -1355,7 +1340,7 @@ public class Config {
 		public Set<String> parse(Config cfg) {
 			final Map<String, String> m = new LinkedHashMap<String, String>();
 			while (cfg != null) {
-				for (final Entry e : cfg.state.get().entryList) {
+				for (final ConfigLine e : cfg.state.get().entryList) {
 					if (e.section != null) {
 						String lc = StringUtils.toLowerCase(e.section);
 						if (!m.containsKey(lc))
@@ -1396,109 +1381,6 @@ public class Config {
 		}
 	}
 
-	private static class State {
-		final List<Entry> entryList;
-
-		final Map<Object, Object> cache;
-
-		final State baseState;
-
-		State(List<Entry> entries, State base) {
-			entryList = entries;
-			cache = new ConcurrentHashMap<Object, Object>(16, 0.75f, 1);
-			baseState = base;
-		}
-	}
-
-	/**
-	 * The configuration file entry
-	 */
-	private static class Entry {
-
-		/**
-		 * The text content before entry
-		 */
-		String prefix;
-
-		/**
-		 * The section name for the entry
-		 */
-		String section;
-
-		/**
-		 * Subsection name
-		 */
-		String subsection;
-
-		/**
-		 * The key name
-		 */
-		String name;
-
-		/**
-		 * The value
-		 */
-		String value;
-
-		/**
-		 * The text content after entry
-		 */
-		String suffix;
-
-		Entry forValue(final String newValue) {
-			final Entry e = new Entry();
-			e.prefix = prefix;
-			e.section = section;
-			e.subsection = subsection;
-			e.name = name;
-			e.value = newValue;
-			e.suffix = suffix;
-			return e;
-		}
-
-		boolean match(final String aSection, final String aSubsection,
-				final String aKey) {
-			return eqIgnoreCase(section, aSection)
-					&& eqSameCase(subsection, aSubsection)
-					&& eqIgnoreCase(name, aKey);
-		}
-
-		boolean match(final String aSection, final String aSubsection) {
-			return eqIgnoreCase(section, aSection)
-					&& eqSameCase(subsection, aSubsection);
-		}
-
-		private static boolean eqIgnoreCase(final String a, final String b) {
-			if (a == null && b == null)
-				return true;
-			if (a == null || b == null)
-				return false;
-			return StringUtils.equalsIgnoreCase(a, b);
-		}
-
-		private static boolean eqSameCase(final String a, final String b) {
-			if (a == null && b == null)
-				return true;
-			if (a == null || b == null)
-				return false;
-			return a.equals(b);
-		}
-
-		@Override
-		public String toString() {
-			if (section == null)
-				return "<empty>";
-			StringBuilder b = new StringBuilder(section);
-			if (subsection != null)
-				b.append(".").append(subsection);
-			if (name != null)
-				b.append(".").append(name);
-			if (value != null)
-				b.append("=").append(value);
-			return b.toString();
-		}
-	}
-
 	private static class StringReader {
 		private final char[] buf;
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigLine.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigLine.java
new file mode 100644
index 0000000000..2715f5f94a
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigLine.java
@@ -0,0 +1,128 @@
+/*
+ * 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) 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>
+ * Copyright (C) 2008, Thad Hughes <thadh@thad.corp.google.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.lib;
+
+import org.eclipse.jgit.util.StringUtils;
+
+/** A line in a Git {@link Config} file. */
+class ConfigLine {
+	/** The text content before entry. */
+	String prefix;
+
+	/** The section name for the entry. */
+	String section;
+
+	/** Subsection name. */
+	String subsection;
+
+	/** The key name. */
+	String name;
+
+	/** The value. */
+	String value;
+
+	/** The text content after entry. */
+	String suffix;
+
+	ConfigLine forValue(final String newValue) {
+		final ConfigLine e = new ConfigLine();
+		e.prefix = prefix;
+		e.section = section;
+		e.subsection = subsection;
+		e.name = name;
+		e.value = newValue;
+		e.suffix = suffix;
+		return e;
+	}
+
+	boolean match(final String aSection, final String aSubsection,
+			final String aKey) {
+		return eqIgnoreCase(section, aSection)
+				&& eqSameCase(subsection, aSubsection)
+				&& eqIgnoreCase(name, aKey);
+	}
+
+	boolean match(final String aSection, final String aSubsection) {
+		return eqIgnoreCase(section, aSection)
+				&& eqSameCase(subsection, aSubsection);
+	}
+
+	private static boolean eqIgnoreCase(final String a, final String b) {
+		if (a == null && b == null)
+			return true;
+		if (a == null || b == null)
+			return false;
+		return StringUtils.equalsIgnoreCase(a, b);
+	}
+
+	private static boolean eqSameCase(final String a, final String b) {
+		if (a == null && b == null)
+			return true;
+		if (a == null || b == null)
+			return false;
+		return a.equals(b);
+	}
+
+	@Override
+	public String toString() {
+		if (section == null)
+			return "<empty>";
+		StringBuilder b = new StringBuilder(section);
+		if (subsection != null)
+			b.append(".").append(subsection);
+		if (name != null)
+			b.append(".").append(name);
+		if (value != null)
+			b.append("=").append(value);
+		return b.toString();
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java
new file mode 100644
index 0000000000..5527267b86
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java
@@ -0,0 +1,170 @@
+/*
+ * 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-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>
+ * Copyright (C) 2008, Thad Hughes <thadh@thad.corp.google.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+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;
+
+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);
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java
index 605f1705ef..f423f98e27 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java
@@ -121,6 +121,50 @@ public final class StringUtils {
 	}
 
 	/**
+	 * Compare two strings, ignoring case.
+	 * <p>
+	 * This method does not honor the JVM locale, but instead always behaves as
+	 * though it is in the US-ASCII locale.
+	 *
+	 * @param a
+	 *            first string to compare.
+	 * @param b
+	 *            second string to compare.
+	 * @return negative, zero or positive if a sorts before, is equal to, or
+	 *         sorts after b.
+	 */
+	public static int compareIgnoreCase(String a, String b) {
+		for (int i = 0; i < a.length() && i < b.length(); i++) {
+			int d = toLowerCase(a.charAt(i)) - toLowerCase(b.charAt(i));
+			if (d != 0)
+				return d;
+		}
+		return a.length() - b.length();
+	}
+
+	/**
+	 * Compare two strings, honoring case.
+	 * <p>
+	 * This method does not honor the JVM locale, but instead always behaves as
+	 * though it is in the US-ASCII locale.
+	 *
+	 * @param a
+	 *            first string to compare.
+	 * @param b
+	 *            second string to compare.
+	 * @return negative, zero or positive if a sorts before, is equal to, or
+	 *         sorts after b.
+	 */
+	public static int compareWithCase(String a, String b) {
+		for (int i = 0; i < a.length() && i < b.length(); i++) {
+			int d = a.charAt(i) - b.charAt(i);
+			if (d != 0)
+				return d;
+		}
+		return a.length() - b.length();
+	}
+
+	/**
 	 * Parse a string as a standard Git boolean value. See
 	 * {@link #toBooleanOrNull(String)}.
 	 *