01: package antlr;
02:
03: /* ANTLR Translator Generator
04: * Project led by Terence Parr at http://www.cs.usfca.edu
05: * Software rights: http://www.antlr.org/license.html
06: */
07:
08: /** A private circular buffer object used by the token buffer */
09: class TokenQueue {
10: /** Physical circular buffer of tokens */
11: private Token[] buffer;
12: /** buffer.length-1 for quick modulos */
13: private int sizeLessOne;
14: /** physical index of front token */
15: private int offset;
16: /** number of tokens in the queue */
17: protected int nbrEntries;
18:
19: public TokenQueue(int minSize) {
20: // Find first power of 2 >= to requested size
21: int size;
22: if (minSize < 0) {
23: init(16); // pick some value for them
24: return;
25: }
26: // check for overflow
27: if (minSize >= (Integer.MAX_VALUE / 2)) {
28: init(Integer.MAX_VALUE); // wow that's big.
29: return;
30: }
31: for (size = 2; size < minSize; size *= 2) {
32: ;
33: }
34: init(size);
35: }
36:
37: /** Add token to end of the queue
38: * @param tok The token to add
39: */
40: public final void append(Token tok) {
41: if (nbrEntries == buffer.length) {
42: expand();
43: }
44: buffer[(offset + nbrEntries) & sizeLessOne] = tok;
45: nbrEntries++;
46: }
47:
48: /** Fetch a token from the queue by index
49: * @param idx The index of the token to fetch, where zero is the token at the front of the queue
50: */
51: public final Token elementAt(int idx) {
52: return buffer[(offset + idx) & sizeLessOne];
53: }
54:
55: /** Expand the token buffer by doubling its capacity */
56: private final void expand() {
57: Token[] newBuffer = new Token[buffer.length * 2];
58: // Copy the contents to the new buffer
59: // Note that this will store the first logical item in the
60: // first physical array element.
61: for (int i = 0; i < buffer.length; i++) {
62: newBuffer[i] = elementAt(i);
63: }
64: // Re-initialize with new contents, keep old nbrEntries
65: buffer = newBuffer;
66: sizeLessOne = buffer.length - 1;
67: offset = 0;
68: }
69:
70: /** Initialize the queue.
71: * @param size The initial size of the queue
72: */
73: private final void init(int size) {
74: // Allocate buffer
75: buffer = new Token[size];
76: // Other initialization
77: sizeLessOne = size - 1;
78: offset = 0;
79: nbrEntries = 0;
80: }
81:
82: /** Clear the queue. Leaving the previous buffer alone.
83: */
84: public final void reset() {
85: offset = 0;
86: nbrEntries = 0;
87: }
88:
89: /** Remove token from front of queue */
90: public final void removeFirst() {
91: offset = (offset + 1) & sizeLessOne;
92: nbrEntries--;
93: }
94: }
|