1 #include "hashStructure.h"
2 //#include "WaitingQueue.h"
6 #include "rcr_runtime.h"
8 //NOTE: this is only temporary (for testing) and will be removed in favor of thread local variables
9 //It's basically an array of hashStructures so we can simulate what would happen in a many-threaded version
10 HashStructure ** allHashStructures;
11 #define ISWRITEBIN(x) (x&BINMASK)
12 #define ISREADBIN(x) (!(x&BINMASK))
13 //#define POPCOUNT(x) __builtin_popcountll(x)
14 //__builtin_popcountll
17 //NOTE: only temporary
18 void rcr_createMasterHashTableArray(int maxSize){
21 HashStructure* rcr_createHashtable(int sizeofWaitingQueue){
23 HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
24 for(i=0;i<RNUMBINS;i++){
25 newTable->array[i].head=NULL;
26 newTable->array[i].tail=NULL;
32 WriteBinItem_rcr* rcr_createWriteBinItem(){
33 WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
34 binitem->item.type=WRITEBIN;
38 ReadBinItem_rcr* rcr_createReadBinItem(){
39 ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
41 binitem->item.type=READBIN;
45 inline int rcr_generateKey(void * ptr){
46 return (((struct ___Object___ *) ptr)->oid)&RH_MASK;
49 inline int rcr_BWRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index, int mode) {
50 //chain of bins exists => tail is valid
51 //if there is something in front of us, then we are not ready
53 int key=rcr_generateKey(ptr);
54 BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
56 //LOCK is still needed as different threads will remove items...
58 val=(BinItem_rcr *)0x1;
59 val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
60 } while(val==(BinItem_rcr*)0x1);
63 BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
64 WriteBinItem_rcr * td = (WriteBinItem_rcr*)b;
68 //common to both types
70 td->bitindexrd=td->bitindexwr=1<<index;
78 BinItem_rcr *bintail=be->tail;
79 bitvt rdmask=0,wrmask=0;
82 if (ISWRITEBIN(bintail->type)) {
83 WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
84 //last one is to check for SESE blocks in a while loop.
85 if(unlikely(td->task == task)) {
88 if (!(bit & td->bitindexwr)) {
93 while(bintail->status!=READY) {
98 return (bintail->status==READY)?SPECREADY:SPECNOTREADY;
106 TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
107 if(unlikely(td->task == task)) {
108 //if it matches, then we remove it and the code below will upgrade it to a write.
109 ((ReadBinItem_rcr *)bintail)->index--;
110 atomic_dec(&bintail->total);
112 if (bintail->status!=READY)
118 WriteBinItem_rcr *b=rcr_createWriteBinItem();
124 //count already includes this
127 b->bitindexwr=bit|wrmask;
128 b->bitindexrd=bit|rdmask;
129 b->item.status=status;
130 bintail->next=(BinItem_rcr*)b;
131 be->tail=(BinItem_rcr*)b;
133 if (bintail->status==READY&&bintail->total==0) {
134 //we may have to set write as ready
135 while(val->total==0) {
136 if (val==((BinItem_rcr *)b)) {
137 b->item.status=READY;
151 while(b->item.status==NOTREADY) {
160 inline int rcr_BREADBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index, int mode) {
162 int key=rcr_generateKey(ptr);
163 BinElement_rcr * be = &(T->array[key]);
165 //LOCK is still needed as different threads will remove items...
167 val=(BinItem_rcr *)0x1;
168 val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
169 } while(val==(BinItem_rcr*)0x1);
172 BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
173 ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
174 TraverserData * td = &(readbin->array[readbin->index++]);
178 //common to both types
180 td->bitindex=1<<index;
190 BinItem_rcr * bintail=be->tail;
192 //check if already added item or not.
193 if (ISWRITEBIN(bintail->type)) {
194 WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
195 if(unlikely(td->task==task)) {
198 int status=bintail->status;
199 if (!(td->bitindexrd & bit)) {
207 while(bintail->status!=READY) {
216 TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
217 if (unlikely(td->task==task)) {
220 int status=bintail->status;
221 if (!(td->bitindex & bit)) {
228 while(bintail->status!=READY) {
238 if (ISREADBIN(bintail->type)) {
239 int stat=rcr_TAILREADCASE(T, ptr, val, bintail, key, task, index);
241 struct BinItem_rcr * bt=be->tail;
242 while(bt->status!=READY) {
250 rcr_TAILWRITECASE(T, ptr, val, bintail, key, task, index);
252 struct BinItem_rcr * bt=be->tail;
253 while(bt->status!=READY) {
264 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
265 return rcr_BWRITEBINCASE(T, ptr, task, index, 0);
267 int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
268 return rcr_BREADBINCASE(T, ptr, task, index, 0);
271 int rcr_WTWRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
272 return rcr_BWRITEBINCASE(T, ptr, task, index, 1);
275 int rcr_WTREADBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
276 return rcr_BREADBINCASE(T, ptr, task, index, 1);
279 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
280 ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
283 if (readbintail->item.status==READY) {
291 if (readbintail->index==RNUMREAD) { // create new read group
292 ReadBinItem_rcr* rb=rcr_createReadBinItem();
293 td = &rb->array[rb->index++];
296 rb->item.status=status;
297 T->array[key].tail->next=(BinItem_rcr*)rb;
298 T->array[key].tail=(BinItem_rcr*)rb;
299 } else { // group into old tail
300 td = &readbintail->array[readbintail->index++];
301 atomic_inc(&readbintail->item.total);
305 td->bitindex=1<<index;
307 T->array[key].head=val;//released lock
311 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
312 ReadBinItem_rcr* rb=rcr_createReadBinItem();
313 TraverserData * td = &(rb->array[rb->index++]);
315 rb->item.status=NOTREADY;
318 td->bitindex=1<<index;
320 T->array[key].tail->next=(BinItem_rcr*)rb;
321 T->array[key].tail=(BinItem_rcr*)rb;
322 T->array[key].head=val;//released lock
325 void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) {
326 BinElement_rcr * be = &(T->array[key]);
327 BinItem_rcr *b=be->head;
329 if(ISREADBIN(READBIN)) {
330 atomic_dec(&b->total);
331 if (b->next==NULL || b->total>0) {
335 //We either have a write bin or we are at the end of a read bin
338 // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
339 BinItem_rcr * val=(BinItem_rcr *)0x1;
341 val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
342 } while(val==(BinItem_rcr*)0x1);
344 // at this point have locked bin
345 BinItem_rcr *ptr=val;
349 if (ISREADBIN(ptr->type)) {
350 if (ptr->status==NOTREADY) {
351 ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
352 for (i=0;i<rptr->index;i++) {
353 TraverserData * td=&rptr->array[i];
354 if (task==td->task) {
355 RESOLVE(td->task, td->bitindex);
356 if (((INTPTR)rptr->array[i].task)&PARENTBIN) {
357 //parents go immediately
358 atomic_dec(&rptr->item.total);
365 if (ptr->next==NULL) {
370 } else if (ptr==val) {
377 if(ptr->status==NOTREADY) {
378 WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
379 RESOLVE(wptr->task, wptr->bitindexwr);
381 if(((INTPTR)wptr->task)&PARENTBIN) {
385 } else { // write bin is already resolved
391 be->head=val; // release lock
395 void RESOLVE(SESEcommon *record, bitvt mask) {
397 struct rcrRecord * array=(struct rcrRecord *)(((char *)record)+record->offsetToParamRecords);
399 int shift=__builtin_ctzll(mask)+1;
401 if (atomic_sub_and_test(1,&array[index].count)) {
402 if(unlikely(record->classID<0)) {
403 //parent stall...clear it
404 psem_give_tag(record->parentsStallSem, ((SESEstall *)record)->tag);
406 int flag=LOCKXCHG32(&array[index].flag,0);
408 if(atomic_sub_and_test(1, &(record->unresolvedDependencies)))
409 workScheduleSubmit((void *)record);