1 /*
2 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43
44 package org.eclipse.jgit.revwalk;
45
46 import java.io.IOException;
47
48 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
49 import org.eclipse.jgit.errors.MissingObjectException;
50
51 abstract class BlockRevQueue extends AbstractRevQueue {
52 protected BlockFreeList free;
53
54 /** Create an empty revision queue. */
55 protected BlockRevQueue() {
56 free = new BlockFreeList();
57 }
58
59 BlockRevQueue(final Generator s) throws MissingObjectException,
60 IncorrectObjectTypeException, IOException {
61 free = new BlockFreeList();
62 outputType = s.outputType();
63 s.shareFreeList(this);
64 for (;;) {
65 final RevCommit c = s.next();
66 if (c == null)
67 break;
68 add(c);
69 }
70 }
71
72 /**
73 * Reconfigure this queue to share the same free list as another.
74 * <p>
75 * Multiple revision queues can be connected to the same free list, making
76 * it less expensive for applications to shuttle commits between them. This
77 * method arranges for the receiver to take from / return to the same free
78 * list as the supplied queue.
79 * <p>
80 * Free lists are not thread-safe. Applications must ensure that all queues
81 * sharing the same free list are doing so from only a single thread.
82 *
83 * @param q
84 * the other queue we will steal entries from.
85 */
86 @Override
87 public void shareFreeList(final BlockRevQueue q) {
88 free = q.free;
89 }
90
91 static final class BlockFreeList {
92 private Block next;
93
94 Block newBlock() {
95 Block b = next;
96 if (b == null)
97 return new Block();
98 next = b.next;
99 b.clear();
100 return b;
101 }
102
103 void freeBlock(final Block b) {
104 b.next = next;
105 next = b;
106 }
107
108 void clear() {
109 next = null;
110 }
111 }
112
113 static final class Block {
114 static final int BLOCK_SIZE = 256;
115
116 /** Next block in our chain of blocks; null if we are the last. */
117 Block next;
118
119 /** Our table of queued commits. */
120 final RevCommit[] commits = new RevCommit[BLOCK_SIZE];
121
122 /** Next valid entry in {@link #commits}. */
123 int headIndex;
124
125 /** Next free entry in {@link #commits} for addition at. */
126 int tailIndex;
127
128 boolean isFull() {
129 return tailIndex == BLOCK_SIZE;
130 }
131
132 boolean isEmpty() {
133 return headIndex == tailIndex;
134 }
135
136 boolean canUnpop() {
137 return headIndex > 0;
138 }
139
140 void add(final RevCommit c) {
141 commits[tailIndex++] = c;
142 }
143
144 void unpop(final RevCommit c) {
145 commits[--headIndex] = c;
146 }
147
148 RevCommit pop() {
149 return commits[headIndex++];
150 }
151
152 RevCommit peek() {
153 return commits[headIndex];
154 }
155
156 void clear() {
157 next = null;
158 headIndex = 0;
159 tailIndex = 0;
160 }
161
162 void resetToMiddle() {
163 headIndex = tailIndex = BLOCK_SIZE / 2;
164 }
165
166 void resetToEnd() {
167 headIndex = tailIndex = BLOCK_SIZE;
168 }
169 }
170 }