![Shawn O. Pearce](https://secure.gravatar.com/avatar/a4611f1fb34714fc54ceec3859c490f7?d=identicon) Create new RefList and RefMap utility types
These types can be used by RefDatabase implementations to manage
the collection.
A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection. Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.
A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.
The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase. By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current. Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array. As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.
Almost complete test coverage is included in the corresponding
unit tests. A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.
Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
14 years ago ![Shawn O. Pearce](https://secure.gravatar.com/avatar/a4611f1fb34714fc54ceec3859c490f7?d=identicon) Create new RefList and RefMap utility types
These types can be used by RefDatabase implementations to manage
the collection.
A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection. Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.
A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.
The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase. By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current. Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array. As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.
Almost complete test coverage is included in the corresponding
unit tests. A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.
Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
14 years ago ![Shawn O. Pearce](https://secure.gravatar.com/avatar/a4611f1fb34714fc54ceec3859c490f7?d=identicon) Create new RefList and RefMap utility types
These types can be used by RefDatabase implementations to manage
the collection.
A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection. Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.
A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.
The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase. By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current. Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array. As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.
Almost complete test coverage is included in the corresponding
unit tests. A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.
Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
14 years ago ![Shawn O. Pearce](https://secure.gravatar.com/avatar/a4611f1fb34714fc54ceec3859c490f7?d=identicon) Create new RefList and RefMap utility types
These types can be used by RefDatabase implementations to manage
the collection.
A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection. Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.
A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.
The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase. By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current. Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array. As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.
Almost complete test coverage is included in the corresponding
unit tests. A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.
Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
14 years ago ![Shawn O. Pearce](https://secure.gravatar.com/avatar/a4611f1fb34714fc54ceec3859c490f7?d=identicon) Create new RefList and RefMap utility types
These types can be used by RefDatabase implementations to manage
the collection.
A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection. Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.
A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.
The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase. By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current. Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array. As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.
Almost complete test coverage is included in the corresponding
unit tests. A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.
Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
14 years ago |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424 |
- /*
- * Copyright (C) 2010, Google Inc.
- * 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.util;
-
- import java.util.AbstractMap;
- import java.util.AbstractSet;
- import java.util.Iterator;
- import java.util.Map;
- import java.util.NoSuchElementException;
- import java.util.Set;
-
- import org.eclipse.jgit.lib.AnyObjectId;
- import org.eclipse.jgit.lib.ObjectId;
- import org.eclipse.jgit.lib.Ref;
- import org.eclipse.jgit.lib.RefComparator;
-
- /**
- * Specialized Map to present a {@code RefDatabase} namespace.
- * <p>
- * Although not declared as a {@link java.util.SortedMap}, iterators from this
- * map's projections always return references in {@link RefComparator} ordering.
- * The map's internal representation is a sorted array of {@link Ref} objects,
- * which means lookup and replacement is O(log N), while insertion and removal
- * can be as expensive as O(N + log N) while the list expands or contracts.
- * Since this is not a general map implementation, all entries must be keyed by
- * the reference name.
- * <p>
- * This class is really intended as a helper for {@code RefDatabase}, which
- * needs to perform a merge-join of three sorted {@link RefList}s in order to
- * present the unified namespace of the packed-refs file, the loose refs/
- * directory tree, and the resolved form of any symbolic references.
- */
- public class RefMap extends AbstractMap<String, Ref> {
- /**
- * Prefix denoting the reference subspace this map contains.
- * <p>
- * All reference names in this map must start with this prefix. If the
- * prefix is not the empty string, it must end with a '/'.
- */
- private final String prefix;
-
- /** Immutable collection of the packed references at construction time. */
- private RefList<Ref> packed;
-
- /**
- * Immutable collection of the loose references at construction time.
- * <p>
- * If an entry appears here and in {@link #packed}, this entry must take
- * precedence, as its more current. Symbolic references in this collection
- * are typically unresolved, so they only tell us who their target is, but
- * not the current value of the target.
- */
- private RefList<Ref> loose;
-
- /**
- * Immutable collection of resolved symbolic references.
- * <p>
- * This collection contains only the symbolic references we were able to
- * resolve at map construction time. Other loose references must be read
- * from {@link #loose}. Every entry in this list must be matched by an entry
- * in {@code loose}, otherwise it might be omitted by the map.
- */
- private RefList<Ref> resolved;
-
- private int size;
-
- private boolean sizeIsValid;
-
- private Set<Entry<String, Ref>> entrySet;
-
- /** Construct an empty map with a small initial capacity. */
- public RefMap() {
- prefix = ""; //$NON-NLS-1$
- packed = RefList.emptyList();
- loose = RefList.emptyList();
- resolved = RefList.emptyList();
- }
-
- /**
- * Construct a map to merge 3 collections together.
- *
- * @param prefix
- * prefix used to slice the lists down. Only references whose
- * names start with this prefix will appear to reside in the map.
- * Must not be null, use {@code ""} (the empty string) to select
- * all list items.
- * @param packed
- * items from the packed reference list, this is the last list
- * searched.
- * @param loose
- * items from the loose reference list, this list overrides
- * {@code packed} if a name appears in both.
- * @param resolved
- * resolved symbolic references. This list overrides the prior
- * list {@code loose}, if an item appears in both. Items in this
- * list <b>must</b> also appear in {@code loose}.
- */
- @SuppressWarnings("unchecked")
- public RefMap(String prefix, RefList<? extends Ref> packed,
- RefList<? extends Ref> loose, RefList<? extends Ref> resolved) {
- this.prefix = prefix;
- this.packed = (RefList<Ref>) packed;
- this.loose = (RefList<Ref>) loose;
- this.resolved = (RefList<Ref>) resolved;
- }
-
- @Override
- public boolean containsKey(Object name) {
- return get(name) != null;
- }
-
- @Override
- public Ref get(Object key) {
- String name = toRefName((String) key);
- Ref ref = resolved.get(name);
- if (ref == null)
- ref = loose.get(name);
- if (ref == null)
- ref = packed.get(name);
- return ref;
- }
-
- @Override
- public Ref put(final String keyName, Ref value) {
- String name = toRefName(keyName);
-
- if (!name.equals(value.getName()))
- throw new IllegalArgumentException();
-
- if (!resolved.isEmpty()) {
- // Collapse the resolved list into the loose list so we
- // can discard it and stop joining the two together.
- for (Ref ref : resolved)
- loose = loose.put(ref);
- resolved = RefList.emptyList();
- }
-
- int idx = loose.find(name);
- if (0 <= idx) {
- Ref prior = loose.get(name);
- loose = loose.set(idx, value);
- return prior;
- } else {
- Ref prior = get(keyName);
- loose = loose.add(idx, value);
- sizeIsValid = false;
- return prior;
- }
- }
-
- @Override
- public Ref remove(Object key) {
- String name = toRefName((String) key);
- Ref res = null;
- int idx;
- if (0 <= (idx = packed.find(name))) {
- res = packed.get(name);
- packed = packed.remove(idx);
- sizeIsValid = false;
- }
- if (0 <= (idx = loose.find(name))) {
- res = loose.get(name);
- loose = loose.remove(idx);
- sizeIsValid = false;
- }
- if (0 <= (idx = resolved.find(name))) {
- res = resolved.get(name);
- resolved = resolved.remove(idx);
- sizeIsValid = false;
- }
- return res;
- }
-
- @Override
- public boolean isEmpty() {
- return entrySet().isEmpty();
- }
-
- @Override
- public Set<Entry<String, Ref>> entrySet() {
- if (entrySet == null) {
- entrySet = new AbstractSet<Entry<String, Ref>>() {
- @Override
- public Iterator<Entry<String, Ref>> iterator() {
- return new SetIterator();
- }
-
- @Override
- public int size() {
- if (!sizeIsValid) {
- size = 0;
- Iterator<?> i = entrySet().iterator();
- for (; i.hasNext(); i.next())
- size++;
- sizeIsValid = true;
- }
- return size;
- }
-
- @Override
- public boolean isEmpty() {
- if (sizeIsValid)
- return 0 == size;
- return !iterator().hasNext();
- }
-
- @Override
- public void clear() {
- packed = RefList.emptyList();
- loose = RefList.emptyList();
- resolved = RefList.emptyList();
- size = 0;
- sizeIsValid = true;
- }
- };
- }
- return entrySet;
- }
-
- @Override
- public String toString() {
- StringBuilder r = new StringBuilder();
- boolean first = true;
- r.append('[');
- for (Ref ref : values()) {
- if (first)
- first = false;
- else
- r.append(", "); //$NON-NLS-1$
- r.append(ref);
- }
- r.append(']');
- return r.toString();
- }
-
- private String toRefName(String name) {
- if (0 < prefix.length())
- name = prefix + name;
- return name;
- }
-
- private String toMapKey(Ref ref) {
- String name = ref.getName();
- if (0 < prefix.length())
- name = name.substring(prefix.length());
- return name;
- }
-
- private class SetIterator implements Iterator<Entry<String, Ref>> {
- private int packedIdx;
-
- private int looseIdx;
-
- private int resolvedIdx;
-
- private Entry<String, Ref> next;
-
- SetIterator() {
- if (0 < prefix.length()) {
- packedIdx = -(packed.find(prefix) + 1);
- looseIdx = -(loose.find(prefix) + 1);
- resolvedIdx = -(resolved.find(prefix) + 1);
- }
- }
-
- public boolean hasNext() {
- if (next == null)
- next = peek();
- return next != null;
- }
-
- public Entry<String, Ref> next() {
- if (hasNext()) {
- Entry<String, Ref> r = next;
- next = peek();
- return r;
- }
- throw new NoSuchElementException();
- }
-
- public Entry<String, Ref> peek() {
- if (packedIdx < packed.size() && looseIdx < loose.size()) {
- Ref p = packed.get(packedIdx);
- Ref l = loose.get(looseIdx);
- int cmp = RefComparator.compareTo(p, l);
- if (cmp < 0) {
- packedIdx++;
- return toEntry(p);
- }
-
- if (cmp == 0)
- packedIdx++;
- looseIdx++;
- return toEntry(resolveLoose(l));
- }
-
- if (looseIdx < loose.size())
- return toEntry(resolveLoose(loose.get(looseIdx++)));
- if (packedIdx < packed.size())
- return toEntry(packed.get(packedIdx++));
- return null;
- }
-
- private Ref resolveLoose(final Ref l) {
- if (resolvedIdx < resolved.size()) {
- Ref r = resolved.get(resolvedIdx);
- int cmp = RefComparator.compareTo(l, r);
- if (cmp == 0) {
- resolvedIdx++;
- return r;
- } else if (cmp > 0) {
- // WTF, we have a symbolic entry but no match
- // in the loose collection. That's an error.
- throw new IllegalStateException();
- }
- }
- return l;
- }
-
- private Ent toEntry(Ref p) {
- if (p.getName().startsWith(prefix))
- return new Ent(p);
- packedIdx = packed.size();
- looseIdx = loose.size();
- resolvedIdx = resolved.size();
- return null;
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
- }
-
- private class Ent implements Entry<String, Ref> {
- private Ref ref;
-
- Ent(Ref ref) {
- this.ref = ref;
- }
-
- public String getKey() {
- return toMapKey(ref);
- }
-
- public Ref getValue() {
- return ref;
- }
-
- public Ref setValue(Ref value) {
- Ref prior = put(getKey(), value);
- ref = value;
- return prior;
- }
-
- @Override
- public int hashCode() {
- return getKey().hashCode();
- }
-
- @Override
- public boolean equals(Object obj) {
- if (obj instanceof Map.Entry) {
- final Object key = ((Map.Entry) obj).getKey();
- final Object val = ((Map.Entry) obj).getValue();
- if (key instanceof String && val instanceof Ref) {
- final Ref r = (Ref) val;
- if (r.getName().equals(ref.getName())) {
- final ObjectId a = r.getObjectId();
- final ObjectId b = ref.getObjectId();
- if (a != null && b != null && AnyObjectId.equals(a, b))
- return true;
- }
- }
- }
- return false;
- }
-
- @Override
- public String toString() {
- return ref.toString();
- }
- }
- }
|