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