manythreads.cs

using System;
using System.Threading;
using System.Collections.Generic;

public class Node {
	Node n1, n2, n3, n4;
#if EDGE8
	Node n5, n6, n7, n8;
#endif

	public void connect (Node _n1, Node _n2, Node _n3, Node _n4
#if EDGE8
			, Node _n5, Node _n6, Node _n7, Node _n8
#endif
			     ) {
		n1 = _n1;
		n2 = _n2;
		n3 = _n3;
		n4 = _n4;
#if EDGE8
		n5 = _n5;
		n6 = _n6;
		n7 = _n7;
		n8 = _n8;
#endif
	}

	public int countNodes () {
		Queue<Node> q = new Queue<Node> ();
		HashSet<Node> s = new HashSet<Node> ();
		/*
		q.Enqueue (this);
		while (q.Count > 0) {
			Node n = q.Dequeue ();
			if (s.Contains (n))
				continue;
			s.Add (n);
			q.Enqueue (n.n1);
			q.Enqueue (n.n2);
			q.Enqueue (n.n3);
			q.Enqueue (n.n4);
#if EDGE8
			q.Enqueue (n.n5);
			q.Enqueue (n.n6);
			q.Enqueue (n.n7);
			q.Enqueue (n.n8);
#endif
		}
		*/
		return s.Count;
	}

	static void connectNode (Node n, Node[] nodes, Random r) {
		int size = nodes.Length;
		n.connect (nodes [r.Next (size)],
				nodes [r.Next (size)],
				nodes [r.Next (size)],
				nodes [r.Next (size)]
#if EDGE8
				, nodes [r.Next (size)],
				nodes [r.Next (size)],
				nodes [r.Next (size)],
				nodes [r.Next (size)]
#endif
			   );
	}

	public static Node randomGraph (int size, Random r) {
		Node[] nodes = new Node [size];
		for (int i = 0; i < size; ++i)
			nodes [i] = new Node ();
		for (int i = 0; i < size; ++i)
			connectNode (nodes [i], nodes, r);
		return nodes [0];
	}

	public static Node otherRandomGraph (int size, int bufsize, Random r) {
		int i;
		Node[] buffer = new Node [bufsize];
		Node n = null;

		for (i = 0; i < bufsize; ++i)
			n = buffer [i] = new Node ();
		for (i = 0; i < bufsize; ++i)
			connectNode (buffer [i], buffer, r);
		for (; i < size; ++i) {
			n = new Node ();
			int j = r.Next (bufsize);
			buffer [j] = n;
			connectNode (n, buffer, r);
		}
		/* in case of pinning */
		for (i = 0; i < bufsize; ++i)
			buffer [i] = null;
		return n;
	}

	public static void RecursiveThreader (object o) {
		int depth = (int)o;
		Random r = new Random ();

		if (depth > 3) {
			otherRandomGraph (50000, 128, r);
		} else {
			Thread t1 = new Thread (new ParameterizedThreadStart (RecursiveThreader));
			Thread t2 = new Thread (new ParameterizedThreadStart (RecursiveThreader));
			t1.Start (depth + 1);
			otherRandomGraph (r.Next (10000), 128, r);
			t2.Start (depth + 2);
			t1.Join ();
			t2.Join ();
		}
	}

	public static void ThreadStarter (object o) {
		int id = (int)o;
		for (int i = 0; i < 20; ++i) {
			Thread t = new Thread (new ParameterizedThreadStart (RecursiveThreader));
			t.Start (0);
			t.Join ();
			Console.WriteLine ("thread " + id);
		}
	}

	public static int Main () {
		//Node g = otherRandomGraph (8000000, 128, r);
		Random r = new Random ();
		Node g = randomGraph (4000000, r);
		Thread[] ts = new Thread [8];
		for (int i = 0; i < ts.Length; ++i) {
			ts [i] = new Thread (new ParameterizedThreadStart (ThreadStarter));
			ts [i].Start (i);
		}
		for (int i = 0; i < ts.Length; ++i)
			ts [i].Join ();
		Console.WriteLine ("nodes: " + g.countNodes ());
		return 0;
	}
}