/****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 A62dbh(void *akeys, int n, int size, int (*compare) (const void*,const void*),int l,int r)
{
 register int i,j,M;
 char	*tmp,*split,*keys;
 char    *pi,*pj,*SRC,*DES;

 if (n<=1) return;
 keys  = (char *) akeys;
 tmp   = (char *) malloc(size*sizeof(char));
 split = (char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
 check_if_null(tmp,  "g62dbh","tmp");
 check_if_null(split,"g62dbh","split");
#endif
 i=l;j=r;
 pi= &keys[l*size];
 pj= &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

 do {
   while (compare(pi,split) < 0)  {i++; pi += size;}
   while (compare(split,pj) < 0)  {j--; pj -= size;}
   if (i <= j ) {
     MEMCPY(tmp,pi,size);
     MEMCPY(pi,pj,size);
     MEMCPY(pj,tmp,size);
     i++;j--;pi += size;pj -= size;
   }
 } while (i <= j);
	
 if (l < j) {
   if ((j-l+1) < THRES16)
      BASES (&keys[l*size],(j-l+1),size,compare);
   else
      A62dbh(keys,n,size,compare,l,j);
 }
 if (i < r) {
    if ((r-i+1) < THRES16)
	BASES (&keys[i*size],(r-i+1),size,compare);
    else
	A62dbh(keys,n,size,compare,i,r);
 }
	
 free((void *)split); free((void *)tmp);
}

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