home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pctech / hlsrc / hlsrtsub.c < prev    next >
C/C++ Source or Header  |  1988-09-09  |  2KB  |  65 lines
  1. /*+
  2.     Name:    HLSRTSUB.C
  3.     Author:    Kent J. Quirk
  4.         (c) Copyright 1988 Ziff Communications Co.
  5.     Abstract:    This file contains a relatively general-purpose Shell sort
  6.         routine for files of fixed-length records. It is completely
  7.         disk based, and has no particular limitations, except speed.
  8.         (But since we're using it to test disk I/O, we almost want it
  9.         to be slow.  We certainly want it to be diskbound.)
  10.     History:    09-Sep-88   kjq     Version 1.00
  11. -*/
  12.  
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15.  
  16. #define ALLOC_ITEM(v,sz) if ((v = malloc(sz)) == NULL) exit(1)
  17. #define READREC(v,f,n,sz) fseek(f, (n)*(long)(sz), SEEK_SET); \
  18.                 fread(v, sz, 1, f); rd_cnt++
  19. #define WRITEREC(v,f,n,sz) fseek(f, (n)*(long)(sz), SEEK_SET); \
  20.                 fwrite(v, sz, 1, f); wt_cnt++
  21.  
  22. long rd_cnt=0L;
  23. long wt_cnt=0L;
  24.  
  25. void shellsort(f, nrecs, recsize, compare)
  26. FILE *f;
  27. long nrecs;
  28. int recsize;
  29. int (*compare)();
  30. {
  31.     long i,j,h;
  32.     char *v, *t;
  33.  
  34.     ALLOC_ITEM(v,recsize);
  35.     ALLOC_ITEM(t, recsize);
  36.  
  37.     for (h=1; h<nrecs; h = 3*h + 1)
  38.         ;                    /* calculate starting h */
  39.  
  40.     do
  41.     {
  42.     h /= 3;
  43.     for (i=h; i<nrecs; i++)
  44.     {
  45.         READREC(v, f, i, recsize);        /* a[i] is in v */
  46.         j = i;
  47.  
  48.         READREC(t, f, j-h, recsize);    /* a[j-h] is in t */
  49.         while((*compare)(t,v) > 0)
  50.         {
  51.         WRITEREC(t, f, j, recsize);    /* write a[j] */
  52.         j = j-h;
  53.         if (j < h)
  54.             break;
  55.         READREC(t, f, j-h, recsize);    /* read new element */
  56.         }
  57.         WRITEREC(v, f, j, recsize);     /* write the last */
  58.     }
  59.     } while (h > 1);        /* end of do loop */
  60.  
  61.     free(v);
  62.     free(t);
  63.     printf("Shellsort: %ld reads, %ld writes.\n", rd_cnt, wt_cnt);
  64. }
  65.