Switched to slotmap

6 files changed, 132 insertions, 24 deletions

diff --git a/04_exercise/CMakeLists.txt b/04_exercise/CMakeLists.txt
index c66bf2c..4e89060 100644
--- a/04_exercise/CMakeLists.txt
+++ b/04_exercise/CMakeLists.txt
@@ -5,7 +5,7 @@ add_executable(quicksort quicksort.c)
 target_link_libraries(quicksort PRIVATE threadpool)
 
 add_library(threadpool threadpool.c)
-target_link_libraries(threadpool PRIVATE array Threads::Threads arena_list)
+target_link_libraries(threadpool PRIVATE Threads::Threads slotmap)
 target_link_libraries(threadpool INTERFACE warnings)
 target_link_libraries(threadpool PUBLIC ppmlib)
 
@@ -27,4 +27,11 @@ target_include_directories(rwlock PUBLIC rwlock)
 target_link_libraries(rwlock INTERFACE warnings)
 
 add_library(ppmlib INTERFACE)
-target_include_directories(ppmlib INTERFACE ppmlib)
\ No newline at end of file
+target_include_directories(ppmlib INTERFACE ppmlib)
+
+add_library(slotmap slotmap/slotmap.c)
+target_include_directories(slotmap PUBLIC slotmap)
+target_link_libraries(slotmap INTERFACE warnings)
+
+add_executable(slotmap_test slotmap/slomap_test.c)
+target_link_libraries(slotmap_test PRIVATE slotmap)
diff --git a/04_exercise/main.c b/04_exercise/main.c
index 69be10b..8c7b8db 100644
--- a/04_exercise/main.c
+++ b/04_exercise/main.c
@@ -14,7 +14,7 @@ static TASK(long, fib, long)
 
     return fibAwait(a) + fibAwait(b);
 }
-
+// Show this runs with only one thread and one place in the work queue
 int main() {
     setvbuf(stdout, NULL, _IONBF, 0);
     if (tpInit(4) != 0)
diff --git a/04_exercise/slotmap/slomap_test.c b/04_exercise/slotmap/slomap_test.c
new file mode 100644
index 0000000..930bfa8
--- /dev/null
+++ b/04_exercise/slotmap/slomap_test.c
@@ -0,0 +1,19 @@
+//
+// Created by stefan on 18.06.20.
+//
+#include <assert.h>
+#include <slotmap.h>
+#include <stdbool.h>
+
+bool find1(void const * ptr) {
+    return * (int const *) ptr == 1;
+}
+int main() {
+    smEntry slab [10];
+    int data [6] = {0, 1, 2,3,4,5};
+    smHeader header = smInit((smEntry *)&slab, 10);
+    smInsert(&header, &data[1]);
+    smEntry * entry = smFindEntry(&header, &find1);
+    assert(*(int *)entry->value == 1);
+    return 0;
+}
diff --git a/04_exercise/slotmap/slotmap.c b/04_exercise/slotmap/slotmap.c
new file mode 100644
index 0000000..57c4ef5
--- /dev/null
+++ b/04_exercise/slotmap/slotmap.c
@@ -0,0 +1,48 @@
+//
+// Created by stefan on 18.06.20.
+//
+
+#include "slotmap.h"
+#include <stdio.h>
+smHeader smInit(smEntry * slab, size_t size) {
+    for (int i = 0; i < size; ++i) {
+        slab[i].value = (intptr_t)NULL;
+    }
+    return (smHeader){.slab = slab, .size=size};
+}
+int smInsert(smHeader const * header, void * value) {
+    for (size_t i = 0; i< header->size; ++i ) {
+        intptr_t ptr = atomic_load(&header->slab[i].value);
+        if((void *)ptr == NULL) {
+            intptr_t expected = (intptr_t) NULL;
+            if(atomic_compare_exchange_strong(&header->slab[i].value, &expected, (intptr_t) value)){
+                return 0;
+            }
+        }
+    }
+    return -1;
+}
+void smDelete(smEntry * node) {
+    intptr_t oldval = atomic_exchange(&node->value, (intptr_t)(NULL));
+    if((void *) oldval == NULL) {
+        fprintf(stderr, "A Node has been double deleted");
+    }
+}
+void smDeleteValue(smHeader const * header, void * value){
+    for (size_t i = 0; i< header->size; ++i ) {
+        intptr_t ptr = atomic_load(&header->slab[i].value);
+        if((void *)ptr == value) {
+            smDelete(&header->slab[i]);
+        }
+    }
+}
+smEntry *smFindEntry(smHeader const * header, SearchFunction func){
+    for (size_t i = 0; i< header->size; ++i ) {
+        void * value = (void *) atomic_load(&header->slab[i].value);
+
+        if(value != NULL && func(value)) {
+            return &header->slab[i];
+        }
+    }
+    return NULL;
+}
diff --git a/04_exercise/slotmap/slotmap.h b/04_exercise/slotmap/slotmap.h
new file mode 100644
index 0000000..1d687fc
--- /dev/null
+++ b/04_exercise/slotmap/slotmap.h
@@ -0,0 +1,36 @@
+//
+// Created by stefan on 18.06.20.
+//
+
+#ifndef BETRIEBSYSTEME_SLOTMAP_H
+#define BETRIEBSYSTEME_SLOTMAP_H
+#include <stdatomic.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+typedef struct smNode {
+    atomic_intptr_t value;
+} smEntry;
+
+typedef struct smHeader {
+    smEntry *slab;
+    size_t size;
+} smHeader;
+
+typedef bool (*SearchFunction)(void const *);
+
+smHeader smInit(smEntry * slab, size_t size);
+int smInsert(smHeader const * header, void * value);
+void smDelete(smEntry * node);
+void smDeleteValue(smHeader const * header, void * value);
+/**
+ * Returns a node whose value is accepted by the SearchFunction
+ * @param header The header of the slotmap to be searched
+ * @param func The search function, that will be applied to each element until one is found
+ * @return the Entry that was found
+ */
+smEntry *smFindEntry(smHeader const * header, SearchFunction func);
+
+
+
+#endif // BETRIEBSYSTEME_SLOTMAP_H
diff --git a/04_exercise/threadpool.c b/04_exercise/threadpool.c
index d4ee8bb..9d73013 100644
--- a/04_exercise/threadpool.c
+++ b/04_exercise/threadpool.c
@@ -1,8 +1,8 @@
 #include "threadpool.h"
-#include "arena_list.h"
 #include "array.h"
 
 #include <pthread.h>
+#include <slotmap.h>
 #include <stdatomic.h>
 #include <stdbool.h>
 #include <stdio.h>
@@ -19,8 +19,8 @@ typedef struct ThreadPool {
     /* TODO: benötigte Attribute hinzufügen */
     size_t size;
     Thread *threads;
-    Node arena[MAX_FUTURES];
-    AtomicArenaList al;
+    smEntry slab [MAX_FUTURES];
+    smHeader header;
 } ThreadPool;
 
 ThreadPool threadPool;
@@ -31,31 +31,32 @@ bool isFutureWaiting(void const *vFuture) {
     //This is racy but we'll CAS it later to make sure it's safe
     return status == FUT_WAITING;
 }
-
-void tryRunningFuture(Future *future) {
+//TODO Document the behaviour of this function
+bool tryRunningFuture(Future *  const future) {
     char expected = FUT_WAITING;
     // This can happen if multiple threads found the same Future
     if (!atomic_compare_exchange_strong(&future->status, &expected, FUT_IN_PROGRESS)) {
-        return;
+        return false;
     }
-
+    smDeleteValue(& threadPool.header, future);
     future->fn(future);
-    expected = FUT_IN_PROGRESS;
-    if (!atomic_compare_exchange_strong(&future->status, &expected, FUT_DONE)) {
+
+    if (atomic_exchange(&future->status, FUT_DONE) != FUT_IN_PROGRESS) {
         perror("The future got marked as done by another thread");
         exit(-1);
     }
+    return true;
 }
 /* TODO: interne Hilfsfunktionen hinzufügen */
 
 bool tryDoingWork() {
-    Future *future = alFindLastElem(&threadPool.al, &isFutureWaiting);
-    if (future == NULL) {
+    smEntry *entry = smFindEntry(&threadPool.header, &isFutureWaiting);
+    if (entry == NULL) {
         return false;
     }
+    Future * fut = (Future *) entry->value;
     // This will just return if some other thread was first
-    tryRunningFuture(future);
-    return true;
+    return tryRunningFuture(fut);
 }
 /** @brief worker function running in the threadpool
  */
@@ -78,10 +79,9 @@ _Noreturn void *poolWorkerFunc(void *v_index) {
 
 int tpInit(size_t size) {
     threadPool.size = size;
-    arrayInit(threadPool.threads);
-    threadPool.al = alInit(threadPool.arena, MAX_FUTURES);
+    threadPool.threads = malloc(sizeof(Thread)*size);
+    threadPool.header = smInit((smEntry *)&threadPool.slab, MAX_FUTURES);
     for (size_t i = 0; i < size; ++i) {
-        arrayPush(threadPool.threads);
         int status;
         threadPool.threads[i].index = i;
         if ((status = pthread_create(&threadPool.threads[i].pthread, NULL,
@@ -107,13 +107,12 @@ void tpRelease(void) {
             exit(status);
         }
     }
-    arrayRelease(threadPool.threads);
+    free(threadPool.threads);
 }
 
 void tpAsync(Future *future) {
-    if (alPush(&threadPool.al, (void *)future) < -1) {
-        perror("Push failed");
-        exit(-1);
+    while (smInsert(&threadPool.header, (void *)future) < 0) {
+        tryDoingWork();
     }
 }
 
@@ -125,5 +124,4 @@ void tpAwait(Future *future) {
     while (atomic_load(&future->status) != FUT_DONE) {
         tryDoingWork();
     }
-    alRemoveElem(&threadPool.al, (void *)future);
 }