Robust/src/Runtime/oooJava/hashStructure.c

   1 #include "hashStructure.h"
   2 #include "WaitingQueue.h"
   3 #include "mlp_lock.h"
   4 #include "tm.h"
   5
   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
  10 //NOTE: only temporary
  11 void createMasterHashTableArray(int maxSize) {
  12   int i;
  13   allHashTables = (HashTable**) malloc(sizeof(Hashtable) * maxSize);
  14
  15   for(i = 0; i < maxSize; i++) {
  16     allHashTables[i] = createHashtable();
  17   }
  18 }
  19
  20 HashStructure* createHashtable(int sizeofWaitingQueue){
  21   int i=0;
  22   HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
  23   for(i=0;i<NUMBINS;i++){
  24     newTable->array[i].head=NULL;
  25     newTable->array[i].tail=NULL;
  26   }
  27
  28   newTable->waitingQueue=mallocWaitingQueue(sizeofWaitingQueue);
  29   return newTable;
  30 }
  31
  32
  33 WriteBinItem_rcr* createWriteBinItem(){
  34   WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
  35   binitem->item.type=WRITEBIN;
  36   return binitem;
  37 }
  38
  39 ReadBinItem_rcr* createReadBinItem(){
  40   ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
  41   binitem->index=0;
  42   binitem->item.type=READBIN;
  43   return binitem;
  44 }
  45
  46 int isReadBinItem(BinItem_rcr* b){
  47   if(b->type==READBIN){
  48     return TRUE;
  49   }else{
  50     return FALSE;
  51   }
  52 }
  53
  54 int isWriteBinItem(BinItem_rcr* b){
  55   if(b->type==WRITEBIN){
  56     return TRUE;
  57   }else{
  58     return FALSE;
  59   }
  60 }
  61
  62 inline int generateKey(void * ptr){
  63   return (((struct genericObjectStruct *) ptr)->oid)&H_MASK;
  64 }
  65
  66 //TODO handle logic for waiting Queues separately
  67 //TODO pass in task to traverser
  68 int ADDTABLEITEM(HashStructure* table, void * ptr, int type, int traverserID, SESEcommon *task, void * heaproot){
  69   //Removed lock since it's not needed if only 1 thread hits the hashtable.
  70   BinItem_rcr * val = table->array[key]->bin->head;
  71   int key=generateKey(ptr);
  72
  73   if (val==NULL) {
  74     return EMPTYBINCASE(table, table->array[key], ptr, type, traverserID, task, heaproot);
  75   } else {
  76     //else create item
  77     if (type == WRITEEFFECT) {
  78       return WRITEBINCASE(table, ptr, val, key, traverserID, task, heaproot);
  79     } else if (type == READEFFECT) {
  80       return READBINCASE(table, ptr, val, key, traverserID, task, heaproot);
  81     }
  82   }
  83 }
  84
  85 int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int traverserId, SESEcommon * task, void *heaproot) {
  86   BinItem_rcr* b;
  87   TraverserData * td;
  88   if (type == WRITEEFFECT) {
  89     b=(BinItem_rcr*)createWriteBinItem();
  90     td = &((WriteBinItem_rcr*)b)->val;
  91   }
  92   else if (type == READEFFECT) {
  93     b=(BinItem_rcr*)createReadBinItem();
  94     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
  95     td = &(readbin->array[readbin->index++]);
  96   }
  97   b->total=1;
  98   b->type= type;
  99   b->status = READY;
 100
 101   //common to both types
 102   td->binitem = b;
 103   td->hashtable=T;
 104   td->resumePtr = ptr;
 105   td->task= task;
 106   td->traverserID = traverserId;
 107   td->heaproot = heaproot;
 108
 109   be->tail=b;
 110   be->head=b;
 111
 112   return READY;
 113 }
 114
 115
 116 int WRITEBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon *task, void *heaproot) {
 117   //chain of bins exists => tail is valid
 118   //if there is something in front of us, then we are not ready
 119   int status=NOTREADY;
 120   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
 121
 122   if(be->tail->type == WRITEBIN) {
 123     TraverserData * td = &(((WriteBinItem_rcr *)be->tail)->val);
 124     //last one is to check for SESE blocks in a while loop.
 125     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID && td->task == task) {
 126       return be->tail->status;
 127     }
 128   } else if(be->tail->type == READBIN) {
 129     TraverserData * td = &((ReadBinItem_rcr *)be->tail)->array[((ReadBinItem_rcr *)be->tail)->index - 1];
 130     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 131       //if it matches, then we remove it and the code below will upgrade it to a write.
 132       ((ReadBinItem_rcr *)be->tail)->index--;
 133       be->tail->total--;
 134     }
 135   }
 136
 137   WriteBinItem_rcr *b=createWriteBinItem();
 138   TraverserData * td = &b->val;
 139   b->item.total=1;
 140
 141   //fillout traverserData
 142   //Note: this list could be smaller in the future, for now I'm just including all the info I may need.
 143   td->binitem = b;
 144   td->hashtable=T;
 145   td->resumePtr = ptr;
 146   td->task= task;
 147   td->traverserID = traverserID;
 148   td->heaproot = heaproot;
 149
 150   b->item.status=status;
 151   be->tail->next=(BinItem_rcr*)b;
 152   be->tail=(BinItem_rcr*)b;
 153   return status;
 154 }
 155
 156 int READBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon * task, void *heaproot) {
 157   BinElement_rcr * be = &(T->array[key]);
 158   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) {
 163       return bintail->status;
 164     }
 165   }
 166   else if(bintail->type == READEFFECT) {
 167     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 168     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 169       return bintail->status;
 170     }
 171   }
 172
 173   if (isReadBinItem(bintail)) {
 174     return TAILREADCASE(T, ptr, bintail, key, traverserID, task, heaproot);
 175   } else if (!isReadBinItem(bintail)) {
 176     TAILWRITECASE(T, ptr, bintail, key, traverserID, task, heaproot);
 177     return NOTREADY;
 178   }
 179 }
 180
 181 int TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
 182   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 183   int status, retval;
 184   TraverserData *td;
 185   if (readbintail->item.status==READY) {
 186     status=READY;
 187     retval=READY;
 188   } else {
 189     status=NOTREADY;
 190     retval=NOTREADY;
 191   }
 192
 193   if (readbintail->index==NUMREAD) { // create new read group
 194     ReadBinItem_rcr* rb=createReadBinItem();
 195     td = &rb->array[rb->index++];
 196
 197     rb->item.total=1;
 198     rb->item.status=status;
 199     T->array[key].tail->next=(BinItem_rcr*)rb;
 200     T->array[key].tail=(BinItem_rcr*)rb;
 201   } else { // group into old tail
 202     td = &readbintail->array[readbintail->index++];
 203     atomic_inc(&readbintail->item.total);
 204     //printf("grouping with %d\n",readbintail->index);
 205   }
 206
 207   td->binitem = bintail;
 208   td->hashtable=T;
 209   td->resumePtr = ptr;
 210   td->task= task;
 211   td->traverserID = traverserID;
 212   td->heaproot = heaproot;
 213
 214   return retval;
 215 }
 216
 217 void TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
 218   //  WriteBinItem* wb=createWriteBinItem();
 219   //wb->val=r;
 220   //wb->item.total=1;//safe because item could not have started
 221   //wb->item.status=NOTREADY;
 222   ReadBinItem_rcr* rb=createReadBinItem();
 223   TraverserData * td = &(rb->array[rb->index++]);
 224   rb->item.total=1;
 225   rb->item.status=NOTREADY;
 226
 227   td->binitem = rb;
 228   td->hashtable=T;
 229   td->resumePtr = ptr;
 230   td->task= task;
 231   td->traverserID = traverserID;
 232   td->heaproot = heaproot;
 233
 234   T->array[key].tail->next=(BinItem_rcr*)rb;
 235   T->array[key].tail=(BinItem_rcr*)rb;
 236 }
 237
 238 //TODO write deletion/removal methods