path: root/04_exercise/arena/arena_list.c

//
// 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(listContains(&al->activeList,node) || i == al->size) {
        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;
}