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#include "linkedlist.h"
24
25/*
26 * Insert a new entry between two known consecutive entries.
27 *
28 * This is only for internal list manipulation where we know
29 * the prev/next entries already!
30 */
31void
32__list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
33{
34 next->prev = new;
35 new->next = next;
36 new->prev = prev;
37 prev->next = new;
38}
39
40/**
41 * list_add - add a new entry
42 * @new: new entry to be added
43 * @head: list head to add it after
44 *
45 * Insert a new entry after the specified head.
46 * This is good for implementing stacks.
47 */
48void
49list_add(struct list_head *new, struct list_head *head)
50{
51 __list_add(new, head, head->next);
52}
53
54/**
55 * list_add_tail - add a new entry
56 * @new: new entry to be added
57 * @head: list head to add it before
58 *
59 * Insert a new entry before the specified head.
60 * This is useful for implementing queues.
61 */
62void
63list_add_tail(struct list_head *new, struct list_head *head)
64{
65 __list_add(new, head->prev, head);
66}
67
68/*
69 * Delete a list entry by making the prev/next entries
70 * point to each other.
71 *
72 * This is only for internal list manipulation where we know
73 * the prev/next entries already!
74 */
75void
76__list_del(struct list_head *prev, struct list_head *next)
77{
78 next->prev = prev;
79 prev->next = next;
80}
81
82/**
83 * list_del - deletes entry from list.
84 * @entry: the element to delete from the list.
85 * Note: list_empty on entry does not return true after this, the entry is
86 * in an undefined state.
87 */
88void
89list_del(struct list_head *entry)
90{
91 __list_del(entry->prev, entry->next);
92}
93
94/**
95 * list_del_init - deletes entry from list and reinitialize it.
96 * @entry: the element to delete from the list.
97 */
98void
99list_del_init(struct list_head *entry)
100{
101 __list_del(entry->prev, entry->next);
102 INIT_LIST_HEAD(entry);
103}
104
105/**
106 * list_move - delete from one list and add as another's head
107 * @list: the entry to move
108 * @head: the head that will precede our entry
109 */
110void
111list_move(struct list_head *list, struct list_head *head)
112{
113 __list_del(list->prev, list->next);
114 list_add(list, head);
115}
116
117/**
118 * list_move_tail - delete from one list and add as another's tail
119 * @list: the entry to move
120 * @head: the head that will follow our entry
121 */
122void
123list_move_tail(struct list_head *list, struct list_head *head)
124{
125 __list_del(list->prev, list->next);
126 list_add_tail(list, head);
127}
128
129/**
130 * list_empty - tests whether a list is empty
131 * @head: the list to test.
132 */
133int
134list_empty(struct list_head *head)
135{
136 return head->next == head;
137}
138
139void
140__list_splice(struct list_head *list, struct list_head *head)
141{
142 struct list_head *first = list->next;
143 struct list_head *last = list->prev;
144 struct list_head *at = head->next;
145
146 first->prev = head;
147 head->next = first;
148
149 last->next = at;
150 at->prev = last;
151}
152
153/**
154 * list_splice - join two lists
155 * @list: the new list to add.
156 * @head: the place to add it in the first list.
157 */
158void
159list_splice(struct list_head *list, struct list_head *head)
160{
161 if (!list_empty(list))
162 __list_splice(list, head);
163}
164
165/**
166 * list_splice_init - join two lists and reinitialise the emptied list.
167 * @list: the new list to add.
168 * @head: the place to add it in the first list.
169 *
170 * The list at @list is reinitialised
171 */
172void
173list_splice_init(struct list_head *list, struct list_head *head)
174{
175 if (!list_empty(list)) {
176 __list_splice(list, head);
177 INIT_LIST_HEAD(list);
178 }
179}
180
181int
182list_size(struct list_head *list)
183{
184 struct list_head *cur;
185 int i = 0;
186
187 list_for_each(cur, list)
188 i++;
189
190 return i;
191}
192
193#define MAX_LIST_LENGTH_BITS 20
194#define ARRAY_SIZE(x) (sizeof(x) / sizeof(*(x)))
195
196/*
197 * Returns a list organized in an intermediate format suited
198 * to chaining of merge() calls: null-terminated, no reserved or
199 * sentinel head node, "prev" links not maintained.
200 */
201static struct list_head *
202merge(void *priv, int (*cmp)(void *priv, struct list_head *a,
203 struct list_head *b), struct list_head *a, struct list_head *b)
204{
205 struct list_head head, *tail = &head;
206
207 while (a && b) {
208 /* if equal, take 'a' -- important for sort stability */
209 if ((*cmp) (priv, a, b) <= 0) {
210 tail->next = a;
211 a = a->next;
212 } else {
213 tail->next = b;
214 b = b->next;
215 }
216 tail = tail->next;
217 }
218 tail->next = a ? : b;
219 return head.next;
220}
221
222/*
223 * Combine final list merge with restoration of standard doubly-linked
224 * list structure. This approach duplicates code from merge(), but
225 * runs faster than the tidier alternatives of either a separate final
226 * prev-link restoration pass, or maintaining the prev links
227 * throughout.
228 */
229static void
230merge_and_restore_back_links(void *priv, int (*cmp)(void *priv,
231 struct list_head *a, struct list_head *b),
232 struct list_head *head, struct list_head *a, struct list_head *b)
233{
234 struct list_head *tail = head;
235 unsigned int count = 0;
236
237 while (a && b) {
238 /* if equal, take 'a' -- important for sort stability */
239 if ((*cmp) (priv, a, b) <= 0) {
240 tail->next = a;
241 a->prev = tail;
242 a = a->next;
243 } else {
244 tail->next = b;
245 b->prev = tail;
246 b = b->next;
247 }
248 tail = tail->next;
249 }
250 tail->next = a ? : b;
251
252 do {
253 /*
254 * In worst cases this loop may run many iterations.
255 * Continue callbacks to the client even though no
256 * element comparison is needed, so the client's cmp()
257 * routine can invoke cond_resched() periodically.
258 */
259 if (!(++count))
260 (*cmp) (priv, tail->next, tail->next);
261
262 if (tail->next) {
263 tail->next->prev = tail;
264 tail = tail->next;
265 }
266 } while (tail->next);
267
268 tail->next = head;
269 head->prev = tail;
270}
271
272/**
273 * list_sort - sort a list
274 * @priv: private data, opaque to list_sort(), passed to @cmp
275 * @head: the list to sort
276 * @cmp: the elements comparison function
277 *
278 * This function implements "merge sort", which has O(nlog(n))
279 * complexity.
280 *
281 * The comparison function @cmp must return a negative value if @a
282 * should sort before @b, and a positive value if @a should sort after
283 * @b. If @a and @b are equivalent, and their original relative
284 * ordering is to be preserved, @cmp must return 0.
285 */
286void
287list_sort(void *priv, struct list_head *head,
288 int (*cmp)(void *priv, struct list_head *a, struct list_head *b))
289{
290 struct list_head *part[MAX_LIST_LENGTH_BITS + 1]; /* sorted partial lists
291 * -- last slot is a
292 * sentinel */
293 int lev; /* index into part[] */
294 int max_lev = 0;
295 struct list_head *list;
296
297 if (list_empty(head))
298 return;
299
300 memset(part, 0, sizeof(part));
301
302 head->prev->next = NULL;
303 list = head->next;
304
305 while (list) {
306 struct list_head *cur = list;
307 list = list->next;
308 cur->next = NULL;
309
310 for (lev = 0; part[lev]; lev++) {
311 cur = merge(priv, cmp, part[lev], cur);
312 part[lev] = NULL;
313 }
314 if (lev > max_lev) {
315 if (lev >= ARRAY_SIZE(part) - 1) {
316 lev--;
317 }
318 max_lev = lev;
319 }
320 part[lev] = cur;
321 }
322
323 for (lev = 0; lev < max_lev; lev++)
324 if (part[lev])
325 list = merge(priv, cmp, part[lev], list);
326
327 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
328}