1 /* -*- Mode: C ; c-basic-offset: 2 -*- */
2 /*****************************************************************************
4 * list_sort() adapted from linux kernel.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *****************************************************************************/
25 /* list sort from Mark J Roberts (mjr@znex.org) */
28 struct list_head
*head
,
30 int (*cmp
)(void * a
, void * b
))
32 struct list_head
*p
, *q
, *e
, *list
, *tail
, *oldhead
;
33 int insize
, nmerges
, psize
, qsize
, i
;
47 for (i
= 0; i
< insize
; i
++) {
49 q
= q
->next
== oldhead
? NULL
: q
->next
;
55 while (psize
> 0 || (qsize
> 0 && q
)) {
62 } else if (!qsize
|| !q
) {
68 } else if (cmp((void *)p
- member_offset
, (void *)q
- member_offset
) <= 0) {
101 head
->prev
= list
->prev
;
102 list
->prev
->next
= head
;
106 struct test_list_el
{
108 struct list_head test_list_node
;
111 int test_list_sort_comparator(struct test_list_el
* e1
, struct test_list_el
* e2
)
113 return e1
->value
- e2
->value
;
116 void test_list_sort(void)
118 struct list_head test_list
;
119 struct test_list_el
*el
, *next
;
120 struct test_list_el te1
= {.value
= 1};
121 struct test_list_el te2
= {.value
= 2};
122 struct test_list_el te3
= {.value
= 3};
123 struct test_list_el te4
= {.value
= 4};
124 struct test_list_el te5
= {.value
= 5};
125 struct test_list_el te6
= {.value
= 6};
126 struct test_list_el te7
= {.value
= 7};
128 const int expected
[] = {1, 2, 3, 4, 5, 6, 7};
131 INIT_LIST_HEAD(&test_list
);
132 list_add_tail(&te2
.test_list_node
, &test_list
);
133 list_add_tail(&te6
.test_list_node
, &test_list
);
134 list_add_tail(&te4
.test_list_node
, &test_list
);
135 list_add_tail(&te5
.test_list_node
, &test_list
);
136 list_add_tail(&te7
.test_list_node
, &test_list
);
137 list_add_tail(&te1
.test_list_node
, &test_list
);
138 list_add_tail(&te3
.test_list_node
, &test_list
);
140 list_sort(&test_list
, struct test_list_el
, test_list_node
, test_list_sort_comparator
);
143 list_for_each_entry_safe(el
, next
, &test_list
, test_list_node
) {
144 assert(el
->value
== expected
[i
]);