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