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 <tb@panthema.net>
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
sort_strings_parallel(unsigned char ** strings,size_t size,size_t memory=0)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
sort_strings_parallel(char ** strings,size_t size,size_t memory=0)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
sort_strings_parallel(const unsigned char ** strings,size_t size,size_t memory=0)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
sort_strings_parallel(const char ** strings,size_t size,size_t memory=0)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
sort_strings_parallel(std::vector<char * > & strings,size_t memory=0)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
sort_strings_parallel(std::vector<unsigned char * > & strings,size_t memory=0)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
sort_strings_parallel(std::vector<const char * > & strings,size_t memory=0)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
sort_strings_parallel(std::vector<const unsigned char * > & strings,size_t memory=0)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
sort_strings_parallel(std::string * strings,size_t size,size_t memory=0)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
sort_strings_parallel(std::vector<std::string> & strings,size_t memory=0)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
sort_strings_parallel_lcp(unsigned char ** strings,size_t size,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(char ** strings,size_t size,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(const unsigned char ** strings,size_t size,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(const char ** strings,size_t size,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(std::vector<char * > & strings,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(std::vector<unsigned char * > & strings,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(std::vector<const char * > & strings,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(std::vector<const unsigned char * > & strings,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(std::string * strings,size_t size,uint32_t * lcp,size_t memory=0)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
sort_strings_parallel_lcp(std::vector<std::string> & strings,uint32_t * lcp,size_t memory=0)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 /******************************************************************************/
313