blob: 5bbb0ff2d296cdc3bb88d2be490ed2347d56c894 [file] [log] [blame]
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
* Copyright (c) 2014, Regents of the University of California.
*
* This file is part of NDN repo-ng (Next generation of NDN repository).
* See AUTHORS.md for complete list of repo-ng authors and contributors.
*
* repo-ng is free software: you can redistribute it and/or modify it under the terms
* of the GNU General Public License as published by the Free Software Foundation,
* either version 3 of the License, or (at your option) any later version.
*
* repo-ng is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
* PURPOSE. See the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along with
* repo-ng, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
*/
#include "storage/skiplist.hpp"
#include "../sqlite-fixture.hpp"
#include "../dataset-fixtures.hpp"
#include <boost/test/unit_test.hpp>
#include <boost/concept_check.hpp>
#include <iostream>
namespace repo {
namespace tests {
BOOST_AUTO_TEST_SUITE(SkipList)
template<class Dataset>
class Fixture : public Dataset
{
};
BOOST_AUTO_TEST_CASE(Correctness)
{
typedef repo::SkipList<int, std::greater<int> > IntGtSkipList;
IntGtSkipList sl;
BOOST_CONCEPT_ASSERT((boost::BidirectionalIterator<IntGtSkipList::iterator>));
// initial state
BOOST_CHECK_EQUAL(sl.size(), 0);
BOOST_CHECK(sl.begin() == sl.end());
BOOST_CHECK(sl.lower_bound(10) == sl.end());
// initial contents
sl.insert(10);
sl.insert(20);
sl.insert(30);
BOOST_CHECK_EQUAL(sl.size(), 3);
// contents: [30,20,10]
// iterators
IntGtSkipList::iterator it1 = sl.begin();
IntGtSkipList::iterator it2 = sl.end();
--it2;
BOOST_CHECK_EQUAL(*it1, 30);
BOOST_CHECK_EQUAL(*it2, 10);
++it1;
BOOST_CHECK_EQUAL(*it1, 20);
IntGtSkipList::iterator it3 = it1;
++it1;
BOOST_CHECK(it2 == it1);
BOOST_CHECK_EQUAL(*it3, 20);
// lower_bound
IntGtSkipList::iterator found = sl.lower_bound(35);
BOOST_CHECK(found == sl.begin());
BOOST_CHECK_EQUAL(*found, 30);
found = sl.lower_bound(30);
BOOST_CHECK_EQUAL(*found, 30);
found = sl.lower_bound(25);
BOOST_CHECK_EQUAL(*found, 20);
found = sl.lower_bound(20);
BOOST_CHECK_EQUAL(*found, 20);
found = sl.lower_bound(15);
BOOST_CHECK_EQUAL(*found, 10);
found = sl.lower_bound(10);
BOOST_CHECK_EQUAL(*found, 10);
found = sl.lower_bound(5);
BOOST_CHECK(found == sl.end());
// insert duplicate
std::pair<IntGtSkipList::iterator, bool> insertRes = sl.insert(10);
BOOST_CHECK_EQUAL(insertRes.second, false);
BOOST_CHECK_EQUAL(*(insertRes.first), 10);
BOOST_CHECK_EQUAL(sl.size(), 3);
insertRes = sl.insert(20);
BOOST_CHECK_EQUAL(insertRes.second, false);
BOOST_CHECK_EQUAL(*(insertRes.first), 20);
BOOST_CHECK_EQUAL(sl.size(), 3);
insertRes = sl.insert(30);
BOOST_CHECK_EQUAL(insertRes.second, false);
BOOST_CHECK_EQUAL(*(insertRes.first), 30);
BOOST_CHECK_EQUAL(sl.size(), 3);
// insert non-duplicate
insertRes = sl.insert(5);
BOOST_CHECK_EQUAL(insertRes.second, true);
BOOST_CHECK_EQUAL(*(insertRes.first), 5);
BOOST_CHECK_EQUAL(sl.size(), 4);
insertRes = sl.insert(35);
BOOST_CHECK_EQUAL(insertRes.second, true);
BOOST_CHECK_EQUAL(*(insertRes.first), 35);
BOOST_CHECK_EQUAL(sl.size(), 5);
// contents: [35,30,20,10,5]
// erase
it1 = sl.erase(sl.begin());
// contents: [30,20,10,5]
BOOST_CHECK_EQUAL(*it1, 30);
BOOST_CHECK_EQUAL(sl.size(), 4);
it2 = sl.end();
--it2;
it1 = sl.erase(it2);
// contents: [30,20,10]
BOOST_CHECK(it1 == sl.end());
BOOST_CHECK_EQUAL(sl.size(), 3);
it2 = sl.lower_bound(20);
it1 = sl.erase(it2);
// contents: [30,10]
BOOST_CHECK_EQUAL(*it1, 10);
BOOST_CHECK_EQUAL(sl.size(), 2);
it3 = it1;
--it1;
BOOST_CHECK(it1 == sl.begin());
BOOST_CHECK_EQUAL(*it1, 30);
++it3;
BOOST_CHECK(it3 == sl.end());
}
class Item : public ndn::Name
{
public:
explicit
Item(const ndn::Name& name = "")
: ndn::Name(name)
, randomValue(ndn::random::generateWord64())
{
}
public:
uint64_t randomValue;
};
BOOST_FIXTURE_TEST_CASE_TEMPLATE(Bulk, T, CommonDatasets, Fixture<T>)
{
BOOST_TEST_MESSAGE(T::getName());
typedef repo::SkipList<Item, std::less<Item> > SkipList;
SkipList skipList;
std::vector<Item> items;
std::set<ndn::Name> names;
for (typename T::DataContainer::iterator i = this->data.begin();
i != this->data.end(); ++i) {
std::pair<std::set<ndn::Name>::iterator, bool> ret = names.insert((*i)->getName());
if (ret.second) {
items.push_back(Item((*i)->getName()));
}
}
// Insert
for (std::vector<Item>::iterator i = items.begin(); i != items.end(); ++i) {
skipList.insert(*i);
}
BOOST_CHECK_EQUAL(items.size(), skipList.size());
// Randomize items
std::random_shuffle(items.begin(), items.end());
// Find items and check if the right item is found
for (std::vector<Item>::iterator i = items.begin(); i != items.end(); ++i) {
SkipList::iterator item = skipList.find(*i);
BOOST_CHECK(item != skipList.end());
BOOST_CHECK_EQUAL(static_cast<const Name&>(*item), static_cast<const Name&>(*i));
BOOST_CHECK_EQUAL(item->randomValue, i->randomValue);
}
}
BOOST_AUTO_TEST_SUITE_END()
} // namespace tests
} // namespace repo