123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257 |
- /*
- * 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.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;
-
- public boolean hasNext() {
- return idx < cnt;
- }
-
- public Note next() {
- if (hasNext())
- return notes[idx++];
- else
- throw new NoSuchElementException();
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
- };
- }
-
- @Override
- int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
- return cnt;
- }
-
- 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() {
- return new ObjectInserter.Formatter().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;
- }
- }
|