tommyDS_hashlin/tommychain.h

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