Broken Mess

3 files changed, 123 insertions, 46 deletions

diff --git a/04_exercise/arena/arena_list.c b/04_exercise/arena/arena_list.c
index 822f8f0..4becef6 100644
--- a/04_exercise/arena/arena_list.c
+++ b/04_exercise/arena/arena_list.c
@@ -2,6 +2,12 @@
 // Created by stefan on 10.06.20.
 //
 #include "arena_list.h"
+#include <pthread.h>
+#include <sched.h>
+#include <stdio.h>
+#include <unistd.h>
+
+#include <rwlock.h>
 
 Node *listPopFront(List *list) {
     Node *front = list->first;
@@ -16,14 +22,30 @@ Node *listPopFront(List *list) {
         return front;
     }
 
-    if (front->next != NULL) {
-        list->first->prev = NULL;
-        front->next = NULL;
-    }
+    list->first->prev = NULL;
+    front->next = NULL;
+
     return front;
 }
 
-Node *listPopBack(List* list) { return NULL; }
+Node *listPopBack(List *list) {
+    Node *back = list->last;
+    if (back == NULL) {
+        return NULL;
+    }
+
+    list->last = back->prev;
+    if (back == list->first) {
+        // Only Node in the list
+        list->last = NULL;
+        return back;
+    }
+
+    list->last->next = NULL;
+    back->prev = NULL;
+
+    return back;
+}
 
 void listPushFront(List *list, Node *new) {
     if (list->first == NULL) {
@@ -38,14 +60,14 @@ void listPushFront(List *list, Node *new) {
     list->first = new;
 }
 
-void listPushBack(List* list, Node *value) {}
+// void listPushBack(List *list, Node *value) {}
 
-ArenaList alInit(Node *arena, size_t size) {
-    ArenaList al;
-    al.activeList = (List){.first = NULL, .last = NULL};
-    al.freeList = (List){.first = arena, .last = &arena[size - 1]};
-    al.arena = arena;
-    al.size = size;
+AtomicArenaList alInit(Node *arena, size_t size) {
+    AtomicArenaList al = {.activeList = (List){.first = NULL, .last = NULL},
+                          .freeList = (List){.first = arena, .last = &arena[size - 1]},
+                          .arena = arena,
+                          .size = size};
+    atomic_init(&al.lock, RW_UNLOCKED);
     arena[0] = (Node){.value = NULL, .prev = NULL, .next = &arena[1]};
     for (size_t i = 1; i < size - 1; ++i) {
         arena[i] = (Node){.value = NULL, .prev = &arena[i - 1], .next = &arena[i + 1]};
@@ -54,48 +76,73 @@ ArenaList alInit(Node *arena, size_t size) {
     return al;
 }
 
-int alPush(ArenaList* al, void *value) {
+int alPush(AtomicArenaList *al, void *value) {
+    fprintf(stderr, "Thread %lu: Pushing \n", pthread_self() % 1000);
+    rwLockWrite(&al->lock);
     Node *current = listPopFront(&al->freeList);
     // List is empty
     if (current == NULL) {
+        rwUnlockWrite(&al->lock);
         return -1;
     }
     current->value = value;
     listPushFront(&al->activeList, current);
+    rwUnlockWrite(&al->lock);
     return 0;
 }
 
+int alRemoveElem(AtomicArenaList *al, void *value) {
+    fprintf(stderr, "Thread %lu: Removing element \n", pthread_self() % 1000);
+    rwLockWrite(&al->lock);
+    for (size_t i = 0; i < al->size; ++i) {
+        if (al->arena[i].value != value) {
+            continue;
+        }
+        Node *node = &al->arena[i];
+        if (node == al->activeList.first) {
+            listPopFront(&al->activeList);
+            listPushFront(&al->freeList, node);
+            atomic_char *a = &al->lock;
+            rwUnlockWrite(a);
+            return 0;
+        }
+        if (node == al->activeList.last) {
+            listPopBack(&al->activeList);
+            listPushFront(&al->freeList, node);
+            rwUnlockWrite(&al->lock);
+            return 0;
+        }
+        // The node is somewhere in the middle
+        Node *prev = node->prev;
+        Node *next = node->next;
 
+        next->prev = prev;
+        prev->next = next;
 
-int alRemoveElem(ArenaList*  al, void * value){
-    for(size_t i = 0; i < al->size; ++i) {
-        if(al->arena[i].value == value) {
-            return alRemove(al, &al->arena[i]);
-        }
+        listPushFront(&al->freeList, node);
+        rwUnlockWrite(&al->lock);
+        return 0;
     }
+    rwUnlockWrite(&al->lock);
     return -1;
 }
 
-int alRemove(ArenaList*  al, Node * node) {
-    //TODO Should we check that the node is actually in the active list
-    //Maybe as an assert that gets optimized out
-    if(node == al->activeList.first) {
-        listPopFront(&al->activeList);
-        listPushFront(&al->freeList, node);
-        return 0;
-    }
-    if(node == al->activeList.last) {
-        listPopBack(&al->activeList);
-        listPushFront(&al->freeList, node);
-        return 0;
-    }
-    // The node is somewhere in the middle
-    Node * prev = node ->prev;
-    Node * next = node ->next;
+void *alFindLastElem(AtomicArenaList *al, SearchFunction f) {
+    fprintf(stderr, "Thread %lu: Finding last element \n", pthread_self() % 1000);
 
-    next->prev = prev;
-    prev->next = next;
+    rwLockRead(&al->lock);
 
-    listPushFront(&al->freeList, node);
-    return 0;
+    List const *const actList = &al->activeList;
+    if (actList->last == NULL) {
+        rwUnlockRead(&al->lock);
+        return NULL;
+    }
+    for (Node *current = actList->last; current != NULL; current = current->prev) {
+        if (f(current->value)) {
+            rwUnlockRead(&al->lock);
+            return current;
+        }
+    }
+    rwUnlockRead(&al->lock);
+    return NULL;
 }
diff --git a/04_exercise/arena/arena_list.h b/04_exercise/arena/arena_list.h
index 387f881..304209c 100644
--- a/04_exercise/arena/arena_list.h
+++ b/04_exercise/arena/arena_list.h
@@ -6,6 +6,9 @@
 #define BETRIEBSYSTEME_ARENA_LIST_H
 
 #include <stdlib.h>
+#include <stdbool.h>
+#include <stdatomic.h>
+
 typedef struct Node {
     void * value;
     struct Node * next;
@@ -16,24 +19,39 @@ typedef struct List {
     Node * first;
     Node * last;
 } List;
-// This structure manages an arena / memory slab to be used
+
+
 // Should we have a free list or just a bit set relative to the size of the slab?
+/** This structure manages an arena / memory slab to be used
+ * This structure is thread-safe as it locks internally
+ * It will spin until a request is safe to access the items
+ * This also means this structure shouldn't be read externally
+ * unless the thread doing so managed to aquire the atomic_flag
+ */
 typedef struct ArenaList {
     List freeList;
     List activeList;
     Node * arena;
     size_t size;
-} ArenaList;
+    atomic_char lock;
+} AtomicArenaList;
 
+typedef bool (*SearchFunction)(void const *);
 //Initializes the node array
-ArenaList alInit(Node * arena, size_t size);
+AtomicArenaList alInit(Node * arena, size_t size);
 // Return -1 if the List is full
-int alPush(ArenaList*  al, void * value);
+int alPush(AtomicArenaList *  al, void * value);
 
 // Return -1 if the Node was already deleted
-int alRemove(ArenaList*  al, Node * node);
+int alRemoveElem(AtomicArenaList *  al, void * value);
 
-// Return -1 if the Node was already deleted
-int alRemoveElem(ArenaList*  al, void * value);
+/**
+ * Searches the activeList for an element
+ * for which the search function returns true
+ * The function will be passed the value pointer
+ * of a given Node
+ * @return the Element pointed or NULL if nothing matched
+ */
+void *alFindLastElem(AtomicArenaList *al, SearchFunction f);
 
 #endif // BETRIEBSYSTEME_ARENA_LIST_H
diff --git a/04_exercise/arena/arena_test.c b/04_exercise/arena/arena_test.c
index b0927f1..51a9b0c 100644
--- a/04_exercise/arena/arena_test.c
+++ b/04_exercise/arena/arena_test.c
@@ -3,9 +3,14 @@
 //
 #include "arena_list.h"
 #include <stdio.h>
+#include <assert.h>
+bool isEqualTo3(void const *data) {
+    int *value = (void *)data;
+    return *value == 3;
+}
 int main() {
     Node arena[5];
-    ArenaList al = alInit(arena, 5);
+    AtomicArenaList al = alInit(arena, 5);
     int data[5] = {1, 2, 3, 4, 5};
     for (int i = 0; i < 5; ++i) {
         alPush(&al, &data[4 - i]);
@@ -14,5 +19,12 @@ int main() {
     for (Node *cur = al.activeList.first; cur != NULL; cur = cur->next) {
         printf("Got digit %d \n", *(int *)cur->value);
     }
+    Node const * node = alFindLastElem(&al, &isEqualTo3);
+    int * value = (int *) node->value;
+    printf("The value was actually %d \n", *value);
+    assert(*value == 3);
+    for (int i = 0; i < 5; ++i) {
+        alRemoveElem(&al, &data[4 - i]);
+    }
 
 }