147 lines
4.3 KiB
C++
147 lines
4.3 KiB
C++
/**
|
|
* SPDX-License-Identifier: GPL-2.0-or-later
|
|
*
|
|
* This file is part of osm2pgsql (https://osm2pgsql.org/).
|
|
*
|
|
* Copyright (C) 2006-2024 by the osm2pgsql developer community.
|
|
* For a full list of authors see the git log.
|
|
*/
|
|
|
|
#include <catch.hpp>
|
|
|
|
#include "ordered-index.hpp"
|
|
|
|
TEST_CASE("ordered index basics", "[NoDB]")
|
|
{
|
|
constexpr std::size_t const block_size = 16;
|
|
ordered_index_t index{block_size};
|
|
|
|
REQUIRE(index.size() == 0);
|
|
REQUIRE(index.capacity() == 0);
|
|
REQUIRE(index.used_memory() == 0);
|
|
|
|
index.add(17, 32);
|
|
REQUIRE(index.size() == 1);
|
|
REQUIRE(index.capacity() == block_size);
|
|
REQUIRE(index.used_memory() > 0);
|
|
|
|
index.add(19, 33);
|
|
REQUIRE(index.size() == 2);
|
|
REQUIRE(index.capacity() == block_size);
|
|
REQUIRE(index.used_memory() > 0);
|
|
|
|
index.clear();
|
|
REQUIRE(index.size() == 0);
|
|
REQUIRE(index.capacity() == 0);
|
|
REQUIRE(index.used_memory() == 0);
|
|
}
|
|
|
|
TEST_CASE("ordered index set/get", "[NoDB]")
|
|
{
|
|
constexpr std::size_t const block_size = 16;
|
|
ordered_index_t index{block_size};
|
|
|
|
index.add(19, 0);
|
|
index.add(22, 10);
|
|
index.add(23, 22);
|
|
index.add(26, 24);
|
|
REQUIRE(index.size() == 4);
|
|
|
|
REQUIRE(index.get(22) == 10);
|
|
REQUIRE(index.get(23) == 22);
|
|
REQUIRE(index.get(26) == 24);
|
|
REQUIRE(index.get(19) == 0);
|
|
|
|
REQUIRE(index.get(0) == index.not_found_value());
|
|
REQUIRE(index.get(20) == index.not_found_value());
|
|
REQUIRE(index.get(27) == index.not_found_value());
|
|
|
|
REQUIRE(index.get_block(0) == index.not_found_value());
|
|
REQUIRE(index.get_block(20) == 0);
|
|
REQUIRE(index.get_block(27) == 24);
|
|
REQUIRE(index.get_block(99999) == 24);
|
|
}
|
|
|
|
TEST_CASE("ordered index set/get with multiple second-level blocks", "[NoDB]")
|
|
{
|
|
constexpr std::size_t const block_size = 4;
|
|
ordered_index_t index{block_size};
|
|
|
|
index.add(19, 0);
|
|
index.add(22, 10);
|
|
index.add(23, 22);
|
|
index.add(26, 24);
|
|
REQUIRE(index.size() == 4);
|
|
REQUIRE(index.capacity() == block_size);
|
|
|
|
REQUIRE(index.get(31) == index.not_found_value());
|
|
|
|
index.add(31, 25);
|
|
index.add(42, 30);
|
|
index.add(65, 32);
|
|
REQUIRE(index.size() == 7);
|
|
REQUIRE(index.capacity() == block_size * (1 + 2));
|
|
|
|
REQUIRE(index.get(22) == 10);
|
|
REQUIRE(index.get(23) == 22);
|
|
REQUIRE(index.get(26) == 24);
|
|
REQUIRE(index.get(19) == 0);
|
|
REQUIRE(index.get(42) == 30);
|
|
REQUIRE(index.get(31) == 25);
|
|
REQUIRE(index.get(65) == 32);
|
|
|
|
REQUIRE(index.get(0) == index.not_found_value());
|
|
REQUIRE(index.get(27) == index.not_found_value());
|
|
REQUIRE(index.get(30) == index.not_found_value());
|
|
REQUIRE(index.get(66) == index.not_found_value());
|
|
REQUIRE(index.get(99) == index.not_found_value());
|
|
|
|
REQUIRE(index.get_block(0) == index.not_found_value());
|
|
REQUIRE(index.get_block(18) == index.not_found_value());
|
|
REQUIRE(index.get_block(22) == 10);
|
|
REQUIRE(index.get_block(24) == 22);
|
|
REQUIRE(index.get_block(50) == 30);
|
|
REQUIRE(index.get_block(66) == 32);
|
|
}
|
|
|
|
TEST_CASE("ordered index with huge gaps in ids", "[NoDB]")
|
|
{
|
|
constexpr std::size_t const block_size = 4;
|
|
ordered_index_t index{block_size};
|
|
|
|
index.add(1, 0);
|
|
REQUIRE(index.size() == 1);
|
|
REQUIRE(index.capacity() == block_size);
|
|
|
|
index.add((1ULL << 32U) + 3U, 1);
|
|
REQUIRE(index.size() == 2);
|
|
REQUIRE(index.capacity() == block_size * (1 + 2));
|
|
|
|
index.add((1ULL << 32U) + 4U, 2);
|
|
REQUIRE(index.size() == 3);
|
|
REQUIRE(index.capacity() == block_size * (1 + 2));
|
|
|
|
index.add((2ULL << 32U) + 9U, 3);
|
|
REQUIRE(index.size() == 4);
|
|
REQUIRE(index.capacity() == block_size * (1 + 2 + 4));
|
|
|
|
REQUIRE(index.used_memory() > (index.capacity() * 8));
|
|
|
|
REQUIRE(index.get(1) == 0);
|
|
REQUIRE(index.get((1ULL << 32U) + 3U) == 1);
|
|
REQUIRE(index.get((1ULL << 32U) + 4U) == 2);
|
|
REQUIRE(index.get((2ULL << 32U) + 9U) == 3);
|
|
REQUIRE(index.get(2) == index.not_found_value());
|
|
|
|
REQUIRE(index.get_block(1) == 0);
|
|
REQUIRE(index.get_block(2) == 0);
|
|
REQUIRE(index.get_block((1ULL << 32U) + 2U) == 0);
|
|
REQUIRE(index.get_block((1ULL << 32U) + 3U) == 1);
|
|
REQUIRE(index.get_block((1ULL << 32U) + 4U) == 2);
|
|
REQUIRE(index.get_block((1ULL << 32U) + 5U) == 2);
|
|
REQUIRE(index.get_block((2ULL << 32U) + 8U) == 2);
|
|
REQUIRE(index.get_block((2ULL << 32U) + 9U) == 3);
|
|
REQUIRE(index.get_block((3ULL << 32U) + 2U) == 3);
|
|
}
|
|
|