From 48136174e089bb1650c0401cd885075a9fa243a1 Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Mon, 26 Feb 2007 12:56:28 +0100
Subject: [PATCH] add code to "balance" the switch fabric tree

---
 src/edu/berkeley/fleet/slipway/Slipway.java |   27 +++++++++++++++++++++++++--
 1 file changed, 25 insertions(+), 2 deletions(-)

diff --git a/src/edu/berkeley/fleet/slipway/Slipway.java b/src/edu/berkeley/fleet/slipway/Slipway.java
index 39abe38..1de2f01 100644
--- a/src/edu/berkeley/fleet/slipway/Slipway.java
+++ b/src/edu/berkeley/fleet/slipway/Slipway.java
@@ -226,6 +226,8 @@ public class Slipway extends Fleet {
                 } else if (prefix.equals("dest")) {
                     p.addr = addr;
                     p.bits = bits;
+                    if (bits >= 11)
+                        throw new RuntimeException("too many benkoboxen!");
                     int count = 0;
                     for(Destination d : p.getDestinations()) {
                         if (!(d instanceof SlipwayBenkoBox.VirtualPort)) continue;
@@ -237,10 +239,24 @@ public class Slipway extends Fleet {
                 return p;
             }
             int len = end-start;
+            int count   = 0;
+            int count2  = 0;
+            int breakpt = 0;
+            if (end-start <= 2) {
+                breakpt = (start+end)/2;
+            } else {
+                for(int i=start; i<end; i++)
+                    count += count(ports[i].getDestinations());
+                for(int i=start; i<end-1; i++) {
+                    count2 += count(ports[i].getDestinations());
+                    breakpt = i;
+                    if (i>start && count2 >= count/2) break;
+                }
+            }
             return new Node(name,
                             component,
-                            mkNode(name+"_0", component, ports, start, start+len/2, addr,               bits+1),
-                            mkNode(name+"_1", component, ports, start+len/2, end,   addr | (1 << bits), bits+1),
+                            mkNode(name+"_0", component, ports, start, breakpt, addr,               bits+1),
+                            mkNode(name+"_1", component, ports, breakpt, end,   addr | (1 << bits), bits+1),
                             addr,
                             bits);
         }
@@ -320,6 +336,13 @@ public class Slipway extends Fleet {
         return ship.getType() + ship.getOrdinal();
     }
 
+    private static int count(Iterable<Destination> it) {
+        int ret = 0;
+        for(Destination d : it)
+            ret++;
+        return ret;
+    }
+
     public void expand(ShipDescription sd) {
         try {
             String filename = sd.getName().toLowerCase();
-- 
1.7.10.4