gcc/rust/util/rust-buffered-queue.h

   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