Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /** \file
29 : * Chain of nodes.
30 : * A chain of nodes is an abstraction used to implements complex list operations
31 : * like sorting.
32 : *
33 : * Do not use this directly. Use lists instead.
34 : */
35 :
36 : #ifndef __TOMMYCHAIN_H
37 : #define __TOMMYCHAIN_H
38 :
39 : #include "tommytypes.h"
40 :
41 : /******************************************************************************/
42 : /* chain */
43 :
44 : /**
45 : * Chain of nodes.
46 : * A chain of nodes is a sequence of nodes with the following properties:
47 : * - It contains at least one node. A chains of zero nodes cannot exist.
48 : * - The next field of the tail is of *undefined* value.
49 : * - The prev field of the head is of *undefined* value.
50 : * - All the other inner prev and next fields are correctly set.
51 : */
52 : typedef struct tommy_chain_struct {
53 : tommy_node* head; /**< Pointer to the head of the chain. */
54 : tommy_node* tail; /**< Pointer to the tail of the chain. */
55 : } tommy_chain;
56 :
57 : /**
58 : * Splices a chain in the middle of another chain.
59 : */
60 4481817 : tommy_inline void tommy_chain_splice(tommy_node* first_before, tommy_node* first_after, tommy_node* second_head, tommy_node* second_tail)
61 : {
62 : /* set the prev list */
63 4481817 : first_after->prev = second_tail;
64 4481817 : second_head->prev = first_before;
65 :
66 : /* set the next list */
67 4481817 : first_before->next = second_head;
68 4481817 : second_tail->next = first_after;
69 4481817 : }
70 :
71 : /**
72 : * Concats two chains.
73 : */
74 1280557 : tommy_inline void tommy_chain_concat(tommy_node* first_tail, tommy_node* second_head)
75 : {
76 : /* set the prev list */
77 1280557 : second_head->prev = first_tail;
78 :
79 : /* set the next list */
80 1280557 : first_tail->next = second_head;
81 1280557 : }
82 :
83 : /**
84 : * Merges two chains.
85 : */
86 472482 : tommy_inline void tommy_chain_merge(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
87 : {
88 472482 : tommy_node* first_i = first->head;
89 472482 : tommy_node* second_i = second->head;
90 :
91 : /* merge */
92 : while (1) {
93 9771302 : if (cmp(first_i->data, second_i->data) > 0) {
94 4715244 : tommy_node* next = second_i->next;
95 4715244 : if (first_i == first->head) {
96 233427 : tommy_chain_concat(second_i, first_i);
97 233427 : first->head = second_i;
98 : } else {
99 4481817 : tommy_chain_splice(first_i->prev, first_i, second_i, second_i);
100 : }
101 4715244 : if (second_i == second->tail)
102 236130 : break;
103 4479114 : second_i = next;
104 : } else {
105 5056058 : if (first_i == first->tail) {
106 236352 : tommy_chain_concat(first_i, second_i);
107 236352 : first->tail = second->tail;
108 236352 : break;
109 : }
110 4819706 : first_i = first_i->next;
111 : }
112 9298820 : }
113 472482 : }
114 :
115 : /**
116 : * Merges two chains managing special degenerated cases.
117 : * It's funtionally equivalent at tommy_chain_merge() but faster with already ordered chains.
118 : */
119 1283260 : tommy_inline void tommy_chain_merge_degenerated(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
120 : {
121 : /* identify the condition first <= second */
122 1283260 : if (cmp(first->tail->data, second->head->data) <= 0) {
123 476274 : tommy_chain_concat(first->tail, second->head);
124 476274 : first->tail = second->tail;
125 476274 : return;
126 : }
127 :
128 : /* identify the condition second < first */
129 : /* here we must be strict on comparison to keep the sort stable */
130 806986 : if (cmp(second->tail->data, first->head->data) < 0) {
131 334504 : tommy_chain_concat(second->tail, first->head);
132 334504 : first->head = second->head;
133 334504 : return;
134 : }
135 :
136 472482 : tommy_chain_merge(first, second, cmp);
137 : }
138 :
139 : /**
140 : * Max number of elements as a power of 2.
141 : */
142 : #define TOMMY_CHAIN_BIT_MAX 32
143 :
144 : /**
145 : * Sorts a chain.
146 : * It's a stable merge sort using power of 2 buckets, with O(N*log(N)) complexity,
147 : * similar at the one used in the SGI STL libraries and in the Linux Kernel,
148 : * but faster on degenerated cases like already ordered lists.
149 : *
150 : * SGI STL stl_list.h
151 : * http://www.sgi.com/tech/stl/stl_list.h
152 : *
153 : * Linux Kernel lib/list_sort.c
154 : * http://lxr.linux.no/#linux+v2.6.36/lib/list_sort.c
155 : */
156 1693 : tommy_inline void tommy_chain_mergesort(tommy_chain* chain, tommy_compare_func* cmp)
157 : {
158 : /*
159 : * Bit buckets of chains.
160 : * Each bucket contains 2^i nodes or it's empty.
161 : * The chain at address TOMMY_CHAIN_BIT_MAX is an independet variable operating as "carry".
162 : * We keep it in the same "bit" vector to avoid reports from the valgrind tool sgcheck.
163 : */
164 : tommy_chain bit[TOMMY_CHAIN_BIT_MAX + 1];
165 :
166 : /**
167 : * Value stored inside the bit bucket.
168 : * It's used to know which bucket is empty of full.
169 : */
170 : tommy_count_t counter;
171 1693 : tommy_node* node = chain->head;
172 1693 : tommy_node* tail = chain->tail;
173 : tommy_count_t mask;
174 : tommy_count_t i;
175 :
176 1693 : counter = 0;
177 : while (1) {
178 : tommy_node* next;
179 : tommy_chain* last;
180 :
181 : /* carry bit to add */
182 1284953 : last = &bit[TOMMY_CHAIN_BIT_MAX];
183 1284953 : bit[TOMMY_CHAIN_BIT_MAX].head = node;
184 1284953 : bit[TOMMY_CHAIN_BIT_MAX].tail = node;
185 1284953 : next = node->next;
186 :
187 : /* add the bit, propagating the carry */
188 1284953 : i = 0;
189 1284953 : mask = counter;
190 3847116 : while ((mask & 1) != 0) {
191 1277210 : tommy_chain_merge_degenerated(&bit[i], last, cmp);
192 1277210 : mask >>= 1;
193 1277210 : last = &bit[i];
194 1277210 : ++i;
195 : }
196 :
197 : /* copy the carry in the first empty bit */
198 1284953 : bit[i] = *last;
199 :
200 : /* add the carry in the counter */
201 1284953 : ++counter;
202 :
203 1284953 : if (node == tail)
204 1693 : break;
205 1283260 : node = next;
206 1283260 : }
207 :
208 : /* merge the buckets */
209 1693 : i = tommy_ctz_u32(counter);
210 1693 : mask = counter >> i;
211 12417 : while (mask != 1) {
212 9031 : mask >>= 1;
213 9031 : if (mask & 1)
214 6050 : tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp);
215 : else
216 2981 : bit[i + 1] = bit[i];
217 9031 : ++i;
218 : }
219 :
220 1693 : *chain = bit[i];
221 1693 : }
222 :
223 : #endif
224 :
|