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