amd/compiler/aco_util.h

/*
 * Copyright Michael Schellenberger Costa
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 */

#ifndef ACO_UTIL_H
#define ACO_UTIL_H

#include <cassert>
#include <iterator>
#include <vector>

namespace aco {

/*! \brief      Definition of a span object
*
*   \details    A "span" is an "array view" type for holding a view of contiguous
*               data. The "span" object does not own the data itself.
*/
template <typename T>
class span {
public:
   using value_type             = T;
   using pointer                = value_type*;
   using const_pointer          = const value_type*;
   using reference              = value_type&;
   using const_reference        = const value_type&;
   using iterator               = pointer;
   using const_iterator         = const_pointer;
   using reverse_iterator       = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
   using size_type              = uint16_t;
   using difference_type        = ptrdiff_t;

   /*! \brief                  Compiler generated default constructor
   */
   constexpr span() = default;

   /*! \brief                 Constructor taking a pointer and the length of the span
   *   \param[in]   data      Pointer to the underlying data array
   *   \param[in]   length    The size of the span
   */
   constexpr span(uint16_t offset, const size_type length)
       : offset{ offset } , length{ length } {}

   /*! \brief                 Returns an iterator to the begin of the span
   *   \return                data
   */
   constexpr iterator begin() noexcept {
      return (pointer)((uintptr_t)this + offset);
   }

   /*! \brief                 Returns a const_iterator to the begin of the span
   *   \return                data
   */
   constexpr const_iterator begin() const noexcept {
      return (const_pointer)((uintptr_t)this + offset);
   }

   /*! \brief                 Returns an iterator to the end of the span
   *   \return                data + length
   */
   constexpr iterator end() noexcept {
      return std::next(begin(), length);
   }

   /*! \brief                 Returns a const_iterator to the end of the span
   *   \return                data + length
   */
   constexpr const_iterator end() const noexcept {
      return std::next(begin(), length);
   }

   /*! \brief                 Returns a const_iterator to the begin of the span
   *   \return                data
   */
   constexpr const_iterator cbegin() const noexcept {
      return begin();
   }

   /*! \brief                 Returns a const_iterator to the end of the span
   *   \return                data + length
   */
   constexpr const_iterator cend() const noexcept {
      return std::next(begin(), length);
   }

   /*! \brief                 Returns a reverse_iterator to the end of the span
   *   \return                reverse_iterator(end())
   */
   constexpr reverse_iterator rbegin() noexcept {
      return reverse_iterator(end());
   }

   /*! \brief                 Returns a const_reverse_iterator to the end of the span
   *   \return                reverse_iterator(end())
   */
   constexpr const_reverse_iterator rbegin() const noexcept {
      return const_reverse_iterator(end());
   }

   /*! \brief                 Returns a reverse_iterator to the begin of the span
   *   \return                reverse_iterator(begin())
   */
   constexpr reverse_iterator rend() noexcept {
      return reverse_iterator(begin());
   }

   /*! \brief                 Returns a const_reverse_iterator to the begin of the span
   *   \return                reverse_iterator(begin())
   */
   constexpr const_reverse_iterator rend() const noexcept {
      return const_reverse_iterator(begin());
   }

   /*! \brief                 Returns a const_reverse_iterator to the end of the span
   *   \return                rbegin()
   */
   constexpr const_reverse_iterator crbegin() const noexcept {
      return const_reverse_iterator(cend());
   }

   /*! \brief                 Returns a const_reverse_iterator to the begin of the span
   *   \return                rend()
   */
   constexpr const_reverse_iterator crend() const noexcept {
      return const_reverse_iterator(cbegin());
   }

   /*! \brief                 Unchecked access operator
   *   \param[in] index       Index of the element we want to access
   *   \return                *(std::next(data, index))
   */
   constexpr reference operator[](const size_type index) noexcept {
      assert(length > index);
      return *(std::next(begin(), index));
   }

   /*! \brief                 Unchecked const access operator
   *   \param[in] index       Index of the element we want to access
   *   \return                *(std::next(data, index))
   */
   constexpr const_reference operator[](const size_type index) const noexcept {
      assert(length > index);
      return *(std::next(begin(), index));
   }

   /*! \brief                 Returns a reference to the last element of the span
   *   \return                *(std::next(data, length - 1))
   */
   constexpr reference back() noexcept {
      assert(length > 0);
      return *(std::next(begin(), length - 1));
   }

   /*! \brief                 Returns a const_reference to the last element of the span
   *   \return                *(std::next(data, length - 1))
   */
   constexpr const_reference back() const noexcept {
      assert(length > 0);
      return *(std::next(begin(), length - 1));
   }

   /*! \brief                 Returns a reference to the first element of the span
   *   \return                *begin()
   */
   constexpr reference front() noexcept {
      assert(length > 0);
      return *begin();
   }

   /*! \brief                 Returns a const_reference to the first element of the span
   *   \return                *cbegin()
   */
   constexpr const_reference front() const noexcept {
      assert(length > 0);
      return *cbegin();
   }

   /*! \brief                 Returns true if the span is empty
   *   \return                length == 0
   */
   constexpr bool empty() const noexcept {
      return length == 0;
   }

   /*! \brief                 Returns the size of the span
   *   \return                length == 0
   */
   constexpr size_type size() const noexcept {
      return length;
   }

   /*! \brief                 Decreases the size of the span by 1
   */
   constexpr void pop_back() noexcept {
      assert(length > 0);
      --length;
   }

   /*! \brief                 Adds an element to the end of the span
   */
   constexpr void push_back(const_reference val) noexcept {
      *std::next(begin(), length++) = val;
   }

   /*! \brief                 Clears the span
   */
   constexpr void clear() noexcept {
      offset = 0;
      length = 0;
   }

private:
   uint16_t offset{ 0 };      //!> Byte offset from span to data
   size_type length{ 0 };     //!> Size of the span
};

/*
 * Cache-friendly set of 32-bit IDs with O(1) insert/erase/lookup and
 * the ability to efficiently iterate over contained elements.
 *
 * Internally implemented as a bit vector: If the set contains an ID, the
 * corresponding bit is set. It doesn't use std::vector<bool> since we then
 * couldn't efficiently iterate over the elements.
 *
 * The interface resembles a subset of std::set/std::unordered_set.
 */
struct IDSet {
   struct Iterator {
      const IDSet *set;
      union {
         struct {
            uint32_t bit:6;
            uint32_t word:26;
         };
         uint32_t id;
      };

      Iterator& operator ++();

      bool operator != (const Iterator& other) const;

      uint32_t operator * () const;
   };

   size_t count(uint32_t id) const {
      if (id >= words.size() * 64)
         return 0;

      return words[id / 64u] & (1ull << (id % 64u)) ? 1 : 0;
   }

   Iterator find(uint32_t id) const {
      if (!count(id))
         return end();

      Iterator it;
      it.set = this;
      it.bit = id % 64u;
      it.word = id / 64u;
      return it;
   }

   std::pair<Iterator, bool> insert(uint32_t id) {
      if (words.size() * 64u <= id)
         words.resize(DIV_ROUND_UP(id + 1, 64u));

      Iterator it;
      it.set = this;
      it.bit = id % 64u;
      it.word = id / 64u;

      uint64_t mask = 1ull << it.bit;
      if (words[it.word] & mask)
         return std::make_pair(it, false);

      words[it.word] |= mask;
      bits_set++;
      return std::make_pair(it, true);
   }

   size_t erase(uint32_t id) {
      if (!count(id))
         return 0;

      words[id / 64u] ^= 1ull << (id % 64u);
      bits_set--;
      return 1;
   }

   Iterator cbegin() const {
      Iterator it;
      it.set = this;
      for (size_t i = 0; i < words.size(); i++) {
         if (words[i]) {
            it.word = i;
            it.bit = ffsll(words[i]) - 1;
            return it;
         }
      }
      return end();
   }

   Iterator cend() const {
      Iterator it;
      it.set = this;
      it.word = words.size();
      it.bit = 0;
      return it;
   }

   Iterator begin() const {
      return cbegin();
   }

   Iterator end() const {
      return cend();
   }

   bool empty() const {
      return bits_set == 0;
   }

   size_t size() const {
      return bits_set;
   }

   std::vector<uint64_t> words;
   uint32_t bits_set;
};

inline IDSet::Iterator& IDSet::Iterator::operator ++() {
   uint64_t m = set->words[word];
   m &= ~((2ull << bit) - 1ull);
   if (!m) {
      /* don't continue past the end */
      if (word == set->words.size())
         return *this;

      word++;
      for (; word < set->words.size(); word++) {
         if (set->words[word]) {
            bit = ffsll(set->words[word]) - 1;
            return *this;
         }
      }
      bit = 0;
   } else {
      bit = ffsll(m) - 1;
   }
   return *this;
}

inline bool IDSet::Iterator::operator != (const IDSet::Iterator& other) const {
   assert(set == other.set);
   return id != other.id;
}

inline uint32_t IDSet::Iterator::operator * () const {
   return (word << 6) | bit;
}

} // namespace aco

#endif // ACO_UTIL_H