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, Fifth Floor, Boston, MA 02110-1335 USA 16 17 *****************************************************************************/ 18 19 /******************************************************************//** 20 @file include/ut0sort.h 21 Sort utility 22 23 Created 11/9/1995 Heikki Tuuri 24 ***********************************************************************/ 25 26 #ifndef ut0sort_h 27 #define ut0sort_h 28 29 /* This module gives a macro definition of the body of 30 a standard sort function for an array of elements of any 31 type. The comparison function is given as a parameter to 32 the macro. The sort algorithm is mergesort which has logarithmic 33 worst case. 34 */ 35 36 /*******************************************************************//** 37 This macro expands to the body of a standard sort function. 38 The sort function uses mergesort and must be defined separately 39 for each type of array. 40 Also the comparison function has to be defined individually 41 for each array cell type. SORT_FUN is the sort function name. 42 The function takes the array to be sorted (ARR), 43 the array of auxiliary space (AUX_ARR) of same size, 44 and the low (LOW), inclusive, and high (HIGH), noninclusive, 45 limits for the sort interval as arguments. 46 CMP_FUN is the comparison function name. It takes as arguments 47 two elements from the array and returns 1, if the first is bigger, 48 0 if equal, and -1 if the second bigger. */ 49 50 #define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)\ 51 {\ 52 ulint ut_sort_mid77;\ 53 ulint ut_sort_i77;\ 54 ulint ut_sort_low77;\ 55 ulint ut_sort_high77;\ 56 \ 57 ut_ad((LOW) < (HIGH));\ 58 ut_ad(ARR);\ 59 ut_ad(AUX_ARR);\ 60 \ 61 if ((LOW) == (HIGH) - 1) {\ 62 return;\ 63 } else if ((LOW) == (HIGH) - 2) {\ 64 if (CMP_FUN((ARR)[LOW], (ARR)[(HIGH) - 1]) > 0) {\ 65 (AUX_ARR)[LOW] = (ARR)[LOW];\ 66 (ARR)[LOW] = (ARR)[(HIGH) - 1];\ 67 (ARR)[(HIGH) - 1] = (AUX_ARR)[LOW];\ 68 }\ 69 return;\ 70 }\ 71 \ 72 ut_sort_mid77 = ((LOW) + (HIGH)) / 2;\ 73 \ 74 SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);\ 75 SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));\ 76 \ 77 ut_sort_low77 = (LOW);\ 78 ut_sort_high77 = ut_sort_mid77;\ 79 \ 80 for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\ 81 \ 82 if (ut_sort_low77 >= ut_sort_mid77) {\ 83 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\ 84 ut_sort_high77++;\ 85 } else if (ut_sort_high77 >= (HIGH)) {\ 86 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\ 87 ut_sort_low77++;\ 88 } else if (CMP_FUN((ARR)[ut_sort_low77],\ 89 (ARR)[ut_sort_high77]) > 0) {\ 90 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\ 91 ut_sort_high77++;\ 92 } else {\ 93 (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\ 94 ut_sort_low77++;\ 95 }\ 96 }\ 97 \ 98 memcpy((void*) ((ARR) + (LOW)), (AUX_ARR) + (LOW),\ 99 ((HIGH) - (LOW)) * sizeof *(ARR));\ 100 }\ 101 102 103 #endif 104 105