Drizzled Public API Documentation

ut0sort.h

Go to the documentation of this file.
00001 /*****************************************************************************
00002 
00003 Copyright (C) 1995, 2009, Innobase Oy. All Rights Reserved.
00004 
00005 This program is free software; you can redistribute it and/or modify it under
00006 the terms of the GNU General Public License as published by the Free Software
00007 Foundation; version 2 of the License.
00008 
00009 This program is distributed in the hope that it will be useful, but WITHOUT
00010 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00011 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00012 
00013 You should have received a copy of the GNU General Public License along with
00014 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
00015 St, Fifth Floor, Boston, MA 02110-1301 USA
00016 
00017 *****************************************************************************/
00018 
00019 /******************************************************************/
00026 #pragma once
00027 #ifndef ut0sort_h
00028 #define ut0sort_h
00029 
00030 #include "univ.i"
00031 
00032 /* This module gives a macro definition of the body of
00033 a standard sort function for an array of elements of any
00034 type. The comparison function is given as a parameter to
00035 the macro. The sort algorithm is mergesort which has logarithmic
00036 worst case.
00037 */
00038 
00039 /*******************************************************************/
00053 #define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)\
00054 {\
00055   ulint   ut_sort_mid77;\
00056   ulint   ut_sort_i77;\
00057   ulint   ut_sort_low77;\
00058   ulint   ut_sort_high77;\
00059 \
00060   ut_ad((LOW) < (HIGH));\
00061   ut_ad(ARR);\
00062   ut_ad(AUX_ARR);\
00063 \
00064   if ((LOW) == (HIGH) - 1) {\
00065     return;\
00066   } else if ((LOW) == (HIGH) - 2) {\
00067     if (CMP_FUN((ARR)[LOW], (ARR)[(HIGH) - 1]) > 0) {\
00068       (AUX_ARR)[LOW] = (ARR)[LOW];\
00069       (ARR)[LOW] = (ARR)[(HIGH) - 1];\
00070       (ARR)[(HIGH) - 1] = (AUX_ARR)[LOW];\
00071     }\
00072     return;\
00073   }\
00074 \
00075   ut_sort_mid77 = ((LOW) + (HIGH)) / 2;\
00076 \
00077   SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);\
00078   SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));\
00079 \
00080   ut_sort_low77 = (LOW);\
00081   ut_sort_high77 = ut_sort_mid77;\
00082 \
00083   for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\
00084 \
00085     if (ut_sort_low77 >= ut_sort_mid77) {\
00086       (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
00087       ut_sort_high77++;\
00088     } else if (ut_sort_high77 >= (HIGH)) {\
00089       (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
00090       ut_sort_low77++;\
00091     } else if (CMP_FUN((ARR)[ut_sort_low77],\
00092            (ARR)[ut_sort_high77]) > 0) {\
00093       (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
00094       ut_sort_high77++;\
00095     } else {\
00096       (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
00097       ut_sort_low77++;\
00098     }\
00099   }\
00100 \
00101   memcpy((void*) ((ARR) + (LOW)), (AUX_ARR) + (LOW),\
00102          ((HIGH) - (LOW)) * sizeof *(ARR));\
00103 }\
00104 
00105 
00106 #endif
00107