space hacks
authorbdemsky <bdemsky@uci.edu>
Sat, 7 Apr 2018 10:09:12 +0000 (03:09 -0700)
committerbdemsky <bdemsky@uci.edu>
Sat, 7 Apr 2018 10:09:12 +0000 (03:09 -0700)
version2/src/C/CloudComm.cpp
version2/src/C/Commit.cpp
version2/src/C/Commit.h
version2/src/C/IoTString.h
version2/src/C/KeyValue.cpp
version2/src/C/NewKey.cpp
version2/src/C/Table.cpp
version2/src/C/Test.C
version2/src/C/hashset.h
version2/src/C/hashtable.h

index 8fe0cee..45b7dac 100644 (file)
@@ -46,10 +46,10 @@ void *threadWrapper(void *cloud) {
  * Constructor for actual use. Takes in the url and password.
  */
 CloudComm::CloudComm(Table *_table,  IoTString *_baseurl, IoTString *_password, int _listeningPort) :
-       baseurl(new IoTString(_baseurl)),
+       baseurl(_baseurl->acquireRef()),
        key(NULL),
        mac(NULL),
-       password(new IoTString(_password)),
+       password(_password->acquireRef()),
        random(new SecureRandom()),
        salt(NULL),
        table(_table),
@@ -69,11 +69,11 @@ CloudComm::~CloudComm() {
        if (salt)
                delete salt;
        if (password)
-               delete password;
+               password->releaseRef();
        if (random)
                delete random;
        if (baseurl)
-               delete baseurl;
+               baseurl->releaseRef();
        if (mac)
                delete mac;
        if (key)
@@ -118,7 +118,7 @@ void CloudComm::initCrypt() {
        }
        try {
                key = initKey();
-               delete password;
+               password->releaseRef();
                password = NULL;// drop password
                mac = new Mac();
                mac->init(key);
index 7665841..d7c9220 100644 (file)
@@ -6,7 +6,6 @@
 Commit::Commit() :
        parts(new Vector<CommitPart *>()),
        partCount(0),
-       missingParts(NULL),
        fldisComplete(false),
        hasLastPart(false),
        keyValueUpdateSet(new Hashset<KeyValue *, uintptr_t, 0>()),
@@ -21,7 +20,6 @@ Commit::Commit() :
 Commit::Commit(int64_t _sequenceNumber, int64_t _machineId, int64_t _transactionSequenceNumber) :
        parts(new Vector<CommitPart *>()),
        partCount(0),
-       missingParts(NULL),
        fldisComplete(true),
        hasLastPart(false),
        keyValueUpdateSet(new Hashset<KeyValue *, uintptr_t, 0>()),
@@ -49,8 +47,6 @@ Commit::~Commit() {
                delete keyValueUpdateSet;
        }
        delete liveKeys;
-       if (missingParts != NULL)
-               delete missingParts;
        if (dataBytes != NULL)
                delete dataBytes;
 }
@@ -72,27 +68,21 @@ void Commit::addPartDecode(CommitPart *newPart) {
                previouslySeenPart->setDead();
                previouslySeenPart->releaseRef();
        } else if (newPart->isLastPart()) {
-               missingParts = new Hashset<int32_t>();
                hasLastPart = true;
-
-               for (int i = 0; i < newPart->getPartNumber(); i++) {
-                       if (parts->get(i) == NULL) {
-                               missingParts->add(i);
-                       }
-               }
        }
 
        if (!fldisComplete && hasLastPart) {
-
                // We have seen this part so remove it from the set of missing parts
-               missingParts->remove(newPart->getPartNumber());
-
-               // Check if all the parts have been seen
-               if (missingParts->size() == 0) {
-
-                       // We have all the parts
-                       fldisComplete = true;
+               uint size = parts->size();
+               fldisComplete = true;
+               for(uint i=0; i < size; i++) {
+                       if (parts->get(i) == NULL) {
+                               fldisComplete = false;
+                               break;
+                       }
+               }
 
+               if (fldisComplete) {
                        // Decode all the parts and create the key value guard and update sets
                        decodeCommitData();
 
index d9f05a9..de6b77b 100644 (file)
@@ -7,7 +7,6 @@ class Commit {
 private:
        Vector<CommitPart *> *parts;
        uint32_t partCount;
-       Hashset<int32_t> *missingParts;
        bool fldisComplete;
        bool hasLastPart;
        Hashset<KeyValue *, uintptr_t, 0> *keyValueUpdateSet;
index 583a098..99e45bb 100644 (file)
@@ -22,8 +22,10 @@ inline unsigned int hashCharArray(Array<char> *array) {
 class IoTString {
 private:
        Array<char> *array;
-       IoTString() {}
        unsigned int hashvalue;
+       unsigned int refCount;
+  IoTString() : refCount (1) {}
+
        /**
         * Builds an IoTString object around the char array.  This
         * constructor makes a copy, so the caller is free to modify the char array.
@@ -32,7 +34,8 @@ private:
 public:
        IoTString(Array<char> *_array) :
                array(new Array<char>(_array)),
-               hashvalue(hashCharArray(array)) {
+                       hashvalue(hashCharArray(array)),
+                       refCount(1) {
        }
 
        IoTString(const char *_array) {
@@ -40,13 +43,25 @@ public:
                array = new Array<char>(len);
                memcpy(array->internalArray(), _array, len);
                hashvalue = hashCharArray(array);
+               refCount = 1;
        }
 
        IoTString(IoTString *string) :
          array(new Array<char>(string->array)),
-               hashvalue(string->hashvalue) {
+                       hashvalue(string->hashvalue),
+                       refCount(1) {
+       }
+
+       IoTString * acquireRef() {
+               refCount++;
+               return this;
        }
 
+       void releaseRef() {
+               if ((--refCount) == 0)
+                       delete this;
+       }
+       
        ~IoTString() {
                delete array;
        }
index 8aea6f2..7041ba4 100644 (file)
@@ -8,8 +8,8 @@
  */
 
 KeyValue::~KeyValue() {
-       delete key;
-       delete value;
+       key->releaseRef();
+       value->releaseRef();
 }
 
 KeyValue *KeyValue_decode(ByteBuffer *bb) {
@@ -47,5 +47,5 @@ int KeyValue::getSize() {
 }
 
 KeyValue *KeyValue::getCopy() {
-       return new KeyValue(new IoTString(key), new IoTString(value));
+       return new KeyValue(key->acquireRef(), value->acquireRef());
 }
index 0b35933..edc5e9e 100644 (file)
@@ -4,12 +4,12 @@
 
 NewKey::NewKey(Slot *slot, IoTString *_key, int64_t _machineid) :
        Entry(slot),
-       key(new IoTString(_key)),
+       key(_key->acquireRef()),
        machineid(_machineid) {
 }
 
 NewKey::~NewKey() {
-       delete key;
+       key->releaseRef();
 }
 
 Entry *NewKey_decode(Slot *slot, ByteBuffer *bb) {
@@ -19,7 +19,7 @@ Entry *NewKey_decode(Slot *slot, ByteBuffer *bb) {
        int64_t machineid = bb->getLong();
        IoTString *str = IoTString_shallow(key);
        NewKey *newkey = new NewKey(slot, str, machineid);
-       delete str;
+       str->releaseRef();
        return newkey;
 }
 
index 255ba3c..5982d2d 100644 (file)
@@ -47,10 +47,10 @@ Table::Table(IoTString *baseurl, IoTString *password, int64_t _localMachineId, i
        localMachineId(_localMachineId),
        sequenceNumber(0),
        localSequenceNumber(0),
-       localTransactionSequenceNumber(0),
+       localTransactionSequenceNumber(1),
        lastTransactionSequenceNumberSpeculatedOn(0),
        oldestTransactionSequenceNumberSpeculatedOn(0),
-       localArbitrationSequenceNumber(0),
+       localArbitrationSequenceNumber(1),
        hadPartialSendToServer(false),
        attemptedToSendToServer(false),
        expectedsize(0),
@@ -109,10 +109,10 @@ Table::Table(CloudComm *_cloud, int64_t _localMachineId) :
        localMachineId(_localMachineId),
        sequenceNumber(0),
        localSequenceNumber(0),
-       localTransactionSequenceNumber(0),
+       localTransactionSequenceNumber(1),
        lastTransactionSequenceNumberSpeculatedOn(0),
        oldestTransactionSequenceNumberSpeculatedOn(0),
-       localArbitrationSequenceNumber(0),
+       localArbitrationSequenceNumber(1),
        hadPartialSendToServer(false),
        attemptedToSendToServer(false),
        expectedsize(0),
@@ -392,7 +392,7 @@ IoTString *Table::getCommitted(IoTString *key)  {
        KeyValue *kv = committedKeyValueTable->get(key);
 
        if (kv != NULL) {
-               return new IoTString(kv->getValue());
+               return kv->getValue()->acquireRef();
        } else {
                return NULL;
        }
@@ -410,7 +410,7 @@ IoTString *Table::getSpeculative(IoTString *key) {
        }
 
        if (kv != NULL) {
-               return new IoTString(kv->getValue());
+               return kv->getValue()->acquireRef();
        } else {
                return NULL;
        }
@@ -431,7 +431,7 @@ IoTString *Table::getCommittedAtomic(IoTString *key) {
 
        if (kv != NULL) {
                pendingTransactionBuilder->addKVGuard(new KeyValue(key, kv->getValue()));
-               return new IoTString(kv->getValue());
+               return kv->getValue()->acquireRef();
        } else {
                pendingTransactionBuilder->addKVGuard(new KeyValue(key, NULL));
                return NULL;
@@ -461,7 +461,7 @@ IoTString *Table::getSpeculativeAtomic(IoTString *key) {
 
        if (kv != NULL) {
                pendingTransactionBuilder->addKVGuard(new KeyValue(key, kv->getValue()));
-               return new IoTString(kv->getValue());
+               return kv->getValue()->acquireRef();
        } else {
                pendingTransactionBuilder->addKVGuard(new KeyValue(key, NULL));
                return NULL;
@@ -523,7 +523,7 @@ void Table::put(IoTString *key, IoTString *value) {
        }
 
        // Add the key value to this transaction
-       KeyValue *kv = new KeyValue(new IoTString(key), new IoTString(value));
+       KeyValue *kv = new KeyValue(key->acquireRef(), value->acquireRef());
        pendingTransactionBuilder->addKV(kv);
 }
 
index 0f6c96c..9393423 100644 (file)
@@ -22,7 +22,8 @@ int main(int numargs, char ** args) {
        t2->update();
        printf("T2 Ready\n");
 
-       delete baseurl; delete password;
+       baseurl->releaseRef();
+       password->releaseRef();
        
        // Make the Keys
        printf("Setting up keys\n");
@@ -41,10 +42,10 @@ int main(int numargs, char ** args) {
                t1->createNewKey(ib, 351);
                t2->createNewKey(ic, 321);
                t2->createNewKey(id, 351);
-               delete ia;
-               delete ib;
-               delete ic;
-               delete id;
+               ia->releaseRef();
+               ib->releaseRef();
+               ic->releaseRef();
+               id->releaseRef();
        }
        
        // Do Updates for the keys
@@ -71,22 +72,26 @@ int main(int numargs, char ** args) {
                t1->startTransaction();
                t1->put(iKeyA, iValueA);
                transStatusList->add(t1->commitTransaction());
-               delete iKeyA; delete iValueA;
+               iKeyA->releaseRef();
+               iValueA->releaseRef();
                
                t1->startTransaction();
                t1->put(iKeyB, iValueB);
                transStatusList->add(t1->commitTransaction());
-               delete iKeyB; delete iValueB;
+               iKeyB->releaseRef();
+               iValueB->releaseRef();
                
                t2->startTransaction();
                t2->put(iKeyC, iValueC);
                transStatusList->add(t2->commitTransaction());
-               delete iKeyC; delete iValueC;
+               iKeyC->releaseRef();
+               iValueC->releaseRef();
                
                t2->startTransaction();
                t2->put(iKeyD, iValueD);
                transStatusList->add(t2->commitTransaction());
-               delete iKeyD; delete iValueD;
+               iKeyD->releaseRef();
+               iValueD->releaseRef();
        }
        
        printf("Updating Clients...\n");
@@ -161,14 +166,22 @@ int main(int numargs, char ** args) {
                        printf("Key-Value t2 incorrect: keyD     testValD2\n");
                        foundError = true;
                }
-               delete iKeyA; delete iValueA;
-               delete iKeyB; delete iValueB;
-               delete iKeyC; delete iValueC;
-               delete iKeyD; delete iValueD;
-               delete testValA1; delete testValA2;
-               delete testValB1; delete testValB2;
-               delete testValC1; delete testValC2;
-               delete testValD1; delete testValD2;
+               iKeyA->releaseRef();
+               iValueA->releaseRef();
+               iKeyB->releaseRef();
+               iValueB->releaseRef();
+               iKeyC->releaseRef();
+               iValueC->releaseRef();
+               iKeyD->releaseRef();
+               iValueD->releaseRef();
+               testValA1->releaseRef();
+               testValA2->releaseRef();
+               testValB1->releaseRef();
+               testValB2->releaseRef();
+               testValC1->releaseRef();
+               testValC2->releaseRef();
+               testValD1->releaseRef();
+               testValD2->releaseRef();
        }
 
        for (uint i = 0; i < transStatusList->size(); i++) {
@@ -188,6 +201,5 @@ int main(int numargs, char ** args) {
 
        delete transStatusList;
        delete t1;
-       delete t2;
 }
 
index 5c81425..7349506 100644 (file)
@@ -17,8 +17,9 @@ class Hashset;
 template<typename _Key, typename _Val, typename _KeyInt = uintptr_t, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
 class SetIterator {
 public:
-       SetIterator(Hashlistnode<_Key, _Val> *_curr, Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *_table) :
-               curr(_curr),
+       SetIterator(Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *_table) :
+    currptr(1),
+    nextptr(0),
                table(_table)
        {
        }
@@ -44,32 +45,52 @@ public:
        }
 
        bool hasNext() {
-               return curr != NULL;
+               if (currptr > nextptr) {
+                       currptr = 0;
+               } else {
+                       nextptr++;
+               }
+               if (nextptr == 0) {
+                       if (table->zero && table->zero->val)
+                               return true;
+                       else
+                               nextptr++;
+               }
+               for(;nextptr < (table->capacity + 1);nextptr++) {
+                       struct Hashlistnode<_Key, _Val> *ptr = & table->table[nextptr-1];
+                       if (ptr->key && ptr->val) {
+                               return true;
+                       }
+               }
+               return false;
        }
 
   _Val currVal() {
-         return last->val;
+    if (currptr == 0)
+                       return table->zero->val;
+               else
+                       return table->table[currptr-1].val;
   }
 
-  _Key next() {
-               _Key k = curr->key;
-               last = curr;
-               curr = curr->next;
-               return k;
+  _Key currKey() {
+               if (currptr == 0)
+                       return table->zero->key;
+               else
+                       return table->table[currptr-1].key;
        }
 
-       _Key currKey() {
-               return last->key;
+  _Key next() {
+               currptr = nextptr;
+               return currKey();
        }
 
        void remove() {
-               _Key k = last->key;
-               table->remove(k);
+               table->remove(currKey());
        }
 
 private:
-       Hashlistnode<_Key,_Val> *curr;
-       Hashlistnode<_Key, _Val> *last;
+  unsigned int currptr;
+  unsigned int nextptr;
        Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *table;
 };
 
@@ -151,7 +172,7 @@ public:
        }
 
        SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *iterator() {
-               return new SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals>(table->list, table);
+               return new SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals>(table);
        }
 
        /** Override: new operator */
@@ -179,6 +200,6 @@ private:
 
 template<typename _Key, typename _Val, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
 SetIterator<_Key, _Val,_KeyInt, _Shift, hash_function, equals> *getKeyIterator(Hashtable<_Key,_Val,_KeyInt,_Shift,hash_function,equals> *table) {
-       return new SetIterator<_Key, _Val, _KeyInt, _Shift, hash_function, equals>(table->list, table);
+       return new SetIterator<_Key, _Val, _KeyInt, _Shift, hash_function, equals>(table);
 }
 #endif
index 6107e33..422eef7 100644 (file)
@@ -30,9 +30,6 @@ template<typename _Key, typename _Val>
 struct Hashlistnode {
        _Key key;
        _Val val;
-       uint hashcode;
-       struct Hashlistnode<_Key, _Val> *next;
-       struct Hashlistnode<_Key, _Val> *prev;
 };
 
 template<typename _Key, int _Shift, typename _KeyInt>
@@ -70,7 +67,7 @@ public:
         * @param factor Sets the percentage full before the hashtable is
         * resized. Default ratio 0.5.
         */
-       Hashtable(unsigned int initialcapacity = 32, double factor = 0.5) {
+       Hashtable(unsigned int initialcapacity = 16, double factor = 0.5) {
                // Allocate space for the hash table
                table = (struct Hashlistnode<_Key, _Val> *)ourcalloc(initialcapacity, sizeof(struct Hashlistnode<_Key, _Val>));
                zero = NULL;
@@ -80,15 +77,17 @@ public:
 
                threshold = (unsigned int)(initialcapacity * loadfactor);
                Size = 0;                                                       // Initial number of elements in the hash
-               tail = list = NULL;
        }
 
        Hashtable<_Key, _Val, _KeyInt, _Shift, hash_function, equals> *clone() {
                Hashtable<_Key, _Val, _KeyInt, _Shift, hash_function, equals> *ctable = new Hashtable<_Key, _Val, _KeyInt, _Shift, hash_function, equals> (capacity, loadfactor);
-               struct Hashlistnode<_Key, _Val> *ptr = list;
-               while (ptr != NULL) {
-                       ctable->put(ptr->key, ptr->val);
-                       ptr = ptr->next;
+               if (zero)
+                       ctable->put(zero->key, zero->val);
+
+               for(unsigned int i=0; i<capacity; i++) {
+                       struct Hashlistnode<_Key, _Val> ptr = table[i];                 
+                       if (ptr.key && ptr.val)
+                               ctable->put(ptr.key, ptr.val);
                }
                return ctable;
        }
@@ -129,7 +128,6 @@ public:
                        zero = NULL;
                }
                Size = 0;
-               tail = list = NULL;
        }
 
        /** Doesn't work with zero value */
@@ -159,7 +157,6 @@ public:
                        zero = NULL;
                }
                Size = 0;
-               tail = list = NULL;
        }
 
        void resetAndDeleteVals() {
@@ -180,7 +177,6 @@ public:
                        zero = NULL;
                }
                Size = 0;
-               tail = list = NULL;
        }
 
        void resetAndFreeVals() {
@@ -201,7 +197,6 @@ public:
                        zero = NULL;
                }
                Size = 0;
-               tail = list = NULL;
        }
 
        /**
@@ -210,17 +205,11 @@ public:
         * @param val The value to store in the table
         */
        _Val put(_Key key, _Val val) {
-               /* Hashtable cannot handle 0 as a key */
+               ASSERT(val);
                if (!key) {
                        _Val oldval;
                        if (!zero) {
                                zero = (struct Hashlistnode<_Key, _Val> *)ourmalloc(sizeof(struct Hashlistnode<_Key, _Val>));
-                               zero->next = list;
-                               if (list != NULL)
-                                       list->prev = zero;
-                               else
-                                       tail = zero;
-                               list = zero;
                                Size++;
                                oldval = (_Val) 0;
                        } else
@@ -244,7 +233,8 @@ public:
                                //key is null, probably done
                                break;
                        }
-                       if (search->hashcode == hashcode)
+                       unsigned int searchhashcode = hash_function(search->key);
+                       if (searchhashcode == hashcode)
                                if (equals(search->key, key)) {
                                        _Val oldval = search->val;
                                        search->val = val;
@@ -255,13 +245,6 @@ public:
 
                search->key = key;
                search->val = val;
-               search->hashcode = hashcode;
-               search->next = list;
-               if (list == NULL)
-                       tail = search;
-               else
-                       list->prev = search;
-               list = search;
                Size++;
                return (_Val) 0;
        }
@@ -290,10 +273,12 @@ public:
                        if (!search->key) {
                                if (!search->val)
                                        break;
-                       } else
-                       if (hashcode == search->hashcode)
-                               if (equals(search->key, key))
-                                       return search->val;
+                       } else {
+                               unsigned int searchhashcode = hash_function(search->key);
+                               if (hashcode == searchhashcode)
+                                       if (equals(search->key, key))
+                                               return search->val;
+                       }
                        index++;
                        index &= capacitymask;
                        if (index == oindex)
@@ -315,15 +300,6 @@ public:
                                return (_Val)0;
                        } else {
                                _Val v = zero->val;
-                               if (zero->next != NULL)
-                                       zero->next->prev = zero->prev;
-                               else
-                                       tail = zero->prev;
-
-                               if (zero->prev != NULL)
-                                       zero->prev->next = zero->next;
-                               else
-                                       list = zero->next;
 
                                ourfree(zero);
                                zero = NULL;
@@ -341,27 +317,18 @@ public:
                        if (!search->key) {
                                if (!search->val)
                                        break;
-                       } else
-                       if (hashcode == search->hashcode)
-                               if (equals(search->key, key)) {
-                                       _Val v = search->val;
-                                       //empty out this bin
-                                       search->val = (_Val) 1;
-                                       search->key = 0;
-
-                                       if (search->next != NULL)
-                                               search->next->prev = search->prev;
-                                       else
-                                               tail = search->prev;
-
-                                       if (search->prev != NULL)
-                                               search->prev->next = search->next;
-                                       else
-                                               list = search->next;
-
-                                       Size--;
-                                       return v;
-                               }
+                       } else {
+                               unsigned int searchhashcode = hash_function(search->key);
+                               if (hashcode == searchhashcode)
+                                       if (equals(search->key, key)) {
+                                               _Val v = search->val;
+                                               //empty out this bin
+                                               search->val = (_Val) 1;
+                                               search->key = 0;
+                                               Size--;
+                                               return v;
+                                       }
+                       }
                        index++;
                } while (true);
                return (_Val)0;
@@ -393,10 +360,12 @@ public:
                        if (!search->key) {
                                if (!search->val)
                                        break;
-                       } else
-                       if (hashcode == search->hashcode)
-                               if (equals(search->key, key))
-                                       return true;
+                       } else {
+                               unsigned int searchhashcode = hash_function(search->key);
+                               if (hashcode == searchhashcode)
+                                       if (equals(search->key, key))
+                                               return true;
+                       }
                        index++;
                } while (true);
                return false;
@@ -419,7 +388,6 @@ public:
                table = newtable;                                                                                       // Update the global hashtable upon resize()
                capacity = newsize;
                capacitymask = newsize - 1;
-               list = tail = NULL;
                threshold = (unsigned int)(newsize * loadfactor);
 
                struct Hashlistnode<_Key, _Val> *bin = &oldtable[0];
@@ -431,7 +399,7 @@ public:
                        if (!key)
                                continue;
 
-                       unsigned int hashcode = bin->hashcode;
+                       unsigned int hashcode = hash_function(bin->key);
                        unsigned int index = hashcode;
                        do {
                                index &= capacitymask;
@@ -439,13 +407,6 @@ public:
                                index++;
                        } while (search->key);
 
-                       if (tail == NULL)
-                               tail = search;
-                       search->next = list;
-                       if (list != NULL)
-                               list->prev = search;
-                       list = search;
-                       search->hashcode = hashcode;
                        search->key = key;
                        search->val = bin->val;
                }
@@ -456,8 +417,6 @@ public:
        unsigned int getCapacity() {return capacity;}
        struct Hashlistnode<_Key, _Val> *table;
        struct Hashlistnode<_Key, _Val> *zero;
-       struct Hashlistnode<_Key, _Val> *list;
-       struct Hashlistnode<_Key, _Val> *tail;
        unsigned int capacity;
        unsigned int Size;
 private: