actionlist.cc

   1 #include "actionlist.h"
   2 #include "action.h"
   3 #include <string.h>
   4 #include "stl-model.h"
   5 #include <limits.h>
   6
   7 actionlist::actionlist() :
   8         _size(0)
   9 {
  10 }
  11
  12 actionlist::~actionlist() {
  13 }
  14
  15 allnode::allnode() :
  16         count(0) {
  17         bzero(children, sizeof(children));
  18 }
  19
  20 allnode::~allnode() {
  21         if (count != 0)
  22                 for(int i=0;i<ALLNODESIZE;i++) {
  23                         if (children[i] != NULL && !(((uintptr_t) children[i]) & ISACT))
  24                                 delete children[i];
  25                 }
  26 }
  27
  28 sllnode<ModelAction *> * allnode::findPrev(modelclock_t index) {
  29         allnode * ptr = this;
  30         modelclock_t increment = 1;
  31         modelclock_t mask = ALLMASK;
  32         int totalshift = 0;
  33         index -= increment;
  34
  35         while(1) {
  36                 modelclock_t shiftclock = index >> totalshift;
  37                 modelclock_t currindex = shiftclock & ALLMASK;
  38
  39                 //See if we went negative...
  40                 if (currindex != ALLMASK) {
  41                         if (ptr->children[currindex] == NULL) {
  42                                 //need to keep searching at this level
  43                                 index -= increment;
  44                                 continue;
  45                         } else {
  46                                 //found non-null...
  47                                 if (totalshift != 0)
  48                                         ptr = ptr->children[currindex];
  49                                 //need to increment here...
  50                                 increment = increment >> ALLBITS;
  51                                 mask = mask >> ALLBITS;
  52                                 totalshift -= ALLBITS;
  53                                 break;
  54                         }
  55                 }
  56                 //If we get here, we already did the decrement earlier...no need to decrement again
  57                 ptr = ptr->parent;
  58                 increment = increment << ALLBITS;
  59                 mask = mask << ALLBITS;
  60                 totalshift += ALLBITS;
  61
  62                 if (increment == 0) {
  63                         return NULL;
  64                 }
  65         }
  66
  67         while(1) {
  68                 while(1) {
  69                         modelclock_t shiftclock = index >> totalshift;
  70                         modelclock_t currindex = shiftclock & ALLMASK;
  71                         if (ptr->children[currindex] != NULL) {
  72                                 if (totalshift != 0) {
  73                                         ptr = ptr->children[currindex];
  74                                 } else {
  75                                         allnode * act = ptr->children[currindex];
  76                                         sllnode<ModelAction *> * node = reinterpret_cast<sllnode<ModelAction *>*>(((uintptr_t)act) & ALLMASK);
  77                                         return node;
  78                                 }
  79                         }
  80                         index -= increment;
  81                 }
  82
  83                 increment = increment >> ALLBITS;
  84                 mask = mask >> ALLBITS;
  85                 totalshift -= ALLBITS;
  86         }
  87 }
  88
  89 void actionlist::addAction(ModelAction * act) {
  90         _size++;
  91         int shiftbits = MODELCLOCKBITS - ALLBITS;
  92         modelclock_t clock = act->get_seq_number();
  93
  94         allnode * ptr = &root;
  95         do {
  96                 int index = (clock >> shiftbits) & ALLMASK;
  97                 allnode * tmp = ptr->children[index];
  98                 if (shiftbits == 0) {
  99                         sllnode<ModelAction *> * llnode = new sllnode<ModelAction *>();
 100                         llnode->val = act;
 101                         if (tmp == NULL) {
 102                                 ptr->children[index] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
 103                                 sllnode<ModelAction *> * llnodeprev = ptr->findPrev(index);
 104                                 if (llnodeprev != NULL) {
 105
 106                                         llnode->next = llnodeprev->next;
 107                                         llnode->prev = llnodeprev;
 108
 109                                         //see if we are the new tail
 110                                         if (llnodeprev->next == NULL)
 111                                                 tail = llnode;
 112                                         else
 113                                                 llnode->next->prev = llnode;
 114
 115                                         llnodeprev->next = llnode;
 116                                 } else {
 117                                         //We are the begining
 118                                         llnode->next = head;
 119                                         llnode->prev = NULL;
 120                                         if (head != NULL) {
 121                                                 head->prev = llnode;
 122                                         } else {
 123                                                 //we are the first node
 124                                                 tail = llnode;
 125                                         }
 126
 127                                         head = llnode;
 128                                 }
 129                                 //need to find next link
 130                                 ptr->count++;
 131                         } else {
 132                                 //handle case where something else is here
 133
 134                                 sllnode<ModelAction *> * llnodeprev = reinterpret_cast<sllnode<ModelAction *>*>(((uintptr_t) llnode) & ALLMASK);
 135                                 llnode->next = llnodeprev->next;
 136                                 llnode->prev = llnodeprev;
 137                                 llnode->next->prev = llnode;
 138                                 llnodeprev->next = llnode;
 139                                 ptr->children[index] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
 140                         }
 141                         return;
 142                 } else if (tmp == NULL) {
 143                         tmp = new allnode();
 144                         ptr->children[index] = tmp;
 145                         tmp->parent=ptr;
 146                         ptr->count++;
 147                 }
 148                 shiftbits -= ALLBITS;
 149                 ptr = tmp;
 150         } while(1);
 151
 152 }
 153
 154 void decrementCount(allnode * ptr) {
 155         ptr->count--;
 156         if (ptr->count == 0) {
 157                 if (ptr->parent != NULL) {
 158                         for(uint i=0;i<ALLNODESIZE;i++) {
 159                                 if (ptr->parent->children[i]==ptr) {
 160                                         ptr->parent->children[i] = NULL;
 161                                         decrementCount(ptr->parent);
 162                                 }
 163                         }
 164                 }
 165                 delete ptr;
 166         }
 167 }
 168
 169 void actionlist::removeAction(ModelAction * act) {
 170         int shiftbits = MODELCLOCKBITS - ALLBITS;
 171         modelclock_t clock = act->get_seq_number();
 172         allnode * ptr = &root;
 173         do {
 174                 int index = (clock >> shiftbits) & ALLMASK;
 175                 allnode * tmp = ptr->children[index];
 176                 if (shiftbits == 0) {
 177                         if (tmp == NULL) {
 178                                 //not found
 179                                 return;
 180                         } else {
 181                                 sllnode<ModelAction *> * llnode = reinterpret_cast<sllnode<ModelAction *> *>(((uintptr_t) tmp) & ALLMASK);
 182                                 bool first = true;
 183                                 do {
 184                                         if (llnode->val == act) {
 185                                                 //found node to remove
 186                                                 sllnode<ModelAction *> * llnodeprev = llnode->prev;
 187                                                 sllnode<ModelAction *> * llnodenext = llnode->next;
 188                                                 if (llnodeprev != NULL) {
 189                                                         llnodeprev->next = llnodenext;
 190                                                 } else {
 191                                                         head = llnodenext;
 192                                                 }
 193                                                 if (llnodenext != NULL) {
 194                                                         llnodenext->prev = llnodeprev;
 195                                                 } else {
 196                                                         tail = llnodeprev;
 197                                                 }
 198                                                 if (first) {
 199                                                         //see if previous node has same clock as us...
 200                                                         if (llnodeprev->val->get_seq_number() == clock) {
 201                                                                 ptr->children[index] = reinterpret_cast<allnode *>(((uintptr_t)llnodeprev) | ISACT);
 202                                                         } else {
 203                                                                 //remove ourselves and go up tree
 204                                                                 ptr->children[index] = NULL;
 205                                                                 decrementCount(ptr);
 206                                                         }
 207                                                 }
 208                                                 delete llnode;
 209                                                 _size--;
 210                                                 return;
 211                                         }
 212                                         llnode = llnode->prev;
 213                                         first = false;
 214                                 } while(llnode != NULL && llnode->val->get_seq_number() == clock);
 215                                 //node not found in list... no deletion
 216                                 return;
 217                         }
 218                 } else if (tmp == NULL) {
 219                         //not found
 220                         return;
 221                 }
 222                 shiftbits -= ALLBITS;
 223                 ptr = tmp;
 224         } while(1);
 225 }
 226
 227 void actionlist::clear() {
 228         for(uint i = 0;i < ALLNODESIZE;i++) {
 229                 if (root.children[i] != NULL) {
 230                         delete root.children[i];
 231                         root.children[i] = NULL;
 232                 }
 233         }
 234
 235         while(head != NULL) {
 236                 sllnode<ModelAction *> *tmp=head->next;
 237                 delete head;
 238                 head = tmp;
 239         }
 240         tail=NULL;
 241
 242         root.count = 0;
 243         _size = 0;
 244 }
 245
 246 bool actionlist::isEmpty() {
 247         return root.count == 0;
 248 }