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/deallocating_vector.hpp (11205B)

#ifndef DEALLOCATING_VECTOR_HPP
#define DEALLOCATING_VECTOR_HPP

#include "storage/io_fwd.hpp"
#include "util/integer_range.hpp"

#include <boost/iterator/iterator_facade.hpp>

#include <algorithm>
#include <limits>
#include <utility>
#include <vector>

namespace osrm::util
{
template <typename ElementT> struct ConstDeallocatingVectorIteratorState
{
    ConstDeallocatingVectorIteratorState()
        : index(std::numeric_limits<std::size_t>::max()), bucket_list(nullptr)
    {
    }
    explicit ConstDeallocatingVectorIteratorState(const ConstDeallocatingVectorIteratorState &r)
        : index(r.index), bucket_list(r.bucket_list)
    {
    }
    explicit ConstDeallocatingVectorIteratorState(const std::size_t idx,
                                                  const std::vector<ElementT *> *input_list)
        : index(idx), bucket_list(input_list)
    {
    }
    std::size_t index;
    const std::vector<ElementT *> *bucket_list;

ConstDeallocatingVectorIteratorState &
    operator=(const ConstDeallocatingVectorIteratorState &other)
    {
        index = other.index;
        bucket_list = other.bucket_list;
        return *this;
    }
};

template <typename ElementT> struct DeallocatingVectorIteratorState
{
    DeallocatingVectorIteratorState()
        : index(std::numeric_limits<std::size_t>::max()), bucket_list(nullptr)
    {
    }
    explicit DeallocatingVectorIteratorState(const DeallocatingVectorIteratorState &r)
        : index(r.index), bucket_list(r.bucket_list)
    {
    }
    explicit DeallocatingVectorIteratorState(const std::size_t idx,
                                             std::vector<ElementT *> *input_list)
        : index(idx), bucket_list(input_list)
    {
    }
    std::size_t index;
    std::vector<ElementT *> *bucket_list;

DeallocatingVectorIteratorState &operator=(const DeallocatingVectorIteratorState &other)
    {
        index = other.index;
        bucket_list = other.bucket_list;
        return *this;
    }
};

template <typename ElementT, std::size_t ELEMENTS_PER_BLOCK>
class ConstDeallocatingVectorIterator
    : public boost::iterator_facade<ConstDeallocatingVectorIterator<ElementT, ELEMENTS_PER_BLOCK>,
                                    ElementT,
                                    std::random_access_iterator_tag>
{
    ConstDeallocatingVectorIteratorState<ElementT> current_state;

public:
    ConstDeallocatingVectorIterator() {}
    ConstDeallocatingVectorIterator(std::size_t idx, const std::vector<ElementT *> *input_list)
        : current_state(idx, input_list)
    {
    }

friend class boost::iterator_core_access;

void advance(std::size_t n) { current_state.index += n; }

void increment() { advance(1); }

void decrement() { advance(-1); }

bool equal(ConstDeallocatingVectorIterator const &other) const
    {
        return current_state.index == other.current_state.index;
    }

std::ptrdiff_t distance_to(ConstDeallocatingVectorIterator const &other) const
    {
        // it is important to implement it 'other minus this'. otherwise sorting breaks
        return other.current_state.index - current_state.index;
    }

ElementT &dereference() const
    {
        const std::size_t current_bucket = current_state.index / ELEMENTS_PER_BLOCK;
        const std::size_t current_index = current_state.index % ELEMENTS_PER_BLOCK;
        return (current_state.bucket_list->at(current_bucket)[current_index]);
    }

ElementT &operator[](const std::size_t index) const
    {
        const std::size_t current_bucket = (index + current_state.index) / ELEMENTS_PER_BLOCK;
        const std::size_t current_index = (index + current_state.index) % ELEMENTS_PER_BLOCK;
        return (current_state.bucket_list->at(current_bucket)[current_index]);
    }
};

template <typename ElementT, std::size_t ELEMENTS_PER_BLOCK>
class DeallocatingVectorIterator
    : public boost::iterator_facade<DeallocatingVectorIterator<ElementT, ELEMENTS_PER_BLOCK>,
                                    ElementT,
                                    std::random_access_iterator_tag>
{
    DeallocatingVectorIteratorState<ElementT> current_state;

public:
    DeallocatingVectorIterator() {}
    DeallocatingVectorIterator(std::size_t idx, std::vector<ElementT *> *input_list)
        : current_state(idx, input_list)
    {
    }

friend class boost::iterator_core_access;

void advance(std::size_t n) { current_state.index += n; }

void increment() { advance(1); }

void decrement() { advance(-1); }

bool equal(DeallocatingVectorIterator const &other) const
    {
        return current_state.index == other.current_state.index;
    }

std::ptrdiff_t distance_to(DeallocatingVectorIterator const &other) const
    {
        // it is important to implement it 'other minus this'. otherwise sorting breaks
        return other.current_state.index - current_state.index;
    }

template <typename ElementT> class DeallocatingVector;

template <typename T> void swap(DeallocatingVector<T> &lhs, DeallocatingVector<T> &rhs);

template <typename ElementT> class DeallocatingVector
{
    static constexpr std::size_t ELEMENTS_PER_BLOCK = 8388608 / sizeof(ElementT);
    std::size_t current_size;
    std::vector<ElementT *> bucket_list;

public:
    using value_type = ElementT;
    using iterator = DeallocatingVectorIterator<ElementT, ELEMENTS_PER_BLOCK>;
    using const_iterator = ConstDeallocatingVectorIterator<ElementT, ELEMENTS_PER_BLOCK>;

DeallocatingVector() : current_size(0)
    {
        bucket_list.emplace_back(new ElementT[ELEMENTS_PER_BLOCK]);
    }

// Performs a deep copy of the buckets
    DeallocatingVector(const DeallocatingVector &other)
    {
        bucket_list.resize(other.bucket_list.size());
        for (const auto index : util::irange<std::size_t>(0, bucket_list.size()))
        {
            bucket_list[index] = new ElementT[ELEMENTS_PER_BLOCK];
            std::copy_n(other.bucket_list[index], ELEMENTS_PER_BLOCK, bucket_list[index]);
        }
        current_size = other.current_size;
    }
    // Note we capture other by value
    DeallocatingVector &operator=(const DeallocatingVector &other)
    {
        auto copy_other = other;
        swap(copy_other);
        return *this;
    }

// moving is fine
    DeallocatingVector(DeallocatingVector &&other) { swap(other); }
    DeallocatingVector &operator=(DeallocatingVector &&other)
    {
        swap(other);
        return *this;
    }

DeallocatingVector(std::initializer_list<ElementT> elements) : DeallocatingVector()
    {
        for (auto &&elem : elements)
        {
            emplace_back(std::move(elem));
        }
    }

~DeallocatingVector() { clear(); }

friend void swap<>(DeallocatingVector<ElementT> &lhs, DeallocatingVector<ElementT> &rhs);

void swap(DeallocatingVector<ElementT> &other)
    {
        std::swap(current_size, other.current_size);
        bucket_list.swap(other.bucket_list);
    }

void clear()
    {
        // Delete[]'ing ptr's to all Buckets
        for (auto bucket : bucket_list)
        {
            delete[] bucket;
        }
        bucket_list.clear();
        bucket_list.shrink_to_fit();
        current_size = 0;
    }

void push_back(const ElementT &element)
    {
        const std::size_t current_capacity = capacity();
        if (current_size == current_capacity)
        {
            bucket_list.push_back(new ElementT[ELEMENTS_PER_BLOCK]);
        }

std::size_t current_index = size() % ELEMENTS_PER_BLOCK;
        bucket_list.back()[current_index] = element;
        ++current_size;
    }

template <typename... Ts> void emplace_back(Ts &&... element)
    {
        const std::size_t current_capacity = capacity();
        if (current_size == current_capacity)
        {
            bucket_list.push_back(new ElementT[ELEMENTS_PER_BLOCK]);
        }

const std::size_t current_index = size() % ELEMENTS_PER_BLOCK;
        bucket_list.back()[current_index] = ElementT(std::forward<Ts>(element)...);
        ++current_size;
    }

void reserve(const std::size_t) const
    { /* don't do anything */
    }

void resize(const std::size_t new_size)
    {
        if (new_size >= current_size)
        {
            while (capacity() < new_size)
            {
                bucket_list.push_back(new ElementT[ELEMENTS_PER_BLOCK]);
            }
        }
        else
        { // down-size
            const std::size_t number_of_necessary_buckets = 1 + (new_size / ELEMENTS_PER_BLOCK);
            for (const auto bucket_index : irange(number_of_necessary_buckets, bucket_list.size()))
            {
                if (nullptr != bucket_list[bucket_index])
                {
                    delete[] bucket_list[bucket_index];
                }
            }
            bucket_list.resize(number_of_necessary_buckets);
        }
        current_size = new_size;
    }

std::size_t size() const { return current_size; }

std::size_t capacity() const { return bucket_list.size() * ELEMENTS_PER_BLOCK; }

iterator begin() { return iterator(static_cast<std::size_t>(0), &bucket_list); }

iterator end() { return iterator(size(), &bucket_list); }

const_iterator begin() const
    {
        return const_iterator(static_cast<std::size_t>(0), &bucket_list);
    }

const_iterator end() const { return const_iterator(size(), &bucket_list); }

ElementT &operator[](const std::size_t index)
    {
        const std::size_t _bucket = index / ELEMENTS_PER_BLOCK;
        const std::size_t _index = index % ELEMENTS_PER_BLOCK;
        return (bucket_list[_bucket][_index]);
    }

ElementT &operator[](const std::size_t index) const
    {
        const std::size_t _bucket = index / ELEMENTS_PER_BLOCK;
        const std::size_t _index = index % ELEMENTS_PER_BLOCK;
        return (bucket_list[_bucket][_index]);
    }

ElementT &back() const
    {
        const std::size_t _bucket = (current_size - 1) / ELEMENTS_PER_BLOCK;
        const std::size_t _index = (current_size - 1) % ELEMENTS_PER_BLOCK;
        return (bucket_list[_bucket][_index]);
    }

template <class InputIterator> void append(InputIterator first, const InputIterator last)
    {
        InputIterator position = first;
        while (position != last)
        {
            push_back(*position);
            ++position;
        }
    }
};

template <typename T> void swap(DeallocatingVector<T> &lhs, DeallocatingVector<T> &rhs)
{
    lhs.swap(rhs);
}
} // namespace osrm::util

#endif /* DEALLOCATING_VECTOR_HPP */

cmd: