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