blob: 6d97ff50c51639b903089d3bb263d2519c547eb3 (
plain)
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
|
/*
* BIRD Library -- Linked Lists
*
* (c) 1998 Martin Mares <mj@ucw.cz>
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
/**
* DOC: Linked lists
*
* The BIRD library provides a set of functions for operating on linked
* lists. The lists are internally represented as standard doubly linked
* lists with synthetic head and tail which makes all the basic operations
* run in constant time and contain no extra end-of-list checks. Each list
* is described by a &list structure, nodes can have any format as long
* as they start with a &node structure. If you want your nodes to belong
* to multiple lists at once, you can embed multiple &node structures in them
* and use the SKIP_BACK() macro to calculate a pointer to the start of the
* structure from a &node pointer, but beware of obscurity.
*
* There also exist safe linked lists (&slist, &snode and all functions
* being prefixed with |s_|) which support asynchronous walking very
* similar to that used in the &fib structure.
*/
#define _BIRD_LISTS_C_
#include "nest/bird.h"
#include "lib/lists.h"
/**
* add_tail - append a node to a list
* @l: linked list
* @n: list node
*
* add_tail() takes a node @n and appends it at the end of the list @l.
*/
LIST_INLINE void
add_tail(list *l, node *n)
{
node *z = l->tail;
n->next = (node *) &l->null;
n->prev = z;
z->next = n;
l->tail = n;
}
/**
* add_head - prepend a node to a list
* @l: linked list
* @n: list node
*
* add_head() takes a node @n and prepends it at the start of the list @l.
*/
LIST_INLINE void
add_head(list *l, node *n)
{
node *z = l->head;
n->next = z;
n->prev = (node *) &l->head;
z->prev = n;
l->head = n;
}
/**
* insert_node - insert a node to a list
* @n: a new list node
* @after: a node of a list
*
* Inserts a node @n to a linked list after an already inserted
* node @after.
*/
LIST_INLINE void
insert_node(node *n, node *after)
{
node *z = after->next;
n->next = z;
n->prev = after;
after->next = n;
z->prev = n;
}
/**
* rem_node - remove a node from a list
* @n: node to be removed
*
* Removes a node @n from the list it's linked in.
*/
LIST_INLINE void
rem_node(node *n)
{
node *z = n->prev;
node *x = n->next;
z->next = x;
x->prev = z;
}
/**
* init_list - create an empty list
* @l: list
*
* init_list() takes a &list structure and initializes its
* fields, so that it represents an empty list.
*/
LIST_INLINE void
init_list(list *l)
{
l->head = (node *) &l->null;
l->null = NULL;
l->tail = (node *) &l->head;
}
/**
* add_tail_list - concatenate two lists
* @to: destination list
* @l: source list
*
* This function appends all elements of the list @l to
* the list @to in constant time.
*/
LIST_INLINE void
add_tail_list(list *to, list *l)
{
node *p = to->tail;
node *q = l->head;
p->next = q;
q->prev = p;
q = l->tail;
q->next = (node *) &to->null;
to->tail = q;
}
|
