From 581e6ca2fe6f5d7c6a65b69a1dcf479c41fffbf2 Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Tue, 27 Mar 2012 10:43:02 -0400 Subject: Extract inner classes from Config The Config class is getting very large. Extract two of its inner classes into new top level types to reduce the size of Config. Rename them slightly in the process. Change-Id: I693148a5ae2977378789bf455c880a6fd856c0f0 --- .../src/org/eclipse/jgit/lib/Config.java | 180 +++++---------------- .../src/org/eclipse/jgit/lib/ConfigLine.java | 128 +++++++++++++++ .../src/org/eclipse/jgit/lib/ConfigSnapshot.java | 68 ++++++++ 3 files changed, 236 insertions(+), 140 deletions(-) create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigLine.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java (limited to 'org.eclipse.jgit/src/org/eclipse') 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..cf166d5b9c 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; + private final AtomicReference state; private final Config baseConfig; @@ -118,7 +117,7 @@ public class Config { */ public Config(Config defaultConfig) { baseConfig = defaultConfig; - state = new AtomicReference(newState()); + state = new AtomicReference(newState()); } /** @@ -527,7 +526,7 @@ public class Config { */ @SuppressWarnings("unchecked") public T get(final SectionParser parser) { - final State myState = getState(); + final ConfigSnapshot myState = getState(); T obj = (T) myState.cache.get(parser); if (obj == null) { obj = parser.parse(this); @@ -601,7 +600,7 @@ public class Config { private List getRawStringList(final String section, final String subsection, final String name) { List r = null; - for (final Entry e : state.get().entryList) { + for (final ConfigLine e : state.get().entryList) { if (e.match(section, subsection, name)) r = add(r, e.value); } @@ -621,19 +620,19 @@ public class Config { 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 +791,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 r = new ArrayList(max); + final ArrayList r = new ArrayList(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 +839,7 @@ public class Config { */ public void setStringList(final String section, final String subsection, final String name, final List values) { - State src, res; + ConfigSnapshot src, res; do { src = state.get(); res = replaceStringList(src, section, subsection, name, values); @@ -848,10 +848,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 values) { - final List entries = copy(srcState, values); + final List entries = copy(srcState, values); int entryIndex = 0; int valueIndex = 0; int insertPosition = -1; @@ -859,7 +859,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 +871,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 +891,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 +910,21 @@ public class Config { return newState(entries); } - private static List copy(final State src, final List values) { + private static List copy(final ConfigSnapshot src, + final List 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 r = new ArrayList(max); + final ArrayList r = new ArrayList(max); r.addAll(src.entryList); return r; } - private static int findSectionEnd(final List entries, + private static int findSectionEnd(final List 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 +945,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 +995,10 @@ public class Config { * made to {@code this}. */ public void fromText(final String text) throws ConfigInvalidException { - final List newEntries = new ArrayList(); + final List newEntries = new ArrayList(); 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 +1010,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 +1057,14 @@ public class Config { state.set(newState(newEntries)); } - private State newState() { - return new State(Collections. emptyList(), getBaseState()); + private ConfigSnapshot newState() { + return new ConfigSnapshot(Collections. emptyList(), + getBaseState()); } - private State newState(final List entries) { - return new State(Collections.unmodifiableList(entries), getBaseState()); + private ConfigSnapshot newState(final List entries) { + return new ConfigSnapshot(Collections.unmodifiableList(entries), + getBaseState()); } /** @@ -1279,7 +1282,7 @@ public class Config { public Set parse(Config cfg) { final Set result = new LinkedHashSet(); 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 +1335,7 @@ public class Config { public Set parse(Config cfg) { final Map m = new LinkedHashMap(); 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 +1358,7 @@ public class Config { public Set parse(Config cfg) { final Map m = new LinkedHashMap(); 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 +1399,6 @@ public class Config { } } - private static class State { - final List entryList; - - final Map cache; - - final State baseState; - - State(List entries, State base) { - entryList = entries; - cache = new ConcurrentHashMap(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 ""; - 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 + * Copyright (C) 2009, Constantine Plotnikov + * Copyright (C) 2007, Dave Watson + * Copyright (C) 2008-2010, Google Inc. + * Copyright (C) 2009, Google, Inc. + * Copyright (C) 2009, JetBrains s.r.o. + * Copyright (C) 2007-2008, Robin Rosenberg + * Copyright (C) 2006-2008, Shawn O. Pearce + * Copyright (C) 2008, Thad Hughes + * 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 ""; + 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..61e4e0c93e --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java @@ -0,0 +1,68 @@ +/* + * Copyright (C) 2010, Mathias Kinzler + * Copyright (C) 2009, Constantine Plotnikov + * Copyright (C) 2007, Dave Watson + * Copyright (C) 2008-2010, Google Inc. + * Copyright (C) 2009, Google, Inc. + * Copyright (C) 2009, JetBrains s.r.o. + * Copyright (C) 2007-2008, Robin Rosenberg + * Copyright (C) 2006-2008, Shawn O. Pearce + * Copyright (C) 2008, Thad Hughes + * 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 java.util.List; +import java.util.Map; +import java.util.concurrent.ConcurrentHashMap; + +class ConfigSnapshot { + final List entryList; + final Map cache; + final ConfigSnapshot baseState; + + ConfigSnapshot(List entries, ConfigSnapshot base) { + entryList = entries; + cache = new ConcurrentHashMap(16, 0.75f, 1); + baseState = base; + } +} -- cgit v1.2.3 From 552682dc6aa8f3a77fac9a2d25a20914fcc65ba0 Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Tue, 27 Mar 2012 11:49:13 -0400 Subject: 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 --- .../src/org/eclipse/jgit/lib/Config.java | 56 ++++------- .../src/org/eclipse/jgit/lib/ConfigSnapshot.java | 106 ++++++++++++++++++++- .../src/org/eclipse/jgit/util/StringUtils.java | 44 +++++++++ 3 files changed, 167 insertions(+), 39 deletions(-) (limited to 'org.eclipse.jgit/src/org/eclipse') 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 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 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 getRawStringList(final String section, - final String subsection, final String name) { - List 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 add(final List curr, final String value) { - if (curr == null) - return Collections.singletonList(value); - if (curr.size() == 1) { - final List r = new ArrayList(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 * Copyright (C) 2009, Constantine Plotnikov * Copyright (C) 2007, Dave Watson - * 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 * Copyright (C) 2006-2008, Shawn O. Pearce @@ -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 entryList; final Map cache; final ConfigSnapshot baseState; + volatile List sorted; ConfigSnapshot(List entries, ConfigSnapshot base) { entryList = entries; cache = new ConcurrentHashMap(16, 0.75f, 1); baseState = base; } + + String[] get(String section, String subsection, String name) { + List 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 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 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 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 sorted() { + List r = sorted; + if (r == null) + sorted = r = sort(entryList); + return r; + } + + private static List sort(List in) { + List sorted = new ArrayList(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 { + 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 @@ -120,6 +120,50 @@ public final class StringUtils { return true; } + /** + * Compare two strings, ignoring case. + *

+ * 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. + *

+ * 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)}. -- cgit v1.2.3