Warning: This file is not a C or C++ file. It does not have highlighting.
| 1 | //===-- include/flang/Common/fast-int-set.h --------------------*- C++ -*-===// |
|---|---|
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | // Implements a Briggs-Torczon fast set of integers in a fixed small range |
| 10 | // [0..(n-1)] This is a data structure with no dynamic memory allocation and all |
| 11 | // O(1) elemental operations. It does not need to initialize its internal state |
| 12 | // arrays, but you can call its InitializeState() member function to avoid |
| 13 | // complaints from valgrind. |
| 14 | |
| 15 | // The set is implemented with two arrays and an element count. |
| 16 | // 1) The distinct values in the set occupy the leading elements of |
| 17 | // value_[0 .. size_-1] in arbitrary order. Their positions may change |
| 18 | // when other values are removed from the set with Remove(). |
| 19 | // 2) For 0 <= j < size_, index_[value_[j]] == j. |
| 20 | // 3) If only Add() and PopValue() are used, the popped values will be the |
| 21 | // most recently Add()ed distinct unpopped values; i.e., the value_ array |
| 22 | // will function as a stack whose top is at (size_-1). |
| 23 | |
| 24 | #ifndef FORTRAN_COMMON_FAST_INT_SET_H_ |
| 25 | #define FORTRAN_COMMON_FAST_INT_SET_H_ |
| 26 | |
| 27 | #include <optional> |
| 28 | |
| 29 | namespace Fortran::common { |
| 30 | |
| 31 | template <int N> class FastIntSet { |
| 32 | public: |
| 33 | static_assert(N > 0); |
| 34 | static constexpr int maxValue{N - 1}; |
| 35 | |
| 36 | int size() const { return size_; } |
| 37 | const int *value() const { return &value_[0]; } |
| 38 | |
| 39 | bool IsValidValue(int n) const { return n >= 0 && n <= maxValue; } |
| 40 | |
| 41 | void Clear() { size_ = 0; } |
| 42 | |
| 43 | bool IsEmpty() const { return size_ == 0; } |
| 44 | |
| 45 | void InitializeState() { |
| 46 | if (!isFullyInitialized_) { |
| 47 | for (int j{size_}; j < N; ++j) { |
| 48 | value_[j] = index_[j] = 0; |
| 49 | } |
| 50 | isFullyInitialized_ = true; |
| 51 | } |
| 52 | } |
| 53 | |
| 54 | bool Contains(int n) const { |
| 55 | if (IsValidValue(n)) { |
| 56 | int j{index_[n]}; |
| 57 | return j >= 0 && j < size_ && value_[j] == n; |
| 58 | } else { |
| 59 | return false; |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | bool Add(int n) { |
| 64 | if (IsValidValue(n)) { |
| 65 | if (!UncheckedContains(n)) { |
| 66 | value_[index_[n] = size_++] = n; |
| 67 | } |
| 68 | return true; |
| 69 | } else { |
| 70 | return false; |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | bool Remove(int n) { |
| 75 | if (IsValidValue(n)) { |
| 76 | if (UncheckedContains(n)) { |
| 77 | int last{value_[--size_]}; |
| 78 | value_[index_[last] = index_[n]] = last; |
| 79 | } |
| 80 | return true; |
| 81 | } else { |
| 82 | return false; |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | std::optional<int> PopValue() { |
| 87 | if (IsEmpty()) { |
| 88 | return std::nullopt; |
| 89 | } else { |
| 90 | return value_[--size_]; |
| 91 | } |
| 92 | } |
| 93 | |
| 94 | private: |
| 95 | bool UncheckedContains(int n) const { |
| 96 | int j{index_[n]}; |
| 97 | return j >= 0 && j < size_ && value_[j] == n; |
| 98 | } |
| 99 | |
| 100 | int value_[N]; |
| 101 | int index_[N]; |
| 102 | int size_{0}; |
| 103 | bool isFullyInitialized_{false}; // memory was cleared |
| 104 | }; |
| 105 | } // namespace Fortran::common |
| 106 | #endif // FORTRAN_COMMON_FAST_INT_SET_H_ |
| 107 |
Warning: This file is not a C or C++ file. It does not have highlighting.