1 /*
2 File: list_sort.c
3
4 Copyright (C) 2011 Christophe GRENIER <grenier@cgsecurity.org>
5
6 This software 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; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License along
17 with this program; if not, write the Free Software Foundation, Inc., 51
18 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 */
20
21 #ifdef HAVE_CONFIG_H
22 #include <config.h>
23 #endif
24
25 #ifdef HAVE_STRING_H
26 #include <string.h>
27 #endif
28 #include "types.h"
29 #include "list.h"
30 #include "list_sort.h"
31
32 #define MAX_LIST_LENGTH_BITS 20
33
34 /*
35 * Returns a list organized in an intermediate format suited
36 * to chaining of merge() calls: null-terminated, no reserved or
37 * sentinel head node, "prev" links not maintained.
38 */
merge(int (* cmp)(const struct td_list_head * a,const struct td_list_head * b),struct td_list_head * a,struct td_list_head * b)39 static struct td_list_head *merge(
40 int (*cmp)(const struct td_list_head *a, const struct td_list_head *b),
41 struct td_list_head *a, struct td_list_head *b)
42 {
43 struct td_list_head head, *tail = &head;
44
45 while (a && b) {
46 /* if equal, take 'a' -- important for sort stability */
47 if ((*cmp)(a, b) <= 0) {
48 tail->next = a;
49 a = a->next;
50 } else {
51 tail->next = b;
52 b = b->next;
53 }
54 tail = tail->next;
55 }
56 tail->next = a?a:b;
57 return head.next;
58 }
59
60 /*
61 * Combine final list merge with restoration of standard doubly-linked
62 * list structure. This approach duplicates code from merge(), but
63 * runs faster than the tidier alternatives of either a separate final
64 * prev-link restoration pass, or maintaining the prev links
65 * throughout.
66 */
merge_and_restore_back_links(int (* cmp)(const struct td_list_head * a,const struct td_list_head * b),struct td_list_head * head,struct td_list_head * a,struct td_list_head * b)67 static void merge_and_restore_back_links(
68 int (*cmp)(const struct td_list_head *a, const struct td_list_head *b),
69 struct td_list_head *head,
70 struct td_list_head *a, struct td_list_head *b)
71 {
72 struct td_list_head *tail = head;
73
74 while (a && b) {
75 /* if equal, take 'a' -- important for sort stability */
76 if ((*cmp)(a, b) <= 0) {
77 tail->next = a;
78 a->prev = tail;
79 a = a->next;
80 } else {
81 tail->next = b;
82 b->prev = tail;
83 b = b->next;
84 }
85 tail = tail->next;
86 }
87 tail->next = a ? a : b;
88
89 do {
90 /*
91 * In worst cases this loop may run many iterations.
92 * Continue callbacks to the client even though no
93 * element comparison is needed, so the client's cmp()
94 * routine can invoke cond_resched() periodically.
95 */
96 (*cmp)(tail->next, tail->next);
97
98 tail->next->prev = tail;
99 tail = tail->next;
100 } while (tail->next);
101
102 tail->next = head;
103 head->prev = tail;
104 }
105
106 /**
107 * td_list_sort - sort a list
108 * @head: the list to sort
109 * @cmp: the elements comparison function
110 *
111 * This function implements "merge sort", which has O(nlog(n))
112 * complexity.
113 *
114 * The comparison function @cmp must return a negative value if @a
115 * should sort before @b, and a positive value if @a should sort after
116 * @b. If @a and @b are equivalent, and their original relative
117 * ordering is to be preserved, @cmp must return 0.
118 */
td_list_sort(struct td_list_head * head,int (* cmp)(const struct td_list_head * a,const struct td_list_head * b))119 void td_list_sort(struct td_list_head *head,
120 int (*cmp)(const struct td_list_head *a, const struct td_list_head *b))
121 {
122 struct td_list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
123 -- last slot is a sentinel */
124 int lev; /* index into part[] */
125 int max_lev = 0;
126 struct td_list_head *list;
127
128 if (td_list_empty(head))
129 return;
130
131 memset(part, 0, sizeof(part));
132
133 head->prev->next = NULL;
134 list = head->next;
135
136 while (list) {
137 struct td_list_head *cur = list;
138 list = list->next;
139 cur->next = NULL;
140
141 for (lev = 0; part[lev]; lev++) {
142 cur = merge(cmp, part[lev], cur);
143 part[lev] = NULL;
144 }
145 if (lev > max_lev) {
146 if (lev >= MAX_LIST_LENGTH_BITS)
147 {
148 // list passed to td_list_sort() too long for efficiency
149 lev--;
150 }
151 max_lev = lev;
152 }
153 part[lev] = cur;
154 }
155
156 for (lev = 0; lev < max_lev; lev++)
157 if (part[lev])
158 list = merge(cmp, part[lev], list);
159
160 merge_and_restore_back_links(cmp, head, part[max_lev], list);
161 }
162