summaryrefslogtreecommitdiffstats
path: root/04_exercise/arena
diff options
context:
space:
mode:
Diffstat (limited to '04_exercise/arena')
-rw-r--r--04_exercise/arena/arena_list.c164
-rw-r--r--04_exercise/arena/arena_list.h57
-rw-r--r--04_exercise/arena/arena_test.c30
3 files changed, 0 insertions, 251 deletions
diff --git a/04_exercise/arena/arena_list.c b/04_exercise/arena/arena_list.c
deleted file mode 100644
index 1453297..0000000
--- a/04_exercise/arena/arena_list.c
+++ /dev/null
@@ -1,164 +0,0 @@
-//
-// Created by stefan on 10.06.20.
-//
-#include "arena_list.h"
-#include <pthread.h>
-#include <stdio.h>
-#include <unistd.h>
-
-#include <rwlock.h>
-static const bool DEBUG = false;
-
-bool listContains(List const * const list ,Node const * const needle) {
- for(Node * current = list ->first; current != NULL; current = current->next) {
- if(current == needle) {
- return true;
- }
- }
- return false;
-}
-Node *listPopFront(List *list) {
- Node *front = list->first;
- if (front == NULL) {
- return NULL;
- }
-
- list->first = front->next;
- if (front == list->last) {
- // Only Node in the list
- list->last = NULL;
- return front;
- }
-
- list->first->prev = NULL;
- front->next = NULL;
-
- return front;
-}
-
-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) {
- // List was empty
- list->first = new;
- list->last = new;
- return;
- }
- new->prev = NULL;
- new->next = list->first;
- new->next->prev = new;
- list->first = new;
-}
-
-// void listPushBack(List *list, Node *value) {}
-
-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]};
- }
- arena[size - 1] = (Node){.value = NULL, .prev = &arena[size - 2], .next = NULL};
- return al;
-}
-
-int alPush(AtomicArenaList *al, void *value) {
- if(DEBUG)
- 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) {
- if(DEBUG)
- fprintf(stderr, "Thread %lu: Removing element \n", pthread_self() % 1000);
- rwLockWrite(&al->lock);
- size_t i = 0;
- for (; i < al->size; ++i) {
- if (al->arena[i].value != value) {
- continue;
- }
- }
- Node *node = &al->arena[i];
- // Irgendwie removen wir das Element zwei Mal und ich verstehe nicht warum
- if(i == al->size || listContains(&al->activeList,node)) {
- rwUnlockWrite(&al->lock);
- return -1;
- }
-
- 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;
-
- listPushFront(&al->freeList, node);
- rwUnlockWrite(&al->lock);
- return 0;
-}
-
-void *alFindLastElem(AtomicArenaList *al, SearchFunction f) {
- if(DEBUG)
- fprintf(stderr, "Thread %lu: Finding last element \n", pthread_self() % 1000);
-
- rwLockRead(&al->lock);
-
- 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
deleted file mode 100644
index 304209c..0000000
--- a/04_exercise/arena/arena_list.h
+++ /dev/null
@@ -1,57 +0,0 @@
-//
-// Created by stefan on 10.06.20.
-//
-
-#ifndef BETRIEBSYSTEME_ARENA_LIST_H
-#define BETRIEBSYSTEME_ARENA_LIST_H
-
-#include <stdlib.h>
-#include <stdbool.h>
-#include <stdatomic.h>
-
-typedef struct Node {
- void * value;
- struct Node * next;
- struct Node * prev;
-} Node;
-
-typedef struct List {
- Node * first;
- Node * last;
-} List;
-
-
-// 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;
- atomic_char lock;
-} AtomicArenaList;
-
-typedef bool (*SearchFunction)(void const *);
-//Initializes the node array
-AtomicArenaList alInit(Node * arena, size_t size);
-// Return -1 if the List is full
-int alPush(AtomicArenaList * al, void * value);
-
-// Return -1 if the Node was already deleted
-int alRemoveElem(AtomicArenaList * 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
deleted file mode 100644
index 51a9b0c..0000000
--- a/04_exercise/arena/arena_test.c
+++ /dev/null
@@ -1,30 +0,0 @@
-//
-// Created by stefan on 10.06.20.
-//
-#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];
- 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]);
- }
-
- 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]);
- }
-
-}
generated by cgit v1.2.3-54-g00ecf (git 2.39.0) at 2024-07-01 03:51:11 +0000