Drizzled Public API Documentation

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 /******************************************************************/
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 /*******************************************************************/
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