• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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()120 inline EdgeSet::EdgeSet() {
121   for (int i = 0; i < kInline; i++) {
122     ptrs_[i] = nullptr;
123   }
124 }
125 
~EdgeSet()126 inline EdgeSet::~EdgeSet() { delete get_set(); }
127 
empty()128 inline bool EdgeSet::empty() const { return size() == 0; }
129 
size()130 inline 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()143 inline 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()151 inline 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()163 inline 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