diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
tree | f435a8308119effd964b339f76abb83a57c29483 /js/src/jsapi-tests/testAvlTree.cpp | |
parent | Initial commit. (diff) | |
download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'js/src/jsapi-tests/testAvlTree.cpp')
-rw-r--r-- | js/src/jsapi-tests/testAvlTree.cpp | 383 |
1 files changed, 383 insertions, 0 deletions
diff --git a/js/src/jsapi-tests/testAvlTree.cpp b/js/src/jsapi-tests/testAvlTree.cpp new file mode 100644 index 0000000000..8d6e849955 --- /dev/null +++ b/js/src/jsapi-tests/testAvlTree.cpp @@ -0,0 +1,383 @@ +/* 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 <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) |