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 __TOMMYCHAIN_H
      13             : #define __TOMMYCHAIN_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     5001488 : 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     5001488 :         first_after->prev = second_tail;
      44     5001488 :         second_head->prev = first_before;
      45             : 
      46             :         /* set the next list */
      47     5001488 :         first_before->next = second_head;
      48     5001488 :         second_tail->next = first_after;
      49     5001488 : }
      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     1441395 : tommy_inline void tommy_chain_concat(tommy_node* first_tail, tommy_node* second_head)
      57             : {
      58             :         /* set the prev list */
      59     1441395 :         second_head->prev = first_tail;
      60             : 
      61             :         /* set the next list */
      62     1441395 :         first_tail->next = second_head;
      63     1441395 : }
      64             : 
      65             : /**
      66             :  * Merges two chains.
      67             :  * \param first First chain (will contain the result).
      68             :  * \param second Second chain (will be empty after the merge).
      69             :  * \param cmp Comparison function.
      70             :  */
      71      527839 : tommy_inline void tommy_chain_merge(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
      72             : {
      73      527839 :         tommy_node* first_i = first->head;
      74      527839 :         tommy_node* second_i = second->head;
      75             : 
      76             :         /* merge */
      77             :         while (1) {
      78    10934182 :                 if (cmp(first_i->data, second_i->data) > 0) {
      79     5267884 :                         tommy_node* next = second_i->next;
      80     5267884 :                         if (first_i == first->head) {
      81      266396 :                                 tommy_chain_concat(second_i, first_i);
      82      266396 :                                 first->head = second_i;
      83             :                         } else {
      84     5001488 :                                 tommy_chain_splice(first_i->prev, first_i, second_i, second_i);
      85             :                         }
      86     5267884 :                         if (second_i == second->tail)
      87      264306 :                                 break;
      88     5003578 :                         second_i = next;
      89             :                 } else {
      90     5666298 :                         if (first_i == first->tail) {
      91      263533 :                                 tommy_chain_concat(first_i, second_i);
      92      263533 :                                 first->tail = second->tail;
      93      263533 :                                 break;
      94             :                         }
      95     5402765 :                         first_i = first_i->next;
      96             :                 }
      97             :         }
      98      527839 : }
      99             : 
     100             : /**
     101             :  * Merges two chains managing special degenerated cases.
     102             :  * It's functionally equivalent to tommy_chain_merge() but faster with already ordered chains.
     103             :  * \param first First chain (will contain the result).
     104             :  * \param second Second chain (will be empty after the merge).
     105             :  * \param cmp Comparison function.
     106             :  */
     107     1439305 : tommy_inline void tommy_chain_merge_degenerated(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
     108             : {
     109             :         /* identify the condition first <= second */
     110     1439305 :         if (cmp(first->tail->data, second->head->data) <= 0) {
     111      533313 :                 tommy_chain_concat(first->tail, second->head);
     112      533313 :                 first->tail = second->tail;
     113      533313 :                 return;
     114             :         }
     115             : 
     116             :         /* identify the condition second < first */
     117             :         /* here we must be strict on comparison to keep the sort stable */
     118      905992 :         if (cmp(second->tail->data, first->head->data) < 0) {
     119      378153 :                 tommy_chain_concat(second->tail, first->head);
     120      378153 :                 first->head = second->head;
     121      378153 :                 return;
     122             :         }
     123             : 
     124      527839 :         tommy_chain_merge(first, second, cmp);
     125             : }
     126             : 
     127             : /**
     128             :  * Sorts a chain.
     129             :  * It's a stable merge sort using power of 2 buckets, with O(N*log(N)) complexity,
     130             :  * similar to the one used in the SGI STL libraries and in the Linux Kernel,
     131             :  * but faster on degenerated cases like already ordered lists.
     132             :  *
     133             :  * SGI STL stl_list.h
     134             :  * http://www.sgi.com/tech/stl/stl_list.h
     135             :  *
     136             :  * Linux Kernel lib/list_sort.c
     137             :  * http://lxr.linux.no/#linux+v2.6.36/lib/list_sort.c
     138             :  *
     139             :  * \param chain Chain to sort.
     140             :  * \param cmp Comparison function.
     141             :  */
     142        2427 : tommy_inline void tommy_chain_mergesort(tommy_chain* chain, tommy_compare_func* cmp)
     143             : {
     144             :         /*
     145             :          * Bit buckets of chains.
     146             :          * Each bucket contains 2^i nodes or it's empty.
     147             :          * The chain at address TOMMY_BIT_MAX is an independent variable operating as "carry".
     148             :          * We keep it in the same "bit" vector to avoid reports from the valgrind tool sgcheck.
     149             :          */
     150             :         tommy_chain bit[TOMMY_SIZE_BIT + 1];
     151             : 
     152             :         /**
     153             :          * Value stored inside the bit bucket.
     154             :          * It's used to know which bucket is empty or full.
     155             :          */
     156             :         tommy_size_t counter;
     157        2427 :         tommy_node* node = chain->head;
     158        2427 :         tommy_node* tail = chain->tail;
     159             :         tommy_size_t mask;
     160             :         tommy_size_t i;
     161             : 
     162        2427 :         counter = 0;
     163     1439305 :         while (1) {
     164             :                 tommy_node* next;
     165             :                 tommy_chain* last;
     166             : 
     167             :                 /* carry bit to add */
     168     1441732 :                 last = &bit[TOMMY_SIZE_BIT];
     169     1441732 :                 bit[TOMMY_SIZE_BIT].head = node;
     170     1441732 :                 bit[TOMMY_SIZE_BIT].tail = node;
     171     1441732 :                 next = node->next;
     172             : 
     173             :                 /* add the bit, propagating the carry */
     174     1441732 :                 i = 0;
     175     1441732 :                 mask = counter;
     176     2873997 :                 while ((mask & 1) != 0) {
     177     1432265 :                         tommy_chain_merge_degenerated(&bit[i], last, cmp);
     178     1432265 :                         mask >>= 1;
     179     1432265 :                         last = &bit[i];
     180     1432265 :                         ++i;
     181             :                 }
     182             : 
     183             :                 /* copy the carry in the first empty bit */
     184     1441732 :                 bit[i] = *last;
     185             : 
     186             :                 /* add the carry in the counter */
     187     1441732 :                 ++counter;
     188             : 
     189     1441732 :                 if (node == tail)
     190        2427 :                         break;
     191     1439305 :                 node = next;
     192             :         }
     193             : 
     194             :         /* merge the buckets */
     195        2427 :         i = tommy_ctz(counter);
     196        2427 :         mask = counter >> i;
     197       13101 :         while (mask != 1) {
     198       10674 :                 mask >>= 1;
     199       10674 :                 if (mask & 1)
     200        7040 :                         tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp);
     201             :                 else
     202        3634 :                         bit[i + 1] = bit[i];
     203       10674 :                 ++i;
     204             :         }
     205             : 
     206        2427 :         *chain = bit[i];
     207        2427 : }
     208             : 
     209             : #endif