← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mysql-5.6/trusty

« back to all changes in this revision

Viewing changes to sql/plistsort.c

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2014-02-12 11:54:27 UTC
  • Revision ID: package-import@ubuntu.com-20140212115427-oq6tfsqxl1wuwehi
Tags: upstream-5.6.15
Import upstream version 5.6.15

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/plistsort.c
 
1
/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */
 
15
 
 
16
 
 
17
/*
 
18
things to define before including the file:
 
19
 
 
20
#define LS_LIST_ITEM ListItem
 
21
#define LS_COMPARE_FUNC_DECL compare_func var_name,
 
22
#define LS_COMPARE_FUNC_CALL(list_el1, list_el2) (*var_name)(list_el1, list_el2)
 
23
#define LS_NEXT(A) (A)->next
 
24
#define LS_SET_NEXT(A,val) (A)->next= val
 
25
#define LS_P_NEXT(A) &(A)->next
 
26
#define LS_NAME plistsort
 
27
#define LS_SCOPE static
 
28
#define LS_STRUCT_NAME ls_struct_name
 
29
*/
 
30
 
 
31
typedef struct LS_STRUCT_NAME
 
32
{
 
33
  LS_LIST_ITEM *list1;
 
34
  int list_len;
 
35
  int return_point;
 
36
} LS_STRUCT_NAME;
 
37
 
 
38
LS_SCOPE LS_LIST_ITEM* LS_NAME(LS_COMPARE_FUNC_DECL LS_LIST_ITEM *list, int list_len)
 
39
{
 
40
  LS_LIST_ITEM *list_end;
 
41
  LS_LIST_ITEM *sorted_list;
 
42
 
 
43
  struct LS_STRUCT_NAME stack[63], *sp= stack;
 
44
 
 
45
  if (list_len < 2)
 
46
    return list;
 
47
 
 
48
  sp->list_len= list_len;
 
49
  sp->return_point= 2;
 
50
 
 
51
recursion_point:
 
52
 
 
53
  if (sp->list_len < 4)
 
54
  {
 
55
    LS_LIST_ITEM *e1, *e2;
 
56
    sorted_list= list;
 
57
    e1= LS_NEXT(sorted_list);
 
58
    list_end= LS_NEXT(e1);
 
59
    if (LS_COMPARE_FUNC_CALL(sorted_list, e1))
 
60
    {
 
61
      sorted_list= e1;
 
62
      e1= list;
 
63
    }
 
64
    if (sp->list_len == 2)
 
65
    {
 
66
      LS_SET_NEXT(sorted_list, e1);
 
67
      LS_SET_NEXT(e1, NULL);
 
68
      goto exit_point;
 
69
    }
 
70
    e2= list_end;
 
71
    list_end= LS_NEXT(e2);
 
72
    if (LS_COMPARE_FUNC_CALL(e1, e2))
 
73
    {
 
74
      {
 
75
        LS_LIST_ITEM *tmp_e= e1;
 
76
        e1= e2;
 
77
        e2= tmp_e;
 
78
      }
 
79
      if (LS_COMPARE_FUNC_CALL(sorted_list, e1))
 
80
      {
 
81
        LS_LIST_ITEM *tmp_e= sorted_list;
 
82
        sorted_list= e1;
 
83
        e1= tmp_e;
 
84
      }
 
85
    }
 
86
 
 
87
    LS_SET_NEXT(sorted_list, e1);
 
88
    LS_SET_NEXT(e1, e2);
 
89
    LS_SET_NEXT(e2, NULL);
 
90
    goto exit_point;
 
91
  }
 
92
 
 
93
  {
 
94
    register struct LS_STRUCT_NAME *sp0= sp++;
 
95
    sp->list_len= sp0->list_len >> 1;
 
96
    sp0->list_len-= sp->list_len;
 
97
    sp->return_point= 0;
 
98
  }
 
99
  goto recursion_point;
 
100
return_point0:
 
101
  sp->list1= sorted_list;
 
102
  {
 
103
    register struct LS_STRUCT_NAME *sp0= sp++;
 
104
    list= list_end;
 
105
    sp->list_len= sp0->list_len;
 
106
    sp->return_point= 1;
 
107
  }
 
108
  goto recursion_point;
 
109
return_point1:
 
110
  {
 
111
    register LS_LIST_ITEM **hook= &sorted_list;
 
112
    register LS_LIST_ITEM *list1= sp->list1;
 
113
    register LS_LIST_ITEM *list2= sorted_list;
 
114
 
 
115
    if (LS_COMPARE_FUNC_CALL(list1, list2))
 
116
    {
 
117
      LS_LIST_ITEM *tmp_e= list2;
 
118
      list2= list1;
 
119
      list1= tmp_e;
 
120
    }
 
121
    for (;;)
 
122
    {
 
123
      *hook= list1;
 
124
      do
 
125
      {
 
126
        if (!(list1= *(hook= LS_P_NEXT(list1))))
 
127
        {
 
128
          *hook= list2;
 
129
          goto exit_point;
 
130
        }
 
131
      } while (LS_COMPARE_FUNC_CALL(list2, list1));
 
132
 
 
133
      *hook= list2;
 
134
      do
 
135
      {
 
136
        if (!(list2= *(hook= LS_P_NEXT(list2))))
 
137
        {
 
138
          *hook= list1;
 
139
          goto exit_point;
 
140
        }
 
141
      } while (LS_COMPARE_FUNC_CALL(list1, list2));
 
142
    }
 
143
  }
 
144
 
 
145
exit_point:
 
146
  switch ((sp--)->return_point)
 
147
  {
 
148
    case 0: goto return_point0;
 
149
    case 1: goto return_point1;
 
150
    default:;
 
151
  }
 
152
 
 
153
  return sorted_list;
 
154
}
 
155
 
 
156
 
 
157
#undef LS_LIST_ITEM
 
158
#undef LS_NEXT
 
159
#undef LS_SET_NEXT
 
160
#undef LS_P_NEXT
 
161
#undef LS_NAME
 
162
#undef LS_STRUCT_NAME
 
163
#undef LS_SCOPE
 
164
#undef LS_COMPARE_FUNC_DECL
 
165
#undef LS_COMPARE_FUNC_CALL
 
166