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