mirror of
https://github.com/classilla/tenfourfox.git
synced 2024-06-10 02:29:43 +00:00
269 lines
5.4 KiB
C++
269 lines
5.4 KiB
C++
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
|
|
* vim: set ts=8 sts=4 et sw=4 tw=99:
|
|
*/
|
|
/* This Source Code Form is subject to the terms of the Mozilla Public
|
|
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
|
|
|
|
#include <stdarg.h>
|
|
#include <string.h>
|
|
|
|
#include "gc/FindSCCs.h"
|
|
#include "jsapi-tests/tests.h"
|
|
|
|
static const unsigned MaxVertices = 10;
|
|
|
|
using js::gc::GraphNodeBase;
|
|
using js::gc::ComponentFinder;
|
|
|
|
struct TestNode : public GraphNodeBase<TestNode>
|
|
{
|
|
unsigned index;
|
|
bool hasEdge[MaxVertices];
|
|
|
|
void findOutgoingEdges(ComponentFinder<TestNode>& finder);
|
|
};
|
|
|
|
static TestNode Vertex[MaxVertices];
|
|
|
|
void
|
|
TestNode::findOutgoingEdges(ComponentFinder<TestNode>& finder)
|
|
{
|
|
for (unsigned i = 0; i < MaxVertices; ++i) {
|
|
if (hasEdge[i])
|
|
finder.addEdgeTo(&Vertex[i]);
|
|
}
|
|
}
|
|
|
|
BEGIN_TEST(testFindSCCs)
|
|
{
|
|
// no vertices
|
|
|
|
setup(0);
|
|
run();
|
|
CHECK(end());
|
|
|
|
// no edges
|
|
|
|
setup(1);
|
|
run();
|
|
CHECK(group(0, -1));
|
|
CHECK(end());
|
|
|
|
setup(3);
|
|
run();
|
|
CHECK(group(2, -1));
|
|
CHECK(group(1, -1));
|
|
CHECK(group(0, -1));
|
|
CHECK(end());
|
|
|
|
// linear
|
|
|
|
setup(3);
|
|
edge(0, 1);
|
|
edge(1, 2);
|
|
run();
|
|
CHECK(group(0, -1));
|
|
CHECK(group(1, -1));
|
|
CHECK(group(2, -1));
|
|
CHECK(end());
|
|
|
|
// tree
|
|
|
|
setup(3);
|
|
edge(0, 1);
|
|
edge(0, 2);
|
|
run();
|
|
CHECK(group(0, -1));
|
|
CHECK(group(2, -1));
|
|
CHECK(group(1, -1));
|
|
CHECK(end());
|
|
|
|
// cycles
|
|
|
|
setup(3);
|
|
edge(0, 1);
|
|
edge(1, 2);
|
|
edge(2, 0);
|
|
run();
|
|
CHECK(group(0, 1, 2, -1));
|
|
CHECK(end());
|
|
|
|
setup(4);
|
|
edge(0, 1);
|
|
edge(1, 2);
|
|
edge(2, 1);
|
|
edge(2, 3);
|
|
run();
|
|
CHECK(group(0, -1));
|
|
CHECK(group(1, 2, -1));
|
|
CHECK(group(3, -1));
|
|
CHECK(end());
|
|
|
|
// remaining
|
|
|
|
setup(2);
|
|
edge(0, 1);
|
|
run();
|
|
CHECK(remaining(0, 1, -1));
|
|
CHECK(end());
|
|
|
|
setup(2);
|
|
edge(0, 1);
|
|
run();
|
|
CHECK(group(0, -1));
|
|
CHECK(remaining(1, -1));
|
|
CHECK(end());
|
|
|
|
setup(2);
|
|
edge(0, 1);
|
|
run();
|
|
CHECK(group(0, -1));
|
|
CHECK(group(1, -1));
|
|
CHECK(remaining(-1));
|
|
CHECK(end());
|
|
|
|
return true;
|
|
}
|
|
|
|
unsigned vertex_count;
|
|
ComponentFinder<TestNode>* finder;
|
|
TestNode* resultsList;
|
|
|
|
void setup(unsigned count)
|
|
{
|
|
vertex_count = count;
|
|
for (unsigned i = 0; i < MaxVertices; ++i) {
|
|
TestNode& v = Vertex[i];
|
|
v.gcNextGraphNode = nullptr;
|
|
v.index = i;
|
|
memset(&v.hasEdge, 0, sizeof(v.hasEdge));
|
|
}
|
|
}
|
|
|
|
void edge(unsigned src_index, unsigned dest_index)
|
|
{
|
|
Vertex[src_index].hasEdge[dest_index] = true;
|
|
}
|
|
|
|
void run()
|
|
{
|
|
finder = new ComponentFinder<TestNode>(rt->mainThread.nativeStackLimit[js::StackForSystemCode]);
|
|
for (unsigned i = 0; i < vertex_count; ++i)
|
|
finder->addNode(&Vertex[i]);
|
|
resultsList = finder->getResultsList();
|
|
}
|
|
|
|
bool group(int vertex, ...)
|
|
{
|
|
TestNode* v = resultsList;
|
|
|
|
va_list ap;
|
|
va_start(ap, vertex);
|
|
while (vertex != -1) {
|
|
CHECK(v != nullptr);
|
|
CHECK(v->index == unsigned(vertex));
|
|
v = v->nextNodeInGroup();
|
|
vertex = va_arg(ap, int);
|
|
}
|
|
va_end(ap);
|
|
|
|
CHECK(v == nullptr);
|
|
resultsList = resultsList->nextGroup();
|
|
return true;
|
|
}
|
|
|
|
bool remaining(int vertex, ...)
|
|
{
|
|
TestNode* v = resultsList;
|
|
|
|
va_list ap;
|
|
va_start(ap, vertex);
|
|
while (vertex != -1) {
|
|
CHECK(v != nullptr);
|
|
CHECK(v->index == unsigned(vertex));
|
|
v = (TestNode*)v->gcNextGraphNode;
|
|
vertex = va_arg(ap, int);
|
|
}
|
|
va_end(ap);
|
|
|
|
CHECK(v == nullptr);
|
|
resultsList = nullptr;
|
|
return true;
|
|
}
|
|
|
|
bool end()
|
|
{
|
|
CHECK(resultsList == nullptr);
|
|
|
|
delete finder;
|
|
finder = nullptr;
|
|
return true;
|
|
}
|
|
END_TEST(testFindSCCs)
|
|
|
|
struct TestNode2 : public GraphNodeBase<TestNode2>
|
|
{
|
|
TestNode2* edge;
|
|
|
|
TestNode2() :
|
|
edge(nullptr)
|
|
{
|
|
}
|
|
|
|
void
|
|
findOutgoingEdges(ComponentFinder<TestNode2>& finder) {
|
|
if (edge)
|
|
finder.addEdgeTo(edge);
|
|
}
|
|
};
|
|
|
|
BEGIN_TEST(testFindSCCsStackLimit)
|
|
{
|
|
/*
|
|
* Test what happens if recusion causes the stack to become full while
|
|
* traversing the graph.
|
|
*
|
|
* The test case is a large number of vertices, almost all of which are
|
|
* arranged in a linear chain. The last few are left unlinked to exercise
|
|
* adding vertices after the stack full condition has already been detected.
|
|
*
|
|
* Such an arrangement with no cycles would normally result in one group for
|
|
* each vertex, but since the stack is exhasted in processing a single group
|
|
* is returned containing all the vertices.
|
|
*/
|
|
const unsigned max = 1000000;
|
|
const unsigned initial = 10;
|
|
|
|
TestNode2* vertices = new TestNode2[max]();
|
|
for (unsigned i = initial; i < (max - 10); ++i)
|
|
vertices[i].edge = &vertices[i + 1];
|
|
|
|
ComponentFinder<TestNode2> finder(rt->mainThread.nativeStackLimit[js::StackForSystemCode]);
|
|
for (unsigned i = 0; i < max; ++i)
|
|
finder.addNode(&vertices[i]);
|
|
|
|
TestNode2* r = finder.getResultsList();
|
|
CHECK(r);
|
|
TestNode2* v = r;
|
|
|
|
unsigned count = 0;
|
|
while (v) {
|
|
++count;
|
|
v = v->nextNodeInGroup();
|
|
}
|
|
CHECK(count == max - initial);
|
|
|
|
count = 0;
|
|
v = r->nextGroup();
|
|
while (v) {
|
|
++count;
|
|
CHECK(!v->nextNodeInGroup());
|
|
v = v->nextGroup();
|
|
}
|
|
|
|
delete [] vertices;
|
|
return true;
|
|
}
|
|
END_TEST(testFindSCCsStackLimit)
|