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 size()36 int size() const { return size_; } value()37 const int *value() const { return &value_[0]; } 38 IsValidValue(int n)39 bool IsValidValue(int n) const { return n >= 0 && n <= maxValue; } 40 Clear()41 void Clear() { size_ = 0; } 42 IsEmpty()43 bool IsEmpty() const { return size_ == 0; } 44 InitializeState()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 Contains(int n)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 Add(int n)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 Remove(int n)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 PopValue()86 std::optional<int> PopValue() { 87 if (IsEmpty()) { 88 return std::nullopt; 89 } else { 90 return value_[--size_]; 91 } 92 } 93 94 private: UncheckedContains(int n)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