1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
#ifndef RUST_BUFFERED_QUEUE_H
#define RUST_BUFFERED_QUEUE_H
#include <vector>
#include "config.h"
#include "system.h"
// order: config, system
namespace Rust {
// Buffered queue implementation. Items are of type T, queue source is of type
// Source.
template <typename T, typename Source> class buffered_queue
{
public:
// Construct empty queue from Source& src.
buffered_queue (Source &src) : source (src), start (0), end (0), buffer () {}
// Returns token at position start + n (i.e. n tokens ahead).
T peek (int n)
{
// n should not be behind
gcc_assert (n >= 0);
int num_queued_items = end - start;
int num_items_required = n + 1;
// if required items go past end of queue, add them to queue
if (num_items_required > num_queued_items)
{
int num_items_to_read = num_items_required - num_queued_items;
// if queue length + extra items is larger than buffer size, expand
// buffer
if (end + num_items_to_read > (int) buffer.size ())
{
// Resize the buffer by 1.5x
int new_size = (buffer.size () + num_items_to_read);
new_size += (new_size >> 1);
// create new queue buffer with new size
std::vector<T> new_queue (new_size);
std::copy (buffer.begin () + start, buffer.begin () + end,
new_queue.begin ());
start = 0;
end = num_queued_items;
// swap member buffer and new queue buffer
std::swap (buffer, new_queue);
// validate that buffer is large enough now
gcc_assert (end + num_queued_items < (int) buffer.size ());
}
// iterate through buffer and invoke operator () on source on values
// past original end
for (int i = 0; i < num_items_to_read; i++)
{
buffer[end + i] = source ();
}
// move end based on additional items added
end += num_items_to_read;
}
gcc_assert (0 <= start);
gcc_assert (start <= end);
gcc_assert (end <= (int) buffer.size ());
gcc_assert (start + n < end);
// return value at start + n in buffer
return buffer[start + n];
}
// TODO: add faster peek current token to remove overhead of conditional
// branches?
// Advances start by n + 1.
void skip (int n)
{
// Call peek to ensure requested n is actually in queue.
peek (n);
// Clear values from start to n (inclusive).
for (int i = 0; i < (n + 1); i++)
{
// Clear value at index
buffer[start + i] = T ();
}
// Move start forward by n + 1.
start += (n + 1);
// Ensure start is not impossible somehow
gcc_assert (0 <= start);
gcc_assert (start <= end);
// Compact buffer if empty
if (start == end)
{
start = end = 0;
}
}
/* Inserts element at front of vector. Really dirty hack with terrible
* performance, only use when really needed. */
void insert_at_front (T elem_to_insert)
{
// TODO: test as this may not work properly
// Insert actual element in buffer at start.
buffer.insert (buffer.begin (), 1, elem_to_insert);
// Increase the end number since added element means all others have shifted
// one along
end++;
}
// Replaces the current value in the buffer. Total HACK.
void replace_current_value (T replacement)
{
// call peek to ensure value exists
peek (0);
buffer[start] = replacement;
// don't move start or end
}
private:
// Source of tokens for queue.
Source &source;
// Begin of range in buffer, inclusive.
int start;
// End of range in buffer, exclusive.
int end;
// Queue buffer.
std::vector<T> buffer;
};
} // namespace Rust
#endif
|
