1 #include "actionlist.h"
7 actionlist::actionlist() :
15 actionlist::~actionlist() {
22 bzero(children, sizeof(children));
27 for(int i=0;i<ALLNODESIZE;i++) {
28 if (children[i] != NULL && !(((uintptr_t) children[i]) & ISACT))
33 sllnode<ModelAction *> * allnode::findPrev(modelclock_t index) {
35 modelclock_t increment = 1;
40 modelclock_t currindex = (index >> totalshift) & ALLMASK;
42 //See if we went negative...
43 if (currindex != ALLMASK) {
44 if (ptr->children[currindex] == NULL) {
45 //need to keep searching at this level
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;
59 //If we get here, we already did the decrement earlier...no need to decrement again
61 increment = increment << ALLBITS;
62 totalshift += ALLBITS;
71 modelclock_t currindex = (index >> totalshift) & ALLMASK;
72 if (ptr->children[currindex] != NULL) {
73 if (totalshift != 0) {
74 ptr = ptr->children[currindex];
77 allnode * act = ptr->children[currindex];
78 sllnode<ModelAction *> * node = reinterpret_cast<sllnode<ModelAction *>*>(((uintptr_t)act) & ACTMASK);
85 increment = increment >> ALLBITS;
86 totalshift -= ALLBITS;
90 void actionlist::addAction(ModelAction * act) {
92 int shiftbits = MODELCLOCKBITS - ALLBITS;
93 modelclock_t clock = act->get_seq_number();
95 allnode * ptr = &root;
97 modelclock_t currindex = (clock >> shiftbits) & ALLMASK;
98 allnode * tmp = ptr->children[currindex];
100 sllnode<ModelAction *> * llnode = new sllnode<ModelAction *>();
103 sllnode<ModelAction *> * llnodeprev = ptr->findPrev(clock);
104 if (llnodeprev != NULL) {
105 llnode->next = llnodeprev->next;
106 llnode->prev = llnodeprev;
108 //see if we are the new tail
109 if (llnode->next != NULL)
110 llnode->next->prev = llnode;
113 llnodeprev->next = llnode;
115 //We are the begining
121 //we are the first node
127 ptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
129 //need to find next link
132 //handle case where something else is here
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;
141 llnodeprev->next = llnode;
142 ptr->children[currindex] = reinterpret_cast<allnode *>(((uintptr_t) llnode) | ISACT);
145 } else if (tmp == NULL) {
147 ptr->children[currindex] = tmp;
151 shiftbits -= ALLBITS;
157 void decrementCount(allnode * ptr) {
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);
173 void actionlist::removeAction(ModelAction * act) {
174 int shiftbits = MODELCLOCKBITS;
175 modelclock_t clock = act->get_seq_number();
176 allnode * ptr = &root;
178 modelclock_t currindex;
180 while(shiftbits != 0) {
181 shiftbits -= ALLBITS;
182 currindex = (clock >> shiftbits) & ALLMASK;
184 ptr = ptr->children[currindex];
189 sllnode<ModelAction *> * llnode = reinterpret_cast<sllnode<ModelAction *> *>(((uintptr_t) ptr) & ACTMASK);
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;
201 if (llnodenext != NULL) {
202 llnodenext->prev = llnodeprev;
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);
211 //remove ourselves and go up tree
212 oldptr->children[currindex] = NULL;
213 decrementCount(oldptr);
220 llnode = llnode->prev;
222 } while(llnode != NULL && llnode->val->get_seq_number() == clock);
223 //node not found in list... no deletion
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;
235 while(head != NULL) {
236 sllnode<ModelAction *> *tmp=head->next;
246 bool actionlist::isEmpty() {
247 return root.count == 0;
251 * Fix the parent pointer of root when root address changes (possible
252 * due to vector<action_list_t> resize)
254 void actionlist::fixupParent()
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;