1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
/* misc_tools.h
*
* Miscellaneous functions and data structures for doing random things.
*
* Copyright (C) 2013 Tox project All Rights Reserved.
*
* This file is part of Tox.
*
* Tox is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Tox is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Tox. If not, see <http://www.gnu.org/licenses/>.
*
*/
#ifndef MISC_TOOLS_H
#define MISC_TOOLS_H
/****************************Algorithms***************************
* Macro/generic definitions for useful algorithms
*****************************************************************/
/* Creates a new quick_sort implementation for arrays of the specified type.
* For a type T (eg: int, char), creates a function named T_quick_sort.
*
* Quick Sort: Complexity O(nlogn)
* arr - the array to sort
* n - the sort index (should be called with n = length(arr))
* cmpfn - a function that compares two values of type type.
* Must return -1, 0, 1 for a < b, a == b, and a > b respectively.
*/
/* Must be called in the header file. */
#define declare_quick_sort(type) \
void type##_quick_sort(type *arr, int n, int (*cmpfn)(type, type));
/* Must be called in the C file. */
#define make_quick_sort(type) \
void type##_quick_sort(type *arr, int n, int (*cmpfn)(type, type)) \
{ \
if ((n) < 2) \
return; \
type _p_ = (arr)[(n) / 2]; \
type *_l_ = (arr); \
type *_r_ = (arr) + n - 1; \
while (_l_ <= _r_) { \
if (cmpfn(*_l_, _p_) == -1) { \
++_l_; \
continue; \
} \
if (cmpfn(*_r_, _p_) == 1) { \
--_r_; \
continue; \
} \
type _t_ = *_l_; \
*_l_++ = *_r_; \
*_r_-- = _t_; \
} \
type##_quick_sort((arr), _r_ - (arr) + 1, cmpfn); \
type##_quick_sort(_l_, (arr) + n - _l_, cmpfn); \
}
#endif // MISC_TOOLS_H
|
