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