drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
ut0sort.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (C) 1995, 2009, Innobase Oy. 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., 51 Franklin
15St, 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
33a standard sort function for an array of elements of any
34type. The comparison function is given as a parameter to
35the macro. The sort algorithm is mergesort which has logarithmic
36worst 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