/* 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