diff options
Diffstat (limited to 'sql/plistsort.c')
| -rw-r--r-- | sql/plistsort.c | 166 |
1 files changed, 166 insertions, 0 deletions
diff --git a/sql/plistsort.c b/sql/plistsort.c new file mode 100644 index 00000000..6efea273 --- /dev/null +++ b/sql/plistsort.c @@ -0,0 +1,166 @@ +/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */ + + +/* +things to define before including the file: + +#define LS_LIST_ITEM ListItem +#define LS_COMPARE_FUNC_DECL compare_func var_name, +#define LS_COMPARE_FUNC_CALL(list_el1, list_el2) (*var_name)(list_el1, list_el2) +#define LS_NEXT(A) (A)->next +#define LS_SET_NEXT(A,val) (A)->next= val +#define LS_P_NEXT(A) &(A)->next +#define LS_NAME plistsort +#define LS_SCOPE static +#define LS_STRUCT_NAME ls_struct_name +*/ + +typedef struct LS_STRUCT_NAME +{ + LS_LIST_ITEM *list1; + int list_len; + int return_point; +} LS_STRUCT_NAME; + +LS_SCOPE LS_LIST_ITEM* LS_NAME(LS_COMPARE_FUNC_DECL LS_LIST_ITEM *list, int list_len) +{ + LS_LIST_ITEM *list_end; + LS_LIST_ITEM *sorted_list; + + struct LS_STRUCT_NAME stack[63], *sp= stack; + + if (list_len < 2) + return list; + + sp->list_len= list_len; + sp->return_point= 2; + +recursion_point: + + if (sp->list_len < 4) + { + LS_LIST_ITEM *e1, *e2; + sorted_list= list; + e1= LS_NEXT(sorted_list); + list_end= LS_NEXT(e1); + if (LS_COMPARE_FUNC_CALL(sorted_list, e1)) + { + sorted_list= e1; + e1= list; + } + if (sp->list_len == 2) + { + LS_SET_NEXT(sorted_list, e1); + LS_SET_NEXT(e1, NULL); + goto exit_point; + } + e2= list_end; + list_end= LS_NEXT(e2); + if (LS_COMPARE_FUNC_CALL(e1, e2)) + { + { + LS_LIST_ITEM *tmp_e= e1; + e1= e2; + e2= tmp_e; + } + if (LS_COMPARE_FUNC_CALL(sorted_list, e1)) + { + LS_LIST_ITEM *tmp_e= sorted_list; + sorted_list= e1; + e1= tmp_e; + } + } + + LS_SET_NEXT(sorted_list, e1); + LS_SET_NEXT(e1, e2); + LS_SET_NEXT(e2, NULL); + goto exit_point; + } + + { + struct LS_STRUCT_NAME *sp0= sp++; + sp->list_len= sp0->list_len >> 1; + sp0->list_len-= sp->list_len; + sp->return_point= 0; + } + goto recursion_point; +return_point0: + sp->list1= sorted_list; + { + struct LS_STRUCT_NAME *sp0= sp++; + list= list_end; + sp->list_len= sp0->list_len; + sp->return_point= 1; + } + goto recursion_point; +return_point1: + { + LS_LIST_ITEM **hook= &sorted_list; + LS_LIST_ITEM *list1= sp->list1; + LS_LIST_ITEM *list2= sorted_list; + + if (LS_COMPARE_FUNC_CALL(list1, list2)) + { + LS_LIST_ITEM *tmp_e= list2; + list2= list1; + list1= tmp_e; + } + for (;;) + { + *hook= list1; + do + { + if (!(list1= *(hook= LS_P_NEXT(list1)))) + { + *hook= list2; + goto exit_point; + } + } while (LS_COMPARE_FUNC_CALL(list2, list1)); + + *hook= list2; + do + { + if (!(list2= *(hook= LS_P_NEXT(list2)))) + { + *hook= list1; + goto exit_point; + } + } while (LS_COMPARE_FUNC_CALL(list1, list2)); + } + } + +exit_point: + switch ((sp--)->return_point) + { + case 0: goto return_point0; + case 1: goto return_point1; + default:; + } + + return sorted_list; +} + + +#undef LS_LIST_ITEM +#undef LS_NEXT +#undef LS_SET_NEXT +#undef LS_P_NEXT +#undef LS_NAME +#undef LS_STRUCT_NAME +#undef LS_SCOPE +#undef LS_COMPARE_FUNC_DECL +#undef LS_COMPARE_FUNC_CALL + |