Mstdlib-1.24.0
m_sort.h
1/* The MIT License (MIT)
2 *
3 * Copyright (c) 2015 Monetra Technologies, LLC.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights
8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 * copies of the Software, and to permit persons to whom the Software is
10 * furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 * THE SOFTWARE.
22 */
23
24#ifndef __M_SORT_H__
25#define __M_SORT_H__
26
27/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
28
29#include <mstdlib/base/m_defs.h>
30#include <mstdlib/base/m_types.h>
31
32/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
33
34__BEGIN_DECLS
35
36/*! \addtogroup m_sort Search and Sort
37 * \ingroup mstdlib_base
38 *
39 * Searching and sorting operations.
40 *
41 * @{
42 */
43
44/*! Comparision function prototype.
45 *
46 * Used the same as qsort or bsearch!
47 *
48 * The internal array holding the data elements is a void pointer which means
49 * the compar function has a reference to the index of the array (void **). That
50 * means you may need to dereference more time than you think if base is an array
51 * of pointer. E.g:
52 *
53 * Array: my_type_t **data;
54 * Deref: my_type_t *t1 = *((my_type_t * const *)arg1);
55 *
56 * Array: M_uint64 **data;
57 * Deref: M_uint64 i1 = *(*((M_uint64 * const *)arg1));
58 *
59 * If base is an arrary of fixed data. E.g:
60 *
61 * my_type_t *data;
62 * data = M_malloc_zero(sizeof(*data) * cnt));
63 * data[0].v1 = "a";
64 * data[0].v2 = "b";
65 * ...
66 * Deref: const my_type_t *t1 = arg1;
67 *
68 *
69 * M_uint64 *data = { 1, 2, 3 };
70 * Deref: M_uint64 i1 = *((M_uint64 const *)arg1);
71 *
72 * \param[in] arg1 The first arg to compare.
73 * \param[in] arg2 The second arg to compare.
74 * \param[in] thunk Additional data to use for comparison.
75 *
76 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
77 */
78typedef int (*M_sort_compar_t)(const void *arg1, const void *arg2, void *thunk);
79
80/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
81 * Binary Search */
82
83/*! Find the index the key should be inserted at in a sorted array.
84 *
85 * \param[in] base The array of elements to search.
86 * \param[in] nmemb The number of elements in the array.
87 * \param[in] esize The size of each element in the array.
88 * \param[in] key The element to be inserted.
89 * \param[in] stable Should the insert find and use the last matching element.
90 * This can cause performance to degrade to worst case O(n/2).
91 * \param[in] compar The comparision function.
92 * \param[in] thunk Additional data to pass to the comparison function.
93 *
94 * \return The index the item should be inserted at. If the the key is
95 * <= the first element, will always return 0. If the key is >=
96 * the last element, will always return nmemb.
97 */
98M_API size_t M_sort_binary_insert_idx(const void *base, size_t nmemb, size_t esize, const void *key, M_bool stable, M_sort_compar_t compar, void *thunk);
99
100/*! Find and element in a sorted array.
101 *
102 * \param[in] base The array of elements to search.
103 * \param[in] nmemb The number of elements in the array.
104 * \param[in] esize The size of each element in the array.
105 * \param[in] key The element to be inserted.
106 * \param[in] stable Should the insert find and use the last matching element.
107 * This can cause performance to degrade to worst case O(n/2).
108 * \param[in] compar The comparision function.
109 * \param[in] thunk Additional data to pass to the comparison function.
110 * \param[out] idx The index of the items location.
111 *
112 * \return True if the item was found. Otherwise false.
113 */
114M_API M_bool M_sort_binary_search(const void *base, size_t nmemb, size_t esize, const void *key, M_bool stable, M_sort_compar_t compar, void *thunk, size_t *idx);
115
116
117/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
118 * Sorting */
119
120/*! Sort elements in array in ascending order according to comparison function.
121 *
122 * This is an unstable sort.
123 *
124 * \param[in,out] base The array of elements to sort.
125 * \param[in] nmemb The number of elements in the array.
126 * \param[in] esize The size of each element in the array.
127 * \param[in] compar The comparison function.
128 * \param[in] thunk Additional data to pass to the comparison function.
129 */
130M_API void M_sort_qsort(void *base, size_t nmemb, size_t esize, M_sort_compar_t compar, void *thunk);
131
132
133/*! Sort elements in array in ascending order according to comparison function.
134 *
135 * This is a stable sort.
136 *
137 * \param[in,out] base The array of elements to sort.
138 * \param[in] nmemb The number of elements in the array.
139 * \param[in] esize The size of each element in the array.
140 * \param[in] compar The comparison function.
141 * \param[in] thunk Additional data to pass to the comparison function.
142 */
143M_API void M_sort_mergesort(void *base, size_t nmemb, size_t esize, M_sort_compar_t compar, void *thunk);
144
145
146/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
147 * str compar */
148
149/*! qsort style string comparison in ascending order.
150 *
151 * Base must be an array of pointers to values.
152 *
153 * const char **array;
154 *
155 * \param[in] arg1 The first arg to compare.
156 * \param[in] arg2 The second arg to compare.
157 * \param[in] thunk Additional data to use for comparison.
158 *
159 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
160 *
161 * \see M_sort_compar_t
162 */
163M_API int M_sort_compar_str(const void *arg1, const void *arg2, void *thunk);
164
165
166/*! qsort style string comparison in descending order.
167 *
168 * Base must be an array of pointers to values.
169 *
170 * const char **array;
171 *
172 * \param[in] arg1 The first arg to compare.
173 * \param[in] arg2 The second arg to compare.
174 * \param[in] thunk Additional data to use for comparison.
175 *
176 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
177 *
178 * \see M_sort_compar_t
179 */
180M_API int M_sort_compar_str_desc(const void *arg1, const void *arg2, void *thunk);
181
182
183/*! qsort style string comparison in ascending order case insensitive.
184 *
185 * Base must be an array of pointers to values.
186 *
187 * const char **array;
188 *
189 * \param[in] arg1 The first arg to compare.
190 * \param[in] arg2 The second arg to compare.
191 * \param[in] thunk Additional data to use for comparison.
192 *
193 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
194 *
195 * \see M_sort_compar_t
196 */
197M_API int M_sort_compar_str_casecmp(const void *arg1, const void *arg2, void *thunk);
198
199
200/*! qsort style string comparison in descending order case insensitive.
201 *
202 * Base must be an array of pointers to values.
203 *
204 * const char **array;
205 *
206 * \param[in] arg1 The first arg to compare.
207 * \param[in] arg2 The second arg to compare.
208 * \param[in] thunk Additional data to use for comparison.
209 *
210 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
211 *
212 * \see M_sort_compar_t
213 */
214M_API int M_sort_compar_str_casecmp_desc(const void *arg1, const void *arg2, void *thunk);
215
216
217/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
218 * u64 compar */
219
220/*! qsort style unsigned integer comparison in ascending order.
221 *
222 * Base must be an array of pointers to values.
223 *
224 * M_uint64 **array;
225 *
226 * \param[in] arg1 The first arg to compare.
227 * \param[in] arg2 The second arg to compare.
228 * \param[in] thunk Additional data to use for comparison.
229 *
230 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
231 *
232 * \see M_sort_compar_t
233 */
234M_API int M_sort_compar_u64(const void *arg1, const void *arg2, void *thunk);
235
236
237/*! qsort style unsigned integer comparison in descending order.
238 *
239 * Base must be an array of pointers to values.
240 *
241 * M_uint64 **array;
242 *
243 * \param[in] arg1 The first arg to compare.
244 * \param[in] arg2 The second arg to compare.
245 * \param[in] thunk Additional data to use for comparison.
246 *
247 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
248 *
249 * \see M_sort_compar_t
250 */
251M_API int M_sort_compar_u64_desc(const void *arg1, const void *arg2, void *thunk);
252
253
254/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
255 * bin compar */
256
257/*! qsort style wrapped binary data comparison for data that has been wrapped using M_bin_wrap.
258 *
259 * The binary data will be compared using M_mem_cmpsort.
260 *
261 * Base must be an array of pointers to values.
262 *
263 * M_uint8 **array;
264 *
265 * \param[in] arg1 The first arg to compare.
266 * \param[in] arg2 The second arg to compare.
267 * \param[in] thunk Additional data to use for comparison.
268 *
269 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
270 *
271 * \see M_sort_compar_t
272 * \see M_mem_cmpsort
273 * \see M_bin_wrap
274 */
275M_API int M_sort_compar_binwraped(const void *arg1, const void *arg2, void *thunk);
276
277
278/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
279 * pointer compar */
280
281/*! qsort style unsigned integer comparison in ascending order.
282 *
283 * The pointer themselves are compared; _not_ the value they point to.
284 *
285 * Base must be an array of pointers to values.
286 *
287 * void **array;
288 *
289 * \param[in] arg1 The first arg to compare.
290 * \param[in] arg2 The second arg to compare.
291 * \param[in] thunk Additional data to use for comparison.
292 *
293 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
294 *
295 * \see M_sort_compar_t
296 */
297M_API int M_sort_compar_vp(const void *arg1, const void *arg2, void *thunk);
298
299
300/*! qsort style unsigned integer comparison in descending order.
301 *
302 * The pointer themselves are compared; _not_ the value they point to.
303 *
304 * Base must be an array of pointers to values.
305 *
306 * void **array;
307 *
308 * \param[in] arg1 The first arg to compare.
309 * \param[in] arg2 The second arg to compare.
310 * \param[in] thunk Additional data to use for comparison.
311 *
312 * \return -1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.
313 *
314 * \see M_sort_compar_t
315 */
316M_API int M_sort_compar_vp_desc(const void *arg1, const void *arg2, void *thunk);
317
318/*! @} */
319
320__END_DECLS
321
322#endif /* __M_SORT_H__ */
M_sort_compar_binwraped
int M_sort_compar_binwraped(const void *arg1, const void *arg2, void *thunk)
M_sort_binary_insert_idx
size_t M_sort_binary_insert_idx(const void *base, size_t nmemb, size_t esize, const void *key, M_bool stable, M_sort_compar_t compar, void *thunk)
M_sort_compar_u64
int M_sort_compar_u64(const void *arg1, const void *arg2, void *thunk)
M_sort_compar_str
int M_sort_compar_str(const void *arg1, const void *arg2, void *thunk)
M_sort_compar_vp_desc
int M_sort_compar_vp_desc(const void *arg1, const void *arg2, void *thunk)
M_sort_mergesort
void M_sort_mergesort(void *base, size_t nmemb, size_t esize, M_sort_compar_t compar, void *thunk)
M_sort_compar_vp
int M_sort_compar_vp(const void *arg1, const void *arg2, void *thunk)
M_sort_compar_u64_desc
int M_sort_compar_u64_desc(const void *arg1, const void *arg2, void *thunk)
M_sort_compar_str_casecmp_desc
int M_sort_compar_str_casecmp_desc(const void *arg1, const void *arg2, void *thunk)
M_sort_compar_str_casecmp
int M_sort_compar_str_casecmp(const void *arg1, const void *arg2, void *thunk)
M_sort_qsort
void M_sort_qsort(void *base, size_t nmemb, size_t esize, M_sort_compar_t compar, void *thunk)
M_sort_binary_search
M_bool M_sort_binary_search(const void *base, size_t nmemb, size_t esize, const void *key, M_bool stable, M_sort_compar_t compar, void *thunk, size_t *idx)
M_sort_compar_str_desc
int M_sort_compar_str_desc(const void *arg1, const void *arg2, void *thunk)
M_sort_compar_t
int(* M_sort_compar_t)(const void *arg1, const void *arg2, void *thunk)
Definition: m_sort.h:78