/
dlist.h
58 lines (51 loc) · 1.52 KB
/
dlist.h
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
#ifndef DLIST_H
#define DLIST_H
/* Doubly linked list.
Inspired by linux/list.h, but we use simplified semantics. Our
memory model is linear, so we only ever move elements from one list
to another. There is no concept of an isolated element, only that
of a singleton list. This removes the need for "add" and "del"
operations.
*/
struct dlist;
struct dlist {
struct dlist *next;
struct dlist *prev;
};
/* The base state is a singleton. */
#define DLIST_INIT(d) {&(d),&(d)}
static inline void dlist_init(struct dlist *entry) {
entry->prev = entry;
entry->next = entry;
}
static inline int dlist_singleton(struct dlist *entry) {
if (entry->next == entry) {
ASSERT(entry->prev == entry);
return 1;
}
else {
return 0;
}
}
/* The only mutating operation besides initialization as singeton is
to move a singleton from one list to another. */
static inline void __dlist_del(struct dlist * prev, struct dlist * next) {
next->prev = prev;
prev->next = next;
}
static inline void __dlist_del_entry(struct dlist *entry) {
__dlist_del(entry->prev, entry->next);
}
static inline void __dlist_add(struct dlist *new,
struct dlist *prev,
struct dlist *next) {
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
static inline void dlist_move(struct dlist *element, struct dlist *head) {
__dlist_del_entry(element);
__dlist_add(element, head, head->next);
}
#endif