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         root(),
   9         head(NULL),
  10         tail(NULL),
  11         _size(0)
  12 {
  13 }
  14
  15 actionlist::~actionlist() {
  16         clear();
  17 }
  18
  19 allnode::allnode() :
  20         parent(NULL),
  21         count(0) {
  22         bzero(children, sizeof(children));
  23 }
  24
  25 allnode::~allnode() {
  26         if (count != 0)
  27                 for(int i=0;i<ALLNODESIZE;i++) {
  28                         if (children[i] != NULL && !(((uintptr_t) children[i]) & ISACT))
  29                                 delete children[i];
  30                 }
  31 }
  32
  33 sllnode<ModelAction *> * allnode::findPrev(modelclock_t index) {
  34         allnode * ptr = this;
  35         modelclock_t increment = 1;
  36         int totalshift = 0;
  37         index -= increment;
  38
  39         while(1) {
  40                 modelclock_t currindex = (index >> totalshift) & 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                                 totalshift -= ALLBITS;
  56                                 break;
  57                         }
  58                 }
  59                 //If we get here, we already did the decrement earlier...no need to decrement again
  60                 ptr = ptr->parent;
  61                 increment = increment << ALLBITS;
  62                 totalshift += ALLBITS;
  63
  64                 if (ptr == NULL) {
  65                         return NULL;
  66                 }
  67         }
  68
  69         while(1) {
  70                 while(1) {
  71                         modelclock_t currindex = (index >> totalshift) & ALLMASK;
  72                         if (ptr->children[currindex] != NULL) {
  73                                 if (totalshift != 0) {
  74                                         ptr = ptr->children[currindex];
  75                                         break;
  76                                 } else {
  77                                         allnode * act = ptr->children[currindex];
  78                                         sllnode<ModelAction *> * node = reinterpret_cast<sllnode<ModelAction *>*>(((uintptr_t)act) & ACTMASK);
  79                                         return node;
  80                                 }
  81                         }
  82                         index -= increment;
  83                 }
  84
  85                 increment = increment >> ALLBITS;
  86                 totalshift -= ALLBITS;
  87         }
  88 }
  89
  90 void actionlist::addAction(ModelAction * act) {
  91         _size++;
  92         int shiftbits = MODELCLOCKBITS - ALLBITS;
  93         modelclock_t clock = act->get_seq_number();
  94
  95         allnode * ptr = &root;
  96         do {
  97                 modelclock_t currindex = (clock >> shiftbits) & ALLMASK;
  98                 allnode * tmp = ptr->children[currindex];
  99                 if (shiftbits == 0) {
 100                         sllnode<ModelAction *> * llnode = new sllnode<ModelAction *>();
 101                         llnode->val = act;
 102                         if (tmp == NULL) {
 103                                 sllnode<ModelAction *> * llnodeprev = ptr->findPrev(clock);
 104                                 if (llnodeprev != NULL) {
 105                                         llnode->next = llnodeprev->next;
 106                                         llnode->prev = llnodeprev;
 107
 108                                         //see if we are the new tail
 109                                         if (llnode->next != NULL)
 110                                                 llnode->next->prev = llnode;
 111                                         else
 112                                                 tail = llnode;
 113                                         llnodeprev->next = llnode;
 114                                 } else {
 115                                         //We are the begining
 116                                         llnode->next = head;
 117                                         llnode->prev = NULL;
 118                                         if (head != NULL) {
 119                                                 head->prev = llnode;
 120                                         } else {
 121                                                 //we are the first node
 122                                                 tail = llnode;
 123                                         }
 124
 125                                         head = llnode;
 126                                 }
 127                                 ptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
 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) tmp) & ACTMASK);
 135                                 llnode->next = llnodeprev->next;
 136                                 llnode->prev = llnodeprev;
 137                                 if (llnode->next != NULL)
 138                                         llnode->next->prev = llnode;
 139                                 else
 140                                         tail = llnode;
 141                                 llnodeprev->next = llnode;
 142                                 ptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
 143                         }
 144                         return;
 145                 } else if (tmp == NULL) {
 146                         tmp = new allnode();
 147                         ptr->children[currindex] = tmp;
 148                         tmp->parent=ptr;
 149                         ptr->count++;
 150                 }
 151                 shiftbits -= ALLBITS;
 152                 ptr = tmp;
 153         } while(1);
 154
 155 }
 156
 157 void decrementCount(allnode * ptr) {
 158         ptr->count--;
 159         if (ptr->count == 0) {
 160                 if (ptr->parent != NULL) {
 161                         for(uint i=0;i<ALLNODESIZE;i++) {
 162                                 if (ptr->parent->children[i]==ptr) {
 163                                         ptr->parent->children[i] = NULL;
 164                                         decrementCount(ptr->parent);
 165                                         break;
 166                                 }
 167                         }
 168                         delete ptr;
 169                 }
 170         }
 171 }
 172
 173 void actionlist::removeAction(ModelAction * act) {
 174         int shiftbits = MODELCLOCKBITS;
 175         modelclock_t clock = act->get_seq_number();
 176         allnode * ptr = &root;
 177         allnode * oldptr;
 178         modelclock_t currindex;
 179
 180         while(shiftbits != 0) {
 181                 shiftbits -= ALLBITS;
 182                 currindex = (clock >> shiftbits) & ALLMASK;
 183                 oldptr = ptr;
 184                 ptr = ptr->children[currindex];
 185                 if (ptr == NULL)
 186                         return;
 187         }
 188
 189         sllnode<ModelAction *> * llnode = reinterpret_cast<sllnode<ModelAction *> *>(((uintptr_t) ptr) & ACTMASK);
 190         bool first = true;
 191         do {
 192                 if (llnode->val == act) {
 193                         //found node to remove
 194                         sllnode<ModelAction *> * llnodeprev = llnode->prev;
 195                         sllnode<ModelAction *> * llnodenext = llnode->next;
 196                         if (llnodeprev != NULL) {
 197                                 llnodeprev->next = llnodenext;
 198                         } else {
 199                                 head = llnodenext;
 200                         }
 201                         if (llnodenext != NULL) {
 202                                 llnodenext->prev = llnodeprev;
 203                         } else {
 204                                 tail = llnodeprev;
 205                         }
 206                         if (first) {
 207                                 //see if previous node has same clock as us...
 208                                 if (llnodeprev != NULL && llnodeprev->val->get_seq_number() == clock) {
 209                                         oldptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t)llnodeprev) | ISACT);
 210                                 } else {
 211                                         //remove ourselves and go up tree
 212                                         oldptr->children[currindex] = NULL;
 213                                         decrementCount(oldptr);
 214                                 }
 215                         }
 216                         delete llnode;
 217                         _size--;
 218                         return;
 219                 }
 220                 llnode = llnode->prev;
 221                 first = false;
 222         } while(llnode != NULL && llnode->val->get_seq_number() == clock);
 223         //node not found in list... no deletion
 224         return;
 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 }
 249
 250 /**
 251  * Fix the parent pointer of root when root address changes (possible
 252  * due to vector<action_list_t> resize)
 253  */
 254 void actionlist::fixupParent()
 255 {
 256         for (int i = 0; i < ALLNODESIZE; i++) {
 257                 allnode * child = root.children[i];
 258                 if (child != NULL && child->parent != &root)
 259                         child->parent = &root;
 260         }
 261 }