Source code
Revision control
Copy as Markdown
Other Tools
/* 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
#include <set>
#include <stdio.h>
#include "ds/AvlTree.h"
#include "jsapi-tests/tests.h"
using namespace js;
////////////////////////////////////////////////////////////////////////
// //
// AvlTree testing interface. //
// //
////////////////////////////////////////////////////////////////////////
// The "standard" AVL interface, `class AvlTree` at the end of
// js/src/ds/AvlTree.h, is too restrictive to allow proper testing of the AVL
// tree internals. In particular it disallows insertion of duplicate values
// and removal of non-present values, and lacks various secondary functions
// such as for counting the number of nodes.
//
// So, for testing, we wrap an alternative interface `AvlTreeTestIF` around
// the core implementation.
template <class T, class C>
class AvlTreeTestIF : public AvlTreeImpl<T, C> {
// Shorthands for names in the implementation (parent) class.
using Impl = AvlTreeImpl<T, C>;
using ImplTag = typename AvlTreeImpl<T, C>::Tag;
using ImplNode = typename AvlTreeImpl<T, C>::Node;
using ImplResult = typename AvlTreeImpl<T, C>::Result;
using ImplNodeAndResult = typename AvlTreeImpl<T, C>::NodeAndResult;
public:
explicit AvlTreeTestIF(LifoAlloc* alloc = nullptr) : Impl(alloc) {}
// Insert `v` if it isn't already there, else leave the tree unchanged.
// Returns true iff an insertion happened.
bool testInsert(const T& v) {
ImplNode* new_root = Impl::insert_worker(v);
if (!new_root) {
// OOM
MOZ_CRASH();
}
if (uintptr_t(new_root) == uintptr_t(1)) {
// Already present
return false;
}
Impl::root_ = new_root;
return true;
}
// Remove `v` if it is present. Returns true iff a removal happened.
bool testRemove(const T& v) {
ImplNodeAndResult pair = Impl::delete_worker(Impl::root_, v);
ImplNode* new_root = pair.first;
ImplResult res = pair.second;
if (res == ImplResult::Error) {
// `v` isn't in the tree.
return false;
} else {
Impl::root_ = new_root;
return true;
}
}
// Count number of elements
size_t testSize_worker(ImplNode* n) const {
if (n) {
return 1 + testSize_worker(n->left) + testSize_worker(n->getRight());
}
return 0;
}
size_t testSize() const { return testSize_worker(Impl::root_); }
size_t testDepth_worker(ImplNode* n) const {
if (n) {
size_t depthL = testDepth_worker(n->left);
size_t depthR = testDepth_worker(n->getRight());
return 1 + (depthL > depthR ? depthL : depthR);
}
return 0;
}
size_t testDepth() const { return testDepth_worker(Impl::root_); }
bool testContains(const T& v) const {
ImplNode* node = Impl::find_worker(v);
return node != nullptr;
}
ImplNode* testGetRoot() const { return Impl::root_; }
ImplNode* testGetFreeList() const { return Impl::freeList_; }
bool testFreeListLooksValid(size_t maxElems) {
size_t numElems = 0;
ImplNode* node = Impl::freeList_;
while (node) {
numElems++;
if (numElems > maxElems) {
return false;
}
if (node->getTag() != ImplTag::Free || node->getRight() != nullptr) {
return false;
}
node = node->left;
}
return true;
}
// For debugging only
private:
void testShow_worker(int depth, const ImplNode* node) const {
if (node) {
testShow_worker(depth + 1, node->getRight());
for (int i = 0; i < depth; i++) {
printf(" ");
}
char* str = node->item.show();
printf("%s\n", str);
free(str);
testShow_worker(depth + 1, node->left);
}
}
public:
// For debugging only
void testShow() const { testShow_worker(0, Impl::root_); }
// AvlTree::Iter is also public; it's just pass-through from AvlTreeImpl.
};
////////////////////////////////////////////////////////////////////////
// //
// AvlTree test cases. //
// //
////////////////////////////////////////////////////////////////////////
class CmpInt {
int x_;
public:
explicit CmpInt(int x) : x_(x) {}
~CmpInt() {}
static int compare(const CmpInt& me, const CmpInt& other) {
if (me.x_ < other.x_) return -1;
if (me.x_ > other.x_) return 1;
return 0;
}
int get() const { return x_; }
char* show() const {
const size_t length = 16;
char* str = (char*)calloc(length, 1);
snprintf(str, length, "%d", x_);
return str;
}
};
bool TreeIsPlausible(const AvlTreeTestIF<CmpInt, CmpInt>& tree,
const std::set<int>& should_be_in_tree, int UNIV_MIN,
int UNIV_MAX) {
// Same cardinality
size_t n_in_set = should_be_in_tree.size();
size_t n_in_tree = tree.testSize();
if (n_in_set != n_in_tree) {
return false;
}
// Tree is not wildly out of balance. Depth should not exceed 1.44 *
// log2(size).
size_t tree_depth = tree.testDepth();
size_t log2_size = 0;
{
size_t n = n_in_tree;
while (n > 0) {
n = n >> 1;
log2_size += 1;
}
}
// Actually a tighter limit than stated above. For these test cases, the
// tree is either perfectly balanced or within one level of being so (hence
// the +1).
if (tree_depth > log2_size + 1) {
return false;
}
// Check that everything that should be in the tree is in it, and vice
// versa.
for (int i = UNIV_MIN; i < UNIV_MAX; i++) {
bool should_be_in = should_be_in_tree.find(i) != should_be_in_tree.end();
// Look it up with a null comparator (so `contains` compares
// directly)
bool is_in = tree.testContains(CmpInt(i));
if (is_in != should_be_in) {
return false;
}
}
return true;
}
template <typename T>
bool SetContains(std::set<T> s, const T& v) {
return s.find(v) != s.end();
}
BEGIN_TEST(testAvlTree_main) {
static const int UNIV_MIN = 5000;
static const int UNIV_MAX = 5999;
static const int UNIV_SIZE = UNIV_MAX - UNIV_MIN + 1;
LifoAlloc alloc(4096);
AvlTreeTestIF<CmpInt, CmpInt> tree(&alloc);
std::set<int> should_be_in_tree;
// Add numbers to the tree, checking as we go.
for (int i = UNIV_MIN; i < UNIV_MAX; i++) {
// Idiotic but simple
if (i % 3 != 0) {
continue;
}
bool was_added = tree.testInsert(CmpInt(i));
should_be_in_tree.insert(i);
CHECK(was_added);
CHECK(TreeIsPlausible(tree, should_be_in_tree, UNIV_MIN, UNIV_MAX));
}
// Then remove the middle half of the tree, also checking.
for (int i = UNIV_MIN + UNIV_SIZE / 4; i < UNIV_MIN + 3 * (UNIV_SIZE / 4);
i++) {
// Note that here, we're asking to delete a bunch of numbers that aren't
// in the tree. It should remain valid throughout.
bool was_removed = tree.testRemove(CmpInt(i));
bool should_have_been_removed = SetContains(should_be_in_tree, i);
CHECK(was_removed == should_have_been_removed);
should_be_in_tree.erase(i);
CHECK(TreeIsPlausible(tree, should_be_in_tree, UNIV_MIN, UNIV_MAX));
}
// Now add some numbers which are already in the tree.
for (int i = UNIV_MIN; i < UNIV_MIN + UNIV_SIZE / 4; i++) {
if (i % 3 != 0) {
continue;
}
bool was_added = tree.testInsert(CmpInt(i));
bool should_have_been_added = !SetContains(should_be_in_tree, i);
CHECK(was_added == should_have_been_added);
should_be_in_tree.insert(i);
CHECK(TreeIsPlausible(tree, should_be_in_tree, UNIV_MIN, UNIV_MAX));
}
// Then remove all numbers from the tree, in reverse order.
for (int ir = UNIV_MIN; ir < UNIV_MAX; ir++) {
int i = UNIV_MIN + (UNIV_MAX - ir);
bool was_removed = tree.testRemove(CmpInt(i));
bool should_have_been_removed = SetContains(should_be_in_tree, i);
CHECK(was_removed == should_have_been_removed);
should_be_in_tree.erase(i);
CHECK(TreeIsPlausible(tree, should_be_in_tree, UNIV_MIN, UNIV_MAX));
}
// Now the tree should be empty.
CHECK(should_be_in_tree.empty());
CHECK(tree.testSize() == 0);
// Now delete some more stuff. Tree should still be empty :-)
for (int i = UNIV_MIN + 10; i < UNIV_MIN + 100; i++) {
CHECK(should_be_in_tree.empty());
CHECK(tree.testSize() == 0);
bool was_removed = tree.testRemove(CmpInt(i));
CHECK(!was_removed);
CHECK(TreeIsPlausible(tree, should_be_in_tree, UNIV_MIN, UNIV_MAX));
}
// The tree root should be NULL.
CHECK(tree.testGetRoot() == nullptr);
CHECK(tree.testGetFreeList() != nullptr);
// Check the freelist to the extent we can: it's non-circular, and the
// elements look plausible. If it's not shorter than the specified length
// then it must have a cycle, since the tests above won't have resulted in
// more than 400 free nodes at the end.
CHECK(tree.testFreeListLooksValid(400 /*arbitrary*/));
// Test iteration, first in a tree with 9 nodes. This tests the general
// case.
{
CHECK(tree.testSize() == 0);
for (int i = 10; i < 100; i += 10) {
bool was_inserted = tree.testInsert(CmpInt(i));
CHECK(was_inserted);
}
// Test iteration across the whole tree.
AvlTreeTestIF<CmpInt, CmpInt>::Iter iter(&tree);
// `expect` produces (independently) the next expected number. `remaining`
// counts the number items of items remaining.
int expect = 10;
int remaining = 9;
while (iter.hasMore()) {
CmpInt ci = iter.next();
CHECK(ci.get() == expect);
expect += 10;
remaining--;
}
CHECK(remaining == 0);
// Test iteration from a specified start point.
for (int i = 10; i < 100; i += 10) {
for (int j = i - 1; j <= i + 1; j++) {
// Set up `expect` and `remaining`.
remaining = (100 - i) / 10;
switch (j % 10) {
case 0:
expect = j;
break;
case 1:
expect = j + 9;
remaining--;
break;
case 9:
expect = j + 1;
break;
default:
MOZ_CRASH();
}
AvlTreeTestIF<CmpInt, CmpInt>::Iter iter(&tree, CmpInt(j));
while (iter.hasMore()) {
CmpInt ci = iter.next();
CHECK(ci.get() == expect);
expect += 10;
remaining--;
}
CHECK(remaining == 0);
}
}
}
// Now with a completely empty tree.
{
AvlTreeTestIF<CmpInt, CmpInt> emptyTree(&alloc);
CHECK(emptyTree.testSize() == 0);
// Full tree iteration gets us nothing.
AvlTreeTestIF<CmpInt, CmpInt>::Iter iter1(&emptyTree);
CHECK(!iter1.hasMore());
// Starting iteration with any number gets us nothing.
AvlTreeTestIF<CmpInt, CmpInt>::Iter iter2(&emptyTree, CmpInt(42));
CHECK(!iter2.hasMore());
}
// Finally with a one-element tree.
{
AvlTreeTestIF<CmpInt, CmpInt> unitTree(&alloc);
bool was_inserted = unitTree.testInsert(CmpInt(1337));
CHECK(was_inserted);
CHECK(unitTree.testSize() == 1);
// Try full tree iteration.
AvlTreeTestIF<CmpInt, CmpInt>::Iter iter3(&unitTree);
CHECK(iter3.hasMore());
CmpInt ci = iter3.next();
CHECK(ci.get() == 1337);
CHECK(!iter3.hasMore());
for (int i = 1336; i <= 1338; i++) {
int remaining = i < 1338 ? 1 : 0;
int expect = i < 1338 ? 1337 : 99999 /*we'll never use this*/;
AvlTreeTestIF<CmpInt, CmpInt>::Iter iter4(&unitTree, CmpInt(i));
while (iter4.hasMore()) {
CmpInt ci = iter4.next();
CHECK(ci.get() == expect);
remaining--;
// expect doesn't change, we only expect it (or nothing)
}
CHECK(remaining == 0);
}
}
return true;
}
END_TEST(testAvlTree_main)