← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to storage/innobase/include/ut0sort.h

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/include/ut0sort.h
 
1
/**********************************************************************
 
2
Sort utility
 
3
 
 
4
(c) 1995 Innobase Oy
 
5
 
 
6
Created 11/9/1995 Heikki Tuuri
 
7
***********************************************************************/
 
8
 
 
9
#ifndef ut0sort_h
 
10
#define ut0sort_h
 
11
 
 
12
#include "univ.i"
 
13
 
 
14
/* This module gives a macro definition of the body of
 
15
a standard sort function for an array of elements of any
 
16
type. The comparison function is given as a parameter to
 
17
the macro. The sort algorithm is mergesort which has logarithmic
 
18
worst case.
 
19
*/
 
20
 
 
21
/***********************************************************************
 
22
This macro expands to the body of a standard sort function.
 
23
The sort function uses mergesort and must be defined separately
 
24
for each type of array.
 
25
Also the comparison function has to be defined individually
 
26
for each array cell type. SORT_FUN is the sort function name.
 
27
The function takes the array to be sorted (ARR),
 
28
the array of auxiliary space (AUX_ARR) of same size,
 
29
and the low (LOW), inclusive, and high (HIGH), noninclusive,
 
30
limits for the sort interval as arguments.
 
31
CMP_FUN is the comparison function name. It takes as arguments
 
32
two elements from the array and returns 1, if the first is bigger,
 
33
0 if equal, and -1 if the second bigger. For an eaxmaple of use
 
34
see test program in tsut.c. */
 
35
 
 
36
#define UT_SORT_FUNCTION_BODY(SORT_FUN, ARR, AUX_ARR, LOW, HIGH, CMP_FUN)\
 
37
{\
 
38
        ulint           ut_sort_mid77;\
 
39
        ulint           ut_sort_i77;\
 
40
        ulint           ut_sort_low77;\
 
41
        ulint           ut_sort_high77;\
 
42
\
 
43
        ut_ad((LOW) < (HIGH));\
 
44
        ut_ad(ARR);\
 
45
        ut_ad(AUX_ARR);\
 
46
\
 
47
        if ((LOW) == (HIGH) - 1) {\
 
48
                return;\
 
49
        } else if ((LOW) == (HIGH) - 2) {\
 
50
                if (CMP_FUN((ARR)[LOW], (ARR)[(HIGH) - 1]) > 0) {\
 
51
                        (AUX_ARR)[LOW] = (ARR)[LOW];\
 
52
                        (ARR)[LOW] = (ARR)[(HIGH) - 1];\
 
53
                        (ARR)[(HIGH) - 1] = (AUX_ARR)[LOW];\
 
54
                }\
 
55
                return;\
 
56
        }\
 
57
\
 
58
        ut_sort_mid77 = ((LOW) + (HIGH)) / 2;\
 
59
\
 
60
        SORT_FUN((ARR), (AUX_ARR), (LOW), ut_sort_mid77);\
 
61
        SORT_FUN((ARR), (AUX_ARR), ut_sort_mid77, (HIGH));\
 
62
\
 
63
        ut_sort_low77 = (LOW);\
 
64
        ut_sort_high77 = ut_sort_mid77;\
 
65
\
 
66
        for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\
 
67
\
 
68
                if (ut_sort_low77 >= ut_sort_mid77) {\
 
69
                        (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
 
70
                        ut_sort_high77++;\
 
71
                } else if (ut_sort_high77 >= (HIGH)) {\
 
72
                        (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
 
73
                        ut_sort_low77++;\
 
74
                } else if (CMP_FUN((ARR)[ut_sort_low77],\
 
75
                                   (ARR)[ut_sort_high77]) > 0) {\
 
76
                        (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_high77];\
 
77
                        ut_sort_high77++;\
 
78
                } else {\
 
79
                        (AUX_ARR)[ut_sort_i77] = (ARR)[ut_sort_low77];\
 
80
                        ut_sort_low77++;\
 
81
                }\
 
82
        }\
 
83
\
 
84
        for (ut_sort_i77 = (LOW); ut_sort_i77 < (HIGH); ut_sort_i77++) {\
 
85
                (ARR)[ut_sort_i77] = (AUX_ARR)[ut_sort_i77];\
 
86
        }\
 
87
}\
 
88
 
 
89
 
 
90
#endif
 
91