jcs.org
jcs ratpoison hax
1/* This file was taken from the Linux kernel and is
2 * Copyright (C) 2003 Linus Torvalds
3 *
4 * Modified by Shawn Betts. Portions created by Shawn Betts are
5 * Copyright (C) 2003, 2004 Shawn Betts
6 *
7 * This file is part of ratpoison.
8 *
9 * ratpoison 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, or (at your option)
12 * any later version.
13 *
14 * ratpoison is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this software; see the file COPYING. If not, write to
21 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
22 * Boston, MA 02111-1307 USA
23 */
24
25#ifndef _RATPOISON_LINKLIST_H
26#define _RATPOISON_LINKLIST_H
27
28#include <string.h>
29
30/*
31 * Simple doubly linked list implementation.
32 *
33 * Some of the internal functions ("__xxx") are useful when
34 * manipulating whole lists rather than single entries, as
35 * sometimes we already know the next/prev entries and we can
36 * generate better code by using them directly rather than
37 * using the generic single-entry routines.
38 */
39
40struct list_head {
41 struct list_head *next, *prev;
42};
43
44#define LIST_HEAD_INIT(name) { &(name), &(name) }
45
46#define LIST_HEAD(name) \
47 struct list_head name = LIST_HEAD_INIT(name)
48
49#define INIT_LIST_HEAD(ptr) do { \
50 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
51} while (0)
52
53/* Prototypes of C functions. */
54int list_size (struct list_head *list);
55void list_splice_init(struct list_head *list,
56 struct list_head *head);
57
58void list_splice_init(struct list_head *list,
59 struct list_head *head);
60
61void list_splice(struct list_head *list, struct list_head *head);
62
63void __list_splice(struct list_head *list,
64 struct list_head *head);
65
66int list_empty(struct list_head *head);
67
68void list_move_tail(struct list_head *list,
69 struct list_head *head);
70
71void list_move(struct list_head *list, struct list_head *head);
72
73void list_del_init(struct list_head *entry);
74void list_del(struct list_head *entry);
75void __list_del(struct list_head * prev, struct list_head * next);
76void list_add_tail(struct list_head *new, struct list_head *head);
77void list_add(struct list_head *new, struct list_head *head);
78void __list_add(struct list_head *new,
79 struct list_head *prev,
80 struct list_head *next);
81
82#ifdef HAVE___BUILTIN_PREFETCH
83#define prefetch(x) __builtin_prefetch(x)
84#else
85#define prefetch(x) ((void)(x))
86#endif
87
88/* Return the last element in the list. */
89#define list_last(last, head, member) \
90{ \
91 last = list_entry((head)->prev, typeof(*last), member); \
92 if (&last->member == (head)) \
93 last = NULL; \
94}
95
96
97/**
98 * container_of - cast a member of a structure out to the containing structure
99 *
100 * @ptr: the pointer to the member.
101 * @type: the type of the container struct this is embedded in.
102 * @member: the name of the member within the struct.
103 *
104 */
105#define container_of(ptr, type, member) ({ \
106 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
107 (type *)( (char *)__mptr - offsetof(type,member) );})
108
109/**
110 * list_entry - get the struct for this entry
111 * @ptr: the &struct list_head pointer.
112 * @type: the type of the struct this is embedded in.
113 * @member: the name of the list_struct within the struct.
114 */
115#define list_entry(ptr, type, member) \
116 container_of(ptr, type, member)
117
118
119/**
120 * __list_for_each - iterate over a list
121 * @pos: the &struct list_head to use as a loop counter.
122 * @head: the head for your list.
123 *
124 * This variant differs from list_for_each() in that it's the
125 * simplest possible list iteration code, no prefetching is done.
126 * Use this for code that knows the list to be very short (empty
127 * or 1 entry) most of the time.
128 */
129#define list_for_each(pos, head) \
130 for (pos = (head)->next; pos != (head); pos = pos->next)
131
132/**
133 * list_for_each_prev - iterate over a list backwards
134 * @pos: the &struct list_head to use as a loop counter.
135 * @head: the head for your list.
136 */
137#define list_for_each_prev(pos, head) \
138 for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
139 pos = pos->prev, prefetch(pos->prev))
140
141/**
142 * list_for_each_safe - iterate over a list safe against removal of list entry
143 * @pos: the &struct list_head to use as a loop counter.
144 * @n: another &struct list_head to use as temporary storage
145 * @head: the head for your list.
146 */
147#define list_for_each_safe(pos, n, head) \
148 for (pos = (head)->next, n = pos->next; pos != (head); \
149 pos = n, n = pos->next)
150
151#define list_for_each_safe_entry(item, pos, n, head, member) \
152 for (pos = (head)->next, \
153 item = list_entry(pos, typeof(*item), member), \
154 n = pos->next \
155 ; \
156 pos != (head) \
157 ; \
158 pos = n, \
159 item = list_entry(pos, typeof(*item), member), \
160 n = pos->next) \
161
162/**
163 * list_for_each_entry - iterate over list of given type
164 * @pos: the type * to use as a loop counter.
165 * @head: the head for your list.
166 * @member: the name of the list_struct within the struct.
167 */
168#define list_for_each_entry(pos, head, member) \
169 for (pos = list_entry((head)->next, typeof(*pos), member), \
170 prefetch(pos->member.next); \
171 &pos->member != (head); \
172 pos = list_entry(pos->member.next, typeof(*pos), member), \
173 prefetch(pos->member.next))
174
175#define list_for_each_entry_safe(pos, n, head, member) \
176 for (pos = list_entry((head)->next, typeof(*pos), member), \
177 n = list_entry(pos->member.next, typeof(*pos), member); \
178 &pos->member != (head); \
179 pos = n, \
180 n = list_entry(pos->member.next, typeof(*pos), member))
181
182#define list_direction_entry(pos, head, member, direction) \
183({ \
184 typeof(pos) ret = NULL; \
185 struct list_head *a_head = head; \
186 if (pos->member.direction == a_head) { \
187 ret = list_entry(a_head->direction, \
188 typeof(*pos), member); \
189 } else { \
190 ret = list_entry(pos->member.direction, \
191 typeof(*pos), member); \
192 } \
193 ret; \
194})
195
196#define list_next_entry(pos, head, member) \
197 list_direction_entry(pos, head, member, next)
198
199#define list_prev_entry(pos, head, member) \
200 list_direction_entry(pos, head, member, prev)
201
202#define list_for_each_entry_prev(pos, head, member) \
203 for (pos = list_entry((head)->prev, typeof(*pos), member), \
204 prefetch(pos->member.prev); \
205 &pos->member != (head); \
206 pos = list_entry(pos->member.prev, typeof(*pos), member), \
207 prefetch(pos->member.prev))
208
209#endif
210
211
212/* Return the first element in the list. */
213#define list_first(first, head, member) \
214{ \
215 first = list_entry((head)->next, typeof(*first), member); \
216 if (&first->member == (head)) \
217 first = NULL; \
218}
219
220void list_sort(void *priv, struct list_head *head,
221 int (*cmp)(void *priv, struct list_head *a,
222 struct list_head *b));