1
/*****************************************************************************
3
Copyright (c) 1995, 2009, Innobase Oy. All Rights Reserved.
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.
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.
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., 59 Temple
15
Place, Suite 330, Boston, MA 02111-1307 USA
17
*****************************************************************************/
19
/******************************************************************//**
20
@file include/ut0sort.h
23
Created 11/9/1995 Heikki Tuuri
24
***********************************************************************/
31
/* This module gives a macro definition of the body of
32
a standard sort function for an array of elements of any
33
type. The comparison function is given as a parameter to
34
the macro. The sort algorithm is mergesort which has logarithmic
38
/*******************************************************************//**
39
This macro expands to the body of a standard sort function.
40
The sort function uses mergesort and must be defined separately
41
for each type of array.
42
Also the comparison function has to be defined individually
43
for each array cell type. SORT_FUN is the sort function name.
44
The function takes the array to be sorted (ARR),
45
the array of auxiliary space (AUX_ARR) of same size,
46
and the low (LOW), inclusive, and high (HIGH), noninclusive,
47
limits for the sort interval as arguments.
48
CMP_FUN is the comparison function name. It takes as arguments
49
two elements from the array and returns 1, if the first is bigger,
50
0 if equal, and -1 if the second bigger. */
52
#define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)\
57
ulint ut_sort_high77;\
59
ut_ad((LOW) < (HIGH));\
63
if ((LOW) == (HIGH) - 1) {\
65
} else if ((LOW) == (HIGH) - 2) {\
66
if (CMP_FUN((ARR)[LOW], (ARR)[(HIGH) - 1]) > 0) {\
67
(AUX_ARR)[LOW] = (ARR)[LOW];\
68
(ARR)[LOW] = (ARR)[(HIGH) - 1];\
69
(ARR)[(HIGH) - 1] = (AUX_ARR)[LOW];\
74
ut_sort_mid77 = ((LOW) + (HIGH)) / 2;\
76
SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);\
77
SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));\
79
ut_sort_low77 = (LOW);\
80
ut_sort_high77 = ut_sort_mid77;\
82
for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\
84
if (ut_sort_low77 >= ut_sort_mid77) {\
85
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
87
} else if (ut_sort_high77 >= (HIGH)) {\
88
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
90
} else if (CMP_FUN((ARR)[ut_sort_low77],\
91
(ARR)[ut_sort_high77]) > 0) {\
92
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
95
(AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
100
memcpy((void*) ((ARR) + (LOW)), (AUX_ARR) + (LOW),\
101
((HIGH) - (LOW)) * sizeof *(ARR));\