COMBINATORIAL_BLAS  1.6
tommychain.h
Go to the documentation of this file.
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 
36 #ifndef __TOMMYCHAIN_H
37 #define __TOMMYCHAIN_H
38 
39 #include "tommytypes.h"
40 
41 /******************************************************************************/
42 /* chain */
43 
52 typedef struct tommy_chain_struct {
55 } tommy_chain;
56 
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 
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 
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 
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 
142 #define TOMMY_CHAIN_BIT_MAX 32
143 
157 {
158  /*
159  * Bit buckets of chains.
160  * Each bucket contains 2^i nodes or it's empty.
161  * The chain at address TOMMY_CHAIN_BIT_MAX is an independet variable operating as "carry".
162  * We keep it in the same "bit" vector to avoid reports from the valgrind tool sgcheck.
163  */
165 
170  tommy_count_t counter;
171  tommy_node* node = chain->head;
172  tommy_node* tail = chain->tail;
173  tommy_count_t mask;
174  tommy_count_t i;
175 
176  counter = 0;
177  while (1) {
178  tommy_node* next;
179  tommy_chain* last;
180 
181  /* carry bit to add */
182  last = &bit[TOMMY_CHAIN_BIT_MAX];
183  bit[TOMMY_CHAIN_BIT_MAX].head = node;
184  bit[TOMMY_CHAIN_BIT_MAX].tail = node;
185  next = node->next;
186 
187  /* add the bit, propagating the carry */
188  i = 0;
189  mask = counter;
190  while ((mask & 1) != 0) {
191  tommy_chain_merge_degenerated(&bit[i], last, cmp);
192  mask >>= 1;
193  last = &bit[i];
194  ++i;
195  }
196 
197  /* copy the carry in the first empty bit */
198  bit[i] = *last;
199 
200  /* add the carry in the counter */
201  ++counter;
202 
203  if (node == tail)
204  break;
205  node = next;
206  }
207 
208  /* merge the buckets */
209  i = tommy_ctz_u32(counter);
210  mask = counter >> i;
211  while (mask != 1) {
212  mask >>= 1;
213  if (mask & 1)
214  tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp);
215  else
216  bit[i + 1] = bit[i];
217  ++i;
218  }
219 
220  *chain = bit[i];
221 }
222 
223 #endif
224 
struct tommy_chain_struct tommy_chain
tommy_uint32_t tommy_count_t
Definition: tommytypes.h:67
#define TOMMY_CHAIN_BIT_MAX
Definition: tommychain.h:142
struct tommy_node_struct * next
Definition: tommytypes.h:188
tommy_inline void tommy_chain_splice(tommy_node *first_before, tommy_node *first_after, tommy_node *second_head, tommy_node *second_tail)
Definition: tommychain.h:60
struct tommy_node_struct * prev
Definition: tommytypes.h:194
tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value)
Definition: tommytypes.h:369
int tommy_compare_func(const void *obj_a, const void *obj_b)
Definition: tommytypes.h:240
#define tommy_inline
Definition: tommytypes.h:115
tommy_node * head
Definition: tommychain.h:53
tommy_inline void tommy_chain_merge_degenerated(tommy_chain *first, tommy_chain *second, tommy_compare_func *cmp)
Definition: tommychain.h:119
tommy_inline void tommy_chain_concat(tommy_node *first_tail, tommy_node *second_head)
Definition: tommychain.h:74
tommy_inline void tommy_chain_merge(tommy_chain *first, tommy_chain *second, tommy_compare_func *cmp)
Definition: tommychain.h:86
tommy_inline void tommy_chain_mergesort(tommy_chain *chain, tommy_compare_func *cmp)
Definition: tommychain.h:156
tommy_node * tail
Definition: tommychain.h:54