src/util/enum.h

   1 /*
   2  * Copyright 2017 Jacob Lifshay
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in all
  12  * copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  *
  22  */
  23
  24 #ifndef UTIL_ENUM_H_
  25 #define UTIL_ENUM_H_
  26
  27 #include <type_traits>
  28 #include <utility>
  29 #include <iterator>
  30 #include "constexpr_array.h"
  31 #include "bitset.h"
  32
  33 namespace vulkan_cpu
  34 {
  35 namespace util
  36 {
  37 template <typename T>
  38 void enum_traits_resolve_function(T) = delete;
  39
  40 template <typename T>
  41 struct Enum_traits
  42 {
  43 private:
  44     typedef decltype(enum_traits_resolve_function(T())) base;
  45
  46 public:
  47     static constexpr std::size_t value_count = base::values.size();
  48     static constexpr Constexpr_array<T, value_count> values = base::values;
  49     typedef typename std::underlying_type<T>::type underlying_type;
  50
  51 private:
  52     static constexpr bool is_compact_helper() noexcept
  53     {
  54         for(std::size_t i = 0; i < value_count; i++)
  55             if(i
  56                != static_cast<std::size_t>(static_cast<underlying_type>(values[i]))
  57                       - static_cast<std::size_t>(static_cast<underlying_type>(values.front())))
  58                 return false;
  59         return true;
  60     }
  61
  62 public:
  63     static constexpr bool is_compact = is_compact_helper();
  64     struct Value_and_index
  65     {
  66         T value;
  67         std::size_t index;
  68         constexpr Value_and_index() noexcept : value(), index()
  69         {
  70         }
  71         constexpr Value_and_index(T value, std::size_t index) noexcept : value(value), index(index)
  72         {
  73         }
  74     };
  75
  76 private:
  77     template <std::size_t N>
  78     static constexpr Constexpr_array<Value_and_index, N> sort_value_index_map(
  79         const Value_and_index *value_index_map) noexcept
  80     {
  81         // uses merge sort algorithm
  82         if(N == 0)
  83             return {};
  84         Constexpr_array<Value_and_index, N> retval{};
  85         if(N == 1)
  86         {
  87             retval[0] = value_index_map[0];
  88             return retval;
  89         }
  90
  91         // split
  92         constexpr std::size_t split_index = N / 2;
  93         constexpr std::size_t part1_size = split_index;
  94         constexpr std::size_t part2_size = N - part1_size;
  95         auto part1 = sort_value_index_map<part1_size>(value_index_map);
  96         auto part2 = sort_value_index_map<part2_size>(value_index_map + split_index);
  97
  98         // merge, preserving order of equal values
  99         std::size_t part1_index = 0;
 100         std::size_t part2_index = 0;
 101         std::size_t retval_index = 0;
 102         while(part1_index < part1_size && part2_index < part2_size)
 103         {
 104             // we want to copy from part1 if values are equal
 105             if(static_cast<underlying_type>(part2[part2_index].value)
 106                < static_cast<underlying_type>(part1[part1_index].value))
 107                 retval[retval_index++] = part2[part2_index++];
 108             else
 109                 retval[retval_index++] = part1[part1_index++];
 110         }
 111         while(part1_index < part1_size)
 112             retval[retval_index++] = part1[part1_index++];
 113         while(part2_index < part2_size)
 114             retval[retval_index++] = part2[part2_index++];
 115         return retval;
 116     }
 117     static constexpr Constexpr_array<Value_and_index, value_count>
 118         make_sorted_value_index_map() noexcept
 119     {
 120         Constexpr_array<Value_and_index, value_count> retval{};
 121         for(std::size_t i = 0; i < value_count; i++)
 122             retval[i] = {values[i], i};
 123         retval = sort_value_index_map<value_count>(retval.data());
 124         return retval;
 125     }
 126
 127 public:
 128     static constexpr Constexpr_array<Value_and_index, value_count> sorted_value_index_map =
 129         make_sorted_value_index_map();
 130     static constexpr std::size_t npos = -1;
 131     /** find first occurrence of value in values and return index if found, otherwise return npos */
 132     static constexpr std::size_t find_value(T value) noexcept
 133     {
 134         std::size_t retval{};
 135         constexpr std::size_t binary_search_transition = 8;
 136         if(is_compact)
 137         {
 138             retval = static_cast<std::size_t>(static_cast<underlying_type>(value))
 139                      - static_cast<std::size_t>(static_cast<underlying_type>(values.front()));
 140         }
 141         else if(value_count < binary_search_transition)
 142         {
 143             retval = npos;
 144             for(std::size_t i = 0; i < value_count; i++)
 145             {
 146                 if(values[i] == value)
 147                 {
 148                     retval = i;
 149                     break;
 150                 }
 151             }
 152         }
 153         else
 154         {
 155             retval = 0;
 156             std::size_t count = value_count;
 157             while(count != 0)
 158             {
 159                 std::size_t step = count / 2;
 160                 if(static_cast<underlying_type>(values[retval + step])
 161                    < static_cast<underlying_type>(value))
 162                 {
 163                     retval += step + 1;
 164                     count -= step + 1;
 165                 }
 166                 else
 167                 {
 168                     count = step;
 169                 }
 170             }
 171         }
 172         if(retval >= value_count)
 173             return npos;
 174         return retval;
 175     }
 176 };
 177
 178 template <typename T>
 179 constexpr std::size_t Enum_traits<T>::value_count;
 180
 181 template <typename T>
 182 constexpr Constexpr_array<T, Enum_traits<T>::value_count> Enum_traits<T>::values;
 183
 184 template <typename T>
 185 constexpr bool Enum_traits<T>::is_compact;
 186
 187 template <typename T>
 188 constexpr Constexpr_array<typename Enum_traits<T>::Value_and_index, Enum_traits<T>::value_count>
 189     Enum_traits<T>::sorted_value_index_map;
 190
 191 template <typename T>
 192 constexpr std::size_t Enum_traits<T>::npos;
 193
 194 namespace detail
 195 {
 196 template <typename Enum, Enum... Values>
 197 struct Default_enum_traits
 198 {
 199     static constexpr Constexpr_array<Enum, sizeof...(Values)> values = {{Values...}};
 200 };
 201
 202 template <typename Enum, Enum... Values>
 203 constexpr Constexpr_array<Enum, sizeof...(Values)> Default_enum_traits<Enum, Values...>::values;
 204 /** generate code for Enum_traits instantiation; use like
 205  * <code>vulkan_cpu_util_generate_enum_traits(Enum, Enum::Value1, Enum::Value2, Enum::Value3,
 206  * <...>);</code> */
 207 #define vulkan_cpu_util_generate_enum_traits(Enum, ...)                \
 208     ::vulkan_cpu::util::detail::Default_enum_traits<Enum, __VA_ARGS__> \
 209         enum_traits_resolve_function(Enum)
 210 }
 211
 212 /** behaves like a std::set<T> */
 213 template <typename T>
 214 class Enum_set
 215 {
 216 private:
 217     typedef util::bitset<Enum_traits<T>::value_count> Bits;
 218
 219 public:
 220     typedef T key_type;
 221     typedef T value_type;
 222     typedef std::size_t size_type;
 223     typedef std::ptrdiff_t difference_type;
 224     typedef T &reference;
 225     typedef const T &const_reference;
 226     typedef T *pointer;
 227     typedef const T *const_pointer;
 228     class iterator
 229     {
 230         template <typename>
 231         friend class Enum_set;
 232
 233     public:
 234         typedef std::ptrdiff_t difference_type;
 235         typedef T value_type;
 236         typedef const T *pointer;
 237         typedef const T &reference;
 238         std::bidirectional_iterator_tag iterator_category;
 239
 240     private:
 241         const Enum_set *enum_set;
 242         std::size_t index;
 243
 244     public:
 245         constexpr iterator() noexcept : enum_set(nullptr), index(0)
 246         {
 247         }
 248
 249     private:
 250         constexpr iterator(const Enum_set *enum_set, std::size_t index) noexcept
 251             : enum_set(enum_set),
 252               index(index)
 253         {
 254         }
 255         static constexpr iterator first_at_or_after(const Enum_set *enum_set,
 256                                                     std::size_t index) noexcept
 257         {
 258             return iterator(enum_set, enum_set->bits.find_first(true, index));
 259         }
 260         static constexpr iterator first_at_or_before(const Enum_set *enum_set,
 261                                                      std::size_t index) noexcept
 262         {
 263             return iterator(enum_set, enum_set->bits.find_last(true, index));
 264         }
 265
 266     public:
 267         constexpr bool operator==(const iterator &rt) const noexcept
 268         {
 269             return index == rt.index && enum_set == rt.enum_set;
 270         }
 271         constexpr bool operator!=(const iterator &rt) const noexcept
 272         {
 273             return !operator==(rt);
 274         }
 275         constexpr iterator &operator++() noexcept
 276         {
 277             *this = first_at_or_after(enum_set, index + 1);
 278             return *this;
 279         }
 280         constexpr iterator &operator--() noexcept
 281         {
 282             *this = first_at_or_before(enum_set, index - 1);
 283             return *this;
 284         }
 285         constexpr iterator operator++(int) noexcept
 286         {
 287             auto retval = *this;
 288             operator++();
 289             return retval;
 290         }
 291         constexpr iterator operator--(int) noexcept
 292         {
 293             auto retval = *this;
 294             operator--();
 295             return retval;
 296         }
 297         constexpr const T &operator*() const noexcept
 298         {
 299             return Enum_traits<T>::values[index];
 300         }
 301         constexpr const T *operator->() const noexcept
 302         {
 303             return &operator*();
 304         }
 305     };
 306     typedef iterator const_iterator;
 307     typedef std::reverse_iterator<iterator> reverse_iterator;
 308     typedef reverse_iterator reverse_const_iterator;
 309
 310 private:
 311     Bits bits;
 312
 313 public:
 314     constexpr Enum_set() noexcept : bits(0)
 315     {
 316     }
 317     template <typename Iter>
 318     constexpr Enum_set(Iter first, Iter last)
 319         : Enum_set()
 320     {
 321         insert(std::move(first), std::move(last));
 322     }
 323     constexpr Enum_set(std::initializer_list<T> il) noexcept : Enum_set(il.begin(), il.end())
 324     {
 325     }
 326     constexpr Enum_set &operator=(std::initializer_list<T> il) noexcept
 327     {
 328         *this = Enum_set(il);
 329         return *this;
 330     }
 331     constexpr iterator begin() const noexcept
 332     {
 333         return iterator::first_at_or_after(this, 0);
 334     }
 335     constexpr iterator end() const noexcept
 336     {
 337         return iterator(this, Bits::npos);
 338     }
 339     constexpr iterator cbegin() const noexcept
 340     {
 341         return begin();
 342     }
 343     constexpr iterator cend() const noexcept
 344     {
 345         return end();
 346     }
 347     constexpr bool empty() const noexcept
 348     {
 349         return bits.none();
 350     }
 351     constexpr std::size_t size() const noexcept
 352     {
 353         return bits.count();
 354     }
 355     constexpr std::size_t max_size() const noexcept
 356     {
 357         return bits.size();
 358     }
 359     constexpr void clear() noexcept
 360     {
 361         bits = Bits();
 362     }
 363     constexpr std::pair<iterator, bool> insert(T value) noexcept
 364     {
 365         std::size_t index = Enum_traits<T>::find_value(value);
 366         bool inserted = !bits[index];
 367         bits[index] = true;
 368         return {iterator(this, index), inserted};
 369     }
 370     constexpr iterator insert(iterator hint, T value) noexcept
 371     {
 372         std::size_t index = Enum_traits<T>::find_value(value);
 373         bits[index] = true;
 374         return iterator(this, index);
 375     }
 376     template <typename Iter>
 377     constexpr void insert(Iter first, Iter last)
 378     {
 379         for(; first != last; ++first)
 380             insert(*first);
 381     }
 382     constexpr void insert(std::initializer_list<T> il) noexcept
 383     {
 384         insert(il.begin(), il.end());
 385     }
 386     template <typename... Args>
 387     std::pair<iterator, bool> emplace(Args &&... args)
 388     {
 389         return insert(T(std::forward<Args>(args)...));
 390     }
 391     template <typename... Args>
 392     iterator emplace_hint(iterator hint, Args &&... args)
 393     {
 394         return insert(hint, T(std::forward<Args>(args)...));
 395     }
 396     constexpr std::size_t erase(T value) noexcept
 397     {
 398         std::size_t index = Enum_traits<T>::find_value(value);
 399         std::size_t retval = 0;
 400         if(index < bits.size())
 401         {
 402             retval = bits[index] ? 1 : 0;
 403             bits[index] = false;
 404         }
 405         return retval;
 406     }
 407     constexpr iterator erase(iterator pos) noexcept
 408     {
 409         auto retval = pos;
 410         ++retval;
 411         bits[pos.index] = false;
 412         return retval;
 413     }
 414     constexpr iterator erase(iterator first, iterator last) noexcept
 415     {
 416         while(first != last)
 417             first = erase(first);
 418         return first;
 419     }
 420     /** invalidates all iterators, all references still valid because they are bound to static
 421      * objects */
 422     constexpr void swap(Enum_set &other) noexcept
 423     {
 424         using std::swap;
 425         swap(bits, other.bits);
 426     }
 427     constexpr std::size_t count(T value) const noexcept
 428     {
 429         std::size_t index = Enum_traits<T>::find_value(value);
 430         if(index < bits.size() && bits[index])
 431             return 1;
 432         return 0;
 433     }
 434     constexpr iterator find(T value) const noexcept
 435     {
 436         std::size_t index = Enum_traits<T>::find_value(value);
 437         if(index < bits.size() && bits[index])
 438             return iterator(this, index);
 439         return 0;
 440     }
 441     std::pair<iterator, iterator> equal_range(T value) const noexcept
 442     {
 443         std::size_t index = Enum_traits<T>::find_value(value);
 444         if(index < bits.size() && bits[index])
 445         {
 446             auto first = iterator(this, index);
 447             auto last = first;
 448             ++last;
 449             return {first, last};
 450         }
 451         return {end(), end()};
 452     }
 453 };
 454 }
 455 }
 456
 457 #endif /* UTIL_ENUM_H_ */