// Copyright (c) 2005, Google 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:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * 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.
// * Neither the name of Google Inc. 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 THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT
// OWNER OR 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.
// ---
//
// Since sparsetable is templatized, it's important that we test every
// function in every class in this file -- not just to see if it
// works, but even if it compiles.
#include <sparsehash/internal/sparseconfig.h>
#include <config.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h> // for size_t
#include <stdlib.h> // defines unlink() on some windows platforms(?)
#ifdef HAVE_UNISTD_H
# include <unistd.h>
#endif // for unlink()
#include <memory> // for allocator
#include <string>
#include <sparsehash/sparsetable>
using std::string;
using std::allocator;
using GOOGLE_NAMESPACE::sparsetable;
using GOOGLE_NAMESPACE::DEFAULT_SPARSEGROUP_SIZE;
typedef u_int16_t uint16;
string FLAGS_test_tmpdir = "/tmp/";
// Many sparsetable operations return a size_t. Rather than have to
// use PRIuS everywhere, we'll just cast to a "big enough" value.
#define UL(x) ( static_cast<unsigned long>(x) )
static char outbuf[10240]; // big enough for these tests
static char* out = outbuf; // where to write next
#define LEFT (outbuf + sizeof(outbuf) - out)
#define TEST(cond) out += snprintf(out, LEFT, #cond "? %s\n", \
(cond) ? "yes" : "no");
inline string AsString(int n) {
const int N = 64;
char buf[N];
snprintf(buf, N, "%d", n);
return string(buf);
}
// Test sparsetable with a POD type, int.
void TestInt() {
out += snprintf(out, LEFT, "int test\n");
sparsetable<int> x(7), y(70), z;
x.set(4, 10);
y.set(12, -12);
y.set(47, -47);
y.set(48, -48);
y.set(49, -49);
const sparsetable<int> constx(x);
const sparsetable<int> consty(y);
// ----------------------------------------------------------------------
// Test the plain iterators
for ( sparsetable<int>::iterator it = x.begin(); it != x.end(); ++it ) {
out += snprintf(out, LEFT, "x[%lu]: %d\n", UL(it - x.begin()), int(*it));
}
for ( sparsetable<int>::const_iterator it = x.begin(); it != x.end(); ++it ) {
out += snprintf(out, LEFT, "x[%lu]: %d\n", UL(it - x.begin()), *it);
}
for ( sparsetable<int>::reverse_iterator it = x.rbegin(); it != x.rend(); ++it ) {
out += snprintf(out, LEFT, "x[%lu]: %d\n", UL(x.rend()-1 - it), int(*it));
}
for ( sparsetable<int>::const_reverse_iterator it = constx.rbegin(); it != constx.rend(); ++it ) {
out += snprintf(out, LEFT, "x[%lu]: %d\n", UL(constx.rend()-1 - it), *it);
}
for ( sparsetable<int>::iterator it = z.begin(); it != z.end(); ++it ) {
out += snprintf(out, LEFT, "z[%lu]: %d\n", UL(it - z.begin()), int(*it));
}
{ // array version
out += snprintf(out, LEFT, "x[3]: %d\n", int(x[3]));
out += snprintf(out, LEFT, "x[4]: %d\n", int(x[4]));
out += snprintf(out, LEFT, "x[5]: %d\n", int(x[5]));
}
{
sparsetable<int>::iterator it; // non-const version
out += snprintf(out, LEFT, "x[4]: %d\n", int(x.begin()[4]));
it = x.begin() + 4; // should point to the non-zero value
out += snprintf(out, LEFT, "x[4]: %d\n", int(*it));
it--;
--it;
it += 5;
it -= 2;
it++;
++it;
it = it - 3;
it = 1 + it; // now at 5
out += snprintf(out, LEFT, "x[3]: %d\n", int(it[-2]));
out += snprintf(out, LEFT, "x[4]: %d\n", int(it[-1]));
*it = 55;
out += snprintf(out, LEFT, "x[5]: %d\n", int(it[0]));
out += snprintf(out, LEFT, "x[5]: %d\n", int(*it));
int *x6 = &(it[1]);
*x6 = 66;
out += snprintf(out, LEFT, "x[6]: %d\n", int(*(it + 1)));
// Let's test comparitors as well
TEST(it == it);
TEST(!(it != it));
TEST(!(it < it));
TEST(!(it > it));
TEST(it <= it);
TEST(it >= it);
sparsetable<int>::iterator it_minus_1 = it - 1;
TEST(!(it == it_minus_1));
TEST(it != it_minus_1);
TEST(!(it < it_minus_1));
TEST(it > it_minus_1);
TEST(!(it <= it_minus_1));
TEST(it >= it_minus_1);
TEST(!(it_minus_1 == it));
TEST(it_minus_1 != it);
TEST(it_minus_1 < it);
TEST(!(it_minus_1 > it));
TEST(it_minus_1 <= it);
TEST(!(it_minus_1 >= it));
sparsetable<int>::iterator it_plus_1 = it + 1;
TEST(!(it == it_plus_1));
TEST(it != it_plus_1);
TEST(it < it_plus_1);
TEST(!(it > it_plus_1));
TEST(it <= it_plus_1);
TEST(!(it >= it_plus_1));
TEST(!(it_plus_1 == it));
TEST(it_plus_1 != it);
TEST(!(it_plus_1 < it));
TEST(it_plus_1 > it);
TEST(!(it_plus_1 <= it));
TEST(it_plus_1 >= it);
}
{
sparsetable<int>::const_iterator it; // const version
out += snprintf(out, LEFT, "x[4]: %d\n", int(x.begin()[4]));
it = x.begin() + 4; // should point to the non-zero value
out += snprintf(out, LEFT, "x[4]: %d\n", *it);
it--;
--it;
it += 5;
it -= 2;
it++;
++it;
it = it - 3;
it = 1 + it; // now at 5
out += snprintf(out, LEFT, "x[3]: %d\n", it[-2]);
out += snprintf(out, LEFT, "x[4]: %d\n", it[-1]);
out += snprintf(out, LEFT, "x[5]: %d\n", *it);
out += snprintf(out, LEFT, "x[6]: %d\n", *(it + 1));
// Let's test comparitors as well
TEST(it == it);
TEST(!(it != it));
TEST(!(it < it));
TEST(!(it > it));
TEST(it <= it);
TEST(it >= it);
sparsetable<int>::const_iterator it_minus_1 = it - 1;
TEST(!(it == it_minus_1));
TEST(it != it_minus_1);
TEST(!(it < it_minus_1));
TEST(it > it_minus_1);
TEST(!(it <= it_minus_1));
TEST(it >= it_minus_1);
TEST(!(it_minus_1 == it));
TEST(it_minus_1 != it);
TEST(it_minus_1 < it);
TEST(!(it_minus_1 > it));
TEST(it_minus_1 <= it);
TEST(!(it_minus_1 >= it));
sparsetable<int>::const_iterator it_plus_1 = it + 1;
TEST(!(it == it_plus_1));
TEST(it != it_plus_1);
TEST(it < it_plus_1);
TEST(!(it > it_plus_1));
TEST(it <= it_plus_1);
TEST(!(it >= it_plus_1));
TEST(!(it_plus_1 == it));
TEST(it_plus_1 != it);
TEST(!(it_plus_1 < it));
TEST(it_plus_1 > it);
TEST(!(it_plus_1 <= it));
TEST(it_plus_1 >= it);
}
TEST(x.begin() == x.begin() + 1 - 1);
TEST(x.begin() < x.end());
TEST(z.begin() < z.end());
TEST(z.begin() <= z.end());
TEST(z.begin() == z.end());
// ----------------------------------------------------------------------
// Test the non-empty iterators
for ( sparsetable<int>::nonempty_iterator it = x.nonempty_begin(); it != x.nonempty_end(); ++it ) {
out += snprintf(out, LEFT, "x[??]: %d\n", *it);
}
for ( sparsetable<int>::const_nonempty_iterator it = y.nonempty_begin(); it != y.nonempty_end(); ++it ) {
out += snprintf(out, LEFT, "y[??]: %d\n", *it);
}
for ( sparsetable<int>::reverse_nonempty_iterator it = y.nonempty_rbegin(); it != y.nonempty_rend(); ++it ) {
out += snprintf(out, LEFT, "y[??]: %d\n", *it);
}
for ( sparsetable<int>::const_reverse_nonempty_iterator it = consty.nonempty_rbegin(); it != consty.nonempty_rend(); ++it ) {
out += snprintf(out, LEFT, "y[??]: %d\n", *it);
}
for ( sparsetable<int>::nonempty_iterator it = z.nonempty_begin(); it != z.nonempty_end(); ++it ) {
out += snprintf(out, LEFT, "z[??]: %d\n", *it);
}
{
sparsetable<int>::nonempty_iterator it; // non-const version
out += snprintf(out, LEFT, "first non-empty y: %d\n", *y.nonempty_begin());
out += snprintf(out, LEFT, "first non-empty x: %d\n", *x.nonempty_begin());
it = x.nonempty_begin();
++it; // should be at end
--it;
out += snprintf(out, LEFT, "first non-empty x: %d\n", *it++);
it--;
out += snprintf(out, LEFT, "first non-empty x: %d\n", *it++);
}
{
sparsetable<int>::const_nonempty_iterator it; // non-const version
out += snprintf(out, LEFT, "first non-empty y: %d\n", *y.nonempty_begin());
out += snprintf(out, LEFT, "first non-empty x: %d\n", *x.nonempty_begin());
it = x.nonempty_begin();
++it; // should be at end
--it;
out += snprintf(out, LEFT, "first non-empty x: %d\n", *it++);
it--;
out += snprintf(out, LEFT, "first non-empty x: %d\n", *it++);
}
TEST(x.begin() == x.begin() + 1 - 1);
TEST(z.begin() != z.end());
// ----------------------------------------------------------------------
// Test the non-empty iterators get_pos function
sparsetable<unsigned int> gp(100);
for (int i = 0; i < 100; i += 9) {
gp.set(i,i);
}
for (sparsetable<unsigned int>::const_nonempty_iterator
it = gp.nonempty_begin(); it != gp.nonempty_end(); ++it) {
out += snprintf(out, LEFT,
"get_pos() for const nonempty_iterator: %u == %lu\n",
*it, UL(gp.get_pos(it)));
}
for (sparsetable<unsigned int>::nonempty_iterator
it = gp.nonempty_begin(); it != gp.nonempty_end(); ++it) {
out += snprintf(out, LEFT,
"get_pos() for nonempty_iterator: %u == %lu\n",
*it, UL(gp.get_pos(it)));
}
// ----------------------------------------------------------------------
// Test sparsetable functions
out += snprintf(out, LEFT, "x has %lu/%lu buckets, "
"y %lu/%lu, z %lu/%lu\n",
UL(x.num_nonempty()), UL(x.size()),
UL(y.num_nonempty()), UL(y.size()),
UL(z.num_nonempty()), UL(z.size()));
y.resize(48); // should get rid of 48 and 49
y.resize(70); // 48 and 49 should still be gone
out += snprintf(out, LEFT, "y shrank and grew: it's now %lu/%lu\n",
UL(y.num_nonempty()), UL(y.size()));
out += snprintf(out, LEFT, "y[12] = %d, y.get(12) = %d\n", int(y[12]), y.get(12));
y.erase(12);
out += snprintf(out, LEFT, "y[12] cleared. y now %lu/%lu. "
"y[12] = %d, y.get(12) = %d\n",
UL(y.num_nonempty()), UL(y.size()), int(y[12]), y.get(12));
swap(x, y);
y.clear();
TEST(y == z);
y.resize(70);
for ( int i = 10; i < 40; ++i )
y[i] = -i;
y.erase(y.begin() + 15, y.begin() + 30);
y.erase(y.begin() + 34);
y.erase(12);
y.resize(38);
y.resize(10000);
y[9898] = -9898;
for ( sparsetable<int>::const_iterator it = y.begin(); it != y.end(); ++it ) {
if ( y.test(it) )
out += snprintf(out, LEFT, "y[%lu] is set\n", UL(it - y.begin()));
}
out += snprintf(out, LEFT, "That's %lu set buckets\n", UL(y.num_nonempty()));
out += snprintf(out, LEFT, "Starting from y[32]...\n");
for ( sparsetable<int>::const_nonempty_iterator it = y.get_iter(32);
it != y.nonempty_end(); ++it )
out += snprintf(out, LEFT, "y[??] = %d\n", *it);
out += snprintf(out, LEFT, "From y[32] down...\n");
for ( sparsetable<int>::nonempty_iterator it = y.get_iter(32);
it != y.nonempty_begin(); )
out += snprintf(out, LEFT, "y[??] = %d\n", *--it);
// ----------------------------------------------------------------------
// Test I/O using deprecated read/write_metadata
string filestr = FLAGS_test_tmpdir + "/.sparsetable.test";
const char *file = filestr.c_str();
FILE *fp = fopen(file, "wb");
if ( fp == NULL ) {
// maybe we can't write to /tmp/. Try the current directory
file = ".sparsetable.test";
fp = fopen(file, "wb");
}
if ( fp == NULL ) {
out += snprintf(out, LEFT, "Can't open %s, skipping disk write...\n", file);
} else {
y.write_metadata(fp); // only write meta-information
y.write_nopointer_data(fp);
fclose(fp);
}
fp = fopen(file, "rb");
if ( fp == NULL ) {
out += snprintf(out, LEFT, "Can't open %s, skipping disk read...\n", file);
} else {
sparsetable<int> y2;
y2.read_metadata(fp);
y2.read_nopointer_data(fp);
fclose(fp);
for ( sparsetable<int>::const_iterator it = y2.begin(); it != y2.end(); ++it ) {
if ( y2.test(it) )
out += snprintf(out, LEFT, "y2[%lu] is %d\n", UL(it - y2.begin()), *it);
}
out += snprintf(out, LEFT, "That's %lu set buckets\n", UL(y2.num_nonempty()));
}
unlink(file);
// ----------------------------------------------------------------------
// Also test I/O using serialize()/unserialize()
fp = fopen(file, "wb");
if ( fp == NULL ) {
out += snprintf(out, LEFT, "Can't open %s, skipping disk write...\n", file);
} else {
y.serialize(sparsetable<int>::NopointerSerializer(), fp);
fclose(fp);
}
fp = fopen(file, "rb");
if ( fp == NULL ) {
out += snprintf(out, LEFT, "Can't open %s, skipping disk read...\n", file);
} else {
sparsetable<int> y2;
y2.unserialize(sparsetable<int>::NopointerSerializer(), fp);
fclose(fp);
for ( sparsetable<int>::const_iterator it = y2.begin(); it != y2.end(); ++it ) {
if ( y2.test(it) )
out += snprintf(out, LEFT, "y2[%lu] is %d\n", UL(it - y2.begin()), *it);
}
out += snprintf(out, LEFT, "That's %lu set buckets\n", UL(y2.num_nonempty()));
}
unlink(file);
}
// Test sparsetable with a non-POD type, std::string
void TestString() {
out += snprintf(out, LEFT, "string test\n");
sparsetable<string> x(7), y(70), z;
x.set(4, "foo");
y.set(12, "orange");
y.set(47, "grape");
y.set(48, "pear");
y.set(49, "apple");
// ----------------------------------------------------------------------
// Test the plain iterators
for ( sparsetable<string>::iterator it = x.begin(); it != x.end(); ++it ) {
out += snprintf(out, LEFT, "x[%lu]: %s\n",
UL(it - x.begin()), static_cast<string>(*it).c_str());
}
for ( sparsetable<string>::iterator it = z.begin(); it != z.end(); ++it ) {
out += snprintf(out, LEFT, "z[%lu]: %s\n",
UL(it - z.begin()), static_cast<string>(*it).c_str());
}
TEST(x.begin() == x.begin() + 1 - 1);
TEST(x.begin() < x.end());
TEST(z.begin() < z.end());
TEST(z.begin() <= z.end());
TEST(z.begin() == z.end());
// ----------------------------------------------------------------------
// Test the non-empty iterators
for ( sparsetable<string>::nonempty_iterator it = x.nonempty_begin(); it != x.nonempty_end(); ++it ) {
out += snprintf(out, LEFT, "x[??]: %s\n", it->c_str());
}
for ( sparsetable<string>::const_nonempty_iterator it = y.nonempty_begin(); it != y.nonempty_end(); ++it ) {
out += snprintf(out, LEFT, "y[??]: %s\n", it->c_str());
}
for ( sparsetable<string>::nonempty_iterator it = z.nonempty_begin(); it != z.nonempty_end(); ++it ) {
out += snprintf(out, LEFT, "z[??]: %s\n", it->c_str());
}
// ----------------------------------------------------------------------
// Test sparsetable functions
out += snprintf(out, LEFT, "x has %lu/%lu buckets, y %lu/%lu, z %lu/%lu\n",
UL(x.num_nonempty()), UL(x.size()),
UL(y.num_nonempty()), UL(y.size()),
UL(z.num_nonempty()), UL(z.size()));
y.resize(48); // should get rid of 48 and 49
y.resize(70); // 48 and 49 should still be gone
out += snprintf(out, LEFT, "y shrank and grew: it's now %lu/%lu\n",
UL(y.num_nonempty()), UL(y.size()));
out += snprintf(out, LEFT, "y[12] = %s, y.get(12) = %s\n",
static_cast<string>(y[12]).c_str(), y.get(12).c_str());
y.erase(12);
out += snprintf(out, LEFT, "y[12] cleared. y now %lu/%lu. "
"y[12] = %s, y.get(12) = %s\n",
UL(y.num_nonempty()), UL(y.size()),
static_cast<string>(y[12]).c_str(),
static_cast<string>(y.get(12)).c_str());
swap(x, y);
y.clear();
TEST(y == z);
y.resize(70);
for ( int i = 10; i < 40; ++i )
y.set(i, AsString(-i));
y.erase(y.begin() + 15, y.begin() + 30);
y.erase(y.begin() + 34);
y.erase(12);
y.resize(38);
y.resize(10000);
y.set(9898, AsString(-9898));
for ( sparsetable<string>::const_iterator it = y.begin(); it != y.end(); ++it ) {
if ( y.test(it) )
out += snprintf(out, LEFT, "y[%lu] is set\n", UL(it - y.begin()));
}
out += snprintf(out, LEFT, "That's %lu set buckets\n", UL(y.num_nonempty()));
out += snprintf(out, LEFT, "Starting from y[32]...\n");
for ( sparsetable<string>::const_nonempty_iterator it = y.get_iter(32);
it != y.nonempty_end(); ++it )
out += snprintf(out, LEFT, "y[??] = %s\n", it->c_str());
out += snprintf(out, LEFT, "From y[32] down...\n");
for ( sparsetable<string>::nonempty_iterator it = y.get_iter(32);
it != y.nonempty_begin(); )
out += snprintf(out, LEFT, "y[??] = %s\n", (*--it).c_str());
}
// An instrumented allocator that keeps track of all calls to
// allocate/deallocate/construct/destroy. It stores the number of times
// they were called and the values they were called with. Such information is
// stored in the following global variables.
static size_t sum_allocate_bytes;
static size_t sum_deallocate_bytes;
void ResetAllocatorCounters() {
sum_allocate_bytes = 0;
sum_deallocate_bytes = 0;
}
template <class T> class instrumented_allocator {
public:
typedef T value_type;
typedef uint16 size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
instrumented_allocator() {}
instrumented_allocator(const instrumented_allocator&) {}
~instrumented_allocator() {}
pointer address(reference r) const { return &r; }
const_pointer address(const_reference r) const { return &r; }
pointer allocate(size_type n, const_pointer = 0) {
sum_allocate_bytes += n * sizeof(value_type);
return static_cast<pointer>(malloc(n * sizeof(value_type)));
}
void deallocate(pointer p, size_type n) {
sum_deallocate_bytes += n * sizeof(value_type);
free(p);
}
size_type max_size() const {
return static_cast<size_type>(-1) / sizeof(value_type);
}
void construct(pointer p, const value_type& val) {
new(p) value_type(val);
}
void destroy(pointer p) {
p->~value_type();
}
template <class U>
explicit instrumented_allocator(const instrumented_allocator<U>&) {}
template<class U>
struct rebind {
typedef instrumented_allocator<U> other;
};
private:
void operator=(const instrumented_allocator&);
};
template<class T>
inline bool operator==(const instrumented_allocator<T>&,
const instrumented_allocator<T>&) {
return true;
}
template<class T>
inline bool operator!=(const instrumented_allocator<T>&,
const instrumented_allocator<T>&) {
return false;
}
// Test sparsetable with instrumented_allocator.
void TestAllocator() {
out += snprintf(out, LEFT, "allocator test\n");
ResetAllocatorCounters();
// POD (int32) with instrumented_allocator.
typedef sparsetable<int, DEFAULT_SPARSEGROUP_SIZE,
instrumented_allocator<int> > IntSparseTable;
IntSparseTable* s1 = new IntSparseTable(10000);
TEST(sum_allocate_bytes > 0);
for (int i = 0; i < 10000; ++i) {
s1->set(i, 0);
}
TEST(sum_allocate_bytes >= 10000 * sizeof(int));
ResetAllocatorCounters();
delete s1;
TEST(sum_deallocate_bytes >= 10000 * sizeof(int));
IntSparseTable* s2 = new IntSparseTable(1000);
IntSparseTable* s3 = new IntSparseTable(1000);
for (int i = 0; i < 1000; ++i) {
s2->set(i, 0);
s3->set(i, 0);
}
TEST(sum_allocate_bytes >= 2000 * sizeof(int));
ResetAllocatorCounters();
s3->clear();
TEST(sum_deallocate_bytes >= 1000 * sizeof(int));
ResetAllocatorCounters();
s2->swap(*s3); // s2 is empty after the swap
s2->clear();
TEST(sum_deallocate_bytes < 1000 * sizeof(int));
for (int i = 0; i < s3->size(); ++i) {
s3->erase(i);
}
TEST(sum_deallocate_bytes >= 1000 * sizeof(int));
delete s2;
delete s3;
// POD (int) with default allocator.
sparsetable<int> x, y;
for (int s = 1000; s <= 40000; s += 1000) {
x.resize(s);
for (int i = 0; i < s; ++i) {
x.set(i, i + 1);
}
y = x;
for (int i = 0; i < s; ++i) {
y.erase(i);
}
y.swap(x);
}
TEST(x.num_nonempty() == 0);
out += snprintf(out, LEFT, "y[0]: %d\n", int(y[0]));
out += snprintf(out, LEFT, "y[39999]: %d\n", int(y[39999]));
y.clear();
// POD (int) with std allocator.
sparsetable<int, DEFAULT_SPARSEGROUP_SIZE, allocator<int> > u, v;
for (int s = 1000; s <= 40000; s += 1000) {
u.resize(s);
for (int i = 0; i < s; ++i) {
u.set(i, i + 1);
}
v = u;
for (int i = 0; i < s; ++i) {
v.erase(i);
}
v.swap(u);
}
TEST(u.num_nonempty() == 0);
out += snprintf(out, LEFT, "v[0]: %d\n", int(v[0]));
out += snprintf(out, LEFT, "v[39999]: %d\n", int(v[39999]));
v.clear();
// Non-POD (string) with default allocator.
sparsetable<string> a, b;
for (int s = 1000; s <= 40000; s += 1000) {
a.resize(s);
for (int i = 0; i < s; ++i) {
a.set(i, "aa");
}
b = a;
for (int i = 0; i < s; ++i) {
b.erase(i);
}
b.swap(a);
}
TEST(a.num_nonempty() == 0);
out += snprintf(out, LEFT, "b[0]: %s\n", b.get(0).c_str());
out += snprintf(out, LEFT, "b[39999]: %s\n", b.get(39999).c_str());
b.clear();
}
// The expected output from all of the above: TestInt(), TestString() and
// TestAllocator().
static const char g_expected[] = (
"int test\n"
"x[0]: 0\n"
"x[1]: 0\n"
"x[2]: 0\n"
"x[3]: 0\n"
"x[4]: 10\n"
"x[5]: 0\n"
"x[6]: 0\n"
"x[0]: 0\n"
"x[1]: 0\n"
"x[2]: 0\n"
"x[3]: 0\n"
"x[4]: 10\n"
"x[5]: 0\n"
"x[6]: 0\n"
"x[6]: 0\n"
"x[5]: 0\n"
"x[4]: 10\n"
"x[3]: 0\n"
"x[2]: 0\n"
"x[1]: 0\n"
"x[0]: 0\n"
"x[6]: 0\n"
"x[5]: 0\n"
"x[4]: 10\n"
"x[3]: 0\n"
"x[2]: 0\n"
"x[1]: 0\n"
"x[0]: 0\n"
"x[3]: 0\n"
"x[4]: 10\n"
"x[5]: 0\n"
"x[4]: 10\n"
"x[4]: 10\n"
"x[3]: 0\n"
"x[4]: 10\n"
"x[5]: 55\n"
"x[5]: 55\n"
"x[6]: 66\n"
"it == it? yes\n"
"!(it != it)? yes\n"
"!(it < it)? yes\n"
"!(it > it)? yes\n"
"it <= it? yes\n"
"it >= it? yes\n"
"!(it == it_minus_1)? yes\n"
"it != it_minus_1? yes\n"
"!(it < it_minus_1)? yes\n"
"it > it_minus_1? yes\n"
"!(it <= it_minus_1)? yes\n"
"it >= it_minus_1? yes\n"
"!(it_minus_1 == it)? yes\n"
"it_minus_1 != it? yes\n"
"it_minus_1 < it? yes\n"
"!(it_minus_1 > it)? yes\n"
"it_minus_1 <= it? yes\n"
"!(it_minus_1 >= it)? yes\n"
"!(it == it_plus_1)? yes\n"
"it != it_plus_1? yes\n"
"it < it_plus_1? yes\n"
"!(it > it_plus_1)? yes\n"
"it <= it_plus_1? yes\n"
"!(it >= it_plus_1)? yes\n"
"!(it_plus_1 == it)? yes\n"
"it_plus_1 != it? yes\n"
"!(it_plus_1 < it)? yes\n"
"it_plus_1 > it? yes\n"
"!(it_plus_1 <= it)? yes\n"
"it_plus_1 >= it? yes\n"
"x[4]: 10\n"
"x[4]: 10\n"
"x[3]: 0\n"
"x[4]: 10\n"
"x[5]: 55\n"
"x[6]: 66\n"
"it == it? yes\n"
"!(it != it)? yes\n"
"!(it < it)? yes\n"
"!(it > it)? yes\n"
"it <= it? yes\n"
"it >= it? yes\n"
"!(it == it_minus_1)? yes\n"
"it != it_minus_1? yes\n"
"!(it < it_minus_1)? yes\n"
"it > it_minus_1? yes\n"
"!(it <= it_minus_1)? yes\n"
"it >= it_minus_1? yes\n"
"!(it_minus_1 == it)? yes\n"
"it_minus_1 != it? yes\n"
"it_minus_1 < it? yes\n"
"!(it_minus_1 > it)? yes\n"
"it_minus_1 <= it? yes\n"
"!(it_minus_1 >= it)? yes\n"
"!(it == it_plus_1)? yes\n"
"it != it_plus_1? yes\n"
"it < it_plus_1? yes\n"
"!(it > it_plus_1)? yes\n"
"it <= it_plus_1? yes\n"
"!(it >= it_plus_1)? yes\n"
"!(it_plus_1 == it)? yes\n"
"it_plus_1 != it? yes\n"
"!(it_plus_1 < it)? yes\n"
"it_plus_1 > it? yes\n"
"!(it_plus_1 <= it)? yes\n"
"it_plus_1 >= it? yes\n"
"x.begin() == x.begin() + 1 - 1? yes\n"
"x.begin() < x.end()? yes\n"
"z.begin() < z.end()? no\n"
"z.begin() <= z.end()? yes\n"
"z.begin() == z.end()? yes\n"
"x[??]: 10\n"
"x[??]: 55\n"
"x[??]: 66\n"
"y[??]: -12\n"
"y[??]: -47\n"
"y[??]: -48\n"
"y[??]: -49\n"
"y[??]: -49\n"
"y[??]: -48\n"
"y[??]: -47\n"
"y[??]: -12\n"
"y[??]: -49\n"
"y[??]: -48\n"
"y[??]: -47\n"
"y[??]: -12\n"
"first non-empty y: -12\n"
"first non-empty x: 10\n"
"first non-empty x: 10\n"
"first non-empty x: 10\n"
"first non-empty y: -12\n"
"first non-empty x: 10\n"
"first non-empty x: 10\n"
"first non-empty x: 10\n"
"x.begin() == x.begin() + 1 - 1? yes\n"
"z.begin() != z.end()? no\n"
"get_pos() for const nonempty_iterator: 0 == 0\n"
"get_pos() for const nonempty_iterator: 9 == 9\n"
"get_pos() for const nonempty_iterator: 18 == 18\n"
"get_pos() for const nonempty_iterator: 27 == 27\n"
"get_pos() for const nonempty_iterator: 36 == 36\n"
"get_pos() for const nonempty_iterator: 45 == 45\n"
"get_pos() for const nonempty_iterator: 54 == 54\n"
"get_pos() for const nonempty_iterator: 63 == 63\n"
"get_pos() for const nonempty_iterator: 72 == 72\n"
"get_pos() for const nonempty_iterator: 81 == 81\n"
"get_pos() for const nonempty_iterator: 90 == 90\n"
"get_pos() for const nonempty_iterator: 99 == 99\n"
"get_pos() for nonempty_iterator: 0 == 0\n"
"get_pos() for nonempty_iterator: 9 == 9\n"
"get_pos() for nonempty_iterator: 18 == 18\n"
"get_pos() for nonempty_iterator: 27 == 27\n"
"get_pos() for nonempty_iterator: 36 == 36\n"
"get_pos() for nonempty_iterator: 45 == 45\n"
"get_pos() for nonempty_iterator: 54 == 54\n"
"get_pos() for nonempty_iterator: 63 == 63\n"
"get_pos() for nonempty_iterator: 72 == 72\n"
"get_pos() for nonempty_iterator: 81 == 81\n"
"get_pos() for nonempty_iterator: 90 == 90\n"
"get_pos() for nonempty_iterator: 99 == 99\n"
"x has 3/7 buckets, y 4/70, z 0/0\n"
"y shrank and grew: it's now 2/70\n"
"y[12] = -12, y.get(12) = -12\n"
"y[12] cleared. y now 1/70. y[12] = 0, y.get(12) = 0\n"
"y == z? no\n"
"y[10] is set\n"
"y[11] is set\n"
"y[13] is set\n"
"y[14] is set\n"
"y[30] is set\n"
"y[31] is set\n"
"y[32] is set\n"
"y[33] is set\n"
"y[35] is set\n"
"y[36] is set\n"
"y[37] is set\n"
"y[9898] is set\n"
"That's 12 set buckets\n"
"Starting from y[32]...\n"
"y[??] = -32\n"
"y[??] = -33\n"
"y[??] = -35\n"
"y[??] = -36\n"
"y[??] = -37\n"
"y[??] = -9898\n"
"From y[32] down...\n"
"y[??] = -31\n"
"y[??] = -30\n"
"y[??] = -14\n"
"y[??] = -13\n"
"y[??] = -11\n"
"y[??] = -10\n"
"y2[10] is -10\n"
"y2[11] is -11\n"
"y2[13] is -13\n"
"y2[14] is -14\n"
"y2[30] is -30\n"
"y2[31] is -31\n"
"y2[32] is -32\n"
"y2[33] is -33\n"
"y2[35] is -35\n"
"y2[36] is -36\n"
"y2[37] is -37\n"
"y2[9898] is -9898\n"
"That's 12 set buckets\n"
"y2[10] is -10\n"
"y2[11] is -11\n"
"y2[13] is -13\n"
"y2[14] is -14\n"
"y2[30] is -30\n"
"y2[31] is -31\n"
"y2[32] is -32\n"
"y2[33] is -33\n"
"y2[35] is -35\n"
"y2[36] is -36\n"
"y2[37] is -37\n"
"y2[9898] is -9898\n"
"That's 12 set buckets\n"
"string test\n"
"x[0]: \n"
"x[1]: \n"
"x[2]: \n"
"x[3]: \n"
"x[4]: foo\n"
"x[5]: \n"
"x[6]: \n"
"x.begin() == x.begin() + 1 - 1? yes\n"
"x.begin() < x.end()? yes\n"
"z.begin() < z.end()? no\n"
"z.begin() <= z.end()? yes\n"
"z.begin() == z.end()? yes\n"
"x[??]: foo\n"
"y[??]: orange\n"
"y[??]: grape\n"
"y[??]: pear\n"
"y[??]: apple\n"
"x has 1/7 buckets, y 4/70, z 0/0\n"
"y shrank and grew: it's now 2/70\n"
"y[12] = orange, y.get(12) = orange\n"
"y[12] cleared. y now 1/70. y[12] = , y.get(12) = \n"
"y == z? no\n"
"y[10] is set\n"
"y[11] is set\n"
"y[13] is set\n"
"y[14] is set\n"
"y[30] is set\n"
"y[31] is set\n"
"y[32] is set\n"
"y[33] is set\n"
"y[35] is set\n"
"y[36] is set\n"
"y[37] is set\n"
"y[9898] is set\n"
"That's 12 set buckets\n"
"Starting from y[32]...\n"
"y[??] = -32\n"
"y[??] = -33\n"
"y[??] = -35\n"
"y[??] = -36\n"
"y[??] = -37\n"
"y[??] = -9898\n"
"From y[32] down...\n"
"y[??] = -31\n"
"y[??] = -30\n"
"y[??] = -14\n"
"y[??] = -13\n"
"y[??] = -11\n"
"y[??] = -10\n"
"allocator test\n"
"sum_allocate_bytes > 0? yes\n"
"sum_allocate_bytes >= 10000 * sizeof(int)? yes\n"
"sum_deallocate_bytes >= 10000 * sizeof(int)? yes\n"
"sum_allocate_bytes >= 2000 * sizeof(int)? yes\n"
"sum_deallocate_bytes >= 1000 * sizeof(int)? yes\n"
"sum_deallocate_bytes < 1000 * sizeof(int)? yes\n"
"sum_deallocate_bytes >= 1000 * sizeof(int)? yes\n"
"x.num_nonempty() == 0? yes\n"
"y[0]: 1\n"
"y[39999]: 40000\n"
"u.num_nonempty() == 0? yes\n"
"v[0]: 1\n"
"v[39999]: 40000\n"
"a.num_nonempty() == 0? yes\n"
"b[0]: aa\n"
"b[39999]: aa\n"
);
// defined at bottom of file for ease of maintainence
int main(int argc, char **argv) { // though we ignore the args
(void)argc;
(void)argv;
TestInt();
TestString();
TestAllocator();
// Finally, check to see if our output (in out) is what it's supposed to be.
const size_t r = sizeof(g_expected) - 1;
if ( r != static_cast<size_t>(out - outbuf) || // output not the same size
memcmp(outbuf, g_expected, r) ) { // or bytes differed
fprintf(stderr, "TESTS FAILED\n\nEXPECTED:\n\n%s\n\nACTUAL:\n\n%s\n\n",
g_expected, outbuf);
return 1;
} else {
printf("PASS.\n");
return 0;
}
}