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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include "list.h"
#include "util.h"
void
list_free(struct link *head, void (*free_item)(void *), int offset)
{
struct link *item;
while (head->next) {
item = link_pop(head->next);
free_item(((void *) item) - offset);
}
}
int
list_empty(struct link *head)
{
ASSERT(head != NULL);
return head->next == NULL;
}
int
list_len(struct link *head)
{
struct link *iter;
int len;
ASSERT(head != NULL);
len = 0;
for (iter = head->next; iter; iter = iter->next)
len += 1;
return len;
}
int
list_ffind(struct link *head, struct link *link)
{
struct link *iter;
ASSERT(head != NULL);
for (iter = head->next; iter && iter != link; iter = iter->next);
return (iter == link);
}
struct link *
list_at(struct link *head, int n)
{
ASSERT(head != NULL);
return link_iter(head->next, n);
}
void
list_push_front(struct link *head, struct link *link)
{
link_append(head, link);
}
void
list_push_back(struct link *cur, struct link *link)
{
struct link *back;
back = link_back(cur);
link_append(back, link);
}
struct link *
list_pop_front(struct link *head)
{
ASSERT(head != NULL);
if (!head->next) return NULL;
return link_pop(head->next);
}
void
link_prepend(struct link *cur, struct link *link)
{
ASSERT(cur != NULL && link != NULL);
link->prev = cur->prev;
link->next = cur;
if (link->prev)
link->prev->next = link;
if (link->next)
link->next->prev = link;
}
void
link_append(struct link *cur, struct link *link)
{
ASSERT(cur != NULL && link != NULL);
link->prev = cur;
link->next = cur->next;
if (link->prev)
link->prev->next = link;
if (link->next)
link->next->prev = link;
}
struct link *
link_back(struct link *link)
{
ASSERT(link != NULL);
for (; link->next; link = link->next);
return link;
}
struct link *
link_pop(struct link *link)
{
ASSERT(link != NULL);
if (link->prev)
link->prev->next = link->next;
if (link->next)
link->next->prev = link->prev;
return link;
}
struct link *
link_iter(struct link *link, int n)
{
int i;
for (i = 0; i < n; i++) {
if (!link) return NULL;
link = link->next;
}
return link;
}
|
