/****Copyright (c) 1997-2009 All rights reserved
 ****A. V. Gerbessiotis 
 ****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 A53fbc(void *akeys, int   n,int size,int (*compare)(const void*,const void*),int l,int r)
{
  register int  i,j,M;
  register char *tmp,*pm;
  char *keys,*DES,*SRC;

  if (n <= 1) return ;
  keys=(char *) akeys;
  tmp = (char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
  check_if_null(tmp  ,"g53fbc","tmp ");
#endif
#if SPLITTER == MIDDLE_KEY
  pm = &keys[((l+r)>>1)*size];
#elif SPLITTER == FIRST_KEY
  pm = &keys[l*size];
#elif SPLITTER == RANDOM_KEY
  pm = &keys[(l+GRANDOM((r-l+1)))*size];
#endif
  MEMCPY(tmp,pm,size);
  MEMCPY(pm,keys+r*size,size);
  MEMCPY(keys+r*size,tmp,size);
  i=l-1; 
  j=l; 
  for(j=l;j<r;j++) {
    if (compare(keys+j*size,keys+r*size) <=0) {
       i++;
       MEMCPY(tmp,keys+j*size,size);
       MEMCPY(keys+j*size,keys+i*size,size);
       MEMCPY(keys+i*size,tmp,size);
    }
  }
  i++;
  MEMCPY(tmp ,keys+r*size,size);
  MEMCPY(keys+r*size,keys+i*size,size);
  MEMCPY(keys+i*size,tmp,size);

  if ((i-l) < THRES16)
     BASES(&keys[l*size],(i-l),size,compare);
  else
     A53fbc(&keys[l*size],i-l,size,compare,0,i-l-1);
  if ((r-i) < THRES16)
     BASES(&keys[(i+1)*size],(r-i),size,compare);
   else
     A53fbc(&keys[(i+1)*size],r-i,size,compare,0,r-i-1);

 free((void *)tmp); 
}
           
void g53fbc (void *keys, int n, int size, int (*compare) (const void*,const void *))
{
  if (n <= 1) return ;
#if SPLITTER == RANDOM_KEY
 GSRANDOM();
#endif
  A53fbc(keys,n,size,compare,0,n-1);
}

