View Javadoc
1   /*
2    * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> and others
3    *
4    * This program and the accompanying materials are made available under the
5    * terms of the Eclipse Distribution License v. 1.0 which is available at
6    * https://www.eclipse.org/org/documents/edl-v10.php.
7    *
8    * SPDX-License-Identifier: BSD-3-Clause
9    */
10  
11  package org.eclipse.jgit.revwalk;
12  
13  class BlockObjQueue {
14  	private BlockFreeList free;
15  
16  	private Block head;
17  
18  	private Block tail;
19  
20  	/** Create an empty queue. */
21  	BlockObjQueue() {
22  		free = new BlockFreeList();
23  	}
24  
25  	void add(RevObject c) {
26  		Block b = tail;
27  		if (b == null) {
28  			b = free.newBlock();
29  			b.add(c);
30  			head = b;
31  			tail = b;
32  			return;
33  		} else if (b.isFull()) {
34  			b = free.newBlock();
35  			tail.next = b;
36  			tail = b;
37  		}
38  		b.add(c);
39  	}
40  
41  	RevObject next() {
42  		final Block b = head;
43  		if (b == null)
44  			return null;
45  
46  		final RevObject c = b.pop();
47  		if (b.isEmpty()) {
48  			head = b.next;
49  			if (head == null)
50  				tail = null;
51  			free.freeBlock(b);
52  		}
53  		return c;
54  	}
55  
56  	static final class BlockFreeList {
57  		private Block next;
58  
59  		Block newBlock() {
60  			Block b = next;
61  			if (b == null)
62  				return new Block();
63  			next = b.next;
64  			b.clear();
65  			return b;
66  		}
67  
68  		void freeBlock(Block b) {
69  			b.next = next;
70  			next = b;
71  		}
72  	}
73  
74  	static final class Block {
75  		private static final int BLOCK_SIZE = 256;
76  
77  		/** Next block in our chain of blocks; null if we are the last. */
78  		Block next;
79  
80  		/** Our table of queued objects. */
81  		final RevObject[] objects = new RevObject[BLOCK_SIZE];
82  
83  		/** Next valid entry in {@link #objects}. */
84  		int headIndex;
85  
86  		/** Next free entry in {@link #objects} for addition at. */
87  		int tailIndex;
88  
89  		boolean isFull() {
90  			return tailIndex == BLOCK_SIZE;
91  		}
92  
93  		boolean isEmpty() {
94  			return headIndex == tailIndex;
95  		}
96  
97  		void add(RevObject c) {
98  			objects[tailIndex++] = c;
99  		}
100 
101 		RevObject pop() {
102 			return objects[headIndex++];
103 		}
104 
105 		void clear() {
106 			next = null;
107 			headIndex = 0;
108 			tailIndex = 0;
109 		}
110 	}
111 }