/****Copyright (c) 1997-2009 All rights reserved
 ****A. V. Gerbessiotis and C. J. Siniolakis
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/
#include "ssrt.h"

void A61wbh(void *akeys, int   n,int size,int (*compare)(const void*,const void*))
{
  register int  l, r,M;
  register char *split,*tmp,*pl,*pr;
  char *keys,*SRC,*DES;

  if (n <= 1) return ;
  keys=(char *) akeys;
  split= (char *) malloc(size*sizeof(char));
  tmp  = (char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
  check_if_null(split,"g61wbh","split");
  check_if_null(tmp  ,"g61wbh",  "tmp  ");
#endif
  l=0;r=n-1;
  pl=&keys[l*size];
  pr=&keys[r*size];
#if SPLITTER == MIDDLE_KEY
 MEMCPY(split,&keys[((l+r)>>1)*size],size);
#elif SPLITTER == FIRST_KEY
 MEMCPY(split,&keys[l*size],size);
#elif SPLITTER == RANDOM_KEY
 MEMCPY(split,&keys[(l+GRANDOM((r-l+1)))*size],size);
#endif

  while (l <= r) {
      while (compare(pl,split)<0) {l++;pl +=size;}
      while (compare(split,pr)<0) {r--;pr -=size;}
      if (l <= r) {
	  MEMCPY(tmp,pl,size);
	  MEMCPY(pl,pr,size);
	  MEMCPY(pr,tmp,size);
          l++;r--;pl += size; pr -= size;
      }
  }
  
  if (r > 0) {
      if ((r+1)<THRES16) BASES (keys,r+1,size,compare);
      else A61wbh(keys,r+1,size,compare);
  }
  if (l < n) {
      if ((n - l)<THRES16) BASES (&keys[l*size],n-l,size,compare);
      else A61wbh(&keys[l*size],n-l,size,compare);
  }
 free((void *)split); free((void *)tmp);
}
           
void g61wbh(void *keys, int n, int size, int (*compare) (const void*,const void *))
{
  if (n <= 1) return ;
#if SPLITTER == RANDOM_KEY
 GSRANDOM();
#endif
  A61wbh(keys,n,size,compare);
}
