1 #include "hashStructure.h"
2 #include "WaitingQueue.h"
6 //NOTE: this is only temporary (for testing) and will be removed in favor of thread local variables
7 //It's basically an array of hashStructures so we can simulate what would happen in a many-threaded version
8 HashStructure ** allHashStructures;
10 //NOTE: only temporary
11 void rcr_createMasterHashTableArray(int maxSize){
14 HashStructure* rcr_createHashtable(int sizeofWaitingQueue){
16 HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
17 for(i=0;i<NUMBINS;i++){
18 newTable->array[i].head=NULL;
19 newTable->array[i].tail=NULL;
22 newTable->waitingQueue=mallocWaitingQueue(sizeofWaitingQueue);
26 WriteBinItem_rcr* rcr_createWriteBinItem(){
27 WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
28 binitem->item.type=WRITEBIN;
32 ReadBinItem_rcr* rcr_createReadBinItem(){
33 ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
35 binitem->item.type=READBIN;
39 int rcr_isReadBinItem(BinItem_rcr* b){
40 return b->type==READBIN;
43 int rcr_isWriteBinItem(BinItem_rcr* b){
44 return b->type==WRITEBIN;
47 inline int rcr_generateKey(void * ptr){
48 return (((struct genericObjectStruct *) ptr)->oid)&H_MASK;
51 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *task, void *heaproot) {
52 //chain of bins exists => tail is valid
53 //if there is something in front of us, then we are not ready
55 int key=rcr_generateKey(ptr);
56 BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
58 //LOCK is still needed as different threads will remove items...
60 val=(BinItem_rcr *)0x1;
61 val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
62 } while(val==(BinItem_rcr*)0x1);
65 BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
66 TraverserData * td = &((WriteBinItem_rcr*)b)->val;
70 //common to both types
75 td->traverserID = traverserID;
76 td->heaproot = heaproot;
85 BinItem_rcr *bintail=be->tail;
87 if (bintail->type == WRITEBIN) {
88 TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val);
89 //last one is to check for SESE blocks in a while loop.
90 if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID && td->task == task) {
91 return bintail->status;
93 } else if (bintail->type == READBIN) {
94 TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
95 if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
96 //if it matches, then we remove it and the code below will upgrade it to a write.
97 ((ReadBinItem_rcr *)bintail)->index--;
102 WriteBinItem_rcr *b=rcr_createWriteBinItem();
103 TraverserData * td = &b->val;
106 //fillout traverserData
107 //Note: this list could be smaller in the future, for now I'm just including all the info I may need.
108 td->binitem = (BinItem_rcr*)b;
112 td->traverserID = traverserID;
113 td->heaproot = heaproot;
115 b->item.status=status;
116 bintail->next=(BinItem_rcr*)b;
117 be->tail=(BinItem_rcr*)b;
123 int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * task, void *heaproot) {
125 int key=rcr_generateKey(ptr);
126 BinElement_rcr * be = &(T->array[key]);
128 //LOCK is still needed as different threads will remove items...
130 val=(BinItem_rcr *)0x1;
131 val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
132 } while(val==(BinItem_rcr*)0x1);
135 BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
136 ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
137 TraverserData * td = &(readbin->array[readbin->index++]);
141 //common to both types
146 td->traverserID = traverserID;
147 td->heaproot = heaproot;
157 BinItem_rcr * bintail=be->tail;
159 //check if already added item or not.
160 if (bintail->type == WRITEBIN) {
161 TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val);
162 if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
165 return bintail->status;
167 } else if (bintail->type == READEFFECT) {
168 TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
169 if (unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
172 return bintail->status;
176 if (isReadBinItem(bintail)) {
177 return rcr_TAILREADCASE(T, ptr, val, bintail, key, traverserID, task, heaproot);
178 } else if (!isReadBinItem(bintail)) {
179 rcr_TAILWRITECASE(T, ptr, val, bintail, key, traverserID, task, heaproot);
185 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
186 ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
189 if (readbintail->item.status==READY) {
197 if (readbintail->index==NUMREAD) { // create new read group
198 ReadBinItem_rcr* rb=rcr_createReadBinItem();
199 td = &rb->array[rb->index++];
202 rb->item.status=status;
203 T->array[key].tail->next=(BinItem_rcr*)rb;
204 T->array[key].tail=(BinItem_rcr*)rb;
205 } else { // group into old tail
206 td = &readbintail->array[readbintail->index++];
207 atomic_inc(&readbintail->item.total);
208 //printf("grouping with %d\n",readbintail->index);
211 td->binitem = bintail;
215 td->traverserID = traverserID;
216 td->heaproot = heaproot;
218 T->array[key].head=val;//released lock
222 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
223 ReadBinItem_rcr* rb=rcr_createReadBinItem();
224 TraverserData * td = &(rb->array[rb->index++]);
226 rb->item.status=NOTREADY;
228 td->binitem = (BinItem_rcr *) rb;
232 td->traverserID = traverserID;
233 td->heaproot = heaproot;
235 T->array[key].tail->next=(BinItem_rcr*)rb;
236 T->array[key].tail=(BinItem_rcr*)rb;
237 T->array[key].head=val;//released lock
240 //TODO write deletion/removal methods
243 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
244 Hashtable *T=r->hashtable;
245 BinItem_rcr *b=r->binitem;
249 RETIREBIN(Hashtable *T, REntry *r, BinItem_rcr *b) {
250 int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
252 atomic_dec(&b->total);
254 if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
255 // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
258 val=(BinItem_rcr*)0x1;
259 val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
260 } while(val==(BinItem_rcr*)0x1);
261 // at this point have locked bin
262 BinItem_rcr *ptr=val;
266 if (isReadBinItem(ptr)) {
267 ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
268 if (rptr->item.status==NOTREADY) {
269 for (i=0;i<rptr->index;i++) {
270 resolveDependencies(rptr->array[i]);
271 if (isParent(rptr->array[i])) {
272 //parents go immediately
273 atomic_dec(&rptr->item.total);
274 atomic_dec(&T->item.total);
278 rptr->item.status=READY;
279 if (rptr->item.next==NULL) {
282 if (rptr->item.total!=0) {
284 } else if ((BinItem_rcr*)rptr==val) {
287 } else if(isWriteBinItem(ptr)) {
290 if(ptr->status==NOTREADY){
291 resolveDependencies(((WriteBinItem_rcr*)ptr)->val);
293 if(isParent(((WriteBinItem_rcr*)ptr)->val)){
294 atomic_dec(&T->item.total);
298 }else{ // write bin is already resolved
304 T->array[key]->head=val; // release lock
310 //Int will return success/fail. -1 indicates error (i.e. there's nothing there).
311 //0 = nothing removed, >0 something was removed
312 int REMOVETABLEITEM(HashStructure* table, void * ptr, int traverserID, SESEcommon *task, void * heaproot) {
313 int key = generateKey(ptr);
314 BinElement_rcr * bucket = table->array[key];
316 if(bucket->head == NULL) {
318 //This can occur if we try to remove something that's in the waitingQueue directly from the hashtable.
321 if(bucket->head->type == WRITEBIN) {
322 TraverserData * td = &(((WriteBinItem_rcr *) head)->val);
323 if(td->resumePtr == ptr && td->traverserID == traverserID && td->heaproot == heaproot) {
324 BinItem_rcr * temp = bucket->head;
325 bucket->head = bucket->head->next;
326 free(temp); //TODO perhaps implement a linked list of free BinElements as was done in WaitingQueue
328 //Handle items behind write item
329 if(bucket->head == NULL) {
330 bucket->tail == NULL;
334 int type = bucket->head->type;
335 switch(bucket->head->type) {
337 bucket->head->status = READY;
338 //TODO Decrement dependency count
340 case WAITINGQUEUENOTE:
341 int retval = removeFromWaitingQueue(table->waitingQueue, ((WaitingQueueNote *) bucket->head)->allocSiteID, traverserID);
343 //we set both to NULL because the note should ALWAYS be the last item in the hashStructure.
349 BinItem_rcr * temp = bucket->head;
350 while(temp != NULL && temp->type == READBIN) {
351 temp->status = READY;
353 //TODO decrement dependency count
362 if(bucket->head->type == READBIN) {
363 //TODO There's an issue here; bins are groups of items that may be enqueued by different ids.
364 //I may have to search through them to find which one to remove but then there'd be a blank spot in an
365 //otherwise clean array. It wouldn't make sense to just check the first one since reads are reorderable.
366 //Nor does it make sense to lop off the reads since that may signal the next write to be ready even before it
370 if(bucket->head->type == WAITINGQUEUENOTE) {
371 int retval = removeFromWaitingQueue(table->waitingQueue, ((WaitingQueueNote *) bucket->head)->allocSiteID, traverserID);