InnoDB Plugin  1.0
ut0sort.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1995, 2009, Oracle and/or its affiliates. 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.,
15 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16 
17 *****************************************************************************/
18 
19 /******************************************************************/
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
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
35 worst case.
36 */
37 
38 /*******************************************************************/
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