FM / util

/srv/osrm/osrm-backend/include/util

Name	Size	Mode	Actions
guidance/	-	0755	rm
alias.hpp	6870	0644	edit dl rm
assert.hpp	1964	0644	edit dl rm
attributes.hpp	357	0644	edit dl rm
bearing.hpp	3964	0644	edit dl rm
bit_range.hpp	2950	0644	edit dl rm
cheap_ruler.hpp	2124	0644	edit dl rm
concurrent_id_map.hpp	2148	0644	edit dl rm
conditional_restrictions.hpp	627	0644	edit dl rm
connectivity_checksum.hpp	1931	0644	edit dl rm
coordinate.hpp	9244	0644	edit dl rm
coordinate_calculation.hpp	16297	0644	edit dl rm
deallocating_vector.hpp	11205	0644	edit dl rm
debug.hpp	5958	0644	edit dl rm
dist_table_wrapper.hpp	2299	0644	edit dl rm
dynamic_graph.hpp	15951	0644	edit dl rm
exception.hpp	5126	0644	edit dl rm
exception_utils.hpp	609	0644	edit dl rm
exclude_flag.hpp	975	0644	edit dl rm
filtered_graph.hpp	5402	0644	edit dl rm
filtered_integer_range.hpp	3097	0644	edit dl rm
fingerprint.hpp	1166	0644	edit dl rm
for_each_indexed.hpp	634	0644	edit dl rm
for_each_pair.hpp	990	0644	edit dl rm
for_each_range.hpp	477	0644	edit dl rm
geojson_debug_logger.hpp	6330	0644	edit dl rm
geojson_debug_policies.hpp	1810	0644	edit dl rm
geojson_debug_policy_toolkit.hpp	3258	0644	edit dl rm
geojson_validation.hpp	2899	0644	edit dl rm
graph_traits.hpp	1245	0644	edit dl rm
graph_utils.hpp	3141	0644	edit dl rm
group_by.hpp	722	0644	edit dl rm
hilbert_value.hpp	3010	0644	edit dl rm
indexed_data.hpp	15039	0644	edit dl rm
integer_range.hpp	3286	0644	edit dl rm
isatty.hpp	610	0644	edit dl rm
json_container.hpp	3181	0644	edit dl rm
json_deep_compare.hpp	4732	0644	edit dl rm
json_renderer.hpp	4160	0644	edit dl rm
json_util.hpp	544	0644	edit dl rm
log.hpp	2187	0644	edit dl rm
lua_util.hpp	891	0644	edit dl rm
matrix_graph_wrapper.hpp	1294	0644	edit dl rm
meminfo.hpp	660	0644	edit dl rm
mmap_file.hpp	2776	0644	edit dl rm
mmap_tar.hpp	1007	0644	edit dl rm
msb.hpp	1178	0644	edit dl rm
node_based_graph.hpp	3530	0644	edit dl rm
opening_hours.hpp	8338	0644	edit dl rm
packed_vector.hpp	21691	0644	edit dl rm
percent.hpp	2106	0644	edit dl rm
permutation.hpp	1991	0644	edit dl rm
query_heap.hpp	10205	0644	edit dl rm
range_table.hpp	7119	0644	edit dl rm
rectangle.hpp	5900	0644	edit dl rm
serialization.hpp	5902	0644	edit dl rm
static_assert.hpp	640	0644	edit dl rm
static_graph.hpp	10702	0644	edit dl rm
static_rtree.hpp	34147	0644	edit dl rm
std_hash.hpp	1035	0644	edit dl rm
string_util.hpp	3400	0644	edit dl rm
tarjan_scc.hpp	6646	0644	edit dl rm
timed_histogram.hpp	2576	0644	edit dl rm
timezones.hpp	1417	0644	edit dl rm
timing_util.hpp	1485	0644	edit dl rm
to_osm_link.hpp	694	0644	edit dl rm
trigonometry_table.hpp	35906	0644	edit dl rm
typedefs.hpp	7627	0644	edit dl rm
vector_tile.hpp	303	0644	edit dl rm
vector_view.hpp	8000	0644	edit dl rm
version.hpp.in	406	0644	edit dl rm
viewport.hpp	1579	0644	edit dl rm
web_mercator.hpp	6480	0644	edit dl rm
xor_fast_hash.hpp	1797	0644	edit dl rm
xor_fast_hash_storage.hpp	2195	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/include/util/range_table.hpp (7119B)

#ifndef RANGE_TABLE_HPP
#define RANGE_TABLE_HPP

#include "storage/shared_memory_ownership.hpp"
#include "storage/tar_fwd.hpp"
#include "util/integer_range.hpp"
#include "util/vector_view.hpp"

#include <array>
#include <fstream>
#include <utility>

namespace osrm::util
{
/*
 * These pre-declarations are needed because parsing C++ is hard
 * and otherwise the compiler gets confused.
 */

template <unsigned BLOCK_SIZE = 16, storage::Ownership Ownership = storage::Ownership::Container>
class RangeTable;

namespace serialization
{
template <unsigned BlockSize, storage::Ownership Ownership>
void write(storage::tar::FileWriter &writer,
           const std::string &name,
           const util::RangeTable<BlockSize, Ownership> &table);

template <unsigned BlockSize, storage::Ownership Ownership>
void read(storage::tar::FileReader &reader,
          const std::string &name,
          util::RangeTable<BlockSize, Ownership> &table);
} // namespace serialization

/**
 * Stores adjacent ranges in a compressed format.
 *
 * Maximum supported length of a range is 255.
 *
 * Note: BLOCK_SIZE is the number of differential encodoed values.
 * But each block consists of an absolute value and BLOCK_SIZE differential values.
 * So the effective block size is sizeof(unsigned) + BLOCK_SIZE.
 */
template <unsigned BLOCK_SIZE, storage::Ownership Ownership> class RangeTable
{
  public:
    using BlockT = std::array<unsigned char, BLOCK_SIZE>;
    using BlockContainerT = util::ViewOrVector<BlockT, Ownership>;
    using OffsetContainerT = util::ViewOrVector<unsigned, Ownership>;
    using RangeT = range<unsigned>;

RangeTable() : sum_lengths(0) {}

// for loading from shared memory
    explicit RangeTable(OffsetContainerT offsets_,
                        BlockContainerT blocks_,
                        const unsigned sum_lengths)
        : block_offsets(std::move(offsets_)), diff_blocks(std::move(blocks_)),
          sum_lengths(sum_lengths)
    {
    }

// construct table from length vector
    template <typename VectorT> explicit RangeTable(const VectorT &lengths)
    {
        const unsigned number_of_blocks = [&lengths]() {
            unsigned num = (lengths.size() + 1) / (BLOCK_SIZE + 1);
            if ((lengths.size() + 1) % (BLOCK_SIZE + 1) != 0)
            {
                num += 1;
            }
            return num;
        }();

block_offsets.reserve(number_of_blocks);
        diff_blocks.reserve(number_of_blocks);

unsigned last_length = 0;
        unsigned lengths_prefix_sum = 0;
        unsigned block_idx = 0;
        BlockT block;
#ifndef BOOST_ASSERT_IS_VOID
        unsigned block_sum = 0;
        unsigned block_counter = 0;
#endif
        for (const unsigned l : lengths)
        {
            // first entry of a block: encode absolute offset
            if (block_idx == 0)
            {
                block_offsets.push_back(lengths_prefix_sum);
#ifndef BOOST_ASSERT_IS_VOID
                block_sum = 0;
#endif
            }
            else
            {
                block[block_idx - 1] = last_length;
#ifndef BOOST_ASSERT_IS_VOID
                block_sum += last_length;
#endif
            }

BOOST_ASSERT((block_idx == 0 && block_offsets[block_counter] == lengths_prefix_sum) ||
                         lengths_prefix_sum == (block_offsets[block_counter] + block_sum));

// block is full
            if (BLOCK_SIZE == block_idx)
            {
                diff_blocks.push_back(block);
#ifndef BOOST_ASSERT_IS_VOID
                block_counter++;
#endif
            }

// we can only store strings with length 255
            BOOST_ASSERT(l <= 255);

lengths_prefix_sum += l;
            last_length = l;

block_idx = (block_idx + 1) % (BLOCK_SIZE + 1);
        }

// Last block can't be finished because we didn't add the sentinel
        BOOST_ASSERT(block_counter == (number_of_blocks - 1));

// one block missing: starts with guard value
        if (0 == block_idx)
        {
            // the last value is used as sentinel
            block_offsets.push_back(lengths_prefix_sum);
            block_idx = 1;
            last_length = 0;
        }

while (0 != block_idx)
        {
            block[block_idx - 1] = last_length;
            last_length = 0;
            block_idx = (block_idx + 1) % (BLOCK_SIZE + 1);
        }
        diff_blocks.push_back(block);

BOOST_ASSERT(diff_blocks.size() == number_of_blocks &&
                     block_offsets.size() == number_of_blocks);

sum_lengths = lengths_prefix_sum;
    }

inline RangeT GetRange(const unsigned id) const
    {
        BOOST_ASSERT(id < block_offsets.size() + diff_blocks.size() * BLOCK_SIZE);
        // internal_idx 0 is implicitly stored in block_offsets[block_idx]
        const unsigned internal_idx = id % (BLOCK_SIZE + 1);
        const unsigned block_idx = id / (BLOCK_SIZE + 1);

BOOST_ASSERT(block_idx < diff_blocks.size());

unsigned begin_idx = 0;
        unsigned end_idx = 0;
        begin_idx = block_offsets[block_idx];
        const BlockT &block = diff_blocks[block_idx];
        if (internal_idx > 0)
        {
            begin_idx += PrefixSumAtIndex(internal_idx - 1, block);
        }

// next index inside current block
        if (internal_idx < BLOCK_SIZE)
        {
            // note internal_idx - 1 is the *current* index for uint8_blocks
            end_idx = begin_idx + block[internal_idx];
        }
        else
        {
            BOOST_ASSERT(block_idx < block_offsets.size() - 1);
            end_idx = block_offsets[block_idx + 1];
        }

BOOST_ASSERT(end_idx <= sum_lengths);
        BOOST_ASSERT(begin_idx <= end_idx);

return irange(begin_idx, end_idx);
    }

friend void serialization::write<BLOCK_SIZE, Ownership>(storage::tar::FileWriter &writer,
                                                            const std::string &name,
                                                            const RangeTable &table);
    friend void serialization::read<BLOCK_SIZE, Ownership>(storage::tar::FileReader &reader,
                                                           const std::string &name,
                                                           RangeTable &table);

private:
    inline unsigned PrefixSumAtIndex(int index, const BlockT &block) const;

// contains offset for each differential block
    OffsetContainerT block_offsets;
    // blocks of differential encoded offsets, should be aligned
    BlockContainerT diff_blocks;
    unsigned sum_lengths;
};

template <unsigned BLOCK_SIZE, storage::Ownership Ownership>
unsigned RangeTable<BLOCK_SIZE, Ownership>::PrefixSumAtIndex(int index, const BlockT &block) const
{
    // this loop looks inefficent, but a modern compiler
    // will emit nice SIMD here, at least for sensible block sizes. (I checked.)
    unsigned sum = 0;
    for (int i = 0; i <= index; ++i)
    {
        sum += block[i];
    }

return sum;
}
} // namespace osrm::util

#endif // RANGE_TABLE_HPP

cmd: