From fce370a6252cdea0ae220afd0c38160018658c5d Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Thu, 5 Feb 2015 20:08:50 -0800 Subject: [PATCH] add hashmap --- concurrent-hashmap/Makefile | 11 ++ concurrent-hashmap/hashmap.h | 225 +++++++++++++++++++++++++++++++++++ concurrent-hashmap/main.cc | 58 +++++++++ 3 files changed, 294 insertions(+) create mode 100644 concurrent-hashmap/Makefile create mode 100644 concurrent-hashmap/hashmap.h create mode 100644 concurrent-hashmap/main.cc diff --git a/concurrent-hashmap/Makefile b/concurrent-hashmap/Makefile new file mode 100644 index 0000000..4db5bca --- /dev/null +++ b/concurrent-hashmap/Makefile @@ -0,0 +1,11 @@ +include ../benchmarks.mk + +TESTS := table + +all: $(TESTS) + +table: main.cc hashmap.h + $(CXX) -o $@ $^ $(SPEC_OBJ) $(CXXFLAGS) -std=c++0x $(LDFLAGS) + +clean: + rm -f *.o *.d $(TESTS) diff --git a/concurrent-hashmap/hashmap.h b/concurrent-hashmap/hashmap.h new file mode 100644 index 0000000..6ea5e76 --- /dev/null +++ b/concurrent-hashmap/hashmap.h @@ -0,0 +1,225 @@ +#ifndef _HASHMAP_H +#define _HASHMAP_H + +#include +#include +#include "stdio.h" +//#include +#ifdef STANDALONE +#include +#define MODEL_ASSERT assert +#else +#include +#endif +#include +#include + +#define relaxed memory_order_relaxed +#define release memory_order_release +#define acquire memory_order_acquire +#define acq_rel memory_order_acq_rel +#define seq_cst memory_order_seq_cst + +using namespace std; + +/** + For the sake of simplicity, we do not use template but some toy structs to + represent the Key and Value. +*/ +struct Key { + // Probably represent the coordinate (x, y, z) + int x; + int y; + int z; + + int hashCode() { + return x + 31 * y + 31 * 31 * z; + } + + bool equals(Key *other) { + if (!other) + return false; + return x == other->x && y == other->y && z == other->z; + } + + Key(int x, int y, int z) : + x(x), + y(y), + z(z) + { + + } +}; + +struct Value { + // Probably represent the speed vector (vX, vY, vZ) + int vX; + int vY; + int vZ; + + Value(int vX, int vY, int vZ) : + vX(vX), + vY(vY), + vZ(vZ) + { + + } +}; + +class Entry { + public: + Key *key; + atomic value; + int hash; + atomic next; + + Entry(int h, Key *k, Value *v, Entry *n) { + this->hash = h; + this->key = k; + this->value.store(v, relaxed); + this->next.store(n, relaxed); + } +}; + +class Segment { + public: + int count; + mutex segMutex; + + void lock() { + segMutex.lock(); + } + + void unlock() { + segMutex.unlock(); + } + + Segment() { + this->count = 0; + } +}; + +class HashMap { + public: + atomic *table; + + int capacity; + int size; + + static const int CONCURRENCY_LEVEL = 16; + + static const int SEGMENT_MASK = CONCURRENCY_LEVEL - 1; + + Segment segments[CONCURRENCY_LEVEL]; + + static const int DEFAULT_INITIAL_CAPACITY = 16; + + // Not gonna consider resize now... + + HashMap() { + this->size = 0; + this->capacity = DEFAULT_INITIAL_CAPACITY; + this->table = new atomic[capacity]; + for (int i = 0; i < capacity; i++) { + atomic_init(&table[i], NULL); + } + } + + int hashKey(Key *x) { + int h = x->hashCode(); + // Use logical right shift + unsigned int tmp = (unsigned int) h; + return ((h << 7) - h + (tmp >> 9) + (tmp >> 17)); + } + + bool eq(Key *x, Key *y) { + return x == y || x->equals(y); + } + + Value* get(Key *key) { + int hash = hashKey(key); // throws null pointer exception if key null + + // Try first without locking... + atomic *tab = table; + int index = hash & (capacity - 1); + atomic *first = &tab[index]; + Entry *e; + Value *res = NULL; + + // Should be a load acquire + Entry *firstPtr = first->load(acquire); + e = firstPtr; + while (e != NULL) { + if (e->hash == hash && eq(key, e->key)) { + res = e->value.load(seq_cst); + if (res != NULL) + return res; + else + break; + // Loading the next entry + e = e->next.load(acquire); + } + } + + // Recheck under synch if key apparently not there or interference + Segment seg = segments[hash & SEGMENT_MASK]; + seg.lock(); // Critical region begins + // Not considering resize now, so ignore the reload of table... + atomic *newFirst = &tab[index]; + + // Synchronized by locking, no need to be load acquire + Entry *newFirstPtr = newFirst->load(relaxed); + if (e != NULL || firstPtr != newFirstPtr) { + e = newFirstPtr; + while (e != NULL) { + if (e->hash == hash && eq(key, e->key)) { + res = e->value.load(seq_cst); + return res; + } + // Synchronized by locking + e = e->next.load(relaxed); + } + } + seg.unlock(); // Critical region ends + return NULL; + } + + Value* put(Key *key, Value *value) { + // Don't allow NULL value + //ASSERT (value != NULL); + + int hash = hashKey(key); + Segment seg = segments[hash & SEGMENT_MASK]; + atomic *tab; + + seg.lock(); // Critical region begins + tab = table; + int index = hash & (capacity - 1); + + atomic *first = &tab[index]; + Entry *e; + Value *res = NULL; + + // The written of the entry is synchronized by locking + Entry *firstPtr = first->load(relaxed); + e = firstPtr; + while (e != NULL) { + if (e->hash == hash && eq(key, e->key)) { + // FIXME: This could be an acquire?? + res = e->value.load(acquire); + e->value.store(value, seq_cst); + seg.unlock(); // Don't forget to unlock before return + return res; + } + } + + // Add to front of list + Entry *newEntry = new Entry(hash, key, value, firstPtr); + // Publish the newEntry to others + tab[index].store(newEntry, release); + seg.unlock(); // Critical region ends + return NULL; + } +}; + +#endif diff --git a/concurrent-hashmap/main.cc b/concurrent-hashmap/main.cc new file mode 100644 index 0000000..fcb1186 --- /dev/null +++ b/concurrent-hashmap/main.cc @@ -0,0 +1,58 @@ +#include +#include +#include "hashmap.h" + +HashMap *table; + +Key *k1, *k2; +Value *r1, *r2, *r3, *r4, *v1, *v2; + +void printKey(Key *key) { + if (key) + printf("pos = (%d, %d, %d)\n", key->x, key->y, key->z); + else + printf("pos = NULL\n"); +} + +void printValue(Value *value) { + if (value) + printf("velocity = (%d, %d, %d)\n", value->vX, value->vY, value->vZ); + else + printf("velocity = NULL\n"); +} + +void threadA(void *arg) { + k1 = new Key(1, 1, 1); + k2 = new Key(3, 4, 5); + v1 = new Value(10, 10, 10); + r1 = table->put(k1, v1); + //printValue(r1); + r2 = table->get(k2); + printf("Thrd A:\n"); + printValue(r2); +} + +void threadB(void *arg) { + k1 = new Key(1, 1, 1); + k2 = new Key(3, 4, 5); + v2 = new Value(30, 40, 50); + r3 = table->put(k2, v2); + //printValue(r3); + r4 = table->get(k1); + printf("Thrd B:\n"); + printValue(r4); +} + +int user_main(int argc, char *argv[]) { + thrd_t t1, t2; + table = new HashMap; + + thrd_create(&t1, threadA, NULL); + thrd_create(&t2, threadB, NULL); + thrd_join(t1); + thrd_join(t2); + + return 0; +} + + -- 2.34.1