1 /*
2 * lists.h Simple doubly linked list implementation,
3 * based on <linux/list.h> and <linux/prefetch.h>.
4 *
5 * Version: 0.1 01-Feb-2011 Fink
6 *
7 * Copyright 2011 Werner Fink, 2005 SUSE LINUX Products GmbH, Germany.
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
13 *
14 * Author: Werner Fink <werner@suse.de>, 2011
15 */
16
17 #ifndef _LISTS_H
18 #define _LISTS_H
19
20 #include <stddef.h>
21 #include <sys/types.h>
22
23 typedef enum _boolean {false, true} boolean;
24 typedef unsigned char uchar;
25 #ifndef __USE_MISC
26 typedef unsigned short ushort;
27 typedef unsigned int uint;
28 #endif
29
30 #ifndef __OPTIMIZE__
31 # warning This will not compile without -O at least
32 #endif
33 #if !defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L)
34 # ifndef inline
35 # define inline __inline__
36 # endif
37 # ifndef restrict
38 # define restrict __restrict__
39 # endif
40 # ifndef volatile
41 # define volatile __volatile__
42 # endif
43 # ifndef asm
44 # define asm __asm__
45 # endif
46 # ifndef extension
47 # define extension __extension__
48 # endif
49 #endif
50 #ifndef attribute
51 # define attribute(attr) __attribute__(attr)
52 #endif
53
54 /*
55 * This is lent from the kernel by e.g. using
56 *
57 * echo '#include <asm-i386/processor.h>\nint main () { prefetch(); return 0; }' | \
58 * gcc -I/usr/src/linux/include -D__KERNEL__ -x c -E -P - | \
59 * sed -rn '/void[[:blank:]]+prefetch[[:blank:]]*\(/,/^}/p'
60 *
61 * on the appropiate architecture (here on i686 for i586).
62 */
prefetch(const void * restrict x)63 extern inline void attribute((used,__gnu_inline__,always_inline,__artificial__)) prefetch(const void *restrict x)
64 {
65 #if defined(__x86_64__)
66 asm volatile ("prefetcht0 %0" :: "m" (*(unsigned long *)x))
67 #elif defined(__ia64__)
68 asm volatile ("lfetch [%0]" :: "r" (x))
69 #elif defined(__powerpc64__)
70 asm volatile ("dcbt 0,%0" :: "r" (x))
71 #elif !defined(__CYGWIN__) && defined(__i386__)
72 asm volatile ("661:\n\t"
73 ".byte 0x8d,0x74,0x26,0x00\n"
74 "\n662:\n"
75 ".section .altinstructions,\"a\"\n"
76 " .align 4\n"
77 " .long 661b\n"
78 " .long 663f\n"
79 " .byte %c0\n"
80 " .byte 662b-661b\n"
81 " .byte 664f-663f\n"
82 ".previous\n"
83 ".section .altinstr_replacement,\"ax\"\n"
84 " 663:\n\t"
85 " prefetchnta (%1)"
86 " \n664:\n"
87 ".previous"
88 :: "i" ((0*32+25)), "r" (x))
89 #else
90 __builtin_prefetch ((x), 0, 1);
91 #endif
92 ;
93 }
94
95 #if defined(DEBUG) && (DEBUG > 0)
96 # define __align attribute((packed))
97 #else
98 # define __align attribute((aligned(sizeof(struct list_struct*))))
99 #endif
100 #define __packed attribute((packed))
101
102 #define alignof(type) ((sizeof(type)+(sizeof(void*)-1)) & ~(sizeof(void*)-1))
103 #define strsize(string) ((strlen(string)+1)*sizeof(char))
104
105 typedef struct list_struct {
106 struct list_struct * next, * prev;
107 } __align list_t;
108
109 /*
110 * Linked list handling
111 * ====================
112 * The structures which will be linked into such lists have to be of the
113 * same type. The structures may have alway a list identifier of the type
114 * `list_t' as very first element. With this the macro list_entry() can
115 * be used to cast the memory address of a list member to the corresponding
116 * allocated structure.
117 */
118
119 /*
120 * Insert new entry as next member.
121 */
122 static inline void _insert(list_t *restrict new, list_t *restrict here) attribute((always_inline,nonnull(1,2)));
_insert(list_t * restrict new,list_t * restrict here)123 static inline void _insert(list_t *restrict new, list_t *restrict here)
124 {
125 list_t * prev = here;
126 list_t * next = here->next;
127
128 next->prev = new;
129 new->next = next;
130 new->prev = prev;
131 prev->next = new;
132 }
133
134 #define insert(new, list) _insert(&((new)->this), (&(list)));
135 #define append(new, list) _insert(&((new)->this), (&(list))->prev);
136
137 /*
138 * Set head
139 */
140 static inline void initial(list_t *restrict head) attribute((always_inline,nonnull(1)));
initial(list_t * restrict head)141 static inline void initial(list_t *restrict head)
142 {
143 head->prev = head->next = head;
144 }
145
146 /*
147 * Remove entries, note that the pointer its self remains.
148 */
149 static inline void delete(list_t *restrict entry) attribute((always_inline,nonnull(1)));
delete(list_t * restrict entry)150 static inline void delete(list_t *restrict entry)
151 {
152 list_t * prev = entry->prev;
153 list_t * next = entry->next;
154
155 next->prev = prev;
156 prev->next = next;
157
158 initial(entry);
159 }
160
161 /*
162 * Replace an entry by a new one.
163 */
164 static inline void replace(list_t *restrict old, list_t *restrict new) attribute((always_inline,nonnull(1,2)));
replace(list_t * restrict old,list_t * restrict new)165 static inline void replace(list_t *restrict old, list_t *restrict new)
166 {
167 new->next = old->next;
168 new->next->prev = new;
169 new->prev = old->prev;
170 new->prev->next = new;
171 }
172
173 static inline void join(list_t *restrict list, list_t *restrict head) attribute((always_inline,nonnull(1,2)));
join(list_t * restrict list,list_t * restrict head)174 static inline void join(list_t *restrict list, list_t *restrict head)
175 {
176 list_t * first = list->next;
177
178 if (first != list) {
179 list_t * last = list->prev;
180 list_t * at = head->next;
181
182 first->prev = head;
183 head->next = first;
184
185 last->next = at;
186 at->prev = last;
187 }
188 }
189
190 static inline boolean list_empty(const list_t *restrict const head) attribute((always_inline,nonnull(1)));
list_empty(const list_t * restrict const head)191 static inline boolean list_empty(const list_t *restrict const head)
192 {
193 return head->next == head;
194 }
195
196 static inline void move_head(list_t *restrict entry, list_t *restrict head) attribute((always_inline,nonnull(1,2)));
move_head(list_t * restrict entry,list_t * restrict head)197 static inline void move_head(list_t *restrict entry, list_t *restrict head)
198 {
199 list_t * prev = entry->prev;
200 list_t * next = entry->next;
201
202 next->prev = prev; /* remove entry from old list */
203 prev->next = next;
204
205 prev = head;
206 next = head->next;
207
208 next->prev = entry; /* and add it at head of new list */
209 entry->next = next;
210 entry->prev = prev;
211 prev->next = entry;
212 }
213
214 static inline void move_tail(list_t *restrict entry, list_t *restrict head) attribute((always_inline,nonnull(1,2)));
move_tail(list_t * restrict entry,list_t * restrict head)215 static inline void move_tail(list_t *restrict entry, list_t *restrict head)
216 {
217 list_t * prev = entry->prev;
218 list_t * next = entry->next;
219
220 next->prev = prev; /* remove entry from old list */
221 prev->next = next;
222
223 prev = head->prev;
224 next = head;
225
226 next->prev = entry; /* and add it at tail of new list */
227 entry->next = next;
228 entry->prev = prev;
229 prev->next = entry;
230 }
231
232 /*
233 * The handle of the list is named `this'
234 */
235 #define list_entry(ptr, type) (__extension__ ({ \
236 const typeof( ((type *)0)->this ) *__mptr = (ptr); \
237 ((type *)( (char *)(__mptr) - offsetof(type,this) )); }))
238 #define list_for_each(pos, head) \
239 for (pos = (head)->next; prefetch(pos->next), pos != (head); pos = pos->next)
240 #define np_list_for_each(pos, head) \
241 for (pos = (head)->next; pos != (head); pos = pos->next)
242 #define list_for_each_safe(pos, safe, head) \
243 for (pos = (head)->next, safe = pos->next; pos != (head); pos = safe, safe = pos->next)
244 #define list_for_each_prev(pos, head) \
245 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); pos = pos->prev)
246 #define np_list_for_each_prev(pos, head) \
247 for (pos = (head)->prev; pos != (head); pos = pos->prev)
248
249 #endif /* _LISTS_H */
250