1/*****************************************************************************
2
3Copyright (c) 1995, 2009, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/******************************************************************//**
20@file include/ut0sort.h
21Sort utility
22
23Created 11/9/1995 Heikki Tuuri
24***********************************************************************/
25
26#ifndef ut0sort_h
27#define ut0sort_h
28
29#include "univ.i"
30
31/* This module gives a macro definition of the body of
32a standard sort function for an array of elements of any
33type. The comparison function is given as a parameter to
34the macro. The sort algorithm is mergesort which has logarithmic
35worst case.
36*/
37
38/*******************************************************************//**
39This macro expands to the body of a standard sort function.
40The sort function uses mergesort and must be defined separately
41for each type of array.
42Also the comparison function has to be defined individually
43for each array cell type. SORT_FUN is the sort function name.
44The function takes the array to be sorted (ARR),
45the array of auxiliary space (AUX_ARR) of same size,
46and the low (LOW), inclusive, and high (HIGH), noninclusive,
47limits for the sort interval as arguments.
48CMP_FUN is the comparison function name. It takes as arguments
49two elements from the array and returns 1, if the first is bigger,
500 if equal, and -1 if the second bigger. */
51
52#define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)\
53{\
54 ulint ut_sort_mid77;\
55 ulint ut_sort_i77;\
56 ulint ut_sort_low77;\
57 ulint ut_sort_high77;\
58\
59 ut_ad((LOW) < (HIGH));\
60 ut_ad(ARR);\
61 ut_ad(AUX_ARR);\
62\
63 if ((LOW) == (HIGH) - 1) {\
64 return;\
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];\
70 }\
71 return;\
72 }\
73\
74 ut_sort_mid77 = ((LOW) + (HIGH)) / 2;\
75\
76 SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);\
77 SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));\
78\
79 ut_sort_low77 = (LOW);\
80 ut_sort_high77 = ut_sort_mid77;\
81\
82 for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\
83\
84 if (ut_sort_low77 >= ut_sort_mid77) {\
85 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
86 ut_sort_high77++;\
87 } else if (ut_sort_high77 >= (HIGH)) {\
88 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
89 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];\
93 ut_sort_high77++;\
94 } else {\
95 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
96 ut_sort_low77++;\
97 }\
98 }\
99\
100 memcpy((void*) ((ARR) + (LOW)), (AUX_ARR) + (LOW),\
101 ((HIGH) - (LOW)) * sizeof *(ARR));\
102}\
103
104
105#endif
106
107