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;
9 #define ISWRITEBIN(x) (x&BINMASK)
10 #define ISREADBIN(x) (!(x&BINMASK))
11 //#define POPCOUNT(x) __builtin_popcountll(x)
12 //__builtin_popcountll
14 //NOTE: only temporary
15 void rcr_createMasterHashTableArray(int maxSize){
18 HashStructure* rcr_createHashtable(int sizeofWaitingQueue){
20 HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
21 for(i=0;i<RNUMBINS;i++){
22 newTable->array[i].head=NULL;
23 newTable->array[i].tail=NULL;
29 WriteBinItem_rcr* rcr_createWriteBinItem(){
30 WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
31 binitem->item.type=WRITEBIN;
35 ReadBinItem_rcr* rcr_createReadBinItem(){
36 ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
38 binitem->item.type=READBIN;
42 inline int rcr_generateKey(void * ptr){
43 return (((struct ___Object___ *) ptr)->oid)&RH_MASK;
46 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
47 //chain of bins exists => tail is valid
48 //if there is something in front of us, then we are not ready
50 int key=rcr_generateKey(ptr);
51 BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
53 //LOCK is still needed as different threads will remove items...
55 val=(BinItem_rcr *)0x1;
56 val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
57 } while(val==(BinItem_rcr*)0x1);
60 BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
61 TraverserData * td = &((WriteBinItem_rcr*)b)->val;
65 //common to both types
67 td->bitindex=1<<index;
75 BinItem_rcr *bintail=be->tail;
76 bitv rdmask=0,wrmask=0;
79 if (ISWRITEBIN(bintail->type)) {
80 WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
81 //last one is to check for SESE blocks in a while loop.
82 if(unlikely(td->task == task)) {
85 if (!(bit & td->bitindexwr)) {
88 return (bintail->status==READY)?READY:SPECNOTREADY;
93 TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
94 if(unlikely(td->task == task)) {
95 //if it matches, then we remove it and the code below will upgrade it to a write.
96 ((ReadBinItem_rcr *)bintail)->index--;
97 atomic_dec(&bintail->total);
99 if (bintail->status!=READY)
105 WriteBinItem_rcr *b=rcr_createWriteBinItem();
111 //count already includes this
114 b->bitindexwr=bit|wrmask;
115 b->bitindexrd=bit|rdmask;
116 b->item.status=status;
117 bintail->next=(BinItem_rcr*)b;
118 be->tail=(BinItem_rcr*)b;
120 if (bintail->status==READY&&bintail->total==0) {
121 //we may have to set write as ready
122 while(val->total==0) {
124 b->item.status=READY;
137 int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
139 int key=rcr_generateKey(ptr);
140 BinElement_rcr * be = &(T->array[key]);
142 //LOCK is still needed as different threads will remove items...
144 val=(BinItem_rcr *)0x1;
145 val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
146 } while(val==(BinItem_rcr*)0x1);
149 BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
150 ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
151 TraverserData * td = &(readbin->array[readbin->index++]);
155 //common to both types
157 td->bitindex=1<<index;
167 BinItem_rcr * bintail=be->tail;
169 //check if already added item or not.
170 if (ISWRITEBIN(bintail->type)) {
171 WriteBinItem_rcr td = (WriteBinItem_rcr *)bintail;
172 if(unlikely(td->task==task)) {
175 int status=bintail->status;
176 if (!(td->bitindexrd & bit)) {
179 if (status==NOTREADY)
187 TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
188 if (unlikely(td->task==task)) {
191 int status=bintail->status;
192 if (!(td->bitindex & bit)) {
194 if (status==NOTREADY)
203 if (ISREADBIN(bintail->type)) {
204 return rcr_TAILREADCASE(T, ptr, val, bintail, key, task, index);
206 rcr_TAILWRITECASE(T, ptr, val, bintail, key, task, index);
212 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
213 ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
216 if (readbintail->item.status==READY) {
224 if (readbintail->index==RNUMREAD) { // create new read group
225 ReadBinItem_rcr* rb=rcr_createReadBinItem();
226 td = &rb->array[rb->index++];
229 rb->item.status=status;
230 T->array[key].tail->next=(BinItem_rcr*)rb;
231 T->array[key].tail=(BinItem_rcr*)rb;
232 } else { // group into old tail
233 td = &readbintail->array[readbintail->index++];
234 atomic_inc(&readbintail->item.total);
238 td->bitindex=1<<index;
240 T->array[key].head=val;//released lock
244 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
245 ReadBinItem_rcr* rb=rcr_createReadBinItem();
246 TraverserData * td = &(rb->array[rb->index++]);
248 rb->item.status=NOTREADY;
250 td->binitem = (BinItem_rcr *) rb;
252 td->bitindex=1<<index;
254 T->array[key].tail->next=(BinItem_rcr*)rb;
255 T->array[key].tail=(BinItem_rcr*)rb;
256 T->array[key].head=val;//released lock
259 RETIREHASHTABLE(HashStructure *T, SESECommon *task, int key) {
260 BinElement_rcr * be = &(T->array[key]);
261 BinItem_rcr *b=be->head;
263 if(ISREADBIN(READBIN)) {
264 atomic_dec(&b->total);
265 if (b->next==NULL || b->total>0) {
269 //We either have a write bin or we are at the end of a read bin
272 // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
273 BinItem_rcr * val=(BinItem_rcr *)0x1;
275 val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
276 } while(val==(BinItem_rcr*)0x1);
278 // at this point have locked bin
279 BinItem_rcr *ptr=val;
283 if (ISREADBIN(ptr->type)) {
284 if (ptr->status==NOTREADY) {
285 ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
286 for (i=0;i<rptr->index;i++) {
287 RESOLVE(rptr->array[i]);
288 if (((INTPTR)rptr->array[i]->task)&PARENTBIN) {
289 //parents go immediately
290 atomic_dec(&rptr->item.total);
295 if (ptr->next==NULL) {
300 } else if (ptr==val) {
307 if(ptr->status==NOTREADY) {
308 WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
311 if(((INTPTR)wptr->task)&PARENTBIN) {
315 } else { // write bin is already resolved
321 be->head=val; // release lock