<commit_before>/*
 * Lower Flows database and next hops computation.
 *
 * Copyright (C) 2018 Nextworks
 * Author: <NAME> <<EMAIL>>
 *
 * This file is part of rlite.
 *
 * 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 <string>
#include <sstream>
#include <iostream>
#include <queue>

#include "BaseRIB.pb.h"
#include "uipcp-normal-lfdb.hpp"

namespace rlite {

void
LFDB::dump(std::stringstream &ss) const
{
    ss << "Lower Flow Database:" << std::endl;
    for (const auto &kvi : db) {
        for (const auto &kvj : kvi.second) {
            const gpb::LowerFlow &flow = kvj.second;

            ss << "    Local: " << flow.local_node()
               << ", Remote: " << flow.remote_node()
               << ", Cost: " << flow.cost() << ", Seqnum: " << flow.seqnum()
               << ", State: " << flow.state() << ", Age: " << flow.age()
               << std::endl;
        }
    }

    ss << std::endl;
}

void
LFDB::dump_routing(std::stringstream &ss, const NodeId &local_node) const
{
    ss << "Routing table for node " << local_node << ":" << std::endl;
    for (const auto &kvr : next_hops) {
        std::string dst_node = kvr.first;

        if (dst_node.size() && kvr.second.size() == 1 &&
            kvr.second.front() == dflt_nhop) {
            /* Hide this entry, as it is covered by the default one. */
            continue;
        }

        ss << "    Remote: " << node_id_pretty(dst_node) << ", Next hops: ";
        for (auto lfa = kvr.second.begin();;) {
            ss << *lfa;
            if (++lfa == kvr.second.end()) {
                break;
            }
            ss << " ";
        }
        ss << std::endl;
    }
}

void
LFDB::compute_shortest_paths(
    const NodeId &source_node,
    const std::unordered_map<NodeId, std::list<Edge>> &graph,
    std::unordered_map<NodeId, DijkstraInfo> &info)
{
    std::priority_queue<PQInfo> frontier;

    frontier.push(PQInfo(source_node, 0));

    /* Initialize the per-node info map. */
    for (const auto &kvg : graph) {
        struct DijkstraInfo inf;

        inf.dist        = UINT_MAX;
        inf.visited     = false;
        info[kvg.first] = std::move(inf);
    }

    while (!frontier.empty()) {
        /* Select the closest node from the ones in the frontier. */
        PQInfo closer = frontier.top();
        frontier.pop();

        if (closer.dist == UINT_MAX) {
            break;
        }

        DijkstraInfo &info_min = info[closer.node];
        info_min.dist          = closer.dist;
        info_min.visited       = true;

        if (verbose) {
            std::cout << "Selecting node " << closer.node << std::endl;
        }

        // TODO use find()
        if (!graph.count(closer.node)) {
            continue; /* nothing to do */
        }

        const std::list<Edge> &edges = graph.at(closer.node);

        for (const Edge &edge : edges) {
            DijkstraInfo &info_to = info[edge.to];

            if (info_to.dist > info_min.dist + edge.cost) {
                info_to.dist = info_min.dist + edge.cost;
                info_to.nhop =
                    (closer.node == source_node) ? edge.to : info_min.nhop;
                frontier.push(PQInfo(edge.to, info_to.dist));
            }
        }
    }

    if (verbose) {
        std::cout << "Dijkstra result:" << std::endl;
        for (const auto &kvi : info) {
            std::cout << "    Node: " << kvi.first
                      << ", Dist: " << kvi.second.dist << ", Visited "
                      << kvi.second.visited << std::endl;
        }
    }
}

int
LFDB::compute_next_hops(const NodeId &local_node)
{
    std::unordered_map<NodeId, std::unordered_map<NodeId, DijkstraInfo>>
        neigh_infos;
    std::unordered_map<NodeId, std::list<Edge>> graph;
    std::unordered_map<NodeId, DijkstraInfo> info;

    /* Clean up state left from the previous run. */
    next_hops.clear();

    /* Build the graph from the Lower Flow Database. */
    graph[local_node] = std::list<Edge>();
    for (const auto &kvi : db) {
        for (const auto &kvj : kvi.second) {
            const gpb::LowerFlow *revlf;

            revlf = find(kvj.second.local_node(), kvj.second.remote_node());

            if (revlf == nullptr || revlf->cost() != kvj.second.cost()) {
                /* Something is wrong, this could be malicious or erroneous. */
                continue;
            }

            graph[kvj.second.local_node()].emplace_back(
                kvj.second.remote_node(), kvj.second.cost());
            if (!graph.count(kvj.second.remote_node())) {
                /* Make sure graph contains all the nodes, even if with
                 * empty lists. */
                graph[kvj.second.remote_node()] = std::list<Edge>();
            }
        }
    }

    if (verbose) {
        std::cout << "Graph [" << db.size() << " nodes]:" << std::endl;
        for (const auto &kvg : graph) {
            std::cout << kvg.first << ": {";
            for (const Edge &edge : kvg.second) {
                std::cout << "(" << edge.to << "," << edge.cost << "), ";
            }
            std::cout << "}" << std::endl;
        }
    }

    /* Compute shortest paths rooted at the local node, and use the
     * result to fill in the next_hops routing table. */
    compute_shortest_paths(local_node, graph, info);
    for (const auto &kvi : info) {
        if (kvi.first == local_node || !kvi.second.visited) {
            /* I don't need a next hop for myself. */
            continue;
        }
        next_hops[kvi.first].push_back(kvi.second.nhop);
    }

    if (lfa_enabled) {
        /* Compute the shortest paths rooted at each neighbor of the local
         * node, storing the results into neigh_infos. */
        for (const Edge &edge : graph[local_node]) {
            compute_shortest_paths(edge.to, graph, neigh_infos[edge.to]);
        }

        /* For each node V other than the local node ... */
        for (const auto &kvv : graph) {
            if (kvv.first == local_node) {
                continue;
            }

            /* For each neighbor U of the local node, excluding U ... */
            for (const auto &kvu : neigh_infos) {
                if (kvu.first == kvv.first) {
                    continue;
                }

                /* dist(U, V) < dist(U, local) + dist(local, V) */
                if (neigh_infos[kvu.first][kvv.first].dist <
                    neigh_infos[kvu.first][local_node].dist +
                        info[kvv.first].dist) {
                    bool dupl = false;

                    for (const NodeId &lfa : next_hops[kvv.first]) {
                        if (lfa == kvu.first) {
                            dupl = true;
                            break;
                        }
                    }

                    if (!dupl) {
                        next_hops[kvv.first].push_back(kvu.first);
                    }
                }
            }
        }
    }

    if (verbose) {
        std::stringstream ss;

        dump_routing(ss, local_node);
        std::cout << ss.str();
    }

    return 0;
}

gpb::LowerFlow *
LFDB::find(const NodeId &local_node, const NodeId &remote_node)
{
    const gpb::LowerFlow *lf = _find(local_node, remote_node);
    return const_cast<gpb::LowerFlow *>(lf);
}

const gpb::LowerFlow *
LFDB::_find(const NodeId &local_node, const NodeId &remote_node) const
{
    const auto it = db.find(local_node);
    std::unordered_map<NodeId, gpb::LowerFlow>::const_iterator jt;

    if (it == db.end()) {
        return nullptr;
    }

    jt = it->second.find(remote_node);

    return jt == it->second.end() ? nullptr : &jt->second;
}

} // namespace rlite
<commit_msg>uipcps: lfdb: save a map lookup by using map::find()<commit_after>/*
 * Lower Flows database and next hops computation.
 *
 * Copyright (C) 2018 Nextworks
 * Author: <NAME> <<EMAIL>>
 *
 * This file is part of rlite.
 *
 * 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 <string>
#include <sstream>
#include <iostream>
#include <queue>

#include "BaseRIB.pb.h"
#include "uipcp-normal-lfdb.hpp"

namespace rlite {

void
LFDB::dump(std::stringstream &ss) const
{
    ss << "Lower Flow Database:" << std::endl;
    for (const auto &kvi : db) {
        for (const auto &kvj : kvi.second) {
            const gpb::LowerFlow &flow = kvj.second;

            ss << "    Local: " << flow.local_node()
               << ", Remote: " << flow.remote_node()
               << ", Cost: " << flow.cost() << ", Seqnum: " << flow.seqnum()
               << ", State: " << flow.state() << ", Age: " << flow.age()
               << std::endl;
        }
    }

    ss << std::endl;
}

void
LFDB::dump_routing(std::stringstream &ss, const NodeId &local_node) const
{
    ss << "Routing table for node " << local_node << ":" << std::endl;
    for (const auto &kvr : next_hops) {
        std::string dst_node = kvr.first;

        if (dst_node.size() && kvr.second.size() == 1 &&
            kvr.second.front() == dflt_nhop) {
            /* Hide this entry, as it is covered by the default one. */
            continue;
        }

        ss << "    Remote: " << node_id_pretty(dst_node) << ", Next hops: ";
        for (auto lfa = kvr.second.begin();;) {
            ss << *lfa;
            if (++lfa == kvr.second.end()) {
                break;
            }
            ss << " ";
        }
        ss << std::endl;
    }
}

void
LFDB::compute_shortest_paths(
    const NodeId &source_node,
    const std::unordered_map<NodeId, std::list<Edge>> &graph,
    std::unordered_map<NodeId, DijkstraInfo> &info)
{
    std::priority_queue<PQInfo> frontier;

    frontier.push({source_node, 0});

    /* Initialize the per-node info map. */
    for (const auto &kvg : graph) {
        struct DijkstraInfo inf;

        inf.dist        = UINT_MAX;
        inf.visited     = false;
        info[kvg.first] = std::move(inf);
    }

    while (!frontier.empty()) {
        /* Select the closest node from the ones in the frontier. */
        PQInfo closer = frontier.top();
        frontier.pop();

        if (closer.dist == UINT_MAX) {
            break;
        }

        DijkstraInfo &info_min = info[closer.node];
        info_min.dist          = closer.dist;
        info_min.visited       = true;

        if (verbose) {
            std::cout << "Selecting node " << closer.node << std::endl;
        }

        auto graphit = graph.find(closer.node);
        if (graphit == graph.end()) {
            continue; /* nothing to do */
        }

        const std::list<Edge> &edges = graphit->second;

        for (const Edge &edge : edges) {
            DijkstraInfo &info_to = info[edge.to];

            if (info_to.dist > info_min.dist + edge.cost) {
                info_to.dist = info_min.dist + edge.cost;
                info_to.nhop =
                    (closer.node == source_node) ? edge.to : info_min.nhop;
                frontier.push({edge.to, info_to.dist});
            }
        }
    }

    if (verbose) {
        std::cout << "Dijkstra result:" << std::endl;
        for (const auto &kvi : info) {
            std::cout << "    Node: " << kvi.first
                      << ", Dist: " << kvi.second.dist << ", Visited "
                      << kvi.second.visited << std::endl;
        }
    }
}

int
LFDB::compute_next_hops(const NodeId &local_node)
{
    std::unordered_map<NodeId, std::unordered_map<NodeId, DijkstraInfo>>
        neigh_infos;
    std::unordered_map<NodeId, std::list<Edge>> graph;
    std::unordered_map<NodeId, DijkstraInfo> info;

    /* Clean up state left from the previous run. */
    next_hops.clear();

    /* Build the graph from the Lower Flow Database. */
    graph[local_node] = std::list<Edge>();
    for (const auto &kvi : db) {
        for (const auto &kvj : kvi.second) {
            const gpb::LowerFlow *revlf;

            revlf = find(kvj.second.local_node(), kvj.second.remote_node());

            if (revlf == nullptr || revlf->cost() != kvj.second.cost()) {
                /* Something is wrong, this could be malicious or erroneous. */
                continue;
            }

            graph[kvj.second.local_node()].emplace_back(
                kvj.second.remote_node(), kvj.second.cost());
            if (!graph.count(kvj.second.remote_node())) {
                /* Make sure graph contains all the nodes, even if with
                 * empty lists. */
                graph[kvj.second.remote_node()] = std::list<Edge>();
            }
        }
    }

    if (verbose) {
        std::cout << "Graph [" << db.size() << " nodes]:" << std::endl;
        for (const auto &kvg : graph) {
            std::cout << kvg.first << ": {";
            for (const Edge &edge : kvg.second) {
                std::cout << "(" << edge.to << "," << edge.cost << "), ";
            }
            std::cout << "}" << std::endl;
        }
    }

    /* Compute shortest paths rooted at the local node, and use the
     * result to fill in the next_hops routing table. */
    compute_shortest_paths(local_node, graph, info);
    for (const auto &kvi : info) {
        if (kvi.first == local_node || !kvi.second.visited) {
            /* I don't need a next hop for myself. */
            continue;
        }
        next_hops[kvi.first].push_back(kvi.second.nhop);
    }

    if (lfa_enabled) {
        /* Compute the shortest paths rooted at each neighbor of the local
         * node, storing the results into neigh_infos. */
        for (const Edge &edge : graph[local_node]) {
            compute_shortest_paths(edge.to, graph, neigh_infos[edge.to]);
        }

        /* For each node V other than the local node ... */
        for (const auto &kvv : graph) {
            if (kvv.first == local_node) {
                continue;
            }

            /* For each neighbor U of the local node, excluding U ... */
            for (const auto &kvu : neigh_infos) {
                if (kvu.first == kvv.first) {
                    continue;
                }

                /* dist(U, V) < dist(U, local) + dist(local, V) */
                if (neigh_infos[kvu.first][kvv.first].dist <
                    neigh_infos[kvu.first][local_node].dist +
                        info[kvv.first].dist) {
                    bool dupl = false;

                    for (const NodeId &lfa : next_hops[kvv.first]) {
                        if (lfa == kvu.first) {
                            dupl = true;
                            break;
                        }
                    }

                    if (!dupl) {
                        next_hops[kvv.first].push_back(kvu.first);
                    }
                }
            }
        }
    }

    if (verbose) {
        std::stringstream ss;

        dump_routing(ss, local_node);
        std::cout << ss.str();
    }

    return 0;
}

gpb::LowerFlow *
LFDB::find(const NodeId &local_node, const NodeId &remote_node)
{
    const gpb::LowerFlow *lf = _find(local_node, remote_node);
    return const_cast<gpb::LowerFlow *>(lf);
}

const gpb::LowerFlow *
LFDB::_find(const NodeId &local_node, const NodeId &remote_node) const
{
    const auto it = db.find(local_node);
    std::unordered_map<NodeId, gpb::LowerFlow>::const_iterator jt;

    if (it == db.end()) {
        return nullptr;
    }

    jt = it->second.find(remote_node);

    return jt == it->second.end() ? nullptr : &jt->second;
}

} // namespace rlite

{'fraction_non_alphanumeric': 0.13483413733547733, 'fraction_numerical': 0.0023822285748317552, 'mean_word_length': 1.8312257629404822, 'pattern_counts': {'":': 4, '<': 257, '<?xml version=': 0, '>': 56, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2116950', 'n_tokens_mistral': 5307, 'n_tokens_neox': 5062, 'n_words': 1339}