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/static_graph.hpp (10702B)

#ifndef STATIC_GRAPH_HPP
#define STATIC_GRAPH_HPP

#include "util/graph_traits.hpp"
#include "util/integer_range.hpp"
#include "util/percent.hpp"
#include "util/permutation.hpp"
#include "util/typedefs.hpp"
#include "util/vector_view.hpp"

#include "storage/shared_memory_ownership.hpp"
#include "storage/tar_fwd.hpp"

#include <boost/assert.hpp>

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

namespace osrm::util
{
template <typename EdgeDataT, storage::Ownership Ownership> class StaticGraph;

namespace serialization
{
template <typename EdgeDataT, storage::Ownership Ownership>
void read(storage::tar::FileReader &reader,
          const std::string &name,
          StaticGraph<EdgeDataT, Ownership> &graph);

template <typename EdgeDataT, storage::Ownership Ownership>
void write(storage::tar::FileWriter &writer,
           const std::string &name,
           const StaticGraph<EdgeDataT, Ownership> &graph);
} // namespace serialization

namespace static_graph_details
{

using NodeIterator = NodeID;
using EdgeIterator = NodeID;

struct NodeArrayEntry
{
    // index of the first edge
    EdgeIterator first_edge;
};

template <typename EdgeDataT> struct EdgeArrayEntry;

template <typename EdgeDataT> struct EdgeArrayEntry
{
    NodeID target;
    EdgeDataT data;
};

template <> struct EdgeArrayEntry<void>
{
    NodeID target;
};

template <typename EdgeDataT> struct SortableEdgeWithData;

template <> struct SortableEdgeWithData<void>
{
    NodeIterator source;
    NodeIterator target;

SortableEdgeWithData() = default;

SortableEdgeWithData(NodeIterator source, NodeIterator target) : source(source), target(target)
    {
    }

bool operator<(const SortableEdgeWithData &right) const
    {
        return std::tie(source, target) < std::tie(right.source, right.target);
    }

bool operator==(const SortableEdgeWithData &right) const
    {
        return std::tie(source, target) == std::tie(right.source, right.target);
    }
};

template <typename EdgeDataT> struct SortableEdgeWithData : SortableEdgeWithData<void>
{
    using Base = SortableEdgeWithData<void>;

EdgeDataT data;

SortableEdgeWithData() = default;

template <typename... Ts>
    SortableEdgeWithData(NodeIterator source, NodeIterator target, Ts &&... data)
        : Base{source, target}, data{std::forward<Ts>(data)...}
    {
    }
};

template <typename EntryT, typename OtherEdge>
EntryT edgeToEntry(const OtherEdge &from, std::true_type)
{
    return EntryT{from.target, from.data};
}
template <typename EntryT, typename OtherEdge>
EntryT edgeToEntry(const OtherEdge &from, std::false_type)
{
    return EntryT{from.target};
}

} // namespace static_graph_details

template <typename EdgeDataT, storage::Ownership Ownership = storage::Ownership::Container>
class StaticGraph
{
    template <typename T> using Vector = util::ViewOrVector<T, Ownership>;

public:
    using InputEdge = static_graph_details::SortableEdgeWithData<EdgeDataT>;
    using NodeIterator = static_graph_details::NodeIterator;
    using EdgeIterator = static_graph_details::EdgeIterator;
    using EdgeRange = range<EdgeIterator>;
    using NodeArrayEntry = static_graph_details::NodeArrayEntry;
    using EdgeArrayEntry = static_graph_details::EdgeArrayEntry<EdgeDataT>;

EdgeRange GetAdjacentEdgeRange(const NodeID node) const
    {
        return irange(BeginEdges(node), EndEdges(node));
    }

StaticGraph() {}

template <typename ContainerT> StaticGraph(const std::uint32_t nodes, const ContainerT &edges)
    {
        BOOST_ASSERT(std::is_sorted(const_cast<ContainerT &>(edges).begin(),
                                    const_cast<ContainerT &>(edges).end()));

InitializeFromSortedEdgeRange(nodes, edges.begin(), edges.end());
    }

StaticGraph(Vector<NodeArrayEntry> node_array_, Vector<EdgeArrayEntry> edge_array_)
        : node_array(std::move(node_array_)), edge_array(std::move(edge_array_))
    {
        BOOST_ASSERT(!node_array.empty());

number_of_nodes = static_cast<decltype(number_of_nodes)>(node_array.size() - 1);
        number_of_edges = static_cast<decltype(number_of_edges)>(node_array.back().first_edge);
        BOOST_ASSERT(number_of_edges <= edge_array.size());
        BOOST_ASSERT(number_of_nodes == node_array.size() - 1);
    }

unsigned GetNumberOfNodes() const { return number_of_nodes; }

unsigned GetNumberOfEdges() const { return number_of_edges; }

unsigned GetOutDegree(const NodeIterator n) const { return EndEdges(n) - BeginEdges(n); }

inline NodeIterator GetTarget(const EdgeIterator e) const
    {
        return NodeIterator(edge_array[e].target);
    }

auto &GetEdgeData(const EdgeIterator e) { return edge_array[e].data; }

const auto &GetEdgeData(const EdgeIterator e) const { return edge_array[e].data; }

EdgeIterator BeginEdges(const NodeIterator n) const
    {
        return EdgeIterator(node_array.at(n).first_edge);
    }

EdgeIterator EndEdges(const NodeIterator n) const
    {
        return EdgeIterator(node_array.at(n + 1).first_edge);
    }

// searches for a specific edge
    EdgeIterator FindEdge(const NodeIterator from, const NodeIterator to) const
    {
        for (const auto i : irange(BeginEdges(from), EndEdges(from)))
        {
            if (to == edge_array[i].target)
            {
                return i;
            }
        }
        return SPECIAL_EDGEID;
    }

/**
     * Finds the edge with the smallest `.weight` going from `from` to `to`
     * @param from the source node ID
     * @param to the target node ID
     * @param filter a functor that returns a `bool` that determines whether an edge should be
     * tested or not.
     *   Takes `EdgeData` as a parameter.
     * @return the ID of the smallest edge if any were found that satisfied *filter*, or
     * `SPECIAL_EDGEID` if no
     *   matching edge is found.
     */
    template <typename FilterFunction>
    EdgeIterator
    FindSmallestEdge(const NodeIterator from, const NodeIterator to, FilterFunction &&filter) const
    {
        static_assert(traits::HasDataMember<EdgeArrayEntry>::value,
                      "Filtering on .data not possible without .data member attribute");

EdgeIterator smallest_edge = SPECIAL_EDGEID;
        EdgeWeight smallest_weight = INVALID_EDGE_WEIGHT;
        for (auto edge : GetAdjacentEdgeRange(from))
        {
            const NodeID target = GetTarget(edge);
            const auto &data = GetEdgeData(edge);
            if (target == to && data.weight < smallest_weight &&
                std::forward<FilterFunction>(filter)(data))
            {
                smallest_edge = edge;
                smallest_weight = data.weight;
            }
        }
        return smallest_edge;
    }

EdgeIterator FindEdgeInEitherDirection(const NodeIterator from, const NodeIterator to) const
    {
        EdgeIterator tmp = FindEdge(from, to);
        return (SPECIAL_NODEID != tmp ? tmp : FindEdge(to, from));
    }

EdgeIterator
    FindEdgeIndicateIfReverse(const NodeIterator from, const NodeIterator to, bool &result) const
    {
        EdgeIterator current_iterator = FindEdge(from, to);
        if (SPECIAL_NODEID == current_iterator)
        {
            current_iterator = FindEdge(to, from);
            if (SPECIAL_NODEID != current_iterator)
            {
                result = true;
            }
        }
        return current_iterator;
    }

void Renumber(const std::vector<NodeID> &old_to_new_node)
    {
        std::vector<NodeID> new_to_old_node(number_of_nodes);
        for (auto node : util::irange<NodeID>(0, number_of_nodes))
            new_to_old_node[old_to_new_node[node]] = node;

Vector<NodeArrayEntry> new_node_array(node_array.size());

// Build up edge permutation
        auto new_edge_index = 0;
        std::vector<EdgeID> old_to_new_edge(edge_array.size(), SPECIAL_EDGEID);
        for (auto node : util::irange<NodeID>(0, number_of_nodes))
        {
            auto new_first_edge = new_edge_index;
            for (auto edge : GetAdjacentEdgeRange(new_to_old_node[node]))
            {
                edge_array[edge].target = old_to_new_node[edge_array[edge].target];
                old_to_new_edge[edge] = new_edge_index++;
            }
            new_node_array[node].first_edge = new_first_edge;
        }
        new_node_array.back().first_edge = new_edge_index;
        node_array = std::move(new_node_array);
        BOOST_ASSERT(std::find(old_to_new_edge.begin(), old_to_new_edge.end(), SPECIAL_EDGEID) ==
                     old_to_new_edge.end());

util::inplacePermutation(edge_array.begin(), edge_array.end(), old_to_new_edge);
    }

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

protected:
    template <typename IterT>
    void InitializeFromSortedEdgeRange(const std::uint32_t nodes, IterT begin, IterT end)
    {
        number_of_nodes = nodes;
        number_of_edges = static_cast<EdgeIterator>(std::distance(begin, end));
        node_array.reserve(number_of_nodes + 1);
        node_array.push_back(NodeArrayEntry{0u});
        auto iter = begin;
        for (auto node : util::irange(0u, nodes))
        {
            iter =
                std::find_if(iter, end, [node](const auto &edge) { return edge.source != node; });
            unsigned offset = std::distance(begin, iter);
            node_array.push_back(NodeArrayEntry{offset});
        }
        BOOST_ASSERT_MSG(
            iter == end,
            ("Still " + std::to_string(std::distance(iter, end)) + " edges left.").c_str());
        BOOST_ASSERT(node_array.size() == number_of_nodes + 1);

edge_array.resize(number_of_edges);
        std::transform(begin, end, edge_array.begin(), [](const auto &from) {
            return static_graph_details::edgeToEntry<EdgeArrayEntry>(
                from, traits::HasDataMember<EdgeArrayEntry>{});
        });
    }

protected:
    NodeIterator number_of_nodes = 0;
    EdgeIterator number_of_edges = 0;

Vector<NodeArrayEntry> node_array;
    Vector<EdgeArrayEntry> edge_array;
};

} // namespace osrm::util

#endif // STATIC_GRAPH_HPP

cmd: