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                 uint size = members->getSize();
  36                 for (uint i = 0; i < size; i++) {
  37                         if (element == members->get(i))
  38                                 return true;
  39                 }
  40                 return false;
  41         }
  42 }
  43
  44 uint64_t Set::getElement(uint index) {
  45         if (isRange)
  46                 return low + index;
  47         else
  48                 return members->get(index);
  49 }
  50
  51 uint Set::getSize() {
  52         if (isRange) {
  53                 return high - low + 1;
  54         } else {
  55                 return members->getSize();
  56         }
  57 }
  58
  59 uint64_t Set::getMemberAt(uint index) {
  60         if (isRange) {
  61                 return low + index;
  62         } else {
  63                 return members->get(index);
  64         }
  65 }
  66
  67 Set::~Set() {
  68         if (!isRange)
  69                 delete members;
  70 }
  71
  72 Set *Set::clone(CSolver *solver, CloneMap *map) {
  73         Set *s = (Set *) map->get(this);
  74         if (s != NULL)
  75                 return s;
  76         if (isRange) {
  77                 s = solver->createRangeSet(type, low, high);
  78         } else {
  79                 s = solver->createSet(type, members->expose(), members->getSize());
  80         }
  81         map->put(this, s);
  82         return s;
  83 }
  84
  85 uint Set::getUnionSize(Set *s) {
  86         uint sSize = s->getSize();
  87         uint thisSize = getSize();
  88         uint sIndex = 0;
  89         uint thisIndex = 0;
  90         uint sum = 0;
  91         uint64_t sValue = s->getElement(sIndex);
  92         uint64_t thisValue = getElement(thisIndex);
  93         while(thisIndex < thisSize && sIndex < sSize) {
  94                 if (sValue < thisValue) {
  95                         sValue = s->getElement(++sIndex);
  96                         sum++;
  97                 } else if (thisValue < sValue) {
  98                         thisValue = getElement(++thisIndex);
  99                         sum++;
 100                 } else {
 101                         thisValue = getElement(++thisIndex);
 102                         sValue = s->getElement(++sIndex);
 103                         sum++;
 104                 }
 105         }
 106         sum += (thisSize - thisIndex) + (sSize - sIndex);
 107
 108         return sum;
 109 }
 110
 111 void Set::serialize(Serializer* serializer){
 112         if(serializer->isSerialized(this))
 113                 return;
 114         serializer->addObject(this);
 115         ASTNodeType asttype = SETTYPE;
 116         serializer->mywrite(&asttype, sizeof(ASTNodeType));
 117         Set* This = this;
 118         serializer->mywrite(&This, sizeof(Set*));
 119         serializer->mywrite(&type, sizeof(VarType));
 120         serializer->mywrite(&isRange, sizeof(bool));
 121         serializer->mywrite(&low, sizeof(uint64_t));
 122         serializer->mywrite(&high, sizeof(uint64_t));
 123         uint size = members->getSize();
 124         serializer->mywrite(&size, sizeof(uint));
 125         for(uint i=0; i<size; i++){
 126                 uint64_t mem = members->get(i);
 127                 serializer->mywrite(&mem, sizeof(uint64_t));
 128         }
 129 }