/****Copyright (c) 1997-2005 All rights reserved
 ****  ???????????????????????????
 ****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"
#define	ALN2I	1.442695022
#define	TINY	1.0e-5

/* May be based on a N. Wirth PASCAL code or Numerical Recipes code */
/* Check if it works ok ; it might not (vague recollection ) */

void g19shlln(void *akeys,int n,int size,int (*compare)(const void*,const void*))
{
 register int nn,m,i,j,lognb2;
 double t;
 char *tmp, *keys;

 keys = (char *) akeys;
 tmp = (char *) malloc(size*sizeof(char));
 lognb2 = (log((double)n)*ALN2I+TINY);
 m=n;
 for(nn=1;nn<=lognb2;nn++){
    m >>=1;
    for(j=m;j<n;j++){
      i=j-m;
      memcpy(tmp,&keys[j*size],size);
      while (i>=0 && compare(&keys[i*size],tmp)>0) {
         memcpy(&keys[(i+m)*size],&keys[i*size],size);
         i-=m;
      }
      memcpy(&keys[(i+m)*size],tmp,size);
    }
  }
}
