org.eclipse.jgit/src/org/eclipse/jgit/lib/Tree.java - jgit/jgit - Git at Google

 /*
  * Copyright (C) 2007, Robin Rosenberg <me@lathund.dewire.com>
  * Copyright (C) 2007-2008, Robin Rosenberg <robin.rosenberg@dewire.com>
  * Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org>
  * 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.io.IOException;
 import java.text.MessageFormat;

 import org.eclipse.jgit.errors.CorruptObjectException;
 import org.eclipse.jgit.errors.EntryExistsException;
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.errors.ObjectWritingException;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.util.RawParseUtils;

 /**
  * A representation of a Git tree entry. A Tree is a directory in Git.
  *
  * @deprecated To look up information about a single path, use
  * {@link org.eclipse.jgit.treewalk.TreeWalk#forPath(Repository, String, org.eclipse.jgit.revwalk.RevTree)}.
  * To lookup information about multiple paths at once, use a
  * {@link org.eclipse.jgit.treewalk.TreeWalk} and obtain the current entry's
  * information from its getter methods.
  */
 @Deprecated
 public class Tree extends TreeEntry {
 	private static final TreeEntry[] EMPTY_TREE = {};

 	/**
 	 * Compare two names represented as bytes. Since git treats names of trees and
 	 * blobs differently we have one parameter that represents a '/' for trees. For
 	 * other objects the value should be NUL. The names are compare by their positive
 	 * byte value (0..255).
 	 *
 	 * A blob and a tree with the same name will not compare equal.
 	 *
 	 * @param a name
 	 * @param b name
 	 * @param lasta '/' if a is a tree, else NUL
 	 * @param lastb '/' if b is a tree, else NUL
 	 *
 	 * @return &lt; 0 if a is sorted before b, 0 if they are the same, else b
 	 */
 	public static final int compareNames(final byte[] a, final byte[] b, final int lasta,final int lastb) {
 		return compareNames(a, b, 0, b.length, lasta, lastb);
 	}

 	private static final int compareNames(final byte[] a, final byte[] nameUTF8,
 			final int nameStart, final int nameEnd, final int lasta, int lastb) {
 		int j,k;
 		for (j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++) {
 			final int aj = a[j] & 0xff;
 			final int bk = nameUTF8[k] & 0xff;
 			if (aj < bk)
 				return -1;
 			else if (aj > bk)
 				return 1;
 		}
 		if (j < a.length) {
 			int aj = a[j]&0xff;
 			if (aj < lastb)
 				return -1;
 			else if (aj > lastb)
 				return 1;
 			else
 				if (j == a.length - 1)
 					return 0;
 				else
 					return -1;
 		}
 		if (k < nameEnd) {
 			int bk = nameUTF8[k] & 0xff;
 			if (lasta < bk)
 				return -1;
 			else if (lasta > bk)
 				return 1;
 			else
 				if (k == nameEnd - 1)
 					return 0;
 				else
 					return 1;
 		}
 		if (lasta < lastb)
 			return -1;
 		else if (lasta > lastb)
 			return 1;

 		final int namelength = nameEnd - nameStart;
 		if (a.length == namelength)
 			return 0;
 		else if (a.length < namelength)
 			return -1;
 		else
 			return 1;
 	}

 	private static final byte[] substring(final byte[] s, final int nameStart,
 			final int nameEnd) {
 		if (nameStart == 0 && nameStart == s.length)
 			return s;
 		final byte[] n = new byte[nameEnd - nameStart];
 		System.arraycopy(s, nameStart, n, 0, n.length);
 		return n;
 	}

 	private static final int binarySearch(final TreeEntry[] entries,
 			final byte[] nameUTF8, final int nameUTF8last, final int nameStart, final int nameEnd) {
 		if (entries.length == 0)
 			return -1;
 		int high = entries.length;
 		int low = 0;
 		do {
 			final int mid = (low + high) >>> 1;
 			final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,
 					nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);
 			if (cmp < 0)
 				low = mid + 1;
 			else if (cmp == 0)
 				return mid;
 			else
 				high = mid;
 		} while (low < high);
 		return -(low + 1);
 	}

 	private final Repository db;

 	private TreeEntry[] contents;

 	/**
 	 * Constructor for a new Tree
 	 *
 	 * @param repo The repository that owns the Tree.
 	 */
 	public Tree(final Repository repo) {
 		super(null, null, null);
 		db = repo;
 		contents = EMPTY_TREE;
 	}

 	/**
 	 * Construct a Tree object with known content and hash value
 	 *
 	 * @param repo
 	 * @param myId
 	 * @param raw
 	 * @throws IOException
 	 */
 	public Tree(final Repository repo, final ObjectId myId, final byte[] raw)
 			throws IOException {
 		super(null, myId, null);
 		db = repo;
 		readTree(raw);
 	}

 	/**
 	 * Construct a new Tree under another Tree
 	 *
 	 * @param parent
 	 * @param nameUTF8
 	 */
 	public Tree(final Tree parent, final byte[] nameUTF8) {
 		super(parent, null, nameUTF8);
 		db = parent.getRepository();
 		contents = EMPTY_TREE;
 	}

 	/**
 	 * Construct a Tree with a known SHA-1 under another tree. Data is not yet
 	 * specified and will have to be loaded on demand.
 	 *
 	 * @param parent
 	 * @param id
 	 * @param nameUTF8
 	 */
 	public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8) {
 		super(parent, id, nameUTF8);
 		db = parent.getRepository();
 	}

 	public FileMode getMode() {
 		return FileMode.TREE;
 	}

 	/**
 	 * @return true if this Tree is the top level Tree.
 	 */
 	public boolean isRoot() {
 		return getParent() == null;
 	}

 	public Repository getRepository() {
 		return db;
 	}

 	/**
 	 * @return true of the data of this Tree is loaded
 	 */
 	public boolean isLoaded() {
 		return contents != null;
 	}

 	/**
 	 * Forget the in-memory data for this tree.
 	 */
 	public void unload() {
 		if (isModified())
 			throw new IllegalStateException(JGitText.get().cannotUnloadAModifiedTree);
 		contents = null;
 	}

 	/**
 	 * Adds a new or existing file with the specified name to this tree.
 	 * Trees are added if necessary as the name may contain '/':s.
 	 *
 	 * @param name Name
 	 * @return a {@link FileTreeEntry} for the added file.
 	 * @throws IOException
 	 */
 	public FileTreeEntry addFile(final String name) throws IOException {
 		return addFile(Repository.gitInternalSlash(Constants.encode(name)), 0);
 	}

 	/**
 	 * Adds a new or existing file with the specified name to this tree.
 	 * Trees are added if necessary as the name may contain '/':s.
 	 *
 	 * @param s an array containing the name
 	 * @param offset when the name starts in the tree.
 	 *
 	 * @return a {@link FileTreeEntry} for the added file.
 	 * @throws IOException
 	 */
 	public FileTreeEntry addFile(final byte[] s, final int offset)
 			throws IOException {
 		int slash;
 		int p;

 		for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 			// search for path component terminator
 		}

 		ensureLoaded();
 		byte xlast = slash<s.length ? (byte)'/' : 0;
 		p = binarySearch(contents, s, xlast, offset, slash);
 		if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 			return ((Tree) contents[p]).addFile(s, slash + 1);

 		final byte[] newName = substring(s, offset, slash);
 		if (p >= 0)
 			throw new EntryExistsException(RawParseUtils.decode(newName));
 		else if (slash < s.length) {
 			final Tree t = new Tree(this, newName);
 			insertEntry(p, t);
 			return t.addFile(s, slash + 1);
 		} else {
 			final FileTreeEntry f = new FileTreeEntry(this, null, newName,
 					false);
 			insertEntry(p, f);
 			return f;
 		}
 	}

 	/**
 	 * Adds a new or existing Tree with the specified name to this tree.
 	 * Trees are added if necessary as the name may contain '/':s.
 	 *
 	 * @param name Name
 	 * @return a {@link FileTreeEntry} for the added tree.
 	 * @throws IOException
 	 */
 	public Tree addTree(final String name) throws IOException {
 		return addTree(Repository.gitInternalSlash(Constants.encode(name)), 0);
 	}

 	/**
 	 * Adds a new or existing Tree with the specified name to this tree.
 	 * Trees are added if necessary as the name may contain '/':s.
 	 *
 	 * @param s an array containing the name
 	 * @param offset when the name starts in the tree.
 	 *
 	 * @return a {@link FileTreeEntry} for the added tree.
 	 * @throws IOException
 	 */
 	public Tree addTree(final byte[] s, final int offset) throws IOException {
 		int slash;
 		int p;

 		for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 			// search for path component terminator
 		}

 		ensureLoaded();
 		p = binarySearch(contents, s, (byte)'/', offset, slash);
 		if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 			return ((Tree) contents[p]).addTree(s, slash + 1);

 		final byte[] newName = substring(s, offset, slash);
 		if (p >= 0)
 			throw new EntryExistsException(RawParseUtils.decode(newName));

 		final Tree t = new Tree(this, newName);
 		insertEntry(p, t);
 		return slash == s.length ? t : t.addTree(s, slash + 1);
 	}

 	/**
 	 * Add the specified tree entry to this tree.
 	 *
 	 * @param e
 	 * @throws IOException
 	 */
 	public void addEntry(final TreeEntry e) throws IOException {
 		final int p;

 		ensureLoaded();
 		p = binarySearch(contents, e.getNameUTF8(), TreeEntry.lastChar(e), 0, e.getNameUTF8().length);
 		if (p < 0) {
 			e.attachParent(this);
 			insertEntry(p, e);
 		} else {
 			throw new EntryExistsException(e.getName());
 		}
 	}

 	private void insertEntry(int p, final TreeEntry e) {
 		final TreeEntry[] c = contents;
 		final TreeEntry[] n = new TreeEntry[c.length + 1];
 		p = -(p + 1);
 		for (int k = c.length - 1; k >= p; k--)
 			n[k + 1] = c[k];
 		n[p] = e;
 		for (int k = p - 1; k >= 0; k--)
 			n[k] = c[k];
 		contents = n;
 		setModified();
 	}

 	void removeEntry(final TreeEntry e) {
 		final TreeEntry[] c = contents;
 		final int p = binarySearch(c, e.getNameUTF8(), TreeEntry.lastChar(e), 0,
 				e.getNameUTF8().length);
 		if (p >= 0) {
 			final TreeEntry[] n = new TreeEntry[c.length - 1];
 			for (int k = c.length - 1; k > p; k--)
 				n[k - 1] = c[k];
 			for (int k = p - 1; k >= 0; k--)
 				n[k] = c[k];
 			contents = n;
 			setModified();
 		}
 	}

 	/**
 	 * @return number of members in this tree
 	 * @throws IOException
 	 */
 	public int memberCount() throws IOException {
 		ensureLoaded();
 		return contents.length;
 	}

 	/**
 	 * Return all members of the tree sorted in Git order.
 	 *
 	 * Entries are sorted by the numerical unsigned byte
 	 * values with (sub)trees having an implicit '/'. An
 	 * example of a tree with three entries. a:b is an
 	 * actual file name here.
 	 *
 	 * <p>
 	 * 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a.b
 	 * 040000 tree 4277b6e69d25e5efa77c455340557b384a4c018a    a
 	 * 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a:b
 	 *
 	 * @return all entries in this Tree, sorted.
 	 * @throws IOException
 	 */
 	public TreeEntry[] members() throws IOException {
 		ensureLoaded();
 		final TreeEntry[] c = contents;
 		if (c.length != 0) {
 			final TreeEntry[] r = new TreeEntry[c.length];
 			for (int k = c.length - 1; k >= 0; k--)
 				r[k] = c[k];
 			return r;
 		} else
 			return c;
 	}

 	private boolean exists(final String s, byte slast) throws IOException {
 		return findMember(s, slast) != null;
 	}

 	/**
 	 * @param path to the tree.
 	 * @return true if a tree with the specified path can be found under this
 	 *         tree.
 	 * @throws IOException
 	 */
 	public boolean existsTree(String path) throws IOException {
 		return exists(path,(byte)'/');
 	}

 	/**
 	 * @param path of the non-tree entry.
 	 * @return true if a blob, symlink, or gitlink with the specified name
 	 *         can be found under this tree.
 	 * @throws IOException
 	 */
 	public boolean existsBlob(String path) throws IOException {
 		return exists(path,(byte)0);
 	}

 	private TreeEntry findMember(final String s, byte slast) throws IOException {
 		return findMember(Repository.gitInternalSlash(Constants.encode(s)), slast, 0);
 	}

 	private TreeEntry findMember(final byte[] s, final byte slast, final int offset)
 			throws IOException {
 		int slash;
 		int p;

 		for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 			// search for path component terminator
 		}

 		ensureLoaded();
 		byte xlast = slash<s.length ? (byte)'/' : slast;
 		p = binarySearch(contents, s, xlast, offset, slash);
 		if (p >= 0) {
 			final TreeEntry r = contents[p];
 			if (slash < s.length-1)
 				return r instanceof Tree ? ((Tree) r).findMember(s, slast, slash + 1)
 						: null;
 			return r;
 		}
 		return null;
 	}

 	/**
 	 * @param s
 	 *            blob name
 	 * @return a {@link TreeEntry} representing an object with the specified
 	 *         relative path.
 	 * @throws IOException
 	 */
 	public TreeEntry findBlobMember(String s) throws IOException {
 		return findMember(s,(byte)0);
 	}

 	/**
 	 * @param s Tree Name
 	 * @return a Tree with the name s or null
 	 * @throws IOException
 	 */
 	public TreeEntry findTreeMember(String s) throws IOException {
 		return findMember(s,(byte)'/');
 	}

 	private void ensureLoaded() throws IOException, MissingObjectException {
 		if (!isLoaded()) {
 			ObjectLoader ldr = db.open(getId(), Constants.OBJ_TREE);
 			readTree(ldr.getCachedBytes());
 		}
 	}

 	private void readTree(final byte[] raw) throws IOException {
 		final int rawSize = raw.length;
 		int rawPtr = 0;
 		TreeEntry[] temp;
 		int nextIndex = 0;

 		while (rawPtr < rawSize) {
 			while (rawPtr < rawSize && raw[rawPtr] != 0)
 				rawPtr++;
 			rawPtr++;
 			rawPtr += Constants.OBJECT_ID_LENGTH;
 			nextIndex++;
 		}

 		temp = new TreeEntry[nextIndex];
 		rawPtr = 0;
 		nextIndex = 0;
 		while (rawPtr < rawSize) {
 			int c = raw[rawPtr++];
 			if (c < '0' || c > '7')
 				throw new CorruptObjectException(getId(), JGitText.get().corruptObjectInvalidEntryMode);
 			int mode = c - '0';
 			for (;;) {
 				c = raw[rawPtr++];
 				if (' ' == c)
 					break;
 				else if (c < '0' || c > '7')
 					throw new CorruptObjectException(getId(), JGitText.get().corruptObjectInvalidMode);
 				mode <<= 3;
 				mode += c - '0';
 			}

 			int nameLen = 0;
 			while (raw[rawPtr + nameLen] != 0)
 				nameLen++;
 			final byte[] name = new byte[nameLen];
 			System.arraycopy(raw, rawPtr, name, 0, nameLen);
 			rawPtr += nameLen + 1;

 			final ObjectId id = ObjectId.fromRaw(raw, rawPtr);
 			rawPtr += Constants.OBJECT_ID_LENGTH;

 			final TreeEntry ent;
 			if (FileMode.REGULAR_FILE.equals(mode))
 				ent = new FileTreeEntry(this, id, name, false);
 			else if (FileMode.EXECUTABLE_FILE.equals(mode))
 				ent = new FileTreeEntry(this, id, name, true);
 			else if (FileMode.TREE.equals(mode))
 				ent = new Tree(this, id, name);
 			else if (FileMode.SYMLINK.equals(mode))
 				ent = new SymlinkTreeEntry(this, id, name);
 			else if (FileMode.GITLINK.equals(mode))
 				ent = new GitlinkTreeEntry(this, id, name);
 			else
 				throw new CorruptObjectException(getId(), MessageFormat.format(
 						JGitText.get().corruptObjectInvalidMode2, Integer.toOctalString(mode)));
 			temp[nextIndex++] = ent;
 		}

 		contents = temp;
 	}

 	/**
 	 * Format this Tree in canonical format.
 	 *
 	 * @return canonical encoding of the tree object.
 	 * @throws IOException
 	 *             the tree cannot be loaded, or its not in a writable state.
 	 */
 	public byte[] format() throws IOException {
 		TreeFormatter fmt = new TreeFormatter();
 		for (TreeEntry e : members()) {
 			ObjectId id = e.getId();
 			if (id == null)
 				throw new ObjectWritingException(MessageFormat.format(JGitText
 						.get().objectAtPathDoesNotHaveId, e.getFullName()));

 			fmt.append(e.getNameUTF8(), e.getMode(), id);
 		}
 		return fmt.toByteArray();
 	}

 	public String toString() {
 		final StringBuilder r = new StringBuilder();
 		r.append(ObjectId.toString(getId()));
 		r.append(" T "); //$NON-NLS-1$
 		r.append(getFullName());
 		return r.toString();
 	}

 }
	/*
	* Copyright (C) 2007, Robin Rosenberg <me@lathund.dewire.com>
	* Copyright (C) 2007-2008, Robin Rosenberg <robin.rosenberg@dewire.com>
	* Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org>
	* 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.io.IOException;
	import java.text.MessageFormat;

	import org.eclipse.jgit.errors.CorruptObjectException;
	import org.eclipse.jgit.errors.EntryExistsException;
	import org.eclipse.jgit.errors.MissingObjectException;
	import org.eclipse.jgit.errors.ObjectWritingException;
	import org.eclipse.jgit.internal.JGitText;
	import org.eclipse.jgit.util.RawParseUtils;

	/**
	* A representation of a Git tree entry. A Tree is a directory in Git.
	*
	* @deprecated To look up information about a single path, use
	* {@link org.eclipse.jgit.treewalk.TreeWalk#forPath(Repository, String, org.eclipse.jgit.revwalk.RevTree)}.
	* To lookup information about multiple paths at once, use a
	* {@link org.eclipse.jgit.treewalk.TreeWalk} and obtain the current entry's
	* information from its getter methods.
	*/
	@Deprecated
	public class Tree extends TreeEntry {
	private static final TreeEntry[] EMPTY_TREE = {};

	/**
	* Compare two names represented as bytes. Since git treats names of trees and
	* blobs differently we have one parameter that represents a '/' for trees. For
	* other objects the value should be NUL. The names are compare by their positive
	* byte value (0..255).
	*
	* A blob and a tree with the same name will not compare equal.
	*
	* @param a name
	* @param b name
	* @param lasta '/' if a is a tree, else NUL
	* @param lastb '/' if b is a tree, else NUL
	*
	* @return < 0 if a is sorted before b, 0 if they are the same, else b
	*/
	public static final int compareNames(final byte[] a, final byte[] b, final int lasta,final int lastb) {
	return compareNames(a, b, 0, b.length, lasta, lastb);
	}

	private static final int compareNames(final byte[] a, final byte[] nameUTF8,
	final int nameStart, final int nameEnd, final int lasta, int lastb) {
	int j,k;
	for (j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++) {
	final int aj = a[j] & 0xff;
	final int bk = nameUTF8[k] & 0xff;
	if (aj < bk)
	return -1;
	else if (aj > bk)
	return 1;
	}
	if (j < a.length) {
	int aj = a[j]&0xff;
	if (aj < lastb)
	return -1;
	else if (aj > lastb)
	return 1;
	else
	if (j == a.length - 1)
	return 0;
	else
	return -1;
	}
	if (k < nameEnd) {
	int bk = nameUTF8[k] & 0xff;
	if (lasta < bk)
	return -1;
	else if (lasta > bk)
	return 1;
	else
	if (k == nameEnd - 1)
	return 0;
	else
	return 1;
	}
	if (lasta < lastb)
	return -1;
	else if (lasta > lastb)
	return 1;

	final int namelength = nameEnd - nameStart;
	if (a.length == namelength)
	return 0;
	else if (a.length < namelength)
	return -1;
	else
	return 1;
	}

	private static final byte[] substring(final byte[] s, final int nameStart,
	final int nameEnd) {
	if (nameStart == 0 && nameStart == s.length)
	return s;
	final byte[] n = new byte[nameEnd - nameStart];
	System.arraycopy(s, nameStart, n, 0, n.length);
	return n;
	}

	private static final int binarySearch(final TreeEntry[] entries,
	final byte[] nameUTF8, final int nameUTF8last, final int nameStart, final int nameEnd) {
	if (entries.length == 0)
	return -1;
	int high = entries.length;
	int low = 0;
	do {
	final int mid = (low + high) >>> 1;
	final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,
	nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);
	if (cmp < 0)
	low = mid + 1;
	else if (cmp == 0)
	return mid;
	else
	high = mid;
	} while (low < high);
	return -(low + 1);
	}

	private final Repository db;

	private TreeEntry[] contents;

	/**
	* Constructor for a new Tree
	*
	* @param repo The repository that owns the Tree.
	*/
	public Tree(final Repository repo) {
	super(null, null, null);
	db = repo;
	contents = EMPTY_TREE;
	}

	/**
	* Construct a Tree object with known content and hash value
	*
	* @param repo
	* @param myId
	* @param raw
	* @throws IOException
	*/
	public Tree(final Repository repo, final ObjectId myId, final byte[] raw)
	throws IOException {
	super(null, myId, null);
	db = repo;
	readTree(raw);
	}

	/**
	* Construct a new Tree under another Tree
	*
	* @param parent
	* @param nameUTF8
	*/
	public Tree(final Tree parent, final byte[] nameUTF8) {
	super(parent, null, nameUTF8);
	db = parent.getRepository();
	contents = EMPTY_TREE;
	}

	/**
	* Construct a Tree with a known SHA-1 under another tree. Data is not yet
	* specified and will have to be loaded on demand.
	*
	* @param parent
	* @param id
	* @param nameUTF8
	*/
	public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8) {
	super(parent, id, nameUTF8);
	db = parent.getRepository();
	}

	public FileMode getMode() {
	return FileMode.TREE;
	}

	/**
	* @return true if this Tree is the top level Tree.
	*/
	public boolean isRoot() {
	return getParent() == null;
	}

	public Repository getRepository() {
	return db;
	}

	/**
	* @return true of the data of this Tree is loaded
	*/
	public boolean isLoaded() {
	return contents != null;
	}

	/**
	* Forget the in-memory data for this tree.
	*/
	public void unload() {
	if (isModified())
	throw new IllegalStateException(JGitText.get().cannotUnloadAModifiedTree);
	contents = null;
	}

	/**
	* Adds a new or existing file with the specified name to this tree.
	* Trees are added if necessary as the name may contain '/':s.
	*
	* @param name Name
	* @return a {@link FileTreeEntry} for the added file.
	* @throws IOException
	*/
	public FileTreeEntry addFile(final String name) throws IOException {
	return addFile(Repository.gitInternalSlash(Constants.encode(name)), 0);
	}

	/**
	* Adds a new or existing file with the specified name to this tree.
	* Trees are added if necessary as the name may contain '/':s.
	*
	* @param s an array containing the name
	* @param offset when the name starts in the tree.
	*
	* @return a {@link FileTreeEntry} for the added file.
	* @throws IOException
	*/
	public FileTreeEntry addFile(final byte[] s, final int offset)
	throws IOException {
	int slash;
	int p;

	for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
	// search for path component terminator
	}

	ensureLoaded();
	byte xlast = slash<s.length ? (byte)'/' : 0;
	p = binarySearch(contents, s, xlast, offset, slash);
	if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
	return ((Tree) contents[p]).addFile(s, slash + 1);

	final byte[] newName = substring(s, offset, slash);
	if (p >= 0)
	throw new EntryExistsException(RawParseUtils.decode(newName));
	else if (slash < s.length) {
	final Tree t = new Tree(this, newName);
	insertEntry(p, t);
	return t.addFile(s, slash + 1);
	} else {
	final FileTreeEntry f = new FileTreeEntry(this, null, newName,
	false);
	insertEntry(p, f);
	return f;
	}
	}

	/**
	* Adds a new or existing Tree with the specified name to this tree.
	* Trees are added if necessary as the name may contain '/':s.
	*
	* @param name Name
	* @return a {@link FileTreeEntry} for the added tree.
	* @throws IOException
	*/
	public Tree addTree(final String name) throws IOException {
	return addTree(Repository.gitInternalSlash(Constants.encode(name)), 0);
	}

	/**
	* Adds a new or existing Tree with the specified name to this tree.
	* Trees are added if necessary as the name may contain '/':s.
	*
	* @param s an array containing the name
	* @param offset when the name starts in the tree.
	*
	* @return a {@link FileTreeEntry} for the added tree.
	* @throws IOException
	*/
	public Tree addTree(final byte[] s, final int offset) throws IOException {
	int slash;
	int p;

	for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
	// search for path component terminator
	}

	ensureLoaded();
	p = binarySearch(contents, s, (byte)'/', offset, slash);
	if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
	return ((Tree) contents[p]).addTree(s, slash + 1);

	final byte[] newName = substring(s, offset, slash);
	if (p >= 0)
	throw new EntryExistsException(RawParseUtils.decode(newName));

	final Tree t = new Tree(this, newName);
	insertEntry(p, t);
	return slash == s.length ? t : t.addTree(s, slash + 1);
	}

	/**
	* Add the specified tree entry to this tree.
	*
	* @param e
	* @throws IOException
	*/
	public void addEntry(final TreeEntry e) throws IOException {
	final int p;

	ensureLoaded();
	p = binarySearch(contents, e.getNameUTF8(), TreeEntry.lastChar(e), 0, e.getNameUTF8().length);
	if (p < 0) {
	e.attachParent(this);
	insertEntry(p, e);
	} else {
	throw new EntryExistsException(e.getName());
	}
	}

	private void insertEntry(int p, final TreeEntry e) {
	final TreeEntry[] c = contents;
	final TreeEntry[] n = new TreeEntry[c.length + 1];
	p = -(p + 1);
	for (int k = c.length - 1; k >= p; k--)
	n[k + 1] = c[k];
	n[p] = e;
	for (int k = p - 1; k >= 0; k--)
	n[k] = c[k];
	contents = n;
	setModified();
	}

	void removeEntry(final TreeEntry e) {
	final TreeEntry[] c = contents;
	final int p = binarySearch(c, e.getNameUTF8(), TreeEntry.lastChar(e), 0,
	e.getNameUTF8().length);
	if (p >= 0) {
	final TreeEntry[] n = new TreeEntry[c.length - 1];
	for (int k = c.length - 1; k > p; k--)
	n[k - 1] = c[k];
	for (int k = p - 1; k >= 0; k--)
	n[k] = c[k];
	contents = n;
	setModified();
	}
	}

	/**
	* @return number of members in this tree
	* @throws IOException
	*/
	public int memberCount() throws IOException {
	ensureLoaded();
	return contents.length;
	}

	/**
	* Return all members of the tree sorted in Git order.
	*
	* Entries are sorted by the numerical unsigned byte
	* values with (sub)trees having an implicit '/'. An
	* example of a tree with three entries. a:b is an
	* actual file name here.
	*
	* <p>
	* 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 a.b
	* 040000 tree 4277b6e69d25e5efa77c455340557b384a4c018a a
	* 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 a:b
	*
	* @return all entries in this Tree, sorted.
	* @throws IOException
	*/
	public TreeEntry[] members() throws IOException {
	ensureLoaded();
	final TreeEntry[] c = contents;
	if (c.length != 0) {
	final TreeEntry[] r = new TreeEntry[c.length];
	for (int k = c.length - 1; k >= 0; k--)
	r[k] = c[k];
	return r;
	} else
	return c;
	}

	private boolean exists(final String s, byte slast) throws IOException {
	return findMember(s, slast) != null;
	}

	/**
	* @param path to the tree.
	* @return true if a tree with the specified path can be found under this
	* tree.
	* @throws IOException
	*/
	public boolean existsTree(String path) throws IOException {
	return exists(path,(byte)'/');
	}

	/**
	* @param path of the non-tree entry.
	* @return true if a blob, symlink, or gitlink with the specified name
	* can be found under this tree.
	* @throws IOException
	*/
	public boolean existsBlob(String path) throws IOException {
	return exists(path,(byte)0);
	}

	private TreeEntry findMember(final String s, byte slast) throws IOException {
	return findMember(Repository.gitInternalSlash(Constants.encode(s)), slast, 0);
	}

	private TreeEntry findMember(final byte[] s, final byte slast, final int offset)
	throws IOException {
	int slash;
	int p;

	for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
	// search for path component terminator
	}

	ensureLoaded();
	byte xlast = slash<s.length ? (byte)'/' : slast;
	p = binarySearch(contents, s, xlast, offset, slash);
	if (p >= 0) {
	final TreeEntry r = contents[p];
	if (slash < s.length-1)
	return r instanceof Tree ? ((Tree) r).findMember(s, slast, slash + 1)
	: null;
	return r;
	}
	return null;
	}

	/**
	* @param s
	* blob name
	* @return a {@link TreeEntry} representing an object with the specified
	* relative path.
	* @throws IOException
	*/
	public TreeEntry findBlobMember(String s) throws IOException {
	return findMember(s,(byte)0);
	}

	/**
	* @param s Tree Name
	* @return a Tree with the name s or null
	* @throws IOException
	*/
	public TreeEntry findTreeMember(String s) throws IOException {
	return findMember(s,(byte)'/');
	}

	private void ensureLoaded() throws IOException, MissingObjectException {
	if (!isLoaded()) {
	ObjectLoader ldr = db.open(getId(), Constants.OBJ_TREE);
	readTree(ldr.getCachedBytes());
	}
	}

	private void readTree(final byte[] raw) throws IOException {
	final int rawSize = raw.length;
	int rawPtr = 0;
	TreeEntry[] temp;
	int nextIndex = 0;

	while (rawPtr < rawSize) {
	while (rawPtr < rawSize && raw[rawPtr] != 0)
	rawPtr++;
	rawPtr++;
	rawPtr += Constants.OBJECT_ID_LENGTH;
	nextIndex++;
	}

	temp = new TreeEntry[nextIndex];
	rawPtr = 0;
	nextIndex = 0;
	while (rawPtr < rawSize) {
	int c = raw[rawPtr++];
	if (c < '0' \|\| c > '7')
	throw new CorruptObjectException(getId(), JGitText.get().corruptObjectInvalidEntryMode);
	int mode = c - '0';
	for (;;) {
	c = raw[rawPtr++];
	if (' ' == c)
	break;
	else if (c < '0' \|\| c > '7')
	throw new CorruptObjectException(getId(), JGitText.get().corruptObjectInvalidMode);
	mode <<= 3;
	mode += c - '0';
	}

	int nameLen = 0;
	while (raw[rawPtr + nameLen] != 0)
	nameLen++;
	final byte[] name = new byte[nameLen];
	System.arraycopy(raw, rawPtr, name, 0, nameLen);
	rawPtr += nameLen + 1;

	final ObjectId id = ObjectId.fromRaw(raw, rawPtr);
	rawPtr += Constants.OBJECT_ID_LENGTH;

	final TreeEntry ent;
	if (FileMode.REGULAR_FILE.equals(mode))
	ent = new FileTreeEntry(this, id, name, false);
	else if (FileMode.EXECUTABLE_FILE.equals(mode))
	ent = new FileTreeEntry(this, id, name, true);
	else if (FileMode.TREE.equals(mode))
	ent = new Tree(this, id, name);
	else if (FileMode.SYMLINK.equals(mode))
	ent = new SymlinkTreeEntry(this, id, name);
	else if (FileMode.GITLINK.equals(mode))
	ent = new GitlinkTreeEntry(this, id, name);
	else
	throw new CorruptObjectException(getId(), MessageFormat.format(
	JGitText.get().corruptObjectInvalidMode2, Integer.toOctalString(mode)));
	temp[nextIndex++] = ent;
	}

	contents = temp;
	}

	/**
	* Format this Tree in canonical format.
	*
	* @return canonical encoding of the tree object.
	* @throws IOException
	* the tree cannot be loaded, or its not in a writable state.
	*/
	public byte[] format() throws IOException {
	TreeFormatter fmt = new TreeFormatter();
	for (TreeEntry e : members()) {
	ObjectId id = e.getId();
	if (id == null)
	throw new ObjectWritingException(MessageFormat.format(JGitText
	.get().objectAtPathDoesNotHaveId, e.getFullName()));

	fmt.append(e.getNameUTF8(), e.getMode(), id);
	}
	return fmt.toByteArray();
	}

	public String toString() {
	final StringBuilder r = new StringBuilder();
	r.append(ObjectId.toString(getId()));
	r.append(" T "); //$NON-NLS-1$
	r.append(getFullName());
	return r.toString();
	}

	}