org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java - sop/jgit - Git at Google

 /*
  * 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.notes;

 import static org.eclipse.jgit.lib.Constants.OBJECT_ID_STRING_LENGTH;
 import static org.eclipse.jgit.lib.FileMode.REGULAR_FILE;

 import java.io.IOException;
 import java.util.Iterator;
 import java.util.NoSuchElementException;

 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.ObjectInserter.Formatter;
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.lib.TreeFormatter;

 /**
  * A note tree holding only notes, with no subtrees.
  *
  * The leaf bucket contains on average less than 256 notes, all of whom share
  * the same leading prefix. If a notes branch has less than 256 notes, the top
  * level tree of the branch should be a LeafBucket. Once a notes branch has more
  * than 256 notes, the root should be a {@link FanoutBucket} and the LeafBucket
  * will appear only as a cell of a FanoutBucket.
  *
  * Entries within the LeafBucket are stored sorted by ObjectId, and lookup is
  * performed using binary search. As the entry list should contain fewer than
  * 256 elements, the average number of compares to find an element should be
  * less than 8 due to the O(log N) lookup behavior.
  *
  * A LeafBucket must be parsed from a tree object by {@link NoteParser}.
  */
 class LeafBucket extends InMemoryNoteBucket {
 	static final int MAX_SIZE = 256;

 	/** All note blobs in this bucket, sorted sequentially. */
 	private Note[] notes;

 	/** Number of items in {@link #notes}. */
 	private int cnt;

 	LeafBucket(int prefixLen) {
 		super(prefixLen);
 		notes = new Note[4];
 	}

 	private int search(AnyObjectId objId) {
 		int low = 0;
 		int high = cnt;
 		while (low < high) {
 			int mid = (low + high) >>> 1;
 			int cmp = objId.compareTo(notes[mid]);
 			if (cmp < 0)
 				high = mid;
 			else if (cmp == 0)
 				return mid;
 			else
 				low = mid + 1;
 		}
 		return -(low + 1);
 	}

 	@Override
 	Note getNote(AnyObjectId objId, ObjectReader or) {
 		int idx = search(objId);
 		return 0 <= idx ? notes[idx] : null;
 	}

 	Note get(int index) {
 		return notes[index];
 	}

 	int size() {
 		return cnt;
 	}

 	@Override
 	Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader) {
 		return new Iterator<Note>() {
 			private int idx;

 			@Override
 			public boolean hasNext() {
 				return idx < cnt;
 			}

 			@Override
 			public Note next() {
 				if (hasNext())
 					return notes[idx++];
 				else
 					throw new NoSuchElementException();
 			}

 			@Override
 			public void remove() {
 				throw new UnsupportedOperationException();
 			}
 		};
 	}

 	@Override
 	int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
 		return cnt;
 	}

 	@Override
 	InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
 			ObjectReader or) throws IOException {
 		int p = search(noteOn);
 		if (0 <= p) {
 			if (noteData != null) {
 				notes[p].setData(noteData.copy());
 				return this;

 			} else {
 				System.arraycopy(notes, p + 1, notes, p, cnt - p - 1);
 				cnt--;
 				return 0 < cnt ? this : null;
 			}

 		} else if (noteData != null) {
 			if (shouldSplit()) {
 				return split().set(noteOn, noteData, or);

 			} else {
 				growIfFull();
 				p = -(p + 1);
 				if (p < cnt)
 					System.arraycopy(notes, p, notes, p + 1, cnt - p);
 				notes[p] = new Note(noteOn, noteData.copy());
 				cnt++;
 				return this;
 			}

 		} else {
 			return this;
 		}
 	}

 	@Override
 	ObjectId writeTree(ObjectInserter inserter) throws IOException {
 		return inserter.insert(build());
 	}

 	@Override
 	ObjectId getTreeId() {
 		try (Formatter f = new ObjectInserter.Formatter()) {
 			return f.idFor(build());
 		}
 	}

 	private TreeFormatter build() {
 		byte[] nameBuf = new byte[OBJECT_ID_STRING_LENGTH];
 		int nameLen = OBJECT_ID_STRING_LENGTH - prefixLen;
 		TreeFormatter fmt = new TreeFormatter(treeSize(nameLen));
 		NonNoteEntry e = nonNotes;

 		for (int i = 0; i < cnt; i++) {
 			Note n = notes[i];

 			n.copyTo(nameBuf, 0);

 			while (e != null
 					&& e.pathCompare(nameBuf, prefixLen, nameLen, REGULAR_FILE) < 0) {
 				e.format(fmt);
 				e = e.next;
 			}

 			fmt.append(nameBuf, prefixLen, nameLen, REGULAR_FILE, n.getData());
 		}

 		for (; e != null; e = e.next)
 			e.format(fmt);
 		return fmt;
 	}

 	private int treeSize(final int nameLen) {
 		int sz = cnt * TreeFormatter.entrySize(REGULAR_FILE, nameLen);
 		for (NonNoteEntry e = nonNotes; e != null; e = e.next)
 			sz += e.treeEntrySize();
 		return sz;
 	}

 	void parseOneEntry(AnyObjectId noteOn, AnyObjectId noteData) {
 		growIfFull();
 		notes[cnt++] = new Note(noteOn, noteData.copy());
 	}

 	@Override
 	InMemoryNoteBucket append(Note note) {
 		if (shouldSplit()) {
 			return split().append(note);

 		} else {
 			growIfFull();
 			notes[cnt++] = note;
 			return this;
 		}
 	}

 	private void growIfFull() {
 		if (notes.length == cnt) {
 			Note[] n = new Note[notes.length * 2];
 			System.arraycopy(notes, 0, n, 0, cnt);
 			notes = n;
 		}
 	}

 	private boolean shouldSplit() {
 		return MAX_SIZE <= cnt && prefixLen + 2 < OBJECT_ID_STRING_LENGTH;
 	}

 	FanoutBucket split() {
 		FanoutBucket n = new FanoutBucket(prefixLen);
 		for (int i = 0; i < cnt; i++)
 			n.append(notes[i]);
 		n.nonNotes = nonNotes;
 		return n;
 	}
 }
	/*
	* 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.notes;

	import static org.eclipse.jgit.lib.Constants.OBJECT_ID_STRING_LENGTH;
	import static org.eclipse.jgit.lib.FileMode.REGULAR_FILE;

	import java.io.IOException;
	import java.util.Iterator;
	import java.util.NoSuchElementException;

	import org.eclipse.jgit.lib.AnyObjectId;
	import org.eclipse.jgit.lib.ObjectId;
	import org.eclipse.jgit.lib.ObjectInserter;
	import org.eclipse.jgit.lib.ObjectInserter.Formatter;
	import org.eclipse.jgit.lib.ObjectReader;
	import org.eclipse.jgit.lib.TreeFormatter;

	/**
	* A note tree holding only notes, with no subtrees.
	*
	* The leaf bucket contains on average less than 256 notes, all of whom share
	* the same leading prefix. If a notes branch has less than 256 notes, the top
	* level tree of the branch should be a LeafBucket. Once a notes branch has more
	* than 256 notes, the root should be a {@link FanoutBucket} and the LeafBucket
	* will appear only as a cell of a FanoutBucket.
	*
	* Entries within the LeafBucket are stored sorted by ObjectId, and lookup is
	* performed using binary search. As the entry list should contain fewer than
	* 256 elements, the average number of compares to find an element should be
	* less than 8 due to the O(log N) lookup behavior.
	*
	* A LeafBucket must be parsed from a tree object by {@link NoteParser}.
	*/
	class LeafBucket extends InMemoryNoteBucket {
	static final int MAX_SIZE = 256;

	/** All note blobs in this bucket, sorted sequentially. */
	private Note[] notes;

	/** Number of items in {@link #notes}. */
	private int cnt;

	LeafBucket(int prefixLen) {
	super(prefixLen);
	notes = new Note[4];
	}

	private int search(AnyObjectId objId) {
	int low = 0;
	int high = cnt;
	while (low < high) {
	int mid = (low + high) >>> 1;
	int cmp = objId.compareTo(notes[mid]);
	if (cmp < 0)
	high = mid;
	else if (cmp == 0)
	return mid;
	else
	low = mid + 1;
	}
	return -(low + 1);
	}

	@Override
	Note getNote(AnyObjectId objId, ObjectReader or) {
	int idx = search(objId);
	return 0 <= idx ? notes[idx] : null;
	}

	Note get(int index) {
	return notes[index];
	}

	int size() {
	return cnt;
	}

	@Override
	Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader) {
	return new Iterator<Note>() {
	private int idx;

	@Override
	public boolean hasNext() {
	return idx < cnt;
	}

	@Override
	public Note next() {
	if (hasNext())
	return notes[idx++];
	else
	throw new NoSuchElementException();
	}

	@Override
	public void remove() {
	throw new UnsupportedOperationException();
	}
	};
	}

	@Override
	int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
	return cnt;
	}

	@Override
	InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
	ObjectReader or) throws IOException {
	int p = search(noteOn);
	if (0 <= p) {
	if (noteData != null) {
	notes[p].setData(noteData.copy());
	return this;

	} else {
	System.arraycopy(notes, p + 1, notes, p, cnt - p - 1);
	cnt--;
	return 0 < cnt ? this : null;
	}

	} else if (noteData != null) {
	if (shouldSplit()) {
	return split().set(noteOn, noteData, or);

	} else {
	growIfFull();
	p = -(p + 1);
	if (p < cnt)
	System.arraycopy(notes, p, notes, p + 1, cnt - p);
	notes[p] = new Note(noteOn, noteData.copy());
	cnt++;
	return this;
	}

	} else {
	return this;
	}
	}

	@Override
	ObjectId writeTree(ObjectInserter inserter) throws IOException {
	return inserter.insert(build());
	}

	@Override
	ObjectId getTreeId() {
	try (Formatter f = new ObjectInserter.Formatter()) {
	return f.idFor(build());
	}
	}

	private TreeFormatter build() {
	byte[] nameBuf = new byte[OBJECT_ID_STRING_LENGTH];
	int nameLen = OBJECT_ID_STRING_LENGTH - prefixLen;
	TreeFormatter fmt = new TreeFormatter(treeSize(nameLen));
	NonNoteEntry e = nonNotes;

	for (int i = 0; i < cnt; i++) {
	Note n = notes[i];

	n.copyTo(nameBuf, 0);

	while (e != null
	&& e.pathCompare(nameBuf, prefixLen, nameLen, REGULAR_FILE) < 0) {
	e.format(fmt);
	e = e.next;
	}

	fmt.append(nameBuf, prefixLen, nameLen, REGULAR_FILE, n.getData());
	}

	for (; e != null; e = e.next)
	e.format(fmt);
	return fmt;
	}

	private int treeSize(final int nameLen) {
	int sz = cnt * TreeFormatter.entrySize(REGULAR_FILE, nameLen);
	for (NonNoteEntry e = nonNotes; e != null; e = e.next)
	sz += e.treeEntrySize();
	return sz;
	}

	void parseOneEntry(AnyObjectId noteOn, AnyObjectId noteData) {
	growIfFull();
	notes[cnt++] = new Note(noteOn, noteData.copy());
	}

	@Override
	InMemoryNoteBucket append(Note note) {
	if (shouldSplit()) {
	return split().append(note);

	} else {
	growIfFull();
	notes[cnt++] = note;
	return this;
	}
	}

	private void growIfFull() {
	if (notes.length == cnt) {
	Note[] n = new Note[notes.length * 2];
	System.arraycopy(notes, 0, n, 0, cnt);
	notes = n;
	}
	}

	private boolean shouldSplit() {
	return MAX_SIZE <= cnt && prefixLen + 2 < OBJECT_ID_STRING_LENGTH;
	}

	FanoutBucket split() {
	FanoutBucket n = new FanoutBucket(prefixLen);
	for (int i = 0; i < cnt; i++)
	n.append(notes[i]);
	n.nonNotes = nonNotes;
	return n;
	}
	}