From 3c985f718d03a555926fb3886af30f19a9b14a33 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Sat, 7 Apr 2018 03:09:12 -0700 Subject: [PATCH] space hacks --- version2/src/C/CloudComm.cpp | 10 ++-- version2/src/C/Commit.cpp | 28 +++------ version2/src/C/Commit.h | 1 - version2/src/C/IoTString.h | 21 ++++++- version2/src/C/KeyValue.cpp | 6 +- version2/src/C/NewKey.cpp | 6 +- version2/src/C/Table.cpp | 18 +++--- version2/src/C/Test.C | 48 +++++++++------ version2/src/C/hashset.h | 55 +++++++++++------ version2/src/C/hashtable.h | 113 +++++++++++------------------------ 10 files changed, 151 insertions(+), 155 deletions(-) diff --git a/version2/src/C/CloudComm.cpp b/version2/src/C/CloudComm.cpp index 8fe0cee..45b7dac 100644 --- a/version2/src/C/CloudComm.cpp +++ b/version2/src/C/CloudComm.cpp @@ -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); diff --git a/version2/src/C/Commit.cpp b/version2/src/C/Commit.cpp index 7665841..d7c9220 100644 --- a/version2/src/C/Commit.cpp +++ b/version2/src/C/Commit.cpp @@ -6,7 +6,6 @@ Commit::Commit() : parts(new Vector()), partCount(0), - missingParts(NULL), fldisComplete(false), hasLastPart(false), keyValueUpdateSet(new Hashset()), @@ -21,7 +20,6 @@ Commit::Commit() : Commit::Commit(int64_t _sequenceNumber, int64_t _machineId, int64_t _transactionSequenceNumber) : parts(new Vector()), partCount(0), - missingParts(NULL), fldisComplete(true), hasLastPart(false), keyValueUpdateSet(new Hashset()), @@ -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(); 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(); diff --git a/version2/src/C/Commit.h b/version2/src/C/Commit.h index d9f05a9..de6b77b 100644 --- a/version2/src/C/Commit.h +++ b/version2/src/C/Commit.h @@ -7,7 +7,6 @@ class Commit { private: Vector *parts; uint32_t partCount; - Hashset *missingParts; bool fldisComplete; bool hasLastPart; Hashset *keyValueUpdateSet; diff --git a/version2/src/C/IoTString.h b/version2/src/C/IoTString.h index 583a098..99e45bb 100644 --- a/version2/src/C/IoTString.h +++ b/version2/src/C/IoTString.h @@ -22,8 +22,10 @@ inline unsigned int hashCharArray(Array *array) { class IoTString { private: Array *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 *_array) : array(new Array(_array)), - hashvalue(hashCharArray(array)) { + hashvalue(hashCharArray(array)), + refCount(1) { } IoTString(const char *_array) { @@ -40,13 +43,25 @@ public: array = new Array(len); memcpy(array->internalArray(), _array, len); hashvalue = hashCharArray(array); + refCount = 1; } IoTString(IoTString *string) : array(new Array(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; } diff --git a/version2/src/C/KeyValue.cpp b/version2/src/C/KeyValue.cpp index 8aea6f2..7041ba4 100644 --- a/version2/src/C/KeyValue.cpp +++ b/version2/src/C/KeyValue.cpp @@ -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()); } diff --git a/version2/src/C/NewKey.cpp b/version2/src/C/NewKey.cpp index 0b35933..edc5e9e 100644 --- a/version2/src/C/NewKey.cpp +++ b/version2/src/C/NewKey.cpp @@ -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; } diff --git a/version2/src/C/Table.cpp b/version2/src/C/Table.cpp index 255ba3c..5982d2d 100644 --- a/version2/src/C/Table.cpp +++ b/version2/src/C/Table.cpp @@ -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); } diff --git a/version2/src/C/Test.C b/version2/src/C/Test.C index 0f6c96c..9393423 100644 --- a/version2/src/C/Test.C +++ b/version2/src/C/Test.C @@ -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; } diff --git a/version2/src/C/hashset.h b/version2/src/C/hashset.h index 5c81425..7349506 100644 --- a/version2/src/C/hashset.h +++ b/version2/src/C/hashset.h @@ -17,8 +17,9 @@ class Hashset; template, 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 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 diff --git a/version2/src/C/hashtable.h b/version2/src/C/hashtable.h index 6107e33..422eef7 100644 --- a/version2/src/C/hashtable.h +++ b/version2/src/C/hashtable.h @@ -30,9 +30,6 @@ template struct Hashlistnode { _Key key; _Val val; - uint hashcode; - struct Hashlistnode<_Key, _Val> *next; - struct Hashlistnode<_Key, _Val> *prev; }; template @@ -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 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: -- 2.34.1