Beispiellösung

Content

#ifndef HASH_HPP
#define HASH_HPP

#include <cassert>
#include <cstdlib>
#include <functional>
#include <memory>
#include <utility>

template<typename Key, typename Value>
class Hash {
   public:
      using Object = std::pair<const Key, Value>;
   private:
      struct Node;
      using NodePtr = std::shared_ptr<Node>;
      struct Node {
	 Node(Object object) : object(std::move(object)) {
	 }
	 Node(Object object, NodePtr next) :
	    object(std::move(object)), next(next) {
	 }
	 Object object;
	 NodePtr next;
      };
      const std::size_t dim;
      std::shared_ptr<NodePtr[]> bucket;
      std::hash<Key> hash;
      std::size_t count;
   public:

      class Iterator {
	 public:
	    friend Hash;
	    Iterator() : dim(0), index(0) {
	    }
	    Iterator(Hash& hash) :
		  dim(hash.dim), bucket(hash.bucket), index(0) {
	       advance();
	    }
	    Iterator(Hash& hash, std::size_t index, NodePtr prev, NodePtr node) :
		  dim(hash.dim), bucket(hash.bucket), index(index),
		  prev(prev), node(node) {
	       assert(node && index < dim);
	    }
	    Object& operator*() {
	       return node.lock()->object;
	    }
	    const Object& operator*() const {
	       return node.lock()->object;
	    }
	    Object* operator->() {
	       return &node.lock()->object;
	    }
	    Iterator& operator++() {
	       advance();
	       return *this;
	    }
	    bool operator==(const Iterator& other) {
	       bool end1 = index >= dim;
	       bool end2 = other.index >= other.dim;
	       if (end1 && end2) return true;
	       if (end1 || end2) return false;
	       return
		  bucket.lock() == other.bucket.lock() &&
		  index == other.index &&
		  node.lock() == other.node.lock();
	    }
	    bool operator!=(const Iterator& other) {
	       return !(*this == other);
	    }
	 private:
	    void advance() {
	       /* move to next object */
	       auto b = bucket.lock();
	       if (b) {
		  auto n = node.lock();
		  if (n) {
		     node = n->next;
		     n = node.lock();
		     if (!n) ++index;
		  }
		  if (!n) {
		     while (index < dim && !b[index]) {
			++index;
		     }
		     if (index < dim) {
			node = b[index];
		     }
		  }
	       } else {
		  node = NodePtr(); index = dim;
	       }
	    }
	    std::size_t dim;
	    std::weak_ptr<NodePtr[]> bucket;
	    std::size_t index; /* current location in bucket table */
	    std::weak_ptr<Node> prev; /* previous object, if any in the same list */
	    std::weak_ptr<Node> node; /* current object at bucket[index] */
      };

      Hash(std::size_t dim) :
	 // dim(dim), bucket(std::make_shared<NodePtr[]>(dim)) {
	 dim(dim), bucket(new NodePtr[dim]), count(0) {
      }
      std::pair<Iterator, bool> insert(Object object) {
	 auto index = hash(object.first) % dim;
	 auto ptr = bucket[index];
	 NodePtr prev;
	 while (ptr && ptr->object.first != object.first) {
	    prev = ptr; ptr = ptr->next;
	 }
	 bool inserted;
	 if (ptr) {
	    inserted = false;
	 } else {
	    ptr = std::make_shared<Node>(std::move(object), bucket[index]);
	    bucket[index] = ptr;
	    prev = nullptr;
	    inserted = true;
	    ++count;
	 }
	 return std::make_pair(Iterator(*this, index, prev, ptr), inserted);
      }
      Iterator find(Key key) {
	 auto index = hash(key) % dim;
	 auto ptr = bucket[index];
	 NodePtr prev;
	 while (ptr && ptr->object.first != key) {
	    prev = ptr; ptr = ptr->next;
	 }
	 if (ptr) {
	    return Iterator(*this, index, prev, ptr);
	 } else {
	    return Iterator();
	 }
      }
      void erase(Iterator it) {
	 if (it.bucket.lock() == bucket && it.index < dim) {
	    auto node = it.node.lock();
	    auto prev = it.prev.lock();
	    if (node) {
	       if (prev) {
		  prev->next = node->next;
	       } else {
		  bucket[it.index] = node->next;
	       }
	       --count;
	    }
	 }
      }
      template<typename F>
      void for_each(F&& f) {
	 for (std::size_t index = 0; index < dim; ++index) {
	    auto ptr = bucket[index];
	    while (ptr) {
	       f(ptr->object);
	       ptr = ptr->next;
	    }
	 }
      }
      Iterator begin() {
	 return Iterator(*this);
      }
      Iterator end() {
	 return Iterator();
      }
      std::size_t size() const {
	 return count;
      }
};

#endif
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include "Hash.hpp"

constexpr std::size_t hashdim = 32;

struct Item;
using ItemPtr = std::shared_ptr<Item>;
using Dependencies = Hash<std::string, ItemPtr>;
struct Item {
   Item(std::string name) :
      name(std::move(name)), dependencies(hashdim), reversed(hashdim) {
   }
   std::string name;
   Dependencies dependencies; /* this item depends on these other items */
   Dependencies reversed;     /* items that depend on us */
};

int main() {
   Hash<std::string, ItemPtr> items(hashdim);

   /* lookup an item by name and create it, if it does not exist yet */
   auto lookup = [&items](const std::string& name) -> ItemPtr {
      auto it = items.find(name);
      if (it == items.end()) {
	 auto item = std::make_shared<Item>(name);
	 std::tie(it, std::ignore) = items.insert(std::make_pair(name, item));
      }
      return it->second;
   };

   /* build data structure */
   std::string line;
   while (std::getline(std::cin, line)) {
      std::istringstream in(line);
      std::string name;
      if (!(in >> name)) continue;
      auto item = lookup(name);
      std::string depname;
      while (in >> depname) {
	 auto dep = lookup(depname);
	 item->dependencies.insert(std::make_pair(depname, dep));
	 dep->reversed.insert(std::make_pair(name, item));
      }
   }

   /* topological sort */
   while (items.size() > 0) {
      std::size_t removed = 0;
      auto it = items.begin();
      while (it != items.end()) {
	 auto next = it; ++next;
	 auto item = it->second;
	 if (item->dependencies.size() == 0) {
	    /* no dependencies left for item:
	       print it and wipe it entirely
	       from our data structure */
	    std::cout << item->name << std::endl;
	    for (auto& revdepobj: item->reversed) {
	       auto revdep = revdepobj.second;
	       auto it = revdep->dependencies.find(item->name);
	       revdep->dependencies.erase(it);
	    }
	    items.erase(it);
	    ++removed;
	 }
	 it = next;
      }
      if (removed == 0) {
	 std::cerr << "reference cycle!" << std::endl; break;
      }
   }

   for (auto& object: items) {
      auto item = object.second;
      std::cout << item->name << ":";
      for (auto& depobj: item->dependencies) {
	 auto dep = depobj.second;
	 std::cout << " " << dep->name;
      }
      std::cout << std::endl;
   }
}
theon$ g++ -std=c++17 -Wall -o tsort tsort.cpp
theon$ valgrind ./tsort 
==3216== Memcheck, a memory error detector
==3216== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3216== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3216== Command: ./tsort
==3216== 
hinfahren
zur_bank_gehen
pin_eingeben
geldautomat_bedienen
geld_abheben
geld_haben
tanken
ware_nehmen
bezahlen
zurueckfahren
einkauf_erledigen
essen_kochen
==3216== 
==3216== HEAP SUMMARY:
==3216==     in use at exit: 5,648 bytes in 2 blocks
==3216==   total heap usage: 167 allocs, 165 frees, 98,766 bytes allocated
==3216== 
==3216== LEAK SUMMARY:
==3216==    definitely lost: 0 bytes in 0 blocks
==3216==    indirectly lost: 0 bytes in 0 blocks
==3216==      possibly lost: 5,648 bytes in 2 blocks
==3216==    still reachable: 0 bytes in 0 blocks
==3216==         suppressed: 0 bytes in 0 blocks
==3216== Rerun with --leak-check=full to see details of leaked memory
==3216== 
==3216== For counts of detected and suppressed errors, rerun with: -v
==3216== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ 

Was passiert aber, wenn in der Eingabe Referenzzyklen enthalten sind?

theon$ cat cycle
a b c
b d e
c g
e c
d f g
f a
theon$ valgrind ./tsort 
==3236== Memcheck, a memory error detector
==3236== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3236== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3236== Command: ./tsort
==3236== 
g
c
e
reference cycle!
a: b
f: a
d: f
b: d
==3236== 
==3236== HEAP SUMMARY:
==3236==     in use at exit: 11,152 bytes in 30 blocks
==3236==   total heap usage: 65 allocs, 35 frees, 89,408 bytes allocated
==3236== 
==3236== LEAK SUMMARY:
==3236==    definitely lost: 128 bytes in 1 blocks
==3236==    indirectly lost: 5,376 bytes in 27 blocks
==3236==      possibly lost: 5,648 bytes in 2 blocks
==3236==    still reachable: 0 bytes in 0 blocks
==3236==         suppressed: 0 bytes in 0 blocks
==3236== Rerun with --leak-check=full to see details of leaked memory
==3236== 
==3236== For counts of detected and suppressed errors, rerun with: -v
==3236== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ 

Ist das bei Ihnen auch der Fall? Woran liegt es? Wie kann das Problem vermieden werden?