1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
//
// Created by stefan on 10.06.20.
//
#include "arena_list.h"
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;
}
if (front->next != NULL) {
list->first->prev = NULL;
front->next = NULL;
}
return front;
}
Node *listPopBack(List* list) { return NULL; }
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) {}
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;
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(ArenaList* al, void *value) {
Node *current = listPopFront(&al->freeList);
// List is empty
if (current == NULL) {
return -1;
}
current->value = value;
listPushFront(&al->activeList, current);
return 0;
}
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]);
}
}
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;
next->prev = prev;
prev->next = next;
listPushFront(&al->freeList, node);
return 0;
}
|
