Tswitch

Thread Demolition Derby

thsearch.cc

#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <list>
#include <thlib.h>

using namespace std;

// Max nodes in the node set.
const int MAXNODES = 200;

/*
 * Input a weighted digraph and a series of node pairs, and find a best
 * path between each pair.
 *
 * Input format:
 *   from -> to cost
 *        -> orto thiscost
 *   @
 *   from => to
 *
 * Node names are non-blank strings.  The portion before the @ define the
 * graph, the from => to items following are requests for shortest path.
 *
 * If the input graph contains negative values, the resulting paths are the
 * lowest-cost acyclic paths.  If the input is non-negative, the search trims
 * paths which have passed the best known max; otherwise, a full exhaustive
 * search.
 *
 */

/*
 * I'm giving the nodes integer names for building the graph, and using a 
 * statically-allocated map to keep track of it all.  This probably saves 
 * space, but my real worry is that I don't know if I can bit-copy a string,
 * so I don't want to th_fork() with strings on the stack. 
 */

/* Names to numbers, each way.  Unknown names map to new integers, unknown
   integers shouldn't be mapped.  Subscript with a string to enter it, then
   you may use either the string or associated integer. */
class NameMap {
private:
        int next;
        map<int, string> itos;
        map<string, int> stoi;
public:
        NameMap(): next(0) { }
        string operator[](int i) { return itos[i]; }
        int operator[](string s) { 
                map<string, int>::iterator i = stoi.find(s);
                if(i == stoi.end()) {
                        // New string.  Assign an id.
                        stoi[s] = next;
                        itos[next] = s;
                        return next++;
                } else
                        // Old string. Return its id.
                        return i->second;
        }
} nmap;

/* Weights.  Integers that know about positive infinity.   Assumes normal
   weights are always small compared to the value used for infinity. */
class Weight {
        enum { infinity = 0x7fffffff };
        int value;
public:
        Weight(int i = 0) { value = i; }
        static Weight inf() { return Weight(infinity); }
        operator int() { return value; }
        int val() { return value; }
        bool infinite() { return value == infinity; }
        Weight & operator=(int i) { value = i; return *this; }
};
Weight operator+(Weight a, Weight b)
{
        if(a.infinite() || b.infinite()) return Weight::inf();
        return Weight(a.val() + b.val());
}
Weight operator+(Weight a, int b) { return a + Weight(b); }
Weight operator+(int a, Weight b) { return Weight(a) + b; }
Weight operator-(Weight a, Weight b)
{
        if(a.infinite() && b.infinite()) return Weight(0);
        if(a.infinite()) return Weight::inf();
        return Weight(a.val() - b.val());
}
Weight operator-(Weight a, int b) { return a - Weight(b); }
Weight operator-(int a, Weight b) { return Weight(a) - b; }
ostream &operator<<(ostream &o, Weight w)
{
        if(w.infinite()) o << "infinity";
        else o << w.val();
        return o;
}

/* Graph itself.  Implemented as a map of sources to a map of sinks to 
   Weights. */
class Graph: public map<int, map<int, Weight> > {
        bool negs;              // There are negative weights.
public:
        Graph(): negs(false) { }

        // Iterator to denote an array of arcs adjacent to a source.
        typedef iterator adjptr_t;

        // Iterator type for scanning the arcs adjacent to a source.
        typedef map<int, Weight>::iterator adjitor_t;

        // Look up a weight.
        Weight operator()(int a, int b) {
                iterator i = find(a);
                if(i == end()) return Weight::inf();
                adjitor_t j = i->second.find(b);
                if(j == i->second.end()) return Weight::inf();
                return j->second;
        }

        // Set a weight.
        void set(int a, int b, int v) {
                iterator i = find(a);
                if(i == end()) {
                        // Not yet any nodes adjacent to a.  Add a map
                        // to hold them.
                        insert(pair<int, map<int, Weight> >
                               (a, map<int, Weight>()));
                        i = find(a);
                }
                i->second[b] = Weight(v);
        }
        
        // Are there negative weights?
        bool negwt() { return negs; }

        // Get the nodes adjacent to a start.  
        typedef map<int, Weight> adj_t;
        adj_t * adj(int i) { 
                adjptr_t ret = find(i);
                if(ret == end()) return 0;
                return &find(i)->second;
        }

        // Read in to the @ terminator.
        string read(istream &, NameMap &);
} graph;

// See if a string looks like an integer.
bool intlike(string s)
{
        if(s.length() >= 2 && s[0] == '-' && 
           s.find_first_not_of("0123456789", 1) == string::npos)
                return true;
        return s.find_first_not_of("0123456789") == string::npos;
}

// Read the graph description.  Terminates with the @ marker or eof.  Returns
// an error message or "OK".
string Graph::read(istream &in, NameMap &nmap)
{
        string fr;              // From node.
        string oldfr = "";      // Previous from node.

        // Read stuff.
        while(in >> fr) {
                if(fr == "@") break;

                string arrow,   // Input ->
                        to;     // Input dest node name.

                // What we read is either a source node name or a -> 
                // symbol, in which case the previous source name is to be
                // reused.  In that case, there better be one.
                if(fr == "->") {
                        // Use the old one as a from.
                        if(oldfr == "") return "Input started with ->";
                        fr = oldfr;
                } else {
                        // Not an ->.  See if its a source node, and see if
                        // the -> follows it.
                        if(intlike(fr))
                                return "Numeric source node name.";
                        oldfr = fr;
                        if(!(in >> arrow)) 
                                return "Triple ended after start node";
                        if(arrow != "->") 
                                return string("Expected -> found ") + arrow;
                }

                // Look for a dest node name and weight.
                int val;
                if(!(in >> to)) return "Triple ended after arrow.";
                if(intlike(to)) return "Numeric dest node name.";
                if(!(in >> val)) return "Triple missing weight";

                // Set the link in the graph.
                set(nmap[fr], nmap[to], val);
                if(val < 0) negs = true;
        }

        return "OK";
}

/* I need a simple set abstaction that can be correctly copied by a simple
   bit-copy of the object.  The STL uses trees, so a simple bit-copy of a set
   will probably not.  Therefore, an STL set object stored on the stack will
   probably not survive a th_fork().  Since I need to make a set of small
   integers, and need only to add and test for membership, a very simple bit
   map will serve nicely. */
template<const int N>
class Set {
        enum { besize = 8*sizeof(unsigned) };
        unsigned map[N / besize + (N % besize > 0)];
public:
        Set() { memset(map, 0, sizeof map); }
        void add(int n) { map[n/besize] |= 1 << n%besize; }
        bool has(int n) { return map[n/besize] & 1 << n%besize; }
};

/* I need to keep track of partial paths, the collection of which will
   essentially look like a tree with the links pointing from child to parent.
   To manage these we have linked structs with a basic reference count
   mechanism. */
struct PathNode {
private:
        int refct;              // How many pointers to us?
        PathNode *next;         // Next node.

        // Private constructor.  Need to be careful about creating nodes
        // which contain links to others.
        PathNode(int v, PathNode *n): refct(1), vert(v), next(n) { }
public:
        int vert;               // Which vertex is this?

        // Public constructor.  Only for list ends.
        PathNode(int v): refct(1), vert(v), next(0) { }

        // This is how we make new nodes.
        static void extend(PathNode* &n, int v) {
                n = new PathNode(v, n);
        }

        // Ref count manipulation.
        void ref() { ++refct; }
        void unref() { 
                if(--refct == 0) delete this;
        }
        ~PathNode() { if(next) next->unref(); }

        // Print a chain in reverse order.  Nodes are mapped to names using
        // the nmap parameter.
        void prrev(ostream &strm, NameMap &nmap) {
                if(next) { 
                        next->prrev(strm, nmap);
                        strm << " => ";
                }
                strm << nmap[vert];
        }
};

// Thread exit codes.
enum {
        EX_BEST,        // Exited after finding best solution so far.
        EX_NONBEST,     // Exited after finding a poorer solution.
        EX_TRIM,        // Exited after exeeding best in non-neg graph.
        EX_DEAD,        // Reached a dead end.
        EX_DIM          // How many of these are there?
};

// This performs the threaded graph search.
void find(int fr, int to)
{
        // Stuff that needs to vary between threads (allocated on stacks).
        Set<MAXNODES> seen;                     // Nodes visited.
        PathNode *path = new PathNode(fr);      // Path (links backward).
        Weight pathcost(0);                     // Cost of current path.

        // Stuff shared between the threads.  These are declared static so
        // they will not be allocated on the stack.  Th_fork() will not
        // attempt to make copies of them, and all the threads will share
        // the same underlying objects.
        static list<th_id_t> zombies;           // Threads that need waiting.
        static int ncreated, nwaited;           // # workers created and waited
        static PathNode *bestpath;              // Best known path.
        static Weight bestcost;                 // Cost of the best path.

        // Initialize current best.
        bestpath = new PathNode(fr);
        PathNode::extend(bestpath, to);
        bestcost = graph(fr, to);

        // Start the monitor thread, which disposes of dead zombies, makes
        // some stats, determines when we are done, and prints the result.
        if(th_fork() != ARE_CHILD) {
                // Note: This is the parent from the first th_fork().  We
                // know this is the main thread.

                ncreated = 1;           // For the child we just created
                zombies.clear();        //   who is still working.
                nwaited = 0;            // Since we haven't waited any.

                // Statistics vars.
                int excode[EX_DIM]      // Counts by exit code.
                        = { 0 };

                // Collect zombies until the search is done.
                while(1) {
                        // Let the workers work.
                        th_yield();

                        // Collect the available bodies.
                        while(!zombies.empty()) { 
                                th_id_t z = zombies.front();
                                zombies.pop_front();
                                ++excode[th_wait(z)];
                                ++nwaited;
                        }

                        // If there are no more active threads, we're done.
                        if(nwaited == ncreated) break;
                }

                // Print the result.
                cout << nmap[fr] << " => " << nmap[to] << ": " << bestcost
                     << " [ " ;
                bestpath->prrev(cout, nmap);
                cout << " ] " << endl;

                // Print statistics.
                cout << "  Search Threads:        " << ncreated << endl;
                cout << "    Found New Best Soln: " << excode[EX_BEST] << endl;
                cout << "    Found Poorer Soln:   " << excode[EX_NONBEST] 
                     << endl;
                cout << "    Trimmed:             " << excode[EX_TRIM] << endl;
                cout << "    Reached Dead End:    " << excode[EX_DEAD] << endl;

                delete bestpath;

                return;
        }

        // Perform the search.
        path->ref();
        while(1) {
                // Find all nodes adjacent to the current path.  For the
                // extra ones, start another thread.
                Graph::adj_t *adj = graph.adj(path->vert);
                Graph::adjitor_t i; 

                // Find the first un-visited neighbor.  I will go there.
                if(adj) {
                        for(i = adj->begin(); i != adj->end(); ++i)
                                if(!seen.has(i->first)) break;
                }

                // See if we found one.
                if(!adj || i == adj->end()) {
                        // There is no unvisited neighbor for me.  I am
                        // useless, and shall therefore exit.
                        path->unref();
                        zombies.push_back(th_me());
                        th_exit(EX_DEAD);
                }

                // Here's where I go.
                int next = i->first;

                // If there are other adjacent neighbors, create threads for
                // them.
                for(++i; i != adj->end(); ++i) {
                        if(seen.has(i->first)) continue;

                        // Record the additional reference to the path.
                        // Logically, it belongs in the child case, but it
                        // may be a long time before that runs, and I want
                        // to make sure the node isn't delete first.
                        path->ref();

                        if(th_fork() == ARE_CHILD) {
                                // This assumes I can copy the iterator
                                // well enough for i->first to work.
                                next = i->first;

                                ++ncreated;

                                break;
                        }
                }

                // Add to the existing search path.
                pathcost = pathcost + graph(path->vert, next);
                PathNode::extend(path, next);
                seen.add(next);

                // See what we want to do with it.
                if(next == to) {
                        // We'll exit soon.  Record ourselves.
                        zombies.push_back(th_me());

                        // Found a path to the required dest.
                        if(pathcost < bestcost) {
                                // New best path.
                                bestpath->unref();
                                bestpath = path;
                                bestcost = pathcost;
                                th_exit(EX_BEST);
                        } else {
                                // More expensive way to make the trip.
                                path->unref();
                                th_exit(EX_NONBEST);
                        }
                }

                // Not there yet.  In some cases, we can give up anyway.
                if(!graph.negwt() && pathcost >= bestcost) {
                        // No negative links, and we've reached the best
                        // known max.
                        path->unref();
                        zombies.push_back(th_me());
                        th_exit(EX_TRIM);
                }

                th_yield();
        }
}

// Read in a request.
string rdreq(istream &in, NameMap &nmap, string &frs, string &tos)
{
        string arrow;

        if(!(in >> frs)) return "EOF";
        if(intlike(frs)) return "Numeric source name in request.";
        if(!(in >> arrow)) return "Missing => in request.";
        if(arrow != "=>") return string("Expected => found ") + arrow;
        if(!(in >> tos)) return "Request ended after arrow.";
        if(intlike(tos)) return "Numeric sink name in request.";
        return "OK";
}

main()
{
        // Read the graph.
        string s = graph.read(cin, nmap);
        if(s != "OK") {
                cerr << "Bad input: " << s << endl;
                exit(1);
        }

        // Fire up the threads.  Takes big stacks.
        th_init();
        th_stksize(8*DEF_STACK_SIZE);

        // Try to find each path.
        while(true) {
                // Read a request
                string from, to;
                string msg =  rdreq(cin, nmap, from, to);
                if(msg == "EOF") break;
                if(msg != "OK") {
                        cout << "Request Input Error: " << msg << endl;
                        exit(1);
                }

                // Map the names to node numbers and solve the query.
                int fromi = nmap[from];
                int toi = nmap[to];
                if(fromi == toi) 
                        cout << from << " => " << to << ": 0 [ ]" << endl;
                else
                        find(fromi, toi);
        }
}

Thread Demolition Derby