src/AST/set.cc

   1 #include "set.h"
   2 #include <stddef.h>
   3 #include "csolver.h"
   4 #include "serializer.h"
   5 #include "qsort.h"
   6
   7 Set::Set(VarType t) : type(t), isRange(false), low(0), high(0) {
   8         members = new Vector<uint64_t>();
   9 }
  10
  11 int intcompare(const void *p1, const void *p2) {
  12         uint64_t a=*(uint64_t const *) p1;
  13         uint64_t b=*(uint64_t const *) p2;
  14         if (a < b)
  15                 return -1;
  16         else if (a==b)
  17                 return 0;
  18         else
  19                 return 1;
  20 }
  21
  22 Set::Set(VarType t, uint64_t *elements, uint num) : type(t), isRange(false), low(0), high(0) {
  23         members = new Vector<uint64_t>(num, elements);
  24         bsdqsort(members->expose(), members->getSize(), sizeof(uint64_t), intcompare);
  25 }
  26
  27
  28 Set::Set(VarType t, uint64_t lowrange, uint64_t highrange) : type(t), isRange(true), low(lowrange), high(highrange), members(NULL) {
  29 }
  30
  31 bool Set::exists(uint64_t element) {
  32         if (isRange) {
  33                 return element >= low && element <= high;
  34         } else {
  35                 //Use Binary Search
  36                 uint low=0;
  37                 uint high=members->getSize()-1;
  38                 while(true) {
  39                         uint middle=(low+high)/2;
  40                         uint64_t val=members->get(middle);
  41                         if (element < val) {
  42                                 high=middle;
  43                                 if (middle==low)
  44                                         return false;
  45                         } else if (element > val) {
  46                                 low=middle;
  47                                 if (middle==high)
  48                                         return false;
  49                         } else {
  50                                 return true;
  51                         }
  52                 }
  53         }
  54 }
  55
  56 uint64_t Set::getElement(uint index) {
  57         if (isRange)
  58                 return low + index;
  59         else
  60                 return members->get(index);
  61 }
  62
  63 uint Set::getSize() {
  64         if (isRange) {
  65                 return high - low + 1;
  66         } else {
  67                 return members->getSize();
  68         }
  69 }
  70
  71 uint64_t Set::getMemberAt(uint index) {
  72         if (isRange) {
  73                 return low + index;
  74         } else {
  75                 return members->get(index);
  76         }
  77 }
  78
  79 Set::~Set() {
  80         if (!isRange)
  81                 delete members;
  82 }
  83
  84 Set *Set::clone(CSolver *solver, CloneMap *map) {
  85         Set *s = (Set *) map->get(this);
  86         if (s != NULL)
  87                 return s;
  88         if (isRange) {
  89                 s = solver->createRangeSet(type, low, high);
  90         } else {
  91                 s = solver->createSet(type, members->expose(), members->getSize());
  92         }
  93         map->put(this, s);
  94         return s;
  95 }
  96
  97 uint Set::getUnionSize(Set *s) {
  98         uint sSize = s->getSize();
  99         uint thisSize = getSize();
 100         uint sIndex = 0;
 101         uint thisIndex = 0;
 102         uint sum = 0;
 103         uint64_t sValue = s->getElement(sIndex);
 104         uint64_t thisValue = getElement(thisIndex);
 105         while(thisIndex < thisSize && sIndex < sSize) {
 106                 if (sValue < thisValue) {
 107                         sValue = s->getElement(++sIndex);
 108                         sum++;
 109                 } else if (thisValue < sValue) {
 110                         thisValue = getElement(++thisIndex);
 111                         sum++;
 112                 } else {
 113                         thisValue = getElement(++thisIndex);
 114                         sValue = s->getElement(++sIndex);
 115                         sum++;
 116                 }
 117         }
 118         sum += (thisSize - thisIndex) + (sSize - sIndex);
 119
 120         return sum;
 121 }
 122
 123 void Set::serialize(Serializer* serializer){
 124         if(serializer->isSerialized(this))
 125                 return;
 126         serializer->addObject(this);
 127         ASTNodeType asttype = SETTYPE;
 128         serializer->mywrite(&asttype, sizeof(ASTNodeType));
 129         Set* This = this;
 130         serializer->mywrite(&This, sizeof(Set*));
 131         serializer->mywrite(&type, sizeof(VarType));
 132         serializer->mywrite(&isRange, sizeof(bool));
 133         serializer->mywrite(&low, sizeof(uint64_t));
 134         serializer->mywrite(&high, sizeof(uint64_t));
 135         uint size = members->getSize();
 136         serializer->mywrite(&size, sizeof(uint));
 137         for(uint i=0; i<size; i++){
 138                 uint64_t mem = members->get(i);
 139                 serializer->mywrite(&mem, sizeof(uint64_t));
 140         }
 141 }