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 implement 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 chain 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 : * \param first_before Node before the splice point.
60 : * \param first_after Node after the splice point.
61 : * \param second_head Head of the chain to splice in.
62 : * \param second_tail Tail of the chain to splice in.
63 : */
64 23430489 : tommy_inline void tommy_chain_splice(tommy_node* first_before, tommy_node* first_after, tommy_node* second_head, tommy_node* second_tail)
65 : {
66 : /* set the prev list */
67 23430489 : first_after->prev = second_tail;
68 23430489 : second_head->prev = first_before;
69 :
70 : /* set the next list */
71 23430489 : first_before->next = second_head;
72 23430489 : second_tail->next = first_after;
73 23430489 : }
74 :
75 : /**
76 : * Concatenates two chains.
77 : * \param first_tail Tail of the first chain.
78 : * \param second_head Head of the second chain.
79 : */
80 4998191 : tommy_inline void tommy_chain_concat(tommy_node* first_tail, tommy_node* second_head)
81 : {
82 : /* set the prev list */
83 4998191 : second_head->prev = first_tail;
84 :
85 : /* set the next list */
86 4998191 : first_tail->next = second_head;
87 4998191 : }
88 :
89 : /**
90 : * Merges two chains.
91 : * \param first First chain (will contain the result).
92 : * \param second Second chain (will be empty after the merge).
93 : * \param cmp Comparison function.
94 : */
95 859955 : tommy_inline void tommy_chain_merge(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
96 : {
97 859955 : tommy_node* first_i = first->head;
98 859955 : tommy_node* second_i = second->head;
99 :
100 : /* merge */
101 : while (1) {
102 49016800 : if (cmp(first_i->data, second_i->data) > 0) {
103 23857535 : tommy_node* next = second_i->next;
104 23857535 : if (first_i == first->head) {
105 427046 : tommy_chain_concat(second_i, first_i);
106 427046 : first->head = second_i;
107 : } else {
108 23430489 : tommy_chain_splice(first_i->prev, first_i, second_i, second_i);
109 : }
110 23857535 : if (second_i == second->tail)
111 428850 : break;
112 23428685 : second_i = next;
113 : } else {
114 25159265 : if (first_i == first->tail) {
115 431105 : tommy_chain_concat(first_i, second_i);
116 431105 : first->tail = second->tail;
117 431105 : break;
118 : }
119 24728160 : first_i = first_i->next;
120 : }
121 : }
122 859955 : }
123 :
124 : /**
125 : * Merges two chains managing special degenerated cases.
126 : * It's functionally equivalent to tommy_chain_merge() but faster with already ordered chains.
127 : * \param first First chain (will contain the result).
128 : * \param second Second chain (will be empty after the merge).
129 : * \param cmp Comparison function.
130 : */
131 4999995 : tommy_inline void tommy_chain_merge_degenerated(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
132 : {
133 : /* identify the condition first <= second */
134 4999995 : if (cmp(first->tail->data, second->head->data) <= 0) {
135 2548313 : tommy_chain_concat(first->tail, second->head);
136 2548313 : first->tail = second->tail;
137 2548313 : return;
138 : }
139 :
140 : /* identify the condition second < first */
141 : /* here we must be strict on comparison to keep the sort stable */
142 2451682 : if (cmp(second->tail->data, first->head->data) < 0) {
143 1591727 : tommy_chain_concat(second->tail, first->head);
144 1591727 : first->head = second->head;
145 1591727 : return;
146 : }
147 :
148 859955 : tommy_chain_merge(first, second, cmp);
149 : }
150 :
151 : /**
152 : * Sorts a chain.
153 : * It's a stable merge sort using power of 2 buckets, with O(N*log(N)) complexity,
154 : * similar to the one used in the SGI STL libraries and in the Linux Kernel,
155 : * but faster on degenerated cases like already ordered lists.
156 : *
157 : * SGI STL stl_list.h
158 : * http://www.sgi.com/tech/stl/stl_list.h
159 : *
160 : * Linux Kernel lib/list_sort.c
161 : * http://lxr.linux.no/#linux+v2.6.36/lib/list_sort.c
162 : *
163 : * \param chain Chain to sort.
164 : * \param cmp Comparison function.
165 : */
166 5 : tommy_inline void tommy_chain_mergesort(tommy_chain* chain, tommy_compare_func* cmp)
167 : {
168 : /*
169 : * Bit buckets of chains.
170 : * Each bucket contains 2^i nodes or it's empty.
171 : * The chain at address TOMMY_BIT_MAX is an independent variable operating as "carry".
172 : * We keep it in the same "bit" vector to avoid reports from the valgrind tool sgcheck.
173 : */
174 : tommy_chain bit[TOMMY_SIZE_BIT + 1];
175 :
176 : /**
177 : * Value stored inside the bit bucket.
178 : * It's used to know which bucket is empty or full.
179 : */
180 : tommy_size_t counter;
181 5 : tommy_node* node = chain->head;
182 5 : tommy_node* tail = chain->tail;
183 : tommy_size_t mask;
184 : tommy_size_t i;
185 :
186 5 : counter = 0;
187 4999995 : while (1) {
188 : tommy_node* next;
189 : tommy_chain* last;
190 :
191 : /* carry bit to add */
192 5000000 : last = &bit[TOMMY_SIZE_BIT];
193 5000000 : bit[TOMMY_SIZE_BIT].head = node;
194 5000000 : bit[TOMMY_SIZE_BIT].tail = node;
195 5000000 : next = node->next;
196 :
197 : /* add the bit, propagating the carry */
198 5000000 : i = 0;
199 5000000 : mask = counter;
200 9999965 : while ((mask & 1) != 0) {
201 4999965 : tommy_chain_merge_degenerated(&bit[i], last, cmp);
202 4999965 : mask >>= 1;
203 4999965 : last = &bit[i];
204 4999965 : ++i;
205 : }
206 :
207 : /* copy the carry in the first empty bit */
208 5000000 : bit[i] = *last;
209 :
210 : /* add the carry in the counter */
211 5000000 : ++counter;
212 :
213 5000000 : if (node == tail)
214 5 : break;
215 4999995 : node = next;
216 : }
217 :
218 : /* merge the buckets */
219 5 : i = tommy_ctz(counter);
220 5 : mask = counter >> i;
221 70 : while (mask != 1) {
222 65 : mask >>= 1;
223 65 : if (mask & 1)
224 30 : tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp);
225 : else
226 35 : bit[i + 1] = bit[i];
227 65 : ++i;
228 : }
229 :
230 5 : *chain = bit[i];
231 5 : }
232 :
233 : #endif
|
