Thrill  0.1
strings_parallel.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/sort/strings_parallel.hpp
3  *
4  * Front-end for parallel string sorting algorithms.
5  *
6  * Part of tlx - http://panthema.net/tlx
7  *
8  * Copyright (C) 2019 Timo Bingmann <[email protected]>
9  *
10  * All rights reserved. Published under the Boost Software License, Version 1.0
11  ******************************************************************************/
12 
13 #ifndef TLX_SORT_STRINGS_PARALLEL_HEADER
14 #define TLX_SORT_STRINGS_PARALLEL_HEADER
15 
16 #include <tlx/sort/strings/parallel_sample_sort.hpp>
17 
18 #include <cstdint>
19 #include <string>
20 #include <vector>
21 
22 namespace tlx {
23 
24 //! \addtogroup tlx_sort
25 //! \{
26 //! \name String Sorting Algorithms
27 //! \{
28 
29 /******************************************************************************/
30 
31 /*!
32  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
33  *
34  * The memory limit is currently not used.
35  */
36 static inline
37 void sort_strings_parallel(unsigned char** strings, size_t size,
38  size_t memory = 0) {
39  sort_strings_detail::parallel_sample_sort(
40  sort_strings_detail::StringPtr<sort_strings_detail::UCharStringSet>(
41  sort_strings_detail::UCharStringSet(strings, strings + size)),
42  /* depth */ 0, memory);
43 }
44 
45 /*!
46  * Sort a set of strings in parallel represented by C-style char* in place.
47  *
48  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
49  * The memory limit is currently not used.
50  */
51 static inline
52 void sort_strings_parallel(char** strings, size_t size, size_t memory = 0) {
53  return sort_strings_parallel(
54  reinterpret_cast<unsigned char**>(strings), size, memory);
55 }
56 
57 /*!
58  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
59  *
60  * The memory limit is currently not used.
61  */
62 static inline
63 void sort_strings_parallel(const unsigned char** strings, size_t size,
64  size_t memory = 0) {
65  sort_strings_detail::parallel_sample_sort(
66  sort_strings_detail::StringPtr<sort_strings_detail::CUCharStringSet>(
67  sort_strings_detail::CUCharStringSet(strings, strings + size)),
68  /* depth */ 0, memory);
69 }
70 
71 /*!
72  * Sort a set of strings in parallel represented by C-style char* in place.
73  *
74  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
75  * The memory limit is currently not used.
76  */
77 static inline
78 void sort_strings_parallel(const char** strings, size_t size,
79  size_t memory = 0) {
80  return sort_strings_parallel(
81  reinterpret_cast<const unsigned char**>(strings), size, memory);
82 }
83 
84 /******************************************************************************/
85 
86 /*!
87  * Sort a set of strings in parallel represented by C-style char* in place.
88  *
89  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
90  * The memory limit is currently not used.
91  */
92 static inline
93 void sort_strings_parallel(std::vector<char*>& strings, size_t memory = 0) {
94  return sort_strings_parallel(strings.data(), strings.size(), memory);
95 }
96 
97 /*!
98  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
99  *
100  * The memory limit is currently not used.
101  */
102 static inline
103 void sort_strings_parallel(std::vector<unsigned char*>& strings,
104  size_t memory = 0) {
105  return sort_strings_parallel(strings.data(), strings.size(), memory);
106 }
107 
108 /*!
109  * Sort a set of strings in parallel represented by C-style char* in place.
110  *
111  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
112  * The memory limit is currently not used.
113  */
114 static inline
115 void sort_strings_parallel(std::vector<const char*>& strings,
116  size_t memory = 0) {
117  return sort_strings_parallel(strings.data(), strings.size(), memory);
118 }
119 
120 /*!
121  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
122  *
123  * The memory limit is currently not used.
124  */
125 static inline
126 void sort_strings_parallel(std::vector<const unsigned char*>& strings,
127  size_t memory = 0) {
128  return sort_strings_parallel(strings.data(), strings.size(), memory);
129 }
130 
131 /******************************************************************************/
132 
133 /*!
134  * Sort a set of std::strings in place in parallel.
135  *
136  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
137  * The memory limit is currently not used.
138  */
139 static inline
140 void sort_strings_parallel(std::string* strings, size_t size,
141  size_t memory = 0) {
142  sort_strings_detail::parallel_sample_sort(
143  sort_strings_detail::StringPtr<sort_strings_detail::StdStringSet>(
144  sort_strings_detail::StdStringSet(strings, strings + size)),
145  /* depth */ 0, memory);
146 }
147 
148 /*!
149  * Sort a vector of std::strings in place in parallel.
150  *
151  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
152  * The memory limit is currently not used.
153  */
154 static inline
155 void sort_strings_parallel(std::vector<std::string>& strings,
156  size_t memory = 0) {
157  return sort_strings_parallel(strings.data(), strings.size(), memory);
158 }
159 
160 /******************************************************************************/
161 /******************************************************************************/
162 /******************************************************************************/
163 
164 /*!
165  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
166  *
167  * The memory limit is currently not used.
168  */
169 static inline
170 void sort_strings_parallel_lcp(unsigned char** strings, size_t size,
171  uint32_t* lcp, size_t memory = 0) {
172  sort_strings_detail::parallel_sample_sort(
173  sort_strings_detail::StringLcpPtr<
174  sort_strings_detail::UCharStringSet, uint32_t>(
175  sort_strings_detail::UCharStringSet(strings, strings + size), lcp),
176  /* depth */ 0, memory);
177 }
178 
179 /*!
180  * Sort a set of strings in parallel represented by C-style char* in place.
181  *
182  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
183  * The memory limit is currently not used.
184  */
185 static inline
186 void sort_strings_parallel_lcp(char** strings, size_t size, uint32_t* lcp,
187  size_t memory = 0) {
188  return sort_strings_parallel_lcp(
189  reinterpret_cast<unsigned char**>(strings), size, lcp, memory);
190 }
191 
192 /*!
193  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
194  *
195  * The memory limit is currently not used.
196  */
197 static inline
198 void sort_strings_parallel_lcp(const unsigned char** strings, size_t size,
199  uint32_t* lcp, size_t memory = 0) {
200  sort_strings_detail::parallel_sample_sort(
201  sort_strings_detail::StringLcpPtr<
202  sort_strings_detail::CUCharStringSet, uint32_t>(
203  sort_strings_detail::CUCharStringSet(strings, strings + size), lcp),
204  /* depth */ 0, memory);
205 }
206 
207 /*!
208  * Sort a set of strings in parallel represented by C-style char* in place.
209  *
210  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
211  * The memory limit is currently not used.
212  */
213 static inline
214 void sort_strings_parallel_lcp(const char** strings, size_t size,
215  uint32_t* lcp, size_t memory = 0) {
216  return sort_strings_parallel_lcp(
217  reinterpret_cast<const unsigned char**>(strings), size, lcp, memory);
218 }
219 
220 /******************************************************************************/
221 
222 /*!
223  * Sort a set of strings in parallel represented by C-style char* in place.
224  *
225  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
226  * The memory limit is currently not used.
227  */
228 static inline
229 void sort_strings_parallel_lcp(std::vector<char*>& strings, uint32_t* lcp,
230  size_t memory = 0) {
231  return sort_strings_parallel_lcp(
232  strings.data(), strings.size(), lcp, memory);
233 }
234 
235 /*!
236  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
237  *
238  * The memory limit is currently not used.
239  */
240 static inline
241 void sort_strings_parallel_lcp(std::vector<unsigned char*>& strings,
242  uint32_t* lcp, size_t memory = 0) {
243  return sort_strings_parallel_lcp(
244  strings.data(), strings.size(), lcp, memory);
245 }
246 
247 /*!
248  * Sort a set of strings in parallel represented by C-style char* in place.
249  *
250  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
251  * The memory limit is currently not used.
252  */
253 static inline
254 void sort_strings_parallel_lcp(std::vector<const char*>& strings, uint32_t* lcp,
255  size_t memory = 0) {
256  return sort_strings_parallel_lcp(
257  strings.data(), strings.size(), lcp, memory);
258 }
259 
260 /*!
261  * Sort a set of strings in parallel represented by C-style uint8_t* in place.
262  *
263  * The memory limit is currently not used.
264  */
265 static inline
266 void sort_strings_parallel_lcp(std::vector<const unsigned char*>& strings,
267  uint32_t* lcp, size_t memory = 0) {
268  return sort_strings_parallel_lcp(
269  strings.data(), strings.size(), lcp, memory);
270 }
271 
272 /******************************************************************************/
273 
274 /*!
275  * Sort a set of std::strings in place in parallel.
276  *
277  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
278  * The memory limit is currently not used.
279  */
280 static inline
281 void sort_strings_parallel_lcp(std::string* strings, size_t size,
282  uint32_t* lcp, size_t memory = 0) {
283  sort_strings_detail::parallel_sample_sort(
284  sort_strings_detail::StringLcpPtr<
285  sort_strings_detail::StdStringSet, uint32_t>(
286  sort_strings_detail::StdStringSet(strings, strings + size), lcp),
287  /* depth */ 0, memory);
288 }
289 
290 /*!
291  * Sort a vector of std::strings in place in parallel.
292  *
293  * The strings are sorted as _unsigned_ 8-bit characters, not signed characters!
294  * The memory limit is currently not used.
295  */
296 static inline
297 void sort_strings_parallel_lcp(std::vector<std::string>& strings,
298  uint32_t* lcp, size_t memory = 0) {
299  return sort_strings_parallel_lcp(
300  strings.data(), strings.size(), lcp, memory);
301 }
302 
303 /******************************************************************************/
304 
305 //! \}
306 //! \}
307 
308 } // namespace tlx
309 
310 #endif // !TLX_SORT_STRINGS_PARALLEL_HEADER
311 
312 /******************************************************************************/
tlx::sort_strings_detail::parallel_sample_sort
void parallel_sample_sort(const StringPtr &strptr, size_t depth, size_t memory)
Definition: parallel_sample_sort.hpp:1510
tlx::sort_strings_detail::GenericCharStringSet
Class implementing StringSet concept for char* and unsigned char* strings.
Definition: string_set.hpp:297
tlx::sort_strings_detail::StdStringSet
Class implementing StringSet concept for arrays of std::string objects.
Definition: string_set.hpp:394
tlx::sort_strings_parallel
static void sort_strings_parallel(unsigned char **strings, size_t size, size_t memory=0)
Sort a set of strings in parallel represented by C-style uint8_t* in place.
Definition: strings_parallel.hpp:37
thrill::mem::string
std::basic_string< char, std::char_traits< char >, Allocator< char > > string
string with Manager tracking
Definition: allocator.hpp:220
tlx::sort_strings_detail::StringLcpPtr
Objectified string and LCP array pointer arrays.
Definition: string_ptr.hpp:97
tlx::sort_strings_parallel_lcp
static void sort_strings_parallel_lcp(unsigned char **strings, size_t size, uint32_t *lcp, size_t memory=0)
Sort a set of strings in parallel represented by C-style uint8_t* in place.
Definition: strings_parallel.hpp:170
tlx::sort_strings_detail::StringPtr
Objectified string array pointer array.
Definition: string_ptr.hpp:47
parallel_sample_sort.hpp