#include <limits.h>
actionlist::actionlist() :
+ root(),
head(NULL),
tail(NULL),
_size(0)
{
- root.parent = NULL;
}
actionlist::~actionlist() {
+ clear();
}
allnode::allnode() :
+ parent(NULL),
count(0) {
bzero(children, sizeof(children));
}
sllnode<ModelAction *> * allnode::findPrev(modelclock_t index) {
allnode * ptr = this;
modelclock_t increment = 1;
- modelclock_t mask = ALLMASK;
int totalshift = 0;
index -= increment;
while(1) {
- modelclock_t shiftclock = index >> totalshift;
- modelclock_t currindex = shiftclock & ALLMASK;
+ modelclock_t currindex = (index >> totalshift) & ALLMASK;
//See if we went negative...
if (currindex != ALLMASK) {
//need to increment here...
ptr = ptr->children[currindex];
increment = increment >> ALLBITS;
- mask = mask >> ALLBITS;
totalshift -= ALLBITS;
break;
}
//If we get here, we already did the decrement earlier...no need to decrement again
ptr = ptr->parent;
increment = increment << ALLBITS;
- mask = mask << ALLBITS;
totalshift += ALLBITS;
if (ptr == NULL) {
while(1) {
while(1) {
- modelclock_t shiftclock = index >> totalshift;
- modelclock_t currindex = shiftclock & ALLMASK;
+ modelclock_t currindex = (index >> totalshift) & ALLMASK;
if (ptr->children[currindex] != NULL) {
if (totalshift != 0) {
ptr = ptr->children[currindex];
}
increment = increment >> ALLBITS;
- mask = mask >> ALLBITS;
totalshift -= ALLBITS;
}
}
allnode * ptr = &root;
do {
- int index = (clock >> shiftbits) & ALLMASK;
- allnode * tmp = ptr->children[index];
+ modelclock_t currindex = (clock >> shiftbits) & ALLMASK;
+ allnode * tmp = ptr->children[currindex];
if (shiftbits == 0) {
sllnode<ModelAction *> * llnode = new sllnode<ModelAction *>();
llnode->val = act;
head = llnode;
}
- ptr->children[index] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
+ ptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
//need to find next link
ptr->count++;
else
tail = llnode;
llnodeprev->next = llnode;
- ptr->children[index] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
+ ptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
}
return;
} else if (tmp == NULL) {
tmp = new allnode();
- ptr->children[index] = tmp;
+ ptr->children[currindex] = tmp;
tmp->parent=ptr;
ptr->count++;
}
if (ptr->parent->children[i]==ptr) {
ptr->parent->children[i] = NULL;
decrementCount(ptr->parent);
+ break;
}
}
delete ptr;
}
void actionlist::removeAction(ModelAction * act) {
- int shiftbits = MODELCLOCKBITS - ALLBITS;
+ int shiftbits = MODELCLOCKBITS;
modelclock_t clock = act->get_seq_number();
allnode * ptr = &root;
+ allnode * oldptr;
+ modelclock_t currindex;
+
+ while(shiftbits != 0) {
+ shiftbits -= ALLBITS;
+ currindex = (clock >> shiftbits) & ALLMASK;
+ oldptr = ptr;
+ ptr = ptr->children[currindex];
+ if (ptr == NULL)
+ return;
+ }
+
+ sllnode<ModelAction *> * llnode = reinterpret_cast<sllnode<ModelAction *> *>(((uintptr_t) ptr) & ACTMASK);
+ bool first = true;
do {
- int index = (clock >> shiftbits) & ALLMASK;
- allnode * tmp = ptr->children[index];
- if (shiftbits == 0) {
- if (tmp == NULL) {
- //not found
- return;
+ if (llnode->val == act) {
+ //found node to remove
+ sllnode<ModelAction *> * llnodeprev = llnode->prev;
+ sllnode<ModelAction *> * llnodenext = llnode->next;
+ if (llnodeprev != NULL) {
+ llnodeprev->next = llnodenext;
} else {
- sllnode<ModelAction *> * llnode = reinterpret_cast<sllnode<ModelAction *> *>(((uintptr_t) tmp) & ACTMASK);
- bool first = true;
- do {
- if (llnode->val == act) {
- //found node to remove
- sllnode<ModelAction *> * llnodeprev = llnode->prev;
- sllnode<ModelAction *> * llnodenext = llnode->next;
- if (llnodeprev != NULL) {
- llnodeprev->next = llnodenext;
- } else {
- head = llnodenext;
- }
- if (llnodenext != NULL) {
- llnodenext->prev = llnodeprev;
- } else {
- tail = llnodeprev;
- }
- if (first) {
- //see if previous node has same clock as us...
- if (llnodeprev != NULL && llnodeprev->val->get_seq_number() == clock) {
- ptr->children[index] = reinterpret_cast<allnode *>(((uintptr_t)llnodeprev) | ISACT);
- } else {
- //remove ourselves and go up tree
- ptr->children[index] = NULL;
- decrementCount(ptr);
- }
- }
- delete llnode;
- _size--;
- return;
- }
- llnode = llnode->prev;
- first = false;
- } while(llnode != NULL && llnode->val->get_seq_number() == clock);
- //node not found in list... no deletion
- return;
+ head = llnodenext;
}
- } else if (tmp == NULL) {
- //not found
+ if (llnodenext != NULL) {
+ llnodenext->prev = llnodeprev;
+ } else {
+ tail = llnodeprev;
+ }
+ if (first) {
+ //see if previous node has same clock as us...
+ if (llnodeprev != NULL && llnodeprev->val->get_seq_number() == clock) {
+ oldptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t)llnodeprev) | ISACT);
+ } else {
+ //remove ourselves and go up tree
+ oldptr->children[currindex] = NULL;
+ decrementCount(oldptr);
+ }
+ }
+ delete llnode;
+ _size--;
return;
}
- shiftbits -= ALLBITS;
- ptr = tmp;
- } while(1);
+ llnode = llnode->prev;
+ first = false;
+ } while(llnode != NULL && llnode->val->get_seq_number() == clock);
+ //node not found in list... no deletion
+ return;
}
void actionlist::clear() {
delete head;
head = tmp;
}
- tail=NULL;
+ tail = NULL;
root.count = 0;
_size = 0;
bool actionlist::isEmpty() {
return root.count == 0;
}
+
+/**
+ * Fix the parent pointer of root when root address changes (possible
+ * due to vector<action_list_t> resize)
+ */
+void actionlist::fixupParent()
+{
+ for (int i = 0;i < ALLNODESIZE;i++) {
+ allnode * child = root.children[i];
+ if (child != NULL && child->parent != &root)
+ child->parent = &root;
+ }
+}