Switched to slotmap

3 files changed, 103 insertions, 0 deletions

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