LCOV - code coverage report
Current view: top level - tommyds/tommyds - tommychain.h (source / functions) Hit Total Coverage
Test: lcov.info Lines: 86 86 100.0 %
Date: 2026-11-12 12:42:49 Functions: 6 6 100.0 %

          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             : 

Generated by: LCOV version 1.0