home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 228_01 / isamsrt.c < prev    next >
Text File  |  1987-07-31  |  5KB  |  156 lines
  1. /*
  2. HEADER:         CUGXXX;
  3. TITLE:          Sort ISAM index (of ISAM system);
  4. DATE:           3-31-86;
  5. DESCRIPTION:    Part of ISAM Library;
  6. KEYWORDS:       ISAM;
  7. FILENAME:       ISAMSRT.C;
  8. WARNINGS:       None;
  9. AUTHORS:        John M. Dashner;
  10. COMPILER:       Lattice C;
  11. REFERENCES:     US-DISK 1310;
  12. ENDREF
  13. */
  14. /*
  15. **                 ISAMC - Written by John M. Dashner
  16. */
  17.  
  18. #include <stdio.h>
  19. #include <ctype.h>
  20.  
  21. #include <isam.h>
  22.  
  23. /*
  24. **                  SORT - Sort ISAMC Index (Reorganize)
  25. */
  26.  
  27. #define MAXSRT 2000     /* practical work size */
  28.  
  29. struct srt_wrk
  30. {
  31.     unsigned ptr;       /* data record pointer */
  32.     char  key[1];       /* beginning of key */
  33. };
  34.  
  35. struct srt_ptr
  36. {
  37.     struct srt_wrk *w[1];   /* symbolic definition of ptr array */
  38. };
  39.  
  40. isamsrt(hdr)
  41. struct isam *hdr;
  42. {
  43.     struct srt_ptr *s1;
  44.     struct srt_wrk *s2, *temp;
  45.     unsigned recs, n, off_set, beg, end;
  46.     int passes, pass, run, run_limit, i, r, r_sz, n1, n2, n3, n4, n5;
  47.     long lrec;
  48.  
  49.     if(hdr->q5 == 0) return NULL;    /* don't reorg if we don't need to */
  50.  
  51.     off_set = 0;    /* init run offset */
  52.     n = MAXSRT;     /* init sort work size */
  53.     recs = hdr->q1 - 1;
  54.     r_sz = hdr->q6 + 2;
  55.  
  56.     /* request a fair sized sort work area and accept something smaller */
  57.  
  58.     while(n && (s2 = (struct srt_wrk *) calloc(n, r_sz)) == NULL)
  59.         n = n * 9 / 10; /* reduce by approx 10% */
  60.  
  61.     if ((n < (recs / 50)) /* if sort work is less than 2% then give up */
  62.        || n == 0)
  63.     {
  64.         if (s2) free(s2);
  65.         isam_err = 9;
  66.         return ERROR;
  67.     }
  68.     /* now get a pointer array */
  69.     if((s1 = (struct srt_ptr *) malloc(n * sizeof(unsigned))) == NULL)
  70.     {
  71.         free(s2);
  72.         isam_err = 9;
  73.         return ERROR;
  74.     }
  75.     /* build array pointers */
  76.     for(i = 0; i < n; i++)
  77.         s1->w[i] = s2 + i * r_sz;
  78.  
  79.     if (recs > n)        /* calculate number of passes */
  80.         passes = ((recs * 2) - 1) / (n + 1);
  81.     else
  82.         passes = 1;
  83.  
  84.     for (pass = 0; pass < passes; pass++)   /* MAIN Sort Loop */
  85.     {
  86.         run_limit = (recs - off_set) / 
  87.                      n - (((recs - off_set) % n) > (n / 2)) - 1;
  88.         if (run_limit < 0)
  89.             run_limit = 0;
  90.  
  91.         for(run = 0; run <= run_limit; run++) /* SORT Run Loop */
  92.         {
  93.             beg = (run * n) + off_set + 1;   /* set start for this run */
  94.             end = beg + n - 1;               /* and end point */
  95.             if (end > recs)                  /* don't fall off the end */
  96.                 end = recs;
  97.             if (end < (beg + 1))    /* make sure we have something to do */
  98.                 continue;
  99.             for(i=0, r = beg; r <= end; i++, r++) /* Read a RUN Loop */
  100.             {
  101.                 lrec = (r + 1) * r_sz;    /* calc byte offset in file */
  102.                 lseek(hdr->q7, lrec, 0);
  103.                 if (read(hdr->q7, s1->w[i], r_sz) == ERROR)
  104.                 {
  105.                     free(s1);
  106.                     free(s2);
  107.                     isam_err = 8;
  108.                     return ERROR;
  109.                 }
  110.             }
  111.             n1 = end - beg + 1;         /* set up the sort */
  112.             n2 = n1 / 2;
  113.             while (n2)                  /* SORT Loop */
  114.             {
  115.                 n3 = n2 + 1;
  116. l1:             n4 = n3 - n2;
  117. l2:             n5 = n4 + n2;
  118.                 if (strncmp(&s1->w[n4]->key[0],
  119.                             &s1->w[n5]->key[0], hdr->q6) <= 0)
  120.                     goto l3;
  121.                 else
  122.                 {
  123.                     temp = s1->w[n4];
  124.                     s1->w[n4] = s1->w[n5];
  125.                     s1->w[n5] = temp;
  126.                 }
  127.                 n4 -= n2;
  128.                 if (n4 > 0) goto l2;
  129. l3:             n3++;
  130.                 if (n3 <= n1) goto l1;
  131.                 n2 /= 2;
  132.             }
  133.             for(i=0, r = beg; r <= end; i++, r++) /* Write a RUN Loop */
  134.             {
  135.                 lrec = (r + 1) * r_sz;    /* calc byte offset in file */
  136.                 lseek(hdr->q7, lrec, 0);
  137.                 if (write(hdr->q7, s1->w[i], r_sz) == ERROR)
  138.                 {
  139.                     free(s1);
  140.                     free(s2);
  141.                     isam_err = 8;
  142.                     return ERROR;
  143.                 }
  144.             }
  145.         }
  146.         if (off_set)
  147.             off_set = 0;
  148.         else
  149.             off_set = n / 2;
  150.     }
  151.     hdr->q5 = 0;                    /* now it's sorted */
  152.     hdr->q3 = hdr->q1 - hdr->q2;    /* update number in sorted portion */
  153.     return(isamupd(hdr));           /* update control rec & return */
  154. }
  155.  
  156.