1 /*
2 * Copyright 2014 Google Inc. All rights reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef SEMISTATIC_GRAPH_TEMPLATES_H
18 #define SEMISTATIC_GRAPH_TEMPLATES_H
19
20 #if !IN_FRUIT_CPP_FILE
21 #error "Fruit .template.h file included in non-cpp file."
22 #endif
23
24 #include <fruit/impl/data_structures/arena_allocator.h>
25 #include <fruit/impl/data_structures/fixed_size_vector.templates.h>
26 #include <fruit/impl/data_structures/memory_pool.h>
27 #include <fruit/impl/data_structures/semistatic_graph.h>
28 #include <fruit/impl/data_structures/semistatic_map.templates.h>
29 #include <fruit/impl/util/hash_helpers.h>
30
31 #if FRUIT_EXTRA_DEBUG
32 #include <iostream>
33 #endif
34
35 namespace fruit {
36 namespace impl {
37
38 template <typename Iter, std::size_t index_increment>
39 struct indexing_iterator {
40 Iter iter;
41 std::size_t index;
42
43 void operator++() {
44 ++iter;
45 index += index_increment;
46 }
47
48 auto operator*() -> decltype(std::make_pair(*iter, SemistaticGraphInternalNodeId{index})) {
49 return std::make_pair(*iter, SemistaticGraphInternalNodeId{index});
50 }
51
52 bool operator==(const indexing_iterator<Iter, index_increment>& other) const {
53 return iter == other.iter;
54 }
55 };
56
57 #if FRUIT_EXTRA_DEBUG
58 template <typename NodeId, typename Node>
59 template <typename NodeIter>
printGraph(NodeIter first,NodeIter last)60 void SemistaticGraph<NodeId, Node>::printGraph(NodeIter first, NodeIter last) {
61 std::cerr << "Constructed injection graph with nodes:" << std::endl;
62 for (NodeIter i = first; i != last; ++i) {
63 std::cerr << i->getId() << " -> ";
64 if (i->isTerminal()) {
65 std::cerr << "(none, terminal)";
66 } else {
67 std::cerr << "{";
68 for (auto j = i->getEdgesBegin(); j != i->getEdgesEnd(); ++j) {
69 if (j != i->getEdgesBegin()) {
70 std::cerr << ", ";
71 }
72 std::cerr << *j;
73 }
74 std::cerr << "}";
75 }
76 std::cerr << std::endl;
77 }
78 std::cerr << std::endl;
79 }
80 #endif // FRUIT_EXTRA_DEBUG
81
82 template <typename NodeId, typename Node>
83 template <typename NodeIter>
SemistaticGraph(NodeIter first,NodeIter last,MemoryPool & memory_pool)84 SemistaticGraph<NodeId, Node>::SemistaticGraph(NodeIter first, NodeIter last, MemoryPool& memory_pool) {
85 std::size_t num_edges = 0;
86 // Step 1: assign IDs to all nodes, fill node_index_map and set first_unused_index.
87 HashSetWithArenaAllocator<NodeId> node_ids = createHashSetWithArenaAllocator<NodeId>(last - first, memory_pool);
88 for (NodeIter i = first; i != last; ++i) {
89 node_ids.insert(i->getId());
90 if (!i->isTerminal()) {
91 for (auto j = i->getEdgesBegin(); j != i->getEdgesEnd(); ++j) {
92 node_ids.insert(*j);
93 ++num_edges;
94 }
95 }
96 }
97
98 using itr_t = typename HashSetWithArenaAllocator<NodeId>::iterator;
99 node_index_map = SemistaticMap<NodeId, InternalNodeId>(
100 indexing_iterator<itr_t, sizeof(NodeData)>{node_ids.begin(), 0},
101 indexing_iterator<itr_t, sizeof(NodeData)>{node_ids.end(), node_ids.size() * sizeof(NodeData)},
102 node_ids.size(),
103 memory_pool);
104
105 first_unused_index = node_ids.size();
106
107 // Step 2: fill `nodes' and edges_storage.
108
109 // Note that not all of these will be assigned in the loop below.
110 nodes = FixedSizeVector<NodeData>(first_unused_index, NodeData{
111 #if FRUIT_EXTRA_DEBUG
112 NodeId(),
113 #endif
114 1, Node()});
115
116 // edges_storage[0] is unused, that's the reason for the +1
117 edges_storage = FixedSizeVector<InternalNodeId>(num_edges + 1);
118 edges_storage.push_back(InternalNodeId());
119
120 for (NodeIter i = first; i != last; ++i) {
121 NodeData& nodeData = *nodeAtId(node_index_map.at(i->getId()));
122 nodeData.node = i->getValue();
123 if (i->isTerminal()) {
124 nodeData.edges_begin = 0;
125 } else {
126 nodeData.edges_begin = reinterpret_cast<std::uintptr_t>(edges_storage.data() + edges_storage.size());
127 for (auto j = i->getEdgesBegin(); j != i->getEdgesEnd(); ++j) {
128 InternalNodeId other_node_id = node_index_map.at(*j);
129 edges_storage.push_back(other_node_id);
130 }
131 }
132 }
133
134 #if FRUIT_EXTRA_DEBUG
135 printGraph(first, last);
136 #endif
137 }
138
139 template <typename NodeId, typename Node>
140 template <typename NodeIter>
SemistaticGraph(const SemistaticGraph & x,NodeIter first,NodeIter last,MemoryPool & memory_pool)141 SemistaticGraph<NodeId, Node>::SemistaticGraph(const SemistaticGraph& x, NodeIter first, NodeIter last,
142 MemoryPool& memory_pool)
143 : first_unused_index(x.first_unused_index) {
144
145 // TODO: The code below is very similar to the other constructor, extract the common parts in separate functions.
146
147 std::size_t num_new_edges = 0;
148
149 // Step 1: assign IDs to new nodes, fill `node_index_map' and update `first_unused_index'.
150
151 // Step 1a: collect all new node IDs.
152 using node_ids_elem_t = std::pair<NodeId, InternalNodeId>;
153 using node_ids_t = std::vector<node_ids_elem_t, ArenaAllocator<node_ids_elem_t>>;
154 node_ids_t node_ids = node_ids_t(ArenaAllocator<node_ids_elem_t>(memory_pool));
155 for (NodeIter i = first; i != last; ++i) {
156 if (x.node_index_map.find(i->getId()) == nullptr) {
157 node_ids.push_back(std::make_pair(i->getId(), InternalNodeId()));
158 }
159 if (!i->isTerminal()) {
160 for (auto j = i->getEdgesBegin(); j != i->getEdgesEnd(); ++j) {
161 if (x.node_index_map.find(*j) == nullptr) {
162 node_ids.push_back(std::make_pair(*j, InternalNodeId()));
163 }
164 ++num_new_edges;
165 }
166 }
167 }
168
169 // Step 1b: remove duplicates.
170 std::sort(node_ids.begin(), node_ids.end());
171 node_ids.erase(std::unique(node_ids.begin(), node_ids.end()), node_ids.end());
172
173 // Step 1c: assign new IDs.
174 for (auto& p : node_ids) {
175 p.second = InternalNodeId{first_unused_index * sizeof(NodeData)};
176 ++first_unused_index;
177 }
178
179 // Step 1d: actually populate node_index_map.
180 node_index_map = SemistaticMap<NodeId, InternalNodeId>(x.node_index_map, std::move(node_ids));
181
182 // Step 2: fill `nodes' and `edges_storage'
183 nodes = FixedSizeVector<NodeData>(x.nodes, first_unused_index);
184 // Note that the loop below does not necessarily assign all of these.
185 for (std::size_t i = x.nodes.size(); i < first_unused_index; ++i) {
186 nodes.push_back(NodeData{
187 #if FRUIT_EXTRA_DEBUG
188 NodeId(),
189 #endif
190 1, Node()});
191 }
192
193 // edges_storage[0] is unused, that's the reason for the +1
194 edges_storage = FixedSizeVector<InternalNodeId>(num_new_edges + 1);
195 edges_storage.push_back(InternalNodeId());
196
197 for (NodeIter i = first; i != last; ++i) {
198 NodeData& nodeData = *nodeAtId(node_index_map.at(i->getId()));
199 nodeData.node = i->getValue();
200 if (i->isTerminal()) {
201 nodeData.edges_begin = 0;
202 } else {
203 nodeData.edges_begin = reinterpret_cast<std::uintptr_t>(edges_storage.data() + edges_storage.size());
204 for (auto j = i->getEdgesBegin(); j != i->getEdgesEnd(); ++j) {
205 InternalNodeId otherNodeId = node_index_map.at(*j);
206 edges_storage.push_back(otherNodeId);
207 }
208 }
209 }
210
211 #if FRUIT_EXTRA_DEBUG
212 printGraph(first, last);
213 #endif
214 }
215
216 #if FRUIT_EXTRA_DEBUG
217 template <typename NodeId, typename Node>
checkFullyConstructed()218 void SemistaticGraph<NodeId, Node>::checkFullyConstructed() {
219 for (NodeData& data : nodes) {
220 if (data.edges_begin == 1) {
221 std::cerr << "Fruit bug: the dependency graph was not fully constructed." << std::endl;
222 abort();
223 }
224 }
225 }
226 #endif // !FRUIT_EXTRA_DEBUG
227
228 // This is here so that we don't have to include fixed_size_vector.templates.h in fruit.h.
229 template <typename NodeId, typename Node>
~SemistaticGraph()230 SemistaticGraph<NodeId, Node>::~SemistaticGraph() {}
231
232 } // namespace impl
233 } // namespace fruit
234
235 #endif // SEMISTATIC_GRAPH_TEMPLATES_H
236