Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/MTree/TestRunner.java

   1 public class TestRunner extends Thread {
   2
   3   int m_index;
   4   int m_size;
   5   int m_nodenum;
   6   Node m_tree; // The root of a BST
   7
   8   public TestRunner(int index,
   9       int size,
  10       int nodenum) {
  11     this.m_index = index;
  12     this.m_size = size;
  13     this.m_nodenum = nodenum;
  14     this.m_tree = new Node();
  15   }
  16
  17   public void run() {
  18     // Randomly generate new (key, value) pair and insert into the tree
  19     // If have collision, simply throw away the old node
  20     // The tree can hold m_size nodes at most, if it has reached the
  21     // limitation of m_size, then replace the node whose key is the
  22     // closest to the new key.
  23     Random rand = new Random(m_index);
  24     while(this.m_nodenum-- > 0) {
  25       // Generate a new (key, value) pair
  26       int key = Math.abs(rand.nextInt());
  27       int value = Math.abs(rand.nextInt());
  28       if(this.m_tree.insert(key, value, !(this.m_size > 0))) {
  29         // insert a new node
  30         this.m_size--;
  31       }
  32     }
  33   }
  34
  35   class Node {
  36     int m_key;
  37     int m_value;
  38     Node m_left;
  39     Node m_right;
  40     Node m_parent;
  41
  42     public Node() {
  43       // an empty node
  44       this.m_key = -1;
  45       this.m_value = -1;
  46       this.m_left = null;
  47       this.m_right = null;
  48       this.m_parent = null;
  49     }
  50
  51     public Node(int key,
  52         int value) {
  53       this.m_key = key;
  54       this.m_value = value;
  55       this.m_left = null;
  56       this.m_right = null;
  57       this.m_parent = null;
  58     }
  59
  60     public int getKey() {
  61       return this.m_key;
  62     }
  63
  64     public void setParent(Node p) {
  65       this.m_parent = p;
  66     }
  67
  68     public void setLeftChild(int key,
  69         int value) {
  70       Node n = new Node(key, value);
  71       this.m_left = n;
  72       n.setParent(this);
  73     }
  74
  75     public void setRightChild(int key,
  76         int value) {
  77       Node n = new Node(key, value);
  78       this.m_right = n;
  79       n.setParent(this);
  80     }
  81
  82     public boolean insert(int key,
  83         int value,
  84         boolean candelete) {
  85       if(this.m_key == -1) {
  86         // empty tree
  87         this.m_key = key;
  88         this.m_value = value;
  89       } else {
  90         if(this.m_key == key) {
  91           // collision
  92           replace(key, value);
  93           return false;
  94         } else if(this.m_key > key) {
  95           if(this.m_left == null) {
  96             // no left subtree
  97             if(candelete) {
  98               // replace this node with the new node
  99               replace(key, value);
 100               return false;
 101             } else {
 102               setLeftChild(key, value);
 103             }
 104           } else {
 105             // insert into the left subtree
 106             return this.m_left.insert(key, value, candelete);
 107           }
 108         } else if(this.m_key < key) {
 109           if(this.m_right == null) {
 110             // no right subtree
 111             if(candelete) {
 112               replace(key, value);
 113               return false;
 114             } else {
 115               setRightChild(key, value);
 116             }
 117           } else {
 118             // insert into the right subtree
 119             return this.m_right.insert(key, value, candelete);
 120           }
 121         }
 122       }
 123       return true;
 124     }
 125
 126     public void replace(int key,
 127         int value) {
 128       Node n = new Node(key, value);
 129       n.m_left = this.m_left;
 130       n.m_right = this.m_right;
 131       n.m_parent = this.m_parent;
 132       if(this.m_parent != null) {
 133         if(this.m_parent.getKey() > key) {
 134           this.m_parent.m_left = n;
 135         } else {
 136           this.m_parent.m_right = n;
 137         }
 138       }
 139       if(this.m_left != null) {
 140         this.m_left.m_parent = n;
 141       }
 142       if(this.m_right != null) {
 143         this.m_right.m_parent = n;
 144       }
 145     }
 146   }
 147
 148   public static void main(String[] args) {
 149     int threadnum = 62; // 56;
 150     int size = 40000;
 151     int nodenum = size*10;
 152     for(int i = 0; i < threadnum; ++i) {
 153       TestRunner tr = new TestRunner(i, size, nodenum);
 154       tr.run();
 155     }
 156   }
 157 }