1 /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #ifndef TENSORFLOW_GRAPH_EDGESET_H_ 17 #define TENSORFLOW_GRAPH_EDGESET_H_ 18 19 #include <stddef.h> 20 #include <set> 21 #include "tensorflow/core/platform/macros.h" 22 #include "tensorflow/core/platform/types.h" 23 24 #include "tensorflow/core/platform/logging.h" 25 namespace tensorflow { 26 27 class Edge; 28 29 // An unordered set of edges. Uses very little memory for small sets. 30 // Unlike std::set, EdgeSet does NOT allow mutations during iteration. 31 class EdgeSet { 32 public: 33 EdgeSet(); 34 ~EdgeSet(); 35 36 typedef const Edge* key_type; 37 typedef const Edge* value_type; 38 typedef size_t size_type; 39 typedef ptrdiff_t difference_type; 40 41 class const_iterator; 42 typedef const_iterator iterator; 43 44 bool empty() const; 45 size_type size() const; 46 void clear(); 47 std::pair<iterator, bool> insert(value_type value); 48 size_type erase(key_type key); 49 50 // Caller is not allowed to mutate the EdgeSet while iterating. 51 const_iterator begin() const; 52 const_iterator end() const; 53 54 private: 55 // Up to kInline elements are stored directly in ptrs_ (nullptr means none). 56 // If ptrs_[0] == this then ptrs_[1] points to a set<const Edge*>. 57 static const int kInline = 4; // Must be >= 2. 58 const void* ptrs_[kInline]; 59 get_set()60 std::set<const Edge*>* get_set() const { 61 if (ptrs_[0] == this) { 62 return static_cast<std::set<const Edge*>*>(const_cast<void*>(ptrs_[1])); 63 } else { 64 return nullptr; 65 } 66 } 67 68 // To detect mutations while iterating. 69 #ifdef NDEBUG RegisterMutation()70 void RegisterMutation() {} 71 #else 72 uint32 mutations_ = 0; RegisterMutation()73 void RegisterMutation() { mutations_++; } 74 #endif 75 76 TF_DISALLOW_COPY_AND_ASSIGN(EdgeSet); 77 }; 78 79 class EdgeSet::const_iterator { 80 public: 81 typedef typename EdgeSet::value_type value_type; 82 typedef const typename EdgeSet::value_type& reference; 83 typedef const typename EdgeSet::value_type* pointer; 84 typedef typename EdgeSet::difference_type difference_type; 85 typedef std::forward_iterator_tag iterator_category; 86 const_iterator()87 const_iterator() {} 88 89 const_iterator& operator++(); 90 const_iterator operator++(int /*unused*/); 91 const value_type* operator->() const; 92 value_type operator*() const; 93 bool operator==(const const_iterator& other) const; 94 bool operator!=(const const_iterator& other) const { 95 return !(*this == other); 96 } 97 98 private: 99 friend class EdgeSet; 100 101 void const* const* array_iter_ = nullptr; 102 typename std::set<const Edge*>::const_iterator tree_iter_; 103 104 #ifdef NDEBUG Init(const EdgeSet * e)105 inline void Init(const EdgeSet* e) {} CheckNoMutations()106 inline void CheckNoMutations() const {} 107 #else Init(const EdgeSet * e)108 inline void Init(const EdgeSet* e) { 109 owner_ = e; 110 init_mutations_ = e->mutations_; 111 } CheckNoMutations()112 inline void CheckNoMutations() const { 113 CHECK_EQ(init_mutations_, owner_->mutations_); 114 } 115 const EdgeSet* owner_ = nullptr; 116 uint32 init_mutations_ = 0; 117 #endif 118 }; 119 EdgeSet()120inline EdgeSet::EdgeSet() { 121 for (int i = 0; i < kInline; i++) { 122 ptrs_[i] = nullptr; 123 } 124 } 125 ~EdgeSet()126inline EdgeSet::~EdgeSet() { delete get_set(); } 127 empty()128inline bool EdgeSet::empty() const { return size() == 0; } 129 size()130inline EdgeSet::size_type EdgeSet::size() const { 131 auto s = get_set(); 132 if (s) { 133 return s->size(); 134 } else { 135 size_t result = 0; 136 for (int i = 0; i < kInline; i++) { 137 if (ptrs_[i]) result++; 138 } 139 return result; 140 } 141 } 142 clear()143inline void EdgeSet::clear() { 144 RegisterMutation(); 145 delete get_set(); 146 for (int i = 0; i < kInline; i++) { 147 ptrs_[i] = nullptr; 148 } 149 } 150 begin()151inline EdgeSet::const_iterator EdgeSet::begin() const { 152 const_iterator ci; 153 ci.Init(this); 154 auto s = get_set(); 155 if (s) { 156 ci.tree_iter_ = s->begin(); 157 } else { 158 ci.array_iter_ = &ptrs_[0]; 159 } 160 return ci; 161 } 162 end()163inline EdgeSet::const_iterator EdgeSet::end() const { 164 const_iterator ci; 165 ci.Init(this); 166 auto s = get_set(); 167 if (s) { 168 ci.tree_iter_ = s->end(); 169 } else { 170 ci.array_iter_ = &ptrs_[size()]; 171 } 172 return ci; 173 } 174 175 inline EdgeSet::const_iterator& EdgeSet::const_iterator::operator++() { 176 CheckNoMutations(); 177 if (array_iter_ != nullptr) { 178 ++array_iter_; 179 } else { 180 ++tree_iter_; 181 } 182 return *this; 183 } 184 185 inline EdgeSet::const_iterator EdgeSet::const_iterator::operator++( 186 int /*unused*/) { 187 CheckNoMutations(); 188 const_iterator tmp = *this; 189 operator++(); 190 return tmp; 191 } 192 193 // gcc's set and multiset always use const_iterator since it will otherwise 194 // allow modification of keys. 195 inline const EdgeSet::const_iterator::value_type* EdgeSet::const_iterator:: 196 operator->() const { 197 CheckNoMutations(); 198 if (array_iter_ != nullptr) { 199 return reinterpret_cast<const value_type*>(array_iter_); 200 } else { 201 return tree_iter_.operator->(); 202 } 203 } 204 205 // gcc's set and multiset always use const_iterator since it will otherwise 206 // allow modification of keys. 207 inline EdgeSet::const_iterator::value_type EdgeSet::const_iterator::operator*() 208 const { 209 CheckNoMutations(); 210 if (array_iter_ != nullptr) { 211 return static_cast<value_type>(*array_iter_); 212 } else { 213 return *tree_iter_; 214 } 215 } 216 217 inline bool EdgeSet::const_iterator::operator==( 218 const const_iterator& other) const { 219 DCHECK((array_iter_ == nullptr) == (other.array_iter_ == nullptr)) 220 << "Iterators being compared must be from same set that has not " 221 << "been modified since the iterator was constructed"; 222 CheckNoMutations(); 223 if (array_iter_ != nullptr) { 224 return array_iter_ == other.array_iter_; 225 } else { 226 return other.array_iter_ == nullptr && tree_iter_ == other.tree_iter_; 227 } 228 } 229 230 } // namespace tensorflow 231 232 #endif // TENSORFLOW_GRAPH_EDGESET_H_ 233