COMBINATORIAL_BLAS  1.6
psort_merge.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2009, David Cheng, Viral B. Shah.
3 
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10 
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13 
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21 */
22 
23 #ifndef PSORT_MERGE_H
24 #define PSORT_MERGE_H
25 
26 #ifdef USE_FUNNEL
27 #include "funnel.h"
28 #endif
29 
30 namespace vpsort {
31  template<typename MergeType>
32  class Merge {
33  public:
34  template<typename _ValueType, typename _Compare, typename _Distance>
35  void merge (_ValueType *in, _ValueType *out,
36  _Distance *disps, int nproc, _Compare comp) {
37 
38  MergeType *m = static_cast<MergeType *>(this);
39  m->real_merge (in, out, disps, nproc, comp);
40  }
41 
42  char *description () {
43  MergeType *m = static_cast<MergeType *>(this);
44  return m->real_description ();
45  }
46  };
47 
48  // p-way flat merge
49  class FlatMerge : public Merge<FlatMerge> {
50  public:
51  char *real_description () {
52  string s("Flat merge");
53  return const_cast<char*>(s.c_str());
54  };
55 
56  template<typename _ValueType, typename _Compare, typename _Distance>
57  void real_merge (_ValueType *in, _ValueType *out,
58  _Distance *disps, int nproc, _Compare comp) {
59 
60  _Distance heads[nproc];
61  copy (disps, disps + nproc, heads);
62  for (int i = 0; i < disps[nproc]; ++i) {
63  int min_head = -1;
64  for (int j = 0; j < nproc; ++j) {
65  if (heads[j] < disps[j+1]
66  && (min_head < 0
67  || comp (in[heads[j]], in[heads[min_head]]))) {
68  min_head = j;
69  }
70  }
71  out[i] = in[heads[min_head]++];
72  }
73  }
74  };
75 
76 
77  // A tree merge
78  class TreeMerge : public Merge<TreeMerge> {
79  public:
80  char *real_description () {
81  string s("Tree merge");
82  return const_cast<char*>(s.c_str());
83  };
84 
85  template<typename _ValueType, typename _Compare, typename _Distance>
86  void real_merge (_ValueType *in, _ValueType *out,
87  _Distance *disps, int nproc, _Compare comp) {
88 
89  // round nproc up to next power of two, pad disps
90  int nproc_p;
91  for (nproc_p = 1; nproc_p < nproc; nproc_p *= 2);
92  _Distance disps_p[nproc_p + 1];
93  copy (disps, disps + nproc + 1, disps_p);
94  fill (disps_p + nproc + 1, disps_p + nproc_p + 1, disps[nproc]);
95 
96  int merged = 0;
97  for (int i = 1; i * 2 < nproc_p + 1; i = i * 2) {
98  for (int j = 0; j + 2*i < nproc_p + 1; j += 2*i) {
99  inplace_merge (in + disps_p[j],
100  in + disps_p[j + i],
101  in + disps_p[j + 2*i],
102  comp);
103  }
104  merged = 2*i;
105  }
106  std::merge (in, in + disps_p[merged],
107  in + disps_p[merged], in + disps_p[nproc_p],
108  out, comp);
109  }
110  };
111 
112  // An out of place tree merge
113  class OOPTreeMerge : public Merge<OOPTreeMerge> {
114  public:
115  char *real_description () {
116  string s ("Out-of-place tree merge");
117  return const_cast<char*>(s.c_str());
118  };
119 
120 
121  template<typename _RandomAccessIter, typename _Compare, typename _Distance>
122  void real_merge (_RandomAccessIter in, _RandomAccessIter out,
123  _Distance *disps, int nproc, _Compare comp) {
124 
125  if (nproc == 1) {
126  copy (in, in + disps[nproc], out);
127  return;
128  }
129 
130  _RandomAccessIter bufs[2] = { in, out };
131  _Distance *locs = new _Distance[nproc];
132  for (int i = 0; i < nproc; ++i) {
133  locs[i] = 0;
134  }
135 
136  _Distance next = 1;
137  while (true) {
138  _Distance stride = next * 2;
139  if (stride >= nproc)
140  break;
141 
142  for (_Distance i = 0; i + next < nproc; i += stride) {
143  _Distance end_ind = min (i + stride, (_Distance) nproc);
144 
145  std::merge (bufs[locs[i]] + disps[i],
146  bufs[locs[i]] + disps[i + next],
147  bufs[locs[i + next]] + disps[i + next],
148  bufs[locs[i + next]] + disps[end_ind],
149  bufs[1 - locs[i]] + disps[i],
150  comp);
151  locs[i] = 1 - locs[i];
152  }
153 
154  next = stride;
155  }
156 
157  // now have 4 cases for final merge
158  if (locs[0] == 0) {
159  // 00, 01 => out of place
160  std::merge (in, in + disps[next],
161  bufs[locs[next]] + disps[next],
162  bufs[locs[next]] + disps[nproc],
163  out, comp);
164  } else if (locs[next] == 0) {
165  // 10 => backwards out of place
166  std::merge (std::reverse_iterator<_RandomAccessIter> (in + disps[nproc]),
167  std::reverse_iterator<_RandomAccessIter> (in + disps[next]),
168  std::reverse_iterator<_RandomAccessIter> (out + disps[next]),
169  std::reverse_iterator<_RandomAccessIter> (out),
170  std::reverse_iterator<_RandomAccessIter> (out + disps[nproc]),
171  not2 (comp));
172  } else {
173  // 11 => in-place
174  std::inplace_merge (out, out + disps[next], out + disps[nproc], comp);
175  }
176  delete [] locs;
177  }
178  };
179 
180 
181 #ifdef USE_FUNNEL
182 
183  class FunnelMerge2 : public Merge<FunnelMerge2> {
184  public:
185  char *real_description () {
186  return ("Funnel(2) merge");
187  };
188 
189  template<typename _RandomAccessIter, typename _Compare, typename _Distance>
190  void real_merge (_RandomAccessIter in, _RandomAccessIter out,
191  _Distance *disps, int nproc, _Compare comp) {
192 
193  if (nproc == 1) {
194  copy (in, in + disps[nproc], out);
195  return;
196  }
197 
199 
200  for (int i=0; i<nproc; ++i) {
201  merger.add_stream (in + disps[i], in + disps[i+1]);
202  }
203 
204  merger (out);
205  }
206  };
207 
208  class FunnelMerge4 : public Merge<FunnelMerge4> {
209  public:
210  char *real_description () {
211  std::string s ("Funnel(4) merge");
212  return const_cast<char*>(s.c_str());
213  };
214 
215  template<typename _RandomAccessIter, typename _Compare, typename _Distance>
216  void real_merge (_RandomAccessIter in, _RandomAccessIter out,
217  _Distance *disps, int nproc, _Compare comp) {
218 
219  if (nproc == 1) {
220  copy (in, in + disps[nproc], out);
221  return;
222  }
223 
225 
226  for (int i=0; i<nproc; ++i) {
227  merger.add_stream (in + disps[i], in + disps[i+1]);
228  }
229 
230  merger (out);
231  }
232  };
233 #endif
234 
235 }
236 
237 
238 #endif /*PSORT_MERGE_H */
Definition: psort.h:28
char * real_description()
Definition: psort_merge.h:51
char * description()
Definition: psort_merge.h:42
void merge(_ValueType *in, _ValueType *out, _Distance *disps, int nproc, _Compare comp)
Definition: psort_merge.h:35
char * real_description()
Definition: psort_merge.h:80
void real_merge(_ValueType *in, _ValueType *out, _Distance *disps, int nproc, _Compare comp)
Definition: psort_merge.h:57
void add_stream(RanIt begin, RanIt end)
Definition: funnel.h:206
void merge(T A_, T A_last, T B_, T B_last, T C_, int p, StrictWeakOrdering comp)
void real_merge(_RandomAccessIter in, _RandomAccessIter out, _Distance *disps, int nproc, _Compare comp)
Definition: psort_merge.h:122
void real_merge(_ValueType *in, _ValueType *out, _Distance *disps, int nproc, _Compare comp)
Definition: psort_merge.h:86
char * real_description()
Definition: psort_merge.h:115