susumu.yata
null+****@clear*****
Thu Feb 14 10:40:42 JST 2013
susumu.yata 2013-02-14 10:40:42 +0900 (Thu, 14 Feb 2013) New Revision: 44cbfe8f1f3d480dd6debbca1614f405a3c65e57 https://github.com/groonga/grnxx/commit/44cbfe8f1f3d480dd6debbca1614f405a3c65e57 Log: Add tests for grnxx::map::da::basic::Trie. Added files: test/test_map_da_basic_trie.cpp Modified files: .gitignore test/Makefile.am Modified: .gitignore (+1 -0) =================================================================== --- .gitignore 2013-02-14 10:19:30 +0900 (ca459a7) +++ .gitignore 2013-02-14 10:40:42 +0900 (0a93985) @@ -46,6 +46,7 @@ test/test_io_path test/test_io_pool test/test_io_view test/test_logger +test/test_map_da_basic_trie test/test_mutex test/test_os test/test_recycler Modified: test/Makefile.am (+30 -26) =================================================================== --- test/Makefile.am 2013-02-14 10:19:30 +0900 (ba11422) +++ test/Makefile.am 2013-02-14 10:40:42 +0900 (835f017) @@ -1,32 +1,33 @@ AM_CXXFLAGS = @AM_CXXFLAGS@ -I$(top_srcdir)/lib -TESTS = \ - test_alpha_double_array \ +TESTS = \ + test_alpha_double_array \ test_alpha_double_array2 \ - test_backtrace \ - test_db_array \ - test_db_blob_vector \ - test_db_vector \ - test_duration \ - test_error \ - test_exception \ - test_features \ - test_grnxx \ - test_intrinsic \ - test_io_file \ - test_io_file_info \ - test_io_path \ - test_io_pool \ - test_io_view \ - test_logger \ - test_mutex \ - test_os \ - test_recycler \ - test_slice \ - test_string \ - test_string_builder \ - test_string_format \ - test_thread \ + test_backtrace \ + test_db_array \ + test_db_blob_vector \ + test_db_vector \ + test_duration \ + test_error \ + test_exception \ + test_features \ + test_grnxx \ + test_intrinsic \ + test_io_file \ + test_io_file_info \ + test_io_path \ + test_io_pool \ + test_io_view \ + test_logger \ + test_map_da_basic_trie \ + test_mutex \ + test_os \ + test_recycler \ + test_slice \ + test_string \ + test_string_builder \ + test_string_format \ + test_thread \ test_time check_PROGRAMS = $(TESTS) @@ -85,6 +86,9 @@ test_io_view_LDADD = ../lib/libgrnxx.la test_logger_SOURCES = test_logger.cpp test_logger_LDADD = ../lib/libgrnxx.la +test_map_da_basic_trie_SOURCES = test_map_da_basic_trie.cpp +test_map_da_basic_trie_LDADD = ../lib/libgrnxx.la + test_mutex_SOURCES = test_mutex.cpp test_mutex_LDADD = ../lib/libgrnxx.la Added: test/test_map_da_basic_trie.cpp (+275 -0) 100644 =================================================================== --- /dev/null +++ test/test_map_da_basic_trie.cpp 2013-02-14 10:40:42 +0900 (084a66e) @@ -0,0 +1,275 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#include <cassert> +#include <random> +#include <string> +#include <unordered_set> +#include <vector> + +#include "map/da/basic_trie.hpp" +#include "logger.hpp" +#include "time.hpp" + +void test_basics() { + grnxx::io::Pool pool; + pool.open(grnxx::io::POOL_TEMPORARY); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::basic::Trie> trie( + grnxx::map::da::basic::Trie::create(options, pool)); + + std::vector<grnxx::Slice> keys; + keys.push_back("apple"); + keys.push_back("banana"); + keys.push_back("strawberry"); + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(!trie->search(keys[i])); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + std::int64_t key_id; + assert(trie->insert(keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + std::int64_t key_id; + assert(trie->search(keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(!trie->insert(keys[i])); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(trie->remove(keys[i])); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(!trie->search(keys[i])); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(!trie->remove(keys[i])); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(trie->insert(keys[i])); + } + + std::vector<grnxx::Slice> new_keys; + new_keys.push_back("dog"); + new_keys.push_back("monkey"); + new_keys.push_back("bird"); + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(trie->update(keys[i], new_keys[i])); + } + + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(!trie->search(keys[i])); + assert(trie->search(new_keys[i])); + } +} + +void create_keys(std::size_t num_keys, + std::size_t min_size, std::size_t max_size, + std::unordered_set<std::string> *both_keys, + std::vector<grnxx::Slice> *true_keys, + std::vector<grnxx::Slice> *false_keys) { + both_keys->clear(); + true_keys->resize(num_keys); + false_keys->resize(num_keys); + { + while (both_keys->size() < (num_keys * 2)) { + std::string key; + key.resize(min_size + (random() % (max_size - min_size + 1))); + for (std::size_t i = 0; i < key.size(); ++i) { + key[i] = '0' + (random() % 10); + } + both_keys->insert(key); + } + auto it = both_keys->begin(); + for (std::size_t i = 0; i < num_keys; ++i) { + (*true_keys)[i] = grnxx::Slice(it->data(), it->size()); + ++it; + (*false_keys)[i] = grnxx::Slice(it->data(), it->size()); + ++it; + } + } +} + +void test_insert() { + constexpr std::size_t NUM_KEYS = 1 << 10; + constexpr std::size_t MIN_SIZE = 1; + constexpr std::size_t MAX_SIZE = 10; + + std::mt19937 random; + + grnxx::io::Pool pool; + pool.open(grnxx::io::POOL_TEMPORARY); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::basic::Trie> trie( + grnxx::map::da::basic::Trie::create(options, pool)); + + std::unordered_set<std::string> both_keys; + std::vector<grnxx::Slice> true_keys; + std::vector<grnxx::Slice> false_keys; + create_keys(NUM_KEYS, MIN_SIZE, MAX_SIZE, + &both_keys, &true_keys, &false_keys); + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + std::int64_t key_id; + assert(trie->insert(true_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + + assert(!trie->insert(true_keys[i], &key_id)); + + key_id = i + 1; + assert(trie->search(true_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + std::int64_t key_id; + assert(trie->search(true_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + + assert(!trie->search(false_keys[i], &key_id)); + } +} + +void test_remove() { + constexpr std::size_t NUM_KEYS = 1 << 10; + constexpr std::size_t MIN_SIZE = 1; + constexpr std::size_t MAX_SIZE = 10; + + std::mt19937 random; + + grnxx::io::Pool pool; + pool.open(grnxx::io::POOL_TEMPORARY); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::basic::Trie> trie( + grnxx::map::da::basic::Trie::create(options, pool)); + + std::unordered_set<std::string> both_keys; + std::vector<grnxx::Slice> true_keys; + std::vector<grnxx::Slice> false_keys; + create_keys(NUM_KEYS, MIN_SIZE, MAX_SIZE, + &both_keys, &true_keys, &false_keys); + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + std::int64_t key_id; + assert(trie->insert(true_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i * 2)); + assert(trie->insert(false_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>((i * 2) + 1)); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->remove((i * 2) + 1)); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->search(true_keys[i])); + assert(!trie->search(false_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->insert(false_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->search(true_keys[i])); + assert(trie->search(false_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->remove(false_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->search(true_keys[i])); + assert(!trie->search(false_keys[i])); + } +} + +void test_update() { + constexpr std::size_t NUM_KEYS = 1 << 10; + constexpr std::size_t MIN_SIZE = 1; + constexpr std::size_t MAX_SIZE = 10; + + std::mt19937 random; + + grnxx::io::Pool pool; + pool.open(grnxx::io::POOL_TEMPORARY); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::basic::Trie> trie( + grnxx::map::da::basic::Trie::create(options, pool)); + + std::unordered_set<std::string> both_keys; + std::vector<grnxx::Slice> true_keys; + std::vector<grnxx::Slice> false_keys; + create_keys(NUM_KEYS, MIN_SIZE, MAX_SIZE, + &both_keys, &true_keys, &false_keys); + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + std::int64_t key_id; + assert(trie->insert(true_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(!trie->update(i, true_keys[i])); + assert(trie->update(i, false_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(!trie->search(true_keys[i])); + assert(trie->search(false_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(!trie->update(true_keys[i], false_keys[i])); + assert(trie->update(false_keys[i], true_keys[i])); + } + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(trie->search(true_keys[i])); + assert(!trie->search(false_keys[i])); + } +} + +int main() { + grnxx::Logger::set_flags(grnxx::LOGGER_WITH_ALL | + grnxx::LOGGER_ENABLE_COUT); + grnxx::Logger::set_max_level(grnxx::NOTICE_LOGGER); + + test_basics(); + + test_insert(); + test_remove(); + test_update(); + + return 0; +} -------------- next part -------------- HTML����������������������������...Download