1 // Copyright (C) 2020-2023 Free Software Foundation, Inc.
2
3 // This file is part of GCC.
4
5 // GCC is free software; you can redistribute it and/or modify it under
6 // the terms of the GNU General Public License as published by the Free
7 // Software Foundation; either version 3, or (at your option) any later
8 // version.
9
10 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 // for more details.
14
15 // You should have received a copy of the GNU General Public License
16 // along with GCC; see the file COPYING3. If not see
17 // <http://www.gnu.org/licenses/>.
18
19 #ifndef RUST_BUFFERED_QUEUE_H
20 #define RUST_BUFFERED_QUEUE_H
21
22 #include "rust-system.h"
23
24 namespace Rust {
25 /* Buffered queue implementation. Items are of type T, queue source is of type
26 * Source. Note that this is owning of the source. */
27 template <typename T, typename Source> class buffered_queue
28 {
29 public:
30 // Construct empty queue from Source src.
31 buffered_queue (Source src) : source (src), start (0), end (0), buffer () {}
32
33 /* disable copying (since source is probably non-copyable)
34 * TODO is this actually a good idea? If source is non-copyable, it would
35 * just delete the copy constructor anyway.*/
36 buffered_queue (const buffered_queue &other) = delete;
37 buffered_queue &operator= (const buffered_queue &other) = delete;
38
39 // enable moving
40 buffered_queue (buffered_queue &&other) = default;
41 buffered_queue &operator= (buffered_queue &&other) = default;
42
43 // Returns token at position start + n (i.e. n tokens ahead).
44 T peek (int n)
45 {
46 // n should not be behind
47 rust_assert (n >= 0);
48
49 int num_queued_items = end - start;
50 int num_items_required = n + 1;
51
52 // if required items go past end of queue, add them to queue
53 if (num_items_required > num_queued_items)
54 {
55 int num_items_to_read = num_items_required - num_queued_items;
56
57 /* if queue length + extra items is larger than buffer size, expand
58 * buffer */
59 if (end + num_items_to_read > (int) buffer.size ())
60 {
61 // Resize the buffer by 1.5x
62 int new_size = (buffer.size () + num_items_to_read);
63 new_size += (new_size >> 1);
64
65 // old method:
66 /*
67 // create new queue buffer with new size
68 std::vector<T> new_queue (new_size);
69 std::copy (buffer.begin () + start, buffer.begin () + end,
70 new_queue.begin ());
71 start = 0;
72 end = num_queued_items;
73 // TODO: would move be better here? optimisation for move with
74 // shared pointer?
75
76 // swap member buffer and new queue buffer
77 std::swap (buffer, new_queue);
78 */
79
80 // TODO: determine overhead of this approach vs copy. Should be
81 // lower.
82 std::vector<T> new_queue;
83 new_queue.reserve (new_size);
84 new_queue.insert (new_queue.begin (),
85 std::make_move_iterator (buffer.begin () + start),
86 std::make_move_iterator (buffer.begin () + end));
87 start = 0;
88 end = num_queued_items;
89 // fill up rest of vector with junk so that indexing can work
90 new_queue.insert (new_queue.begin () + end,
91 new_size - new_queue.size (), T ());
92
93 buffer = std::move (new_queue);
94 /* this should be best method - std::move(range) would have
95 * allocation problems; initial construction would require
96 * reallocation upon resizing */
97
98 // validate that buffer is large enough now
99 rust_assert (end + num_items_to_read <= (int) buffer.size ());
100 }
101
102 /* iterate through buffer and invoke operator () on source on values
103 * past original end */
104 for (int i = 0; i < num_items_to_read; i++)
105 buffer[end + i] = source.next ();
106
107 // move end based on additional items added
108 end += num_items_to_read;
109 }
110
111 rust_assert (0 <= start);
112 rust_assert (start <= end);
113 rust_assert (end <= (int) buffer.size ());
114
115 rust_assert (start + n < end);
116
117 // return value at start + n in buffer
118 return buffer[start + n];
119 }
120
121 /* TODO: add faster peek current token to remove overhead of conditional
122 * branches? */
123
124 // Advances start by n + 1.
125 void skip (int n)
126 {
127 // Call peek to ensure requested n is actually in queue.
128 peek (n);
129
130 // Clear queue values from start to n (inclusive).
131 for (int i = 0; i < (n + 1); i++)
132 buffer[start + i] = T ();
133
134 // Move start forward by n + 1.
135 start += (n + 1);
136
137 // Ensure start is not impossible somehow
138 rust_assert (0 <= start);
139 rust_assert (start <= end);
140
141 // Compact buffer if empty
142 if (start == end)
143 start = end = 0;
144 }
145
146 /* Inserts element at front of vector. Really dirty hack with terrible
147 * performance, only use when really needed. */
148 void insert_at_front (T elem_to_insert)
149 {
150 // TODO: test as this may not work properly
151
152 // Insert actual element in buffer at start.
153 buffer.insert (buffer.begin (), elem_to_insert);
154
155 /* Increase the end number since added element means all others have shifted
156 * one along */
157 end++;
158 }
159
160 // Insert at arbitrary position (attempt)
161 void insert (int index, T elem_to_insert)
162 {
163 // TODO: test as this may not work properly
164
165 // n should not be behind
166 rust_assert (index >= 0);
167
168 // call peek to ensure that the items behind this (at least) are in queue
169 if (index >= 1)
170 peek (index - 1);
171 else
172 peek (index);
173
174 buffer.insert (buffer.begin () + start + index, std::move (elem_to_insert));
175
176 end++;
177 }
178
179 // Replaces the current value in the buffer. Total HACK.
180 void replace_current_value (T replacement)
181 {
182 // call peek to ensure value exists
183 peek (0);
184
185 buffer[start] = std::move (replacement);
186
187 // don't move start or end
188 }
189
190 private:
191 // Source of tokens for queue.
192 Source source;
193
194 // Begin of range in buffer, inclusive.
195 int start;
196 // End of range in buffer, exclusive.
197 int end;
198
199 // Queue buffer.
200 std::vector<T> buffer;
201 };
202 } // namespace Rust
203
204 #endif