drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
ut0sort.h
Go to the documentation of this file.
1
/*****************************************************************************
2
3
Copyright (C) 1995, 2009, Innobase Oy. All Rights Reserved.
4
5
This program is free software; you can redistribute it and/or modify it under
6
the terms of the GNU General Public License as published by the Free Software
7
Foundation; version 2 of the License.
8
9
This program is distributed in the hope that it will be useful, but WITHOUT
10
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13
You should have received a copy of the GNU General Public License along with
14
this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
15
St, Fifth Floor, Boston, MA 02110-1301 USA
16
17
*****************************************************************************/
18
19
/******************************************************************/
25
26
#pragma once
27
#ifndef ut0sort_h
28
#define ut0sort_h
29
30
#include "univ.i"
31
32
/* This module gives a macro definition of the body of
33
a standard sort function for an array of elements of any
34
type. The comparison function is given as a parameter to
35
the macro. The sort algorithm is mergesort which has logarithmic
36
worst case.
37
*/
38
39
/*******************************************************************/
52
53
#define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)\
54
{\
55
ulint ut_sort_mid77;\
56
ulint ut_sort_i77;\
57
ulint ut_sort_low77;\
58
ulint ut_sort_high77;\
59
\
60
ut_ad((LOW) < (HIGH));\
61
ut_ad(ARR);\
62
ut_ad(AUX_ARR);\
63
\
64
if ((LOW) == (HIGH) - 1) {\
65
return;\
66
} else if ((LOW) == (HIGH) - 2) {\
67
if (CMP_FUN((ARR)[LOW], (ARR)[(HIGH) - 1]) > 0) {\
68
(AUX_ARR)[LOW] = (ARR)[LOW];\
69
(ARR)[LOW] = (ARR)[(HIGH) - 1];\
70
(ARR)[(HIGH) - 1] = (AUX_ARR)[LOW];\
71
}\
72
return;\
73
}\
74
\
75
ut_sort_mid77 = ((LOW) + (HIGH)) / 2;\
76
\
77
SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);\
78
SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));\
79
\
80
ut_sort_low77 = (LOW);\
81
ut_sort_high77 = ut_sort_mid77;\
82
\
83
for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\
84
\
85
if (ut_sort_low77 >= ut_sort_mid77) {\
86
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
87
ut_sort_high77++;\
88
} else if (ut_sort_high77 >= (HIGH)) {\
89
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
90
ut_sort_low77++;\
91
} else if (CMP_FUN((ARR)[ut_sort_low77],\
92
(ARR)[ut_sort_high77]) > 0) {\
93
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
94
ut_sort_high77++;\
95
} else {\
96
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
97
ut_sort_low77++;\
98
}\
99
}\
100
\
101
memcpy((void*) ((ARR) + (LOW)), (AUX_ARR) + (LOW),\
102
((HIGH) - (LOW)) * sizeof *(ARR));\
103
}\
104
105
106
#endif
107
← Back to Drizzle docs
plugin
innobase
include
ut0sort.h
Generated by
1.15.0