src/external/tng_io/src/compression/merge_sort.c

   1 /* This code is part of the tng compression routines.
   2  *
   3  * Written by Daniel Spangberg
   4  * Copyright (c) 2010, 2013, The GROMACS development team.
   5  *
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the Revised BSD License.
   9  */
  10
  11
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <string.h>
  15 #include "../../include/compression/warnmalloc.h"
  16 #include "../../include/compression/merge_sort.h"
  17
  18 static void ms_inner(void *base, const size_t size,
  19              const size_t start, const size_t end,
  20              int (*compar)(const void *v1,const void *v2,const void *private),
  21              const void *private,
  22              char *workarray)
  23 {
  24   size_t middle;
  25   if ((end-start)>1)
  26     {
  27       char *cbase=(char *)base;
  28       middle=start+(end-start)/2;
  29 #if 0
  30       printf("For start %d end %d obtained new middle: %d\n",start,end,middle);
  31 #endif
  32       ms_inner(base,size,
  33            start,middle,
  34            compar,private,workarray);
  35       ms_inner(base,size,
  36            middle,end,
  37            compar,private,workarray);
  38 #if 0
  39       printf("For start %d end %d Before merge: Comparing element %d with %d\n",start,end,middle-1,middle);
  40 #endif
  41       if (compar(cbase+(middle-1)*size,cbase+middle*size,private)>0)
  42         {
  43           /* Merge to work array. */
  44           size_t i, n=end-start;
  45           size_t ileft=start;
  46           size_t iright=middle;
  47           for (i=0; i<n; i++)
  48             {
  49               if (ileft==middle)
  50                 {
  51                   memcpy(workarray+i*size,cbase+iright*size,size);
  52                   iright++;
  53                 }
  54               else if (iright==end)
  55                 {
  56                   memcpy(workarray+i*size,cbase+ileft*size,size);
  57                   ileft++;
  58                 }
  59               else
  60                 {
  61         #if 0
  62                   printf("For start %d end %d In merge: Comparing element %d with %d\n",start,end,ileft,iright);
  63         #endif
  64                   if (compar(cbase+ileft*size,cbase+iright*size,private)>0)
  65                     {
  66                       memcpy(workarray+i*size,cbase+iright*size,size);
  67                       iright++;
  68                     }
  69                   else
  70                     {
  71                       memcpy(workarray+i*size,cbase+ileft*size,size);
  72                       ileft++;
  73                     }
  74                 }
  75             }
  76           /* Copy result back. */
  77           memcpy(cbase+start*size,workarray,(end-start)*size);
  78         }
  79     }
  80 }
  81
  82
  83 void Ptngc_merge_sort(void *base, const size_t nmemb, const size_t size,
  84         int (*compar)(const void *v1,const void *v2,const void *private),
  85         void *private)
  86 {
  87   char *warr=warnmalloc(nmemb*size);
  88   ms_inner(base,size,0,nmemb,compar,private,warr);
  89   free(warr);
  90 }
  91
  92
  93 #ifdef TEST
  94
  95 static int compint(const void *v1, const void *v2,const void *private)
  96 {
  97   const int *i1=(const int *)v1;
  98   const int *i2=(const int *)v2;
  99   if (*i1<*i2)
 100     return -1;
 101   else if (*i1>*i2)
 102     return 1;
 103   else
 104     return 0;
 105 }
 106
 107 static int qcompint(const void *v1, const void *v2)
 108 {
 109   return compint(v1,v2,NULL);
 110 }
 111
 112 #define N 1000000
 113 int main()
 114 {
 115   int *arr=warnmalloc(N*sizeof *arr);
 116   int i;
 117   for (i=0; i<N; i++)
 118     scanf("%d",arr+i);
 119 #if 1
 120   merge_sort(arr,N,sizeof *arr,compint,NULL);
 121 #else
 122   qsort(arr,N,sizeof *arr,qcompint);
 123 #endif
 124   for (i=0; i<N; i++)
 125     printf("%d %d\n",i,arr[i]);
 126   return 0;
 127 }
 128 #endif