Branch data Line data Source code
1 : : // Copyright (C) 2020-2024 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 : 3834 : template <typename T, typename Source> class buffered_queue
28 : : {
29 : : public:
30 : : // Construct empty queue from Source src.
31 : 3746 : 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 : 5729649 : T peek (int n)
45 : : {
46 : : // n should not be behind
47 : 5729649 : rust_assert (n >= 0);
48 : :
49 : 5729649 : int num_queued_items = end - start;
50 : 5729649 : int num_items_required = n + 1;
51 : :
52 : : // if required items go past end of queue, add them to queue
53 : 5729649 : if (num_items_required > num_queued_items)
54 : : {
55 : 2006514 : 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 : 2006514 : if (end + num_items_to_read > (int) buffer.size ())
60 : : {
61 : : // Resize the buffer by 1.5x
62 : 18186 : int new_size = (buffer.size () + num_items_to_read);
63 : 18186 : 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 : 18186 : std::vector<T> new_queue;
83 : 18186 : new_queue.reserve (new_size);
84 : 18186 : new_queue.insert (new_queue.begin (),
85 : 18186 : std::make_move_iterator (buffer.begin () + start),
86 : 18186 : std::make_move_iterator (buffer.begin () + end));
87 : 18186 : start = 0;
88 : 18186 : end = num_queued_items;
89 : : // fill up rest of vector with junk so that indexing can work
90 : 18186 : new_queue.insert (new_queue.begin () + end,
91 : 18186 : new_size - new_queue.size (), T ());
92 : :
93 : 18186 : 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 : 18186 : rust_assert (end + num_items_to_read <= (int) buffer.size ());
100 : 18186 : }
101 : :
102 : : /* iterate through buffer and invoke operator () on source on values
103 : : * past original end */
104 : 4036055 : for (int i = 0; i < num_items_to_read; i++)
105 : 2029541 : buffer[end + i] = source.get ().next ();
106 : :
107 : : // move end based on additional items added
108 : 2006514 : end += num_items_to_read;
109 : : }
110 : :
111 : 5729649 : rust_assert (0 <= start);
112 : 5729649 : rust_assert (start <= end);
113 : 5729649 : rust_assert (end <= (int) buffer.size ());
114 : :
115 : 5729649 : rust_assert (start + n < end);
116 : :
117 : : // return value at start + n in buffer
118 : 5729649 : 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 : 2022196 : void skip (int n)
126 : : {
127 : : // Call peek to ensure requested n is actually in queue.
128 : 2022196 : peek (n);
129 : :
130 : : // Clear queue values from start to n (inclusive).
131 : 4047691 : for (int i = 0; i < (n + 1); i++)
132 : 2025495 : buffer[start + i] = T ();
133 : :
134 : : // Move start forward by n + 1.
135 : 2022196 : start += (n + 1);
136 : :
137 : : // Ensure start is not impossible somehow
138 : 2022196 : rust_assert (0 <= start);
139 : 2022196 : rust_assert (start <= end);
140 : :
141 : : // Compact buffer if empty
142 : 2022196 : if (start == end)
143 : 1934830 : start = end = 0;
144 : 2022196 : }
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 : 92 : 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 : 92 : rust_assert (index >= 0);
167 : :
168 : : // call peek to ensure that the items behind this (at least) are in queue
169 : 92 : if (index >= 1)
170 : 184 : peek (index - 1);
171 : : else
172 : 0 : peek (index);
173 : :
174 : 92 : buffer.insert (buffer.begin () + start + index, std::move (elem_to_insert));
175 : :
176 : 92 : end++;
177 : 92 : }
178 : :
179 : : // Replaces the current value in the buffer. Total HACK.
180 : 91 : void replace_current_value (T replacement)
181 : : {
182 : : // call peek to ensure value exists
183 : 91 : peek (0);
184 : :
185 : 91 : buffer[start] = std::move (replacement);
186 : :
187 : : // don't move start or end
188 : 91 : }
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
|
