Line data Source code
1 : // SPDX-License-Identifier: BSD-2-Clause 2 : // Copyright (C) 2010 Andrea Mazzoleni 3 : 4 : /** \file 5 : * Chain of nodes. 6 : * A chain of nodes is an abstraction used to implement complex list operations 7 : * like sorting. 8 : * 9 : * Do not use this directly. Use lists instead. 10 : */ 11 : 12 : #ifndef TOMMY_CHAIN_H 13 : #define TOMMY_CHAIN_H 14 : 15 : #include "tommytypes.h" 16 : 17 : /******************************************************************************/ 18 : /* chain */ 19 : 20 : /** 21 : * Chain of nodes. 22 : * A chain of nodes is a sequence of nodes with the following properties: 23 : * - It contains at least one node. A chain of zero nodes cannot exist. 24 : * - The next field of the tail is of *undefined* value. 25 : * - The prev field of the head is of *undefined* value. 26 : * - All the other inner prev and next fields are correctly set. 27 : */ 28 : typedef struct tommy_chain_struct { 29 : tommy_node* head; /**< Pointer to the head of the chain. */ 30 : tommy_node* tail; /**< Pointer to the tail of the chain. */ 31 : } tommy_chain; 32 : 33 : /** 34 : * Splices a chain in the middle of another chain. 35 : * \param first_before Node before the splice point. 36 : * \param first_after Node after the splice point. 37 : * \param second_head Head of the chain to splice in. 38 : * \param second_tail Tail of the chain to splice in. 39 : */ 40 14448336 : tommy_inline void tommy_chain_splice(tommy_node* first_before, tommy_node* first_after, tommy_node* second_head, tommy_node* second_tail) 41 : { 42 : /* set the prev list */ 43 14448336 : first_after->prev = second_tail; 44 14448336 : second_head->prev = first_before; 45 : 46 : /* set the next list */ 47 14448336 : first_before->next = second_head; 48 14448336 : second_tail->next = first_after; 49 14448336 : } 50 : 51 : /** 52 : * Concatenates two chains. 53 : * \param first_tail Tail of the first chain. 54 : * \param second_head Head of the second chain. 55 : */ 56 20011142 : tommy_inline void tommy_chain_concat(tommy_node* first_tail, tommy_node* second_head) 57 : { 58 : /* set the prev list */ 59 20011142 : second_head->prev = first_tail; 60 : 61 : /* set the next list */ 62 20011142 : first_tail->next = second_head; 63 20011142 : } 64 : 65 : /** 66 : * Merges two chains. 67 : * \param first First chain (will contain the result). 68 : * \param second Second chain (consumed by the merge; its descriptor is not cleared 69 : * and must not be used as an independent chain afterward). 70 : * \param cmp Comparison function. 71 : */ 72 617844 : tommy_inline void tommy_chain_merge(tommy_chain* tommy_restrict first, tommy_chain* tommy_restrict second, tommy_compare_func* cmp) 73 : { 74 : /* 75 : * comparators must not change the chains, so cache these endpoints across calls. 76 : * also caching first_tail caused register spills with GCC and Clang on x86-64. 77 : */ 78 617844 : tommy_node* first_head = first->head; 79 617844 : tommy_node* second_tail = second->tail; 80 617844 : tommy_node* first_i = first_head; 81 617844 : tommy_node* second_i = second->head; 82 : 83 : /* merge */ 84 : while (1) { 85 32190524 : if (cmp(first_i->data, second_i->data) > 0) { 86 14729402 : tommy_node* next = second_i->next; 87 14729402 : if (first_i == first_head) { 88 281102 : tommy_chain_concat(second_i, first_i); 89 281102 : first_head = second_i; 90 281102 : first->head = first_head; 91 : } else { 92 14448300 : tommy_chain_splice(first_i->prev, first_i, second_i, second_i); 93 : } 94 14729402 : if (second_i == second_tail) 95 292354 : break; 96 14437048 : second_i = next; 97 : } else { 98 17461122 : if (first_i == first->tail) { 99 325490 : tommy_chain_concat(first_i, second_i); 100 325490 : first->tail = second_tail; 101 325490 : break; 102 : } 103 17135632 : first_i = first_i->next; 104 : } 105 : } 106 617844 : } 107 : 108 : /** 109 : * Merges two chains containing one node each. 110 : * \param first First singleton chain (will contain the result). 111 : * \param second Second singleton chain (consumed by the merge; its descriptor is not cleared 112 : * and must not be used as an independent chain afterward). 113 : * \param cmp Comparison function. 114 : */ 115 10014408 : tommy_inline void tommy_chain_merge_singleton(tommy_chain* tommy_restrict first, tommy_chain* tommy_restrict second, tommy_compare_func* cmp) 116 : { 117 10014408 : tommy_node* first_node = first->head; 118 10014408 : tommy_node* second_node = second->head; 119 : 120 : /* keep equal elements in their original order for a stable sort */ 121 10014408 : if (cmp(first_node->data, second_node->data) <= 0) { 122 5770584 : tommy_chain_concat(first_node, second_node); 123 5770584 : first->tail = second_node; 124 : } else { 125 4243824 : tommy_chain_concat(second_node, first_node); 126 4243824 : first->head = second_node; 127 : } 128 10014408 : } 129 : 130 : /** 131 : * Merges two chains managing special degenerate cases. 132 : * It's functionally equivalent to tommy_chain_merge() but faster with already ordered chains. 133 : * \param first First chain (will contain the result). 134 : * \param second Second chain (consumed by the merge; its descriptor is not cleared 135 : * and must not be used as an independent chain afterward). 136 : * \param cmp Comparison function. 137 : */ 138 10007986 : tommy_inline void tommy_chain_merge_degenerated(tommy_chain* tommy_restrict first, tommy_chain* tommy_restrict second, tommy_compare_func* cmp) 139 : { 140 : /* identify the condition first <= second */ 141 10007986 : if (cmp(first->tail->data, second->head->data) <= 0) { 142 5433146 : tommy_chain_concat(first->tail, second->head); 143 5433146 : first->tail = second->tail; 144 5433146 : return; 145 : } 146 : 147 : /* identify the condition second < first */ 148 : /* here we must be strict on comparison to keep the sort stable */ 149 4574840 : if (cmp(second->tail->data, first->head->data) < 0) { 150 3956996 : tommy_chain_concat(second->tail, first->head); 151 3956996 : first->head = second->head; 152 3956996 : return; 153 : } 154 : 155 617844 : tommy_chain_merge(first, second, cmp); 156 : } 157 : 158 : /** 159 : * Sorts a chain. 160 : * It's a stable merge sort using power of 2 buckets, with O(n log n) complexity, 161 : * similar to the one used in the SGI STL libraries and in the Linux Kernel, 162 : * but faster on degenerate cases like already ordered lists. 163 : * 164 : * SGI STL stl_list.h 165 : * http://www.sgi.com/tech/stl/stl_list.h 166 : * 167 : * Linux Kernel lib/list_sort.c 168 : * http://lxr.linux.no/#linux+v2.6.36/lib/list_sort.c 169 : * 170 : * \param chain The chain. 171 : * \param cmp Comparison function. 172 : */ 173 29721 : tommy_inline void tommy_chain_mergesort(tommy_chain* chain, tommy_compare_func* cmp) 174 : { 175 : /* 176 : * Bit buckets of chains. 177 : * Each bucket contains 2^(i+1) nodes or it's empty. 178 : * The bucket containing an unpaired final node has one node less. 179 : * The chain at address TOMMY_BIT_MAX is an independent variable operating as "carry". 180 : * We keep it in the same "bit" vector to avoid reports from the valgrind tool sgcheck. 181 : */ 182 : tommy_chain bit[TOMMY_SIZE_BIT + 1]; 183 : 184 : /* 185 : * Value stored inside the bit bucket. 186 : * It's used to know which bucket is empty or full. 187 : */ 188 29721 : tommy_size_t counter = 0; 189 29721 : tommy_node* node = chain->head; 190 29721 : tommy_node* tail = chain->tail; 191 : 192 10006830 : while (1) { 193 : /* carry bit to add */ 194 10036551 : tommy_chain* last = &bit[TOMMY_SIZE_BIT]; 195 10036551 : bit[TOMMY_SIZE_BIT].head = node; 196 10036551 : bit[TOMMY_SIZE_BIT].tail = node; 197 10036551 : tommy_node* next = node->next; 198 : 199 : /* start with a sorted pair to halve the number of bucket insertions */ 200 10036551 : if (node != tail) { 201 10014408 : node = next; 202 : /* save the next input node before merging can change the links */ 203 10014408 : next = node->next; 204 10014408 : tommy_chain second = { node, node }; 205 10014408 : tommy_chain_merge_singleton(last, &second, cmp); 206 : } 207 : 208 : /* add the bit, propagating the carry */ 209 10036551 : tommy_size_t i = 0; 210 10036551 : tommy_size_t mask = counter; 211 : 212 20021736 : while ((mask & 1) != 0) { 213 9985185 : tommy_chain_merge_degenerated(&bit[i], last, cmp); 214 9985185 : mask >>= 1; 215 9985185 : last = &bit[i]; 216 9985185 : ++i; 217 : } 218 : 219 : /* copy the carry in the first empty bit */ 220 10036551 : bit[i] = *last; 221 : 222 : /* add the carry in the counter */ 223 10036551 : ++counter; 224 : 225 10036551 : if (node == tail) 226 29721 : break; 227 10006830 : node = next; 228 : } 229 : 230 : /* merge the buckets */ 231 29721 : tommy_size_t i = tommy_ctz(counter); 232 29721 : tommy_size_t mask = counter >> i; 233 72237 : while (mask != 1) { 234 42516 : mask >>= 1; 235 42516 : if (mask & 1) 236 21645 : tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp); 237 : else 238 20871 : bit[i + 1] = bit[i]; 239 42516 : ++i; 240 : } 241 : 242 29721 : *chain = bit[i]; 243 29721 : } 244 : 245 : #endif 246 :