1 files changed, 85 insertions, 38 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;
 }