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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#ifndef TYPE
#error "Set TYPE before including this file"
#else
INIT_F ( LLIST(TYPE) ) {
this->length = 0;
NEW(LINK(TYPE), head);
NEW(LINK(TYPE), tail);
this->head = head;
this->tail = tail;
head->after = tail;
tail->before = head;
this->cur = head;
return 0;
}
FREE_F (LINK(TYPE)) {
if (this->before != NULL) this->before->after = NULL;
if (this->after != NULL) this->after->before = NULL;
// TODO how much of value do I really wanna free?
// Should I implement some form of shared pointer?
if (this->value != NULL) FFREE(TYPE, this->value);
return 0;
}
FREE_F( LLIST(TYPE) ) {
LINK(TYPE) *n, *next;
n = this->head;
while ( n != NULL ) {
next = n->after;
FFREE(LINK(TYPE), n);
n = next;
}
this->length = -1;
return 0;
}
INIT_F ( LINK(TYPE) ) {
this->before = NULL;
this->after = NULL;
this->value = NULL;
return 0;
}
INIT_F ( LINK(TYPE), TYPE* val ) {
this->before = NULL;
this->after = NULL;
this->value = val;
return 0;
}
int PUSH(LLIST(TYPE)) ( LLIST(TYPE)* lst, TYPE* val) {
NEW(LINK(TYPE), link, val);
link->after = lst->head->after;
lst->head->after = link;
link->after->before = link;
link->before = lst->head;
++lst->length;
// TODO do I want to change that?
lst->cur = link;
return 0;
}
int DEEP_COPY(LLIST(TYPE)) ( LLIST(TYPE)* dest, LLIST(TYPE)* src ) {
LINK(TYPE)* n = src->head->after;
while (n->after != NULL) {
NEW(TYPE, cpy);
DEEP_COPY(TYPE)(cpy, n->value);
PUSH(LLIST(TYPE)) ( dest, cpy );
n = n->after;
}
return 0;
}
/*
* Adds two linked lists together.
* O(1) time.
* destroys new in the process, but keeps the elements.
* make sure to free(new) after.
*/
int APPEND(LLIST(TYPE)) ( LLIST(TYPE)* dest, LLIST(TYPE)* new ) {
LINK(TYPE)* og_new_head = new->head;
dest->tail->before->after = new->head->after;
new->head->after->before = dest->tail->before;
LINK(TYPE)* old_tail = dest->tail;
dest->tail = new->tail;
dest->length += new->length;
free(old_tail);
free(og_new_head);
return 0;
}
int SIZE(LLIST(TYPE)) ( LLIST(TYPE)* llist ) {
int size = 0;
LINK(TYPE)* l = llist->head->after;
while (l->after != NULL) {
++size;
}
return size;
}
int EMPTY(LLIST(TYPE)) ( LLIST(TYPE)* llist ) {
return llist->head->after == llist->tail;
}
#endif /* TYPE */
|
