Deleted: trunk/Source/bmalloc/libpas/src/test/SkipListTests.cpp (286650 => 286651)
--- trunk/Source/bmalloc/libpas/src/test/SkipListTests.cpp 2021-12-08 11:05:54 UTC (rev 286650)
+++ trunk/Source/bmalloc/libpas/src/test/SkipListTests.cpp 2021-12-08 13:42:30 UTC (rev 286651)
@@ -1,440 +0,0 @@
-/*
- * Copyright (C) 2011-2020 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. Neither the name of Apple Inc. ("Apple") nor the names of
- * its contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-// This is based on WebKit's TestWebkitAPI test for WTF's RedBlackTree.
-
-#include "TestHarness.h"
-#include <algorithm>
-#include "pas_heap_lock.h"
-#include "pas_immortal_heap.h"
-#include "pas_skip_list_inlines.h"
-#include <sstream>
-#include <vector>
-
-using namespace std;
-
-namespace {
-
-static constexpr bool verbose = false;
-
-struct TestNode {
- TestNode(char key, unsigned value)
- : key(key)
- , value(value)
- {
- }
-
- char key;
- unsigned value;
-
- pas_skip_list_node node;
-
- static TestNode* fromSkipListNode(pas_skip_list_node* node)
- {
- if (!node)
- return NULL;
- return reinterpret_cast<TestNode*>(reinterpret_cast<char*>(node) -
- PAS_OFFSETOF(TestNode, node));
- }
-
- static int compareKey(pas_skip_list_node* aNode, void* bRaw)
- {
- TestNode* a = fromSkipListNode(aNode);
- char b = static_cast<char>(reinterpret_cast<uintptr_t>(bRaw));
-
- if (a->key < b)
- return -1;
- if (a->key == b)
- return 0;
- return 1;
- }
-
- static int compareKeyLeastGreaterThanOrEqual(pas_skip_list_node* aNode, void* bRaw)
- {
- TestNode* a = fromSkipListNode(aNode);
- char b = static_cast<char>(reinterpret_cast<uintptr_t>(bRaw));
-
- if (a->key < b)
- return -1;
- return 1;
- }
-
- static int compareKeyForInsert(pas_skip_list_node* aNode, void* bRaw)
- {
- TestNode* a = fromSkipListNode(aNode);
- char b = static_cast<char>(reinterpret_cast<uintptr_t>(bRaw));
-
- if (a->key <= b)
- return -1;
- return 1;
- }
-
- static int compare(pas_skip_list_node* aNode,
- pas_skip_list_node* bNode)
- {
- TestNode* a = fromSkipListNode(aNode);
- TestNode* b = fromSkipListNode(bNode);
-
- if (a->key < b->key)
- return -1;
- if (a->key == b->key)
- return 0;
- return 1;
- }
-};
-
-static unsigned counter;
-
-struct Pair {
- Pair() = default;
-
- Pair(char key, unsigned value)
- : key(key)
- , value(value)
- {
- }
-
- bool operator==(const Pair& other) const
- {
- return key == other.key;
- }
-
- bool operator<(const Pair& other) const
- {
- return key < other.key;
- }
-
- char key;
- unsigned value;
-};
-
-typedef vector<Pair> PairVector;
-
-PairVector findExact(PairVector& asVector, char key)
-{
- PairVector result;
-
- for (size_t index = 0; index < asVector.size(); ++index) {
- if (asVector[index].key == key)
- result.push_back(asVector[index]);
- }
-
- sort(result.begin(), result.end());
-
- return result;
-}
-
-void remove(PairVector& asVector, size_t index)
-{
- asVector[index] = asVector.back();
- asVector.pop_back();
-}
-
-PairVector findLeastGreaterThanOrEqual(PairVector& asVector, char key)
-{
- char bestKey = 0; // assignment to make gcc happy
- bool foundKey = false;
-
- for (size_t index = 0; index < asVector.size(); ++index) {
- if (asVector[index].key >= key) {
- if (asVector[index].key < bestKey || !foundKey) {
- foundKey = true;
- bestKey = asVector[index].key;
- }
- }
- }
-
- PairVector result;
-
- if (!foundKey)
- return result;
-
- return findExact(asVector, bestKey);
-}
-
-void assertFoundAndRemove(PairVector& asVector, char key, unsigned value)
-{
- bool found = false;
- size_t foundIndex = 0; // make compilers happy
-
- for (size_t index = 0; index < asVector.size(); ++index) {
- if (asVector[index].key == key
- && asVector[index].value == value) {
- CHECK(!found);
-
- found = true;
- foundIndex = index;
- }
- }
-
- CHECK(found);
-
- remove(asVector, foundIndex);
-}
-
-// This deliberately passes a copy of the vector.
-void assertEqual(pas_skip_list& asSkipList, PairVector asVector)
-{
- for (TestNode* current = TestNode::fromSkipListNode(pas_skip_list_head(&asSkipList));
- current;
- current = TestNode::fromSkipListNode(pas_skip_list_node_next(¤t->node)))
- assertFoundAndRemove(asVector, current->key, current->value);
- CHECK(asVector.empty());
-}
-
-void assertSameValuesForKey(pas_skip_list& asSkipList, TestNode* node,
- PairVector foundValues, char key)
-{
- if (node) {
- CHECK_EQUAL(node->key, key);
-
- TestNode* prevNode = node;
- do {
- node = prevNode;
- prevNode = TestNode::fromSkipListNode(pas_skip_list_node_prev(&prevNode->node));
- } while (prevNode && prevNode->key == key);
-
- if (verbose)
- printf("in assertSameValuesForKey, starting the search: node = %p\n", node);
-
- CHECK_EQUAL(node->key, key);
- CHECK(!prevNode || prevNode->key < key);
-
- do {
- if (verbose)
- printf("node = %p\n", node);
-
- assertFoundAndRemove(foundValues, node->key, node->value);
-
- node = TestNode::fromSkipListNode(pas_skip_list_node_next(&node->node));
- CHECK(!node || node->key >= key);
- } while (node && node->key == key);
- }
-
- CHECK(foundValues.empty());
-}
-
-void dumpSkipList(pas_skip_list& asSkipList, const char* prefix)
-{
- unsigned maxHeight = 0;
- for (pas_skip_list_node* node = pas_skip_list_head(&asSkipList);
- node;
- node = pas_skip_list_node_next(node))
- maxHeight = PAS_MAX(maxHeight, node->height);
- for (unsigned index = maxHeight; index--;) {
- cout << prefix;
- for (pas_skip_list_node* node = pas_skip_list_head(&asSkipList);
- node;
- node = pas_skip_list_node_next(node)) {
- if (node->height <= index) {
- cout << " ";
- continue;
- }
- cout << TestNode::fromSkipListNode(node)->key;
- }
- cout << "\n";
- }
-}
-
-void dumpVector(PairVector vector)
-{
- for (const Pair& pair : vector) {
- cout << pair.key;
- }
-}
-
-// The control string is a null-terminated list of commands. Each
-// command is two characters, with the first identifying the operation
-// and the second giving a key. The commands are:
-// +x Add x
-// *x Find all elements equal to x
-// @x Find all elements that have the smallest key that is greater than or equal to x
-// !x Remove all elements equal to x
-void testDriver(const char* controlString)
-{
- PairVector asVector;
- pas_skip_list asSkipList;
-
- pas_skip_list_construct(&asSkipList);
-
- for (const char* current = controlString; *current; current += 2) {
- char command = current[0];
- char key = current[1];
- unsigned value = ++counter;
-
- CHECK(command);
- CHECK(key);
-
- if (verbose)
- printf("Running command: %c%c\n", command, key);
-
- switch (command) {
- case '+': {
- pas_heap_lock_lock();
- TestNode* node = static_cast<TestNode*>(
- pas_skip_list_node_allocate(PAS_OFFSETOF(TestNode, node)));
- new (node) TestNode(key, value);
- pas_skip_list_insert(
- &asSkipList,
- reinterpret_cast<void*>(static_cast<uintptr_t>(key)),
- &node->node,
- TestNode::compareKeyForInsert);
- pas_heap_lock_unlock();
- asVector.push_back(Pair(key, value));
- break;
- }
-
- case '*': {
- pas_skip_list_find_result findResult = pas_skip_list_find(
- &asSkipList,
- reinterpret_cast<void*>(static_cast<uintptr_t>(key)),
- TestNode::compareKey);
- TestNode* node;
- if (findResult.did_find_exact)
- node = TestNode::fromSkipListNode(findResult.next);
- else
- node = nullptr;
- if (verbose)
- printf("Found node = %p\n", node);
- if (node)
- CHECK_EQUAL(node->key, key);
- assertSameValuesForKey(asSkipList, node, findExact(asVector, key), key);
- break;
- }
-
- case '@': {
- pas_skip_list_find_result findResult = pas_skip_list_find(
- &asSkipList,
- reinterpret_cast<void*>(static_cast<uintptr_t>(key)),
- TestNode::compareKeyLeastGreaterThanOrEqual);
- if (verbose) {
- cout << "SkipList:\n";
- dumpSkipList(asSkipList, " ");
- cout << "Vector: ";
- dumpVector(asVector);
- cout << "\n";
- }
- CHECK(!findResult.did_find_exact);
- TestNode* node = TestNode::fromSkipListNode(findResult.next);
- if (verbose)
- printf("Found node = %p\n", node);
- if (node) {
- CHECK_GREATER_EQUAL(node->key, key);
- assertSameValuesForKey(asSkipList, node, findLeastGreaterThanOrEqual(asVector, key), node->key);
- } else
- CHECK(findLeastGreaterThanOrEqual(asVector, key).empty());
- break;
- }
-
- case '!': {
- while (true) {
- pas_skip_list_find_result findResult = pas_skip_list_find(
- &asSkipList,
- reinterpret_cast<void*>(static_cast<uintptr_t>(key)),
- TestNode::compareKey);
- TestNode* node;
- if (findResult.did_find_exact)
- node = TestNode::fromSkipListNode(findResult.next);
- else
- node = nullptr;
- if (node) {
- pas_skip_list_remove(&asSkipList, &node->node);
- CHECK_EQUAL(node->key, key);
- assertFoundAndRemove(asVector, node->key, node->value);
- } else {
- CHECK(findExact(asVector, key).empty());
- break;
- }
- }
- break;
- }
-
- default:
- CHECK(!"bad command");
- break;
- }
-
- CHECK_EQUAL(pas_skip_list_size(&asSkipList), asVector.size());
- pas_skip_list_validate(&asSkipList, TestNode::compare);
- assertEqual(asSkipList, asVector);
- }
-}
-
-void randomTestDriver(unsigned numAddOperations, unsigned numOperations)
-{
- ostringstream out;
- const char* things = "abcdefghijklmnopqrstuvwxyzQWERTYUIOPASDFGHJKLZXCVBNM1234567890";
- const char* operations = "+*@!";
- auto randomChar =
- [] (const char* things) -> char {
- return things[deterministicRandomNumber(static_cast<unsigned>(strlen(things)))];
- };
- for (unsigned index = numAddOperations; index--;) {
- out << "+" << randomChar(things);
- }
- for (unsigned index = numOperations; index--;) {
- out << randomChar(operations) << randomChar(things);
- }
- string str = out.str();
- if (verbose)
- cout << " Operation string: " << str << "\n";
- testDriver(str.c_str());
-}
-
-} // anonymous namespace
-
-void addSkipListTests()
-{
- ADD_TEST(testDriver(""));
- ADD_TEST(testDriver("*x@y!z"));
- ADD_TEST(testDriver("+a"));
- ADD_TEST(testDriver("+a*x@y!z"));
- ADD_TEST(testDriver("+a*a@a!a"));
- ADD_TEST(testDriver("+a+b"));
- ADD_TEST(testDriver("+a+b+c"));
- ADD_TEST(testDriver("+a+b+c+d"));
- ADD_TEST(testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d"));
- ADD_TEST(testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z"));
- ADD_TEST(testDriver("+z+y+x+w+v+u+t+s+r+q+p+o+n+m+l+k+j+i+h+g+f+e+d+c+b+a*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z"));
- ADD_TEST(testDriver("+z+y+x+w+v+u+t+s+r+q+p+o+n+m+l+k+j+i+h+g+f+e+d+c+b+a*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!z!y!x!w!v!u!t!s!r!q!p!o!n!m!l!k!j!i!h!g!f!e!d!c!b!a"));
- ADD_TEST(testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z"));
- ADD_TEST(testDriver("+d+d+m+w@d@m@w@a@g@q"));
- ADD_TEST(testDriver("+d+d+d+d+d+d+d+d+d+d+f+f+f+f+f+f+f+h+h+i+j+k+l+m+o+p+q+r+z@a@b@c@d@e@f@g@h@i@j@k@l@m@n@o@p@q@r@s@t@u@v@w@x@y@z"));
- ADD_TEST(randomTestDriver(10, 1000));
- ADD_TEST(randomTestDriver(20, 1000));
- ADD_TEST(randomTestDriver(30, 1000));
- ADD_TEST(randomTestDriver(40, 1000));
- ADD_TEST(randomTestDriver(50, 1000));
- ADD_TEST(randomTestDriver(100, 1000));
- ADD_TEST(randomTestDriver(1000, 1000));
- ADD_TEST(randomTestDriver(10, 10000));
- ADD_TEST(randomTestDriver(20, 10000));
- ADD_TEST(randomTestDriver(100, 10000));
- ADD_TEST(randomTestDriver(1000, 10000));
-}
-
