The Tor Browser / file comparison
comparison: js/src/jsapi-tests/testFindSCCs.cpp
js/src/jsapi-tests/testFindSCCs.cpp
- branch
- TOR_BUG_9701
- changeset 14
- 925c144e1f1f
equal
deleted
inserted
replaced
| -1:000000000000 | 0:4f3c110f511a |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | |
| 2 * vim: set ts=8 sts=4 et sw=4 tw=99: | |
| 3 */ | |
| 4 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 5 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 7 | |
| 8 #include <stdarg.h> | |
| 9 #include <string.h> | |
| 10 | |
| 11 #include "gc/FindSCCs.h" | |
| 12 #include "jsapi-tests/tests.h" | |
| 13 | |
| 14 static const unsigned MaxVertices = 10; | |
| 15 | |
| 16 using js::gc::GraphNodeBase; | |
| 17 using js::gc::ComponentFinder; | |
| 18 | |
| 19 struct TestNode : public GraphNodeBase<TestNode> | |
| 20 { | |
| 21 unsigned index; | |
| 22 bool hasEdge[MaxVertices]; | |
| 23 | |
| 24 void findOutgoingEdges(ComponentFinder<TestNode> &finder); | |
| 25 }; | |
| 26 | |
| 27 static TestNode Vertex[MaxVertices]; | |
| 28 | |
| 29 void | |
| 30 TestNode::findOutgoingEdges(ComponentFinder<TestNode> &finder) | |
| 31 { | |
| 32 for (unsigned i = 0; i < MaxVertices; ++i) { | |
| 33 if (hasEdge[i]) | |
| 34 finder.addEdgeTo(&Vertex[i]); | |
| 35 } | |
| 36 } | |
| 37 | |
| 38 BEGIN_TEST(testFindSCCs) | |
| 39 { | |
| 40 // no vertices | |
| 41 | |
| 42 setup(0); | |
| 43 run(); | |
| 44 CHECK(end()); | |
| 45 | |
| 46 // no edges | |
| 47 | |
| 48 setup(1); | |
| 49 run(); | |
| 50 CHECK(group(0, -1)); | |
| 51 CHECK(end()); | |
| 52 | |
| 53 setup(3); | |
| 54 run(); | |
| 55 CHECK(group(2, -1)); | |
| 56 CHECK(group(1, -1)); | |
| 57 CHECK(group(0, -1)); | |
| 58 CHECK(end()); | |
| 59 | |
| 60 // linear | |
| 61 | |
| 62 setup(3); | |
| 63 edge(0, 1); | |
| 64 edge(1, 2); | |
| 65 run(); | |
| 66 CHECK(group(0, -1)); | |
| 67 CHECK(group(1, -1)); | |
| 68 CHECK(group(2, -1)); | |
| 69 CHECK(end()); | |
| 70 | |
| 71 // tree | |
| 72 | |
| 73 setup(3); | |
| 74 edge(0, 1); | |
| 75 edge(0, 2); | |
| 76 run(); | |
| 77 CHECK(group(0, -1)); | |
| 78 CHECK(group(2, -1)); | |
| 79 CHECK(group(1, -1)); | |
| 80 CHECK(end()); | |
| 81 | |
| 82 // cycles | |
| 83 | |
| 84 setup(3); | |
| 85 edge(0, 1); | |
| 86 edge(1, 2); | |
| 87 edge(2, 0); | |
| 88 run(); | |
| 89 CHECK(group(0, 1, 2, -1)); | |
| 90 CHECK(end()); | |
| 91 | |
| 92 setup(4); | |
| 93 edge(0, 1); | |
| 94 edge(1, 2); | |
| 95 edge(2, 1); | |
| 96 edge(2, 3); | |
| 97 run(); | |
| 98 CHECK(group(0, -1)); | |
| 99 CHECK(group(1, 2, -1)); | |
| 100 CHECK(group(3, -1)); | |
| 101 CHECK(end()); | |
| 102 | |
| 103 // remaining | |
| 104 | |
| 105 setup(2); | |
| 106 edge(0, 1); | |
| 107 run(); | |
| 108 CHECK(remaining(0, 1, -1)); | |
| 109 CHECK(end()); | |
| 110 | |
| 111 setup(2); | |
| 112 edge(0, 1); | |
| 113 run(); | |
| 114 CHECK(group(0, -1)); | |
| 115 CHECK(remaining(1, -1)); | |
| 116 CHECK(end()); | |
| 117 | |
| 118 setup(2); | |
| 119 edge(0, 1); | |
| 120 run(); | |
| 121 CHECK(group(0, -1)); | |
| 122 CHECK(group(1, -1)); | |
| 123 CHECK(remaining(-1)); | |
| 124 CHECK(end()); | |
| 125 | |
| 126 return true; | |
| 127 } | |
| 128 | |
| 129 unsigned vertex_count; | |
| 130 ComponentFinder<TestNode> *finder; | |
| 131 TestNode *resultsList; | |
| 132 | |
| 133 void setup(unsigned count) | |
| 134 { | |
| 135 vertex_count = count; | |
| 136 for (unsigned i = 0; i < MaxVertices; ++i) { | |
| 137 TestNode &v = Vertex[i]; | |
| 138 v.gcNextGraphNode = nullptr; | |
| 139 v.index = i; | |
| 140 memset(&v.hasEdge, 0, sizeof(v.hasEdge)); | |
| 141 } | |
| 142 } | |
| 143 | |
| 144 void edge(unsigned src_index, unsigned dest_index) | |
| 145 { | |
| 146 Vertex[src_index].hasEdge[dest_index] = true; | |
| 147 } | |
| 148 | |
| 149 void run() | |
| 150 { | |
| 151 finder = new ComponentFinder<TestNode>(rt->mainThread.nativeStackLimit[js::StackForSystemCode]); | |
| 152 for (unsigned i = 0; i < vertex_count; ++i) | |
| 153 finder->addNode(&Vertex[i]); | |
| 154 resultsList = finder->getResultsList(); | |
| 155 } | |
| 156 | |
| 157 bool group(int vertex, ...) | |
| 158 { | |
| 159 TestNode *v = resultsList; | |
| 160 | |
| 161 va_list ap; | |
| 162 va_start(ap, vertex); | |
| 163 while (vertex != -1) { | |
| 164 CHECK(v != nullptr); | |
| 165 CHECK(v->index == unsigned(vertex)); | |
| 166 v = v->nextNodeInGroup(); | |
| 167 vertex = va_arg(ap, int); | |
| 168 } | |
| 169 va_end(ap); | |
| 170 | |
| 171 CHECK(v == nullptr); | |
| 172 resultsList = resultsList->nextGroup(); | |
| 173 return true; | |
| 174 } | |
| 175 | |
| 176 bool remaining(int vertex, ...) | |
| 177 { | |
| 178 TestNode *v = resultsList; | |
| 179 | |
| 180 va_list ap; | |
| 181 va_start(ap, vertex); | |
| 182 while (vertex != -1) { | |
| 183 CHECK(v != nullptr); | |
| 184 CHECK(v->index == unsigned(vertex)); | |
| 185 v = (TestNode *)v->gcNextGraphNode; | |
| 186 vertex = va_arg(ap, int); | |
| 187 } | |
| 188 va_end(ap); | |
| 189 | |
| 190 CHECK(v == nullptr); | |
| 191 resultsList = nullptr; | |
| 192 return true; | |
| 193 } | |
| 194 | |
| 195 bool end() | |
| 196 { | |
| 197 CHECK(resultsList == nullptr); | |
| 198 | |
| 199 delete finder; | |
| 200 finder = nullptr; | |
| 201 return true; | |
| 202 } | |
| 203 END_TEST(testFindSCCs) | |
| 204 | |
| 205 struct TestNode2 : public GraphNodeBase<TestNode2> | |
| 206 { | |
| 207 TestNode2 *edge; | |
| 208 | |
| 209 TestNode2() : | |
| 210 edge(nullptr) | |
| 211 { | |
| 212 } | |
| 213 | |
| 214 void | |
| 215 findOutgoingEdges(ComponentFinder<TestNode2> &finder) { | |
| 216 if (edge) | |
| 217 finder.addEdgeTo(edge); | |
| 218 } | |
| 219 }; | |
| 220 | |
| 221 BEGIN_TEST(testFindSCCsStackLimit) | |
| 222 { | |
| 223 /* | |
| 224 * Test what happens if recusion causes the stack to become full while | |
| 225 * traversing the graph. | |
| 226 * | |
| 227 * The test case is a large number of vertices, almost all of which are | |
| 228 * arranged in a linear chain. The last few are left unlinked to exercise | |
| 229 * adding vertices after the stack full condition has already been detected. | |
| 230 * | |
| 231 * Such an arrangement with no cycles would normally result in one group for | |
| 232 * each vertex, but since the stack is exhasted in processing a single group | |
| 233 * is returned containing all the vertices. | |
| 234 */ | |
| 235 const unsigned max = 1000000; | |
| 236 const unsigned initial = 10; | |
| 237 | |
| 238 TestNode2 *vertices = new TestNode2[max](); | |
| 239 for (unsigned i = initial; i < (max - 10); ++i) | |
| 240 vertices[i].edge = &vertices[i + 1]; | |
| 241 | |
| 242 ComponentFinder<TestNode2> finder(rt->mainThread.nativeStackLimit[js::StackForSystemCode]); | |
| 243 for (unsigned i = 0; i < max; ++i) | |
| 244 finder.addNode(&vertices[i]); | |
| 245 | |
| 246 TestNode2 *r = finder.getResultsList(); | |
| 247 CHECK(r); | |
| 248 TestNode2 *v = r; | |
| 249 | |
| 250 unsigned count = 0; | |
| 251 while (v) { | |
| 252 ++count; | |
| 253 v = v->nextNodeInGroup(); | |
| 254 } | |
| 255 CHECK(count == max - initial); | |
| 256 | |
| 257 count = 0; | |
| 258 v = r->nextGroup(); | |
| 259 while (v) { | |
| 260 ++count; | |
| 261 CHECK(!v->nextNodeInGroup()); | |
| 262 v = v->nextGroup(); | |
| 263 } | |
| 264 | |
| 265 delete [] vertices; | |
| 266 return true; | |
| 267 } | |
| 268 END_TEST(testFindSCCsStackLimit) |
