Checking in super-optimized SimpleHash code... Good for a little performance increase...

diff --git a/Repair/RepairCompiler/MCC/Compiler.java b/Repair/RepairCompiler/MCC/Compiler.java
index 1c0d7e1a3174b56e39aa45cfe19dce680b4443b5..05c60339cc176a91cfa1cfc4eaa4ffb7d4983dbe 100755 (executable)
--- a/Repair/RepairCompiler/MCC/Compiler.java
+++ b/Repair/RepairCompiler/MCC/Compiler.java
@@ -100,6 +100,8 @@ public class Compiler {
                    gcode3.close();
                } else {
                    WorklistGenerator ng = new WorklistGenerator(state);
                    gcode3.close();
                } else {
                    WorklistGenerator ng = new WorklistGenerator(state);

+                   SetInclusion.worklist=true;
+                   RelationInclusion.worklist=true;

                    ng.generate(gcode);
                }
                 gcode.close();
                    ng.generate(gcode);
                }
                 gcode.close();

diff --git a/Repair/RepairCompiler/MCC/IR/RelationInclusion.java b/Repair/RepairCompiler/MCC/IR/RelationInclusion.java
index 4e415bfbc8f57b86f45dd18bc463f4faf6b7b0fd..58e266478fec77a6d7bc0e79d33bbd3e6906267d 100755 (executable)
--- a/Repair/RepairCompiler/MCC/IR/RelationInclusion.java
+++ b/Repair/RepairCompiler/MCC/IR/RelationInclusion.java
@@ -9,7 +9,7 @@ public class RelationInclusion extends Inclusion {
 
     // #TBD#: this flag needs to be set by some static analysis
     boolean typesafe = true;
 
     // #TBD#: this flag needs to be set by some static analysis
     boolean typesafe = true;

-    static boolean worklist = false;
+    public static boolean worklist = false;

 
     public RelationInclusion(Expr leftelementexpr, Expr rightelementexpr, RelationDescriptor relation) {
         this.leftelementexpr = leftelementexpr;
 
     public RelationInclusion(Expr leftelementexpr, Expr rightelementexpr, RelationDescriptor relation) {
         this.leftelementexpr = leftelementexpr;

diff --git a/Repair/RepairCompiler/MCC/IR/SetInclusion.java b/Repair/RepairCompiler/MCC/IR/SetInclusion.java
index fb0f9ec32f7b994aa768666a66d1cde370d9f3db..b18b08e70bcf2266281fadaf704be0e1d889415a 100755 (executable)
--- a/Repair/RepairCompiler/MCC/IR/SetInclusion.java
+++ b/Repair/RepairCompiler/MCC/IR/SetInclusion.java
@@ -10,7 +10,7 @@ public class SetInclusion extends Inclusion {
     public String generatedresult = null;
     public String generatedaddeditem = null;
 
     public String generatedresult = null;
     public String generatedaddeditem = null;
 

-    static boolean worklist = false;
+    public static boolean worklist = false;

     public boolean dostore = true;
 
     public String toString() {
     public boolean dostore = true;
 
     public String toString() {

diff --git a/Repair/RepairCompiler/MCC/SimpleHash.cc b/Repair/RepairCompiler/MCC/SimpleHash.cc
index ed8401d83fe4e5e23a7d38783d37cf081607cd3e..c3e21654c368e6de4bee528a605a692ff7e5949d 100755 (executable)
--- a/Repair/RepairCompiler/MCC/SimpleHash.cc
+++ b/Repair/RepairCompiler/MCC/SimpleHash.cc
@@ -134,39 +134,32 @@ void WorkList::add(int id,int type, int lvalue, int rvalue) {
 }
 
 /* SIMPLE HASH ********************************************************/
 }
 
 /* SIMPLE HASH ********************************************************/

+SimpleIterator* SimpleHash::iterator() {
+  return new SimpleIterator(listhead,this);
+}

 
 SimpleHash::SimpleHash(int size) {
     if (size <= 0) {
         throw SimpleHashException();
     }
     this->size = size;
 
 SimpleHash::SimpleHash(int size) {
     if (size <= 0) {
         throw SimpleHashException();
     }
     this->size = size;

-    this->bucket = new LinkedHashNode* [size];
-    for (int i=0;i<size;i++)
-      bucket[i]=0;
-    this->nodelist=0;
+    this->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
+    /* Set allocation blocks*/
+    this->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
+    this->listtail=this->listhead;
+    this->tailindex=0;
+    /*Set data counts*/

     this->numparents = 0;
     this->numchildren = 0;
     this->numelements = 0;
 }
 
     this->numparents = 0;
     this->numchildren = 0;
     this->numelements = 0;
 }
 

-SimpleHash::SimpleHash() {
-    this->size = 100;
-    this->bucket = new LinkedHashNode* [size];
-    for (int i=0;i<size;i++)
-      bucket[i]=0;
-    this->nodelist = 0;
-    this->numparents = 0;
-    this->numelements = 0;
-    this->numchildren = 0;
-}
-
-

 SimpleHash::~SimpleHash() {
 SimpleHash::~SimpleHash() {

-  delete [] this->bucket;
-  LinkedHashNode *ptr=nodelist;
+  free(bucket);
+  struct ArraySimple *ptr=listhead;

   while(ptr) {
   while(ptr) {

-      LinkedHashNode *next=ptr->lnext;
-      delete ptr;
+      struct ArraySimple *next=ptr->nextarray;
+      free(ptr);

       ptr=next;
   }
 }
       ptr=next;
   }
 }


@@ -183,7 +176,7 @@ void SimpleHash::addChild(SimpleHash *child) {
 int SimpleHash::remove(int key, int data) {
     unsigned int hashkey = (unsigned int)key % size;
     
 int SimpleHash::remove(int key, int data) {
     unsigned int hashkey = (unsigned int)key % size;
     

-    LinkedHashNode **ptr = &bucket[hashkey];
+    struct SimpleNode **ptr = &bucket[hashkey];

 
     for (int i = 0; i < numchildren; i++) {
       children[i]->remove(key, data);
 
     for (int i = 0; i < numchildren; i++) {
       children[i]->remove(key, data);


@@ -191,13 +184,11 @@ int SimpleHash::remove(int key, int data) {
 
     while (*ptr) {
         if ((*ptr)->key == key && (*ptr)->data == data) {
 
     while (*ptr) {
         if ((*ptr)->key == key && (*ptr)->data == data) {

-         LinkedHashNode *toremove=*ptr;
+         struct SimpleNode *toremove=*ptr;

          *ptr=(*ptr)->next;
          *ptr=(*ptr)->next;

-         if (toremove->lprev)
-           toremove->lprev->lnext=toremove->lnext;
-         if (toremove->lnext)
-           toremove->lnext->lprev=toremove->lprev;
-         delete toremove;
+
+         toremove->inuse=0; /* Marked as unused */
+

          numelements--;
          return 1;
         }
          numelements--;
          return 1;
         }


@@ -212,7 +203,7 @@ int SimpleHash::remove(int key, int data) {
 int SimpleHash::add(int key, int data) {
     unsigned int hashkey = (unsigned int)key % size;
     
 int SimpleHash::add(int key, int data) {
     unsigned int hashkey = (unsigned int)key % size;
     

-    LinkedHashNode **ptr = &bucket[hashkey];
+    struct SimpleNode **ptr = &bucket[hashkey];

 
     /* check that this key/object pair isn't already here */
     // TBD can be optimized for set v. relation */
 
     /* check that this key/object pair isn't already here */
     // TBD can be optimized for set v. relation */


@@ -222,12 +213,17 @@ int SimpleHash::add(int key, int data) {
         }
         ptr = &((*ptr)->next);
     }
         }
         ptr = &((*ptr)->next);
     }

+    if (tailindex==ARRAYSIZE) {
+      listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
+      tailindex=0;
+      listtail=listtail->nextarray;
+    }

     
     

-    *ptr = new LinkedHashNode(key, data, 0);
-    (*ptr)->lnext=nodelist;
-    if (nodelist!=0)
-      nodelist->lprev=*ptr;
-    nodelist=*ptr;
+    *ptr = &listtail->nodes[tailindex++];
+    (*ptr)->key=key;
+    (*ptr)->data=data;
+    (*ptr)->inuse=1;
+

     numelements++;
     
     for (int i = 0; i < numparents; i++) {
     numelements++;
     
     for (int i = 0; i < numparents; i++) {


@@ -240,7 +236,7 @@ int SimpleHash::add(int key, int data) {
 bool SimpleHash::contains(int key) {
     unsigned int hashkey = (unsigned int)key % size;
     
 bool SimpleHash::contains(int key) {
     unsigned int hashkey = (unsigned int)key % size;
     

-    LinkedHashNode *ptr = bucket[hashkey];
+    struct SimpleNode *ptr = bucket[hashkey];

     while (ptr) {
         if (ptr->key == key) {
             // we already have this object 
     while (ptr) {
         if (ptr->key == key) {
             // we already have this object 


@@ -255,7 +251,7 @@ bool SimpleHash::contains(int key) {
 bool SimpleHash::contains(int key, int data) {
     unsigned int hashkey = (unsigned int)key % size;
     
 bool SimpleHash::contains(int key, int data) {
     unsigned int hashkey = (unsigned int)key % size;
     

-    LinkedHashNode *ptr = bucket[hashkey];
+    struct SimpleNode *ptr = bucket[hashkey];

     while (ptr) {
         if (ptr->key == key && ptr->data == data) {
             // we already have this object 
     while (ptr) {
         if (ptr->key == key && ptr->data == data) {
             // we already have this object 


@@ -271,7 +267,7 @@ int SimpleHash::count(int key) {
     unsigned int hashkey = (unsigned int)key % size;
     int count = 0;
 
     unsigned int hashkey = (unsigned int)key % size;
     int count = 0;
 

-    LinkedHashNode *ptr = bucket[hashkey];
+    struct SimpleNode *ptr = bucket[hashkey];

     while (ptr) {
         if (ptr->key == key) {
             count++;
     while (ptr) {
         if (ptr->key == key) {
             count++;


@@ -284,7 +280,7 @@ int SimpleHash::count(int key) {
 int SimpleHash::get(int key, int&data) {
     unsigned int hashkey = (unsigned int)key % size;
     
 int SimpleHash::get(int key, int&data) {
     unsigned int hashkey = (unsigned int)key % size;
     

-    LinkedHashNode *ptr = bucket[hashkey];
+    struct SimpleNode *ptr = bucket[hashkey];

     while (ptr) {
         if (ptr->key == key) {
             data = ptr->data;
     while (ptr) {
         if (ptr->key == key) {
             data = ptr->data;


@@ -298,12 +294,22 @@ int SimpleHash::get(int key, int&data) {
 
 int SimpleHash::countdata(int data) {
     int count = 0;
 
 int SimpleHash::countdata(int data) {
     int count = 0;

-    LinkedHashNode *ptr = nodelist;
+    struct ArraySimple *ptr = listhead;

     while(ptr) {
     while(ptr) {

-      if (ptr->data == data) {
-       count++;
+      if (ptr->nextarray) {
+       for(int i=0;i<ARRAYSIZE;i++)
+         if (ptr->nodes[i].data == data
+             &&ptr->nodes[i].inuse) {
+           count++;
+         }
+      } else {
+       for(int i=0;i<tailindex;i++)
+         if (ptr->nodes[i].data == data
+             &&ptr->nodes[i].inuse) {
+           count++;
+         }

       }
       }

-      ptr = ptr->next;
+      ptr = ptr->nextarray;

     }
     return count;
 }
     }
     return count;
 }

diff --git a/Repair/RepairCompiler/MCC/SimpleHash.h b/Repair/RepairCompiler/MCC/SimpleHash.h
index 182351cc8a6fb789fcf12496f174142a41ec4f2a..82b2821ea7fabe280a871f120e7970ee26bf345f 100755 (executable)
--- a/Repair/RepairCompiler/MCC/SimpleHash.h
+++ b/Repair/RepairCompiler/MCC/SimpleHash.h
@@ -59,62 +59,26 @@ struct ListNode {
   int data[WLISTSIZE];
   ListNode *next;
 };
   int data[WLISTSIZE];
   ListNode *next;
 };

-
-
-/* SimpleIterator *****************************************************/
-
-class SimpleIterator {
-
-private:
-
-    LinkedHashNode *cur;
-
-public:
-
-    inline SimpleIterator(LinkedHashNode *start) {
-        cur = start;
-    }
-
-    inline int hasNext() {
-        return (int)cur->next == 0 ? 0 : 1;
-    }
-
-    inline int next() {
-        cur = cur->next;
-        return cur->data;
-    }
-
-    inline int key() {
-        return cur->key;
-    }
-
-    inline int size() {
-        int temp = 0;
-        while (cur->next) {
-            temp++;
-            cur = cur->next;
-        }
-        return temp;
-    }
-
-};
-

 /* SimpleHash *********************************************************/
 /* SimpleHash *********************************************************/

+class SimpleIterator;

 
 class SimpleHash {
 private:
     int numelements;
     int size;
 
 class SimpleHash {
 private:
     int numelements;
     int size;

-    LinkedHashNode **bucket;
-    LinkedHashNode *nodelist;
+    struct SimpleNode **bucket;
+    struct ArraySimple *listhead;
+    struct ArraySimple *listtail;
+
+

     int numparents;
     int numchildren;
     SimpleHash* parents[10];
     SimpleHash* children[10];
     void addChild(SimpleHash* child);
 public:
     int numparents;
     int numchildren;
     SimpleHash* parents[10];
     SimpleHash* children[10];
     void addChild(SimpleHash* child);
 public:

-    SimpleHash();
-    SimpleHash(int size);
+    int tailindex;
+    SimpleHash(int size=100);

     ~SimpleHash();
     int add(int key, int data);
     int remove(int key, int data);
     ~SimpleHash();
     int add(int key, int data);
     int remove(int key, int data);


@@ -123,12 +87,8 @@ public:
     int get(int key, int& data);
     int countdata(int data);
     void addParent(SimpleHash* parent);
     int get(int key, int& data);
     int countdata(int data);
     void addParent(SimpleHash* parent);

-    inline int firstkey() {
-       return nodelist->key;
-    }
-    inline SimpleIterator* iterator() {
-        return new SimpleIterator(nodelist);
-    }
+    int firstkey();
+    SimpleIterator* iterator();

     inline int count() {
         return numelements;
     }
     inline int count() {
         return numelements;
     }


@@ -138,6 +98,66 @@ public:
 
 /* SimpleHashExcepion  *************************************************/
 
 
 /* SimpleHashExcepion  *************************************************/
 

+
+/* SimpleIterator *****************************************************/
+#define ARRAYSIZE 100
+
+struct SimpleNode {
+  struct SimpleNode *next;
+  int data;
+  int key;  
+  int inuse;
+};
+
+struct ArraySimple {
+  struct SimpleNode nodes[ARRAYSIZE];
+  struct ArraySimple * nextarray;
+};
+
+
+class SimpleIterator {
+
+private:
+
+  struct ArraySimple *cur;
+  int index;
+  SimpleHash * table;
+public:
+
+  inline SimpleIterator(struct ArraySimple *start, SimpleHash *t) {
+    cur = start;
+    table=t;
+    index=0;
+  }
+
+  inline int hasNext() {
+    while((index==ARRAYSIZE)||!cur->nodes[index].inuse) {
+      if (cur->nextarray==0 &&
+         index==table->tailindex)
+       return 0;
+      index++;
+      if (index==ARRAYSIZE) {
+       index=0;
+       cur=cur->nextarray;
+      }
+    }
+    if (cur->nodes[index].inuse)
+      return 1;
+    else
+      return 0;
+  }
+
+  inline int next() {
+    return cur->nodes[index++].data;
+  }
+  
+  inline int key() {
+    return cur->nodes[index].key;
+  }
+};
+
+/* SimpleHashExcepion  *************************************************/
+

 class SimpleHashException {
 public:
     SimpleHashException();
 class SimpleHashException {
 public:
     SimpleHashException();

diff --git a/Repair/RepairCompiler/MCC/ex_test.cc b/Repair/RepairCompiler/MCC/ex_test.cc
index 9b0ab1e5128e1e810bea2d600779ff8f86702ea9..fd08277ec2b577c37312737f4752c2ef014d8695 100755 (executable)
--- a/Repair/RepairCompiler/MCC/ex_test.cc
+++ b/Repair/RepairCompiler/MCC/ex_test.cc
@@ -1,5 +1,4 @@
 #include "ex_aux.h"
 #include "ex_aux.h"

-

 struct Node {
      int data;
      struct Node *next;
 struct Node {
      int data;
      struct Node *next;


@@ -18,5 +17,5 @@ int main(int argc, char **argv) {
   for(int j=0;j<6000;j++) {
 #include "ex.cc"
   }
   for(int j=0;j<6000;j++) {
 #include "ex.cc"
   }

-  
+ 

 }
 }