main.cc

Go to the documentation of this file.

#include <cstdint>
#include <limits>
#include <print>
#include <queue>
#include <stack>
#include <string>
#include <vector>
 
#include "include/broom-unordered-map.h"
#include "include/broom.h"
 
#if defined(__clang__) || defined(__GNUC__)
#define NOINLINE __attribute__((noinline))
#elif defined(_MSC_VER)
#define NOINLINE __declspec(noinline)
#endif
 
class Node {
 public:
  Node(std::string s, size_t id) : name_(s), id_(id) {}
  ~Node() { std::println("Destroying node: {}", id_); }
  Node* Connect(Node* which, size_t distance) {
    adjacent_nodes_.push_back({which, distance});
    which->adjacent_nodes_.push_back({this, distance});
    return this;
  }
 
  const std::string& Name() const { return name_; }
  const std::vector<std::pair<Node*, size_t>>& Adjacent() const {
    return adjacent_nodes_;
  }
  size_t Identifier() const { return id_; }
 
 private:
  std::string name_;
  std::vector<std::pair<Node*, size_t>> adjacent_nodes_;
  size_t id_;
};
 
class Graph {
 public:
  Graph() = default;
  Node* New(std::string s) {
    adj_[s] = broom::allocate<Node>(1, s, id_++);
    return adj_[s];
  }
 
  Node* operator[](std::string s) { return adj_[s]; }
 
  size_t ShortestPath(std::string from, std::string to) {
    std::queue<Node*> to_visit;
    Node* from_node = adj_[from];
    Node* to_node = adj_[to];
    std::vector<size_t> distance(adj_.size(),
                                 std::numeric_limits<size_t>::max());
    to_visit.push(from_node);
    distance[from_node->Identifier()] = 0;
 
    while (!to_visit.empty()) {
      Node* current = to_visit.front();
      to_visit.pop();
 
      for (auto [n, dist] : current->Adjacent()) {
        if (distance[n->Identifier()] >
            distance[current->Identifier()] + dist) {
          distance[n->Identifier()] = distance[current->Identifier()] + dist;
          to_visit.push(n);
        }
      }
    }
    return distance[to_node->Identifier()];
  }
 
 private:
  broom::unordered_map<std::string, Node*> adj_;
  size_t id_ = 0;
};
 
NOINLINE void CalculateShortestPaths(Graph& g) {
  std::println("Shortest path from home 8 to library: {}",
               g.ShortestPath("home 8", "library"));
  std::println("Shortest path from home bus station to library: {}",
               g.ShortestPath("bus station", "library"));
  std::println("Shortest path from home 4 to library: {}",
               g.ShortestPath("home 4", "library"));
  std::println("Shortest path from home 5 to home 7: {}",
               g.ShortestPath("home 5", "home 7"));
}
 
NOINLINE void GraphInFunction() {
  Graph collected_g;
  collected_g.New("bakery");
  collected_g.New("restaurant")->Connect(collected_g["bakery"], 21);
  collected_g.New("fountain")
      ->Connect(collected_g["bakery"], 2)
      ->Connect(collected_g["restaurant"], 34);
}
 
int main() {
  broom::scope gc_scope;
  std::println("Creating graph in function");
  GraphInFunction();
  // The nodes from collected_g will be alive here.
  std::println("Creating new graph");
  Graph g;
  g.New("library");
  g.New("train station")->Connect(g["library"], 12);
  g.New("bus station")
      ->Connect(g["train station"], 3)
      ->Connect(g["library"], 70);
  g.New("home 1")->Connect(g["train station"], 17);
  g.New("home 2")->Connect(g["home 1"], 2);
  g.New("home 3")
      ->Connect(g["home 1"], 17)
      ->Connect(g["train station"], 95)
      ->Connect(g["library"], 9);
  g.New("home 4")
      ->Connect(g["home 3"], 16)
      ->Connect(g["home 1"], 103)
      ->Connect(g["train station"], 5);
  g.New("home 5")->Connect(g["train station"], 27);
  g.New("home 6")
      ->Connect(g["home 5"], 173)
      ->Connect(g["home 1"], 2304)
      ->Connect(g["library"], 123)
      ->Connect(g["home 2"], 3);
  g.New("home 7")->Connect(g["library"], 78);
  g.New("home 8")->Connect(g["home 7"], 421);
  std::println("Created new graph");
 
  // Force collect the collected_g. This may or may not always happen, depending
  // on what bytes are scanned. Broom is a conservative GC, so it might make
  // mistakes and keep dead allocations alive.
  broom::force_collection();
  CalculateShortestPaths(g);
  return 0;
}