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
|
#ifndef DLISTS_H
#define DLISTS_H
/*
* include/linux/dlists.h - macros for double linked lists
*
* Copyright (C) 1997, Thomas Schoebel-Theuer,
* <schoebel@informatik.uni-stuttgart.de>.
*/
/* dlists are cyclic ringlists, so the last element cannot be tested
* for NULL. Use the following construct for traversing cyclic lists:
* ptr = anchor;
* if(ptr) do {
* ...
* ptr = ptr->{something}_{next,prev};
* } while(ptr != anchor);
* The effort here is paid off with much simpler inserts/removes.
* Examples for usage of these macros can be found in fs/ninode.c.
* To access the last element in constant time, simply use
* anchor->{something}_prev.
*/
#define DEF_GENERIC_INSERT(CHANGE,PREFIX,NAME,TYPE,NEXT,PREV) \
static inline void PREFIX##NAME(TYPE ** anchor, TYPE * elem)\
{\
TYPE * oldfirst = *anchor;\
if(!oldfirst) {\
elem->NEXT = elem->PREV = *anchor = elem;\
} else {\
elem->PREV = oldfirst->PREV;\
elem->NEXT = oldfirst;\
oldfirst->PREV->NEXT = elem;\
oldfirst->PREV = elem;\
if(CHANGE)\
*anchor = elem;\
}\
}
/* insert_* is always at the first position */
#define DEF_INSERT(NAME,TYPE,NEXT,PREV) \
DEF_GENERIC_INSERT(1,insert_,NAME,TYPE,NEXT,PREV)
/* append_* is always at the tail */
#define DEF_APPEND(NAME,TYPE,NEXT,PREV) \
DEF_GENERIC_INSERT(0,append_,NAME,TYPE,NEXT,PREV)
/* use this to insert _before_ oldelem somewhere in the middle of the list.
* the list must not be empty, and oldelem must be already a member.*/
#define DEF_INSERT_MIDDLE(NAME,TYPE) \
static inline void insert_middle_##NAME(TYPE ** anchor, TYPE * oldelem, TYPE * elem)\
{\
int status = (oldelem == *anchor);\
insert_##NAME(&oldelem, elem);\
if(status)\
*anchor = oldelem;\
}
/* remove can be done with any element in the list */
#define DEF_REMOVE(NAME,TYPE,NEXT,PREV) \
static inline void remove_##NAME(TYPE ** anchor, TYPE * elem)\
{\
TYPE * next = elem->NEXT;\
if(next == elem) {\
*anchor = NULL;\
} else {\
TYPE * prev = elem->PREV;\
prev->NEXT = next;\
next->PREV = prev;\
elem->NEXT = elem->PREV = NULL;/*leave this during debugging*/\
if(*anchor == elem)\
*anchor = next;\
}\
}
/* According to ideas from David S. Miller, here is a slightly
* more efficient plug-in compatible version using non-cyclic lists,
* but allowing neither backward traversals nor constant time access
* to the last element.
* Note that although the interface is the same, the PPREV pointer must be
* declared doubly indirect and the test for end-of-list is different. */
/* as above, this inserts always at the head */
#define DEF_LIN_INSERT(NAME,TYPE,NEXT,PPREV) \
static inline void insert_##NAME(TYPE ** anchor, TYPE * elem)\
{\
TYPE * first;\
if((elem->NEXT = first = *anchor))\
first->PPREV = &elem->NEXT;\
*anchor = elem;\
elem->PPREV = anchor;\
}
/* as above, this works with any list element */
#define DEF_LIN_REMOVE(NAME,TYPE,NEXT,PPREV) \
static inline void remove_##NAME(TYPE ** anchor, TYPE * elem)\
{\
TYPE * pprev;\
if((pprev = elem->PPREV)) {\
TYPE * next;\
if((next = elem->NEXT))\
next->PPREV = pprev;\
*pprev = next;\
elem->PPREV = elem->NEXT = NULL; /*leave this for debugging*/\
}\
}
#endif
|
