home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / db12 / sort.c < prev    next >
Encoding:
Text File  |  1987-09-11  |  14.5 KB  |  648 lines
  1. /****************************************************************************/
  2. /*                                                                          */
  3. /*                 S O R T  -  Callable Sort Facility                       */
  4. /*                             (c) 1987 Ken Harris                          */
  5. /*                                                                          */
  6. /****************************************************************************/
  7. /*                                                                          */
  8. /*      This software is made available on an AS-IS basis. Unrestricted     */
  9. /*      use is granted provided that the copywrite notice remains in tack.  */
  10. /*      The author makes no warranties expressed or implied.                */
  11. /*                                                                          */
  12. /****************************************************************************/
  13.  
  14. char *copywrite = "sort v1.0 (c) 1987 Ken Harris";
  15.  
  16. #define  LINT_ARGS
  17. #include <stdio.h>
  18. #ifdef MSC
  19. #include <fcntl.h>
  20. #include <sys\types.h>
  21. #include <sys\stat.h>
  22. #include <ctype.h>
  23. #endif
  24.  
  25. #define SORT_CLOSED          0
  26. #define SORT_OPEN         1
  27. #define SORT_DONE         2
  28. #define SORT_EOF             3
  29. #define MIN_BUFFER_SIZE   1000
  30. #define MAX_BUFFER_SIZE  32000
  31.  
  32. struct sort_buffer
  33. {    int   sb_file;            /* file descriptor        */
  34.     long  sb_fcnt;            /* file block count        */
  35.     long  sb_fpos;            /* file position        */
  36.     char *sb_badr;            /* buffer address        */
  37.     long  sb_bsiz;            /* buffer size in bytes     */
  38.     long  sb_rsiz;            /* buffer size in records    */
  39.     long  sb_rcnt;            /* current record count     */
  40.     char *sb_radr;            /* current record address    */
  41. };
  42.  
  43. struct key_field
  44. {    struct key_field *kf_next;    /* next key field        */
  45.     char   kf_type;         /* field type  'A' = Ascii    */
  46.                     /*           'I' = Integer    */
  47.                     /*           'U' = Unsigned    */
  48.     char   kf_seq;            /* sort order  'A' = Ascending    */
  49.                     /*           'D' = Descending */
  50.     int    kf_pos;            /* starting position        */
  51.     int    kf_size;         /* field size            */
  52. };
  53.  
  54. static int  sfile1;            /* temp file #1         */
  55. static int  sfile2;            /* temp file #2         */
  56. static int  sfile3;            /* temp file #3         */
  57.  
  58. static int  sort_state = 0;        /* current state of the sort    */  
  59.                     /* 0 = Sort not initialized    */
  60.                     /* 1 = Sort is    initialized    */
  61.                     /* 2 = Sort has been done    */
  62.  
  63. static int  sort_rec_size;        /* Size of user data record    */
  64. static long sort_rec_cnt;        /* Record Count         */
  65. static int  sort_key_size;        /* Size of user key        */
  66. static int  sort_krec_size;        /* Size of key + control info    */   
  67. static long sort_merge_cnt;        /* count records in merge pass    */
  68. static long sort_next_fpos;        /* position of next file block    */
  69. static struct key_field *key_spec=NULL; /* sort key specs        */
  70. static char *sort_key_rec;
  71.  
  72. static struct sort_buffer sbuf1;    /* Sort buffer #1        */
  73. static struct sort_buffer sbuf2;    /* Sort buffer #2        */
  74. static struct sort_buffer sbuf3;    /* Sort buffer #3        */
  75.  
  76. long lseek();
  77.  
  78. /*
  79.  *    sort_init  -  Initialize the sort data
  80.  */
  81.  
  82. sort_init(rec_size, spec_str)
  83.  int   rec_size;
  84.  char *spec_str;
  85. {
  86. #ifdef MSC
  87.         unsigned _memavl();
  88. #endif
  89. #ifdef CI86
  90.     unsigned coreleft();
  91. #endif
  92.         long  buf_size;
  93.         char *calloc();
  94.  
  95.     if (sort_state != SORT_CLOSED)
  96.         sort_error("Sort Already Initialized");
  97.  
  98.     sort_rec_size    = rec_size;
  99.     bld_key_spec(spec_str);
  100.  
  101.         sort_krec_size  = sort_key_size + sizeof(long);
  102.     sort_krec_size += sort_krec_size % 2;
  103.     sort_rec_cnt    = 0;
  104.  
  105.         sort_key_rec = (char *) calloc(1,sort_key_size);
  106.  
  107. #ifdef MSC
  108.         sfile1 = open("SORT1.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  109.         sfile2 = open("SORT2.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  110.         sfile3 = open("SORT3.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  111. #endif
  112. #ifdef CI86
  113.     sfile1 = creat("SORT1.TMP",BUPDATE);
  114.     sfile2 = creat("SORT2.TMP",BUPDATE);
  115.     sfile3 = creat("SORT3.TMP",BUPDATE);
  116. #endif
  117.  
  118.     if (sfile1 < 0 || sfile2 < 0 || sfile3 < 0)
  119.         sort_error("Can't Open Temp Files");
  120.  
  121. #ifdef MSC
  122.         buf_size  = _memavl();
  123. #endif
  124. #ifdef CI86
  125.     buf_size  = coreleft();
  126. #endif
  127.     if (buf_size > MAX_BUFFER_SIZE) buf_size = MAX_BUFFER_SIZE;
  128.     buf_size  = (buf_size * 3)/4;
  129.     buf_size -= buf_size % sort_krec_size;
  130.  
  131.     if (buf_size < MIN_BUFFER_SIZE)
  132.         sort_error("Insufficient Memory");
  133.  
  134.         sbuf1.sb_badr = (char *) calloc(1,buf_size);
  135.     sbuf1.sb_bsiz = buf_size;
  136.     sbuf1.sb_rsiz = buf_size/sort_krec_size;
  137.     sbuf1.sb_radr = sbuf1.sb_badr;
  138.     sbuf1.sb_rcnt = 0;
  139.  
  140.     sort_state = SORT_OPEN;
  141. }                      
  142.  
  143. /*
  144.  *    bld_key_spec  -  Build Sort Key Spec
  145.  */
  146. bld_key_spec(s)
  147.  char *s;
  148. {
  149.         struct  key_field *f;
  150.         char   *calloc();
  151.  
  152.     sort_key_size = 0;
  153.     f = key_spec  = NULL;
  154.     while (*s)
  155.     {
  156.         if (!key_spec)
  157.                         key_spec = f = (struct key_field *) calloc(1,sizeof(struct key_field));
  158.         else
  159.                 {       f->kf_next = (struct key_field *) calloc(1,sizeof(struct key_field));
  160.             f = f->kf_next;
  161.         }
  162.  
  163.         f->kf_next = NULL;
  164.         if (islower(*s)) *s = _toupper(*s);
  165.         if (*s=='A' || *s=='D')
  166.             f->kf_seq = *s++;
  167.         else
  168.             sort_error("Invalid Key Spec - Unknown Sequence");
  169.  
  170.         if (islower(*s)) *s = _toupper(*s);
  171.         if (*s=='A' || *s=='I' || *s=='U' || *s=='R')
  172.             f->kf_type = *s++;
  173.         else
  174.             sort_error("Invalid Key Spec - Unknown Field Type");
  175.  
  176.         f->kf_pos=0;
  177.         while (isdigit(*s))
  178.             f->kf_pos = 10 * f->kf_pos + (*s++ - '0');
  179.  
  180.         if (f->kf_pos < 1)
  181.             sort_error("Invalid Sort Spec - Invalid Starting Position");
  182.  
  183.         if (*s++ != '.')
  184.             sort_error("Invalid Sort Spec - Missing Field Size");
  185.  
  186.         f->kf_size=0;
  187.         while (isdigit(*s))
  188.             f->kf_size = 10 * f->kf_size + (*s++ - '0');
  189.              
  190.         sort_key_size += f->kf_size;
  191.  
  192.         if (f->kf_pos + f->kf_size - 1 > sort_rec_size)
  193.             sort_error("Invalid Sort Spec - Field Exceeds Record");
  194.  
  195.         if (*s==',') s++;
  196.     }
  197. }
  198.  
  199. /*
  200.  *    sort_release  -  Release a record to the sort
  201.  */
  202.  
  203. sort_release(data)
  204.  char *data;
  205. {
  206.     int  sort_cmp();
  207.     long *k_cnt;
  208.     char *k_dat;
  209.  
  210.  
  211.     if (sort_state != SORT_OPEN)
  212.         sort_error("Improper Record Release");
  213.  
  214.     bld_sort_key(data);
  215.  
  216.     sort_rec_cnt++;
  217.     sort_write(sfile1, data, sort_rec_size);
  218.  
  219.     k_cnt  = (long *) sbuf1.sb_radr;
  220.     k_dat  = sbuf1.sb_radr + sizeof(long);
  221.     *k_cnt = sort_rec_cnt;
  222.     memcpy(k_dat, sort_key_rec, sort_key_size);
  223.  
  224.     sbuf1.sb_rcnt++;
  225.         if (sbuf1.sb_rcnt < sbuf1.sb_rsiz)
  226.         sbuf1.sb_radr += sort_krec_size;
  227.     else
  228.     {    qsort(sbuf1.sb_badr, (int)sbuf1.sb_rcnt, sort_krec_size, sort_cmp);
  229.         sort_write(sfile2, &sbuf1.sb_rcnt, sizeof(long));
  230.         sort_write(sfile2, sbuf1.sb_badr, sbuf1.sb_rcnt*sort_krec_size);
  231.         sbuf1.sb_rcnt = 0;
  232.         sbuf1.sb_radr = sbuf1.sb_badr;
  233.     }
  234. }
  235.  
  236.  
  237.  
  238.  
  239. /*
  240.  *    sort_cmp  -  sort compare function
  241.  */
  242.  sort_cmp(s1,s2)
  243.   char *s1, *s2;
  244. {
  245.     return(memcmp(s1+sizeof(long),s2+sizeof(long),sort_key_size));
  246. }
  247.  
  248. /*
  249.  *    bld_sort_key  -  Build the sort key record
  250.  */
  251.  
  252. bld_sort_key(data)
  253.  char *data;
  254. {
  255.     struct key_field *f;
  256.     char *s,*d;
  257.     int  i, tmp, cmpl;
  258.  
  259.     d = sort_key_rec;
  260.     f = key_spec;     
  261.  
  262.     while (f)
  263.     {
  264.         s = data + f->kf_pos - 1;
  265.  
  266.         switch(f->kf_type)
  267.         {    case 'A':      
  268.                 for (i=0; i < f->kf_size; i++)
  269.                     if (f->kf_seq == 'A')
  270.                         *d++ = *s++;
  271.                     else
  272.                         *d++ = ~*s++;
  273.                 break;
  274.  
  275.                         case 'U':
  276.                 s += f->kf_size - 1;
  277.  
  278.                                 for (i=0; i < f->kf_size; i++)
  279.                     if (f->kf_seq == 'A')
  280.                         *d++ = *s--;
  281.                     else
  282.                         *d++ = ~*s--;
  283.                 break;
  284.  
  285.             case 'I':
  286.                 s += f->kf_size - 1;
  287.  
  288.                                 if (f->kf_seq == 'A')
  289.                     *d++ = (*s--)^0200;
  290.                 else
  291.                     *d++ = ~((*s--)^0200);
  292.  
  293.                                 for (i=1; i < f->kf_size; i++)
  294.                     if (f->kf_seq == 'A')
  295.                         *d++ = *s--;
  296.                     else
  297.                         *d++ = ~*s--;
  298.  
  299.                                 break;
  300.  
  301.                         case 'R':
  302.                 s += f->kf_size - 1;
  303.  
  304.                 if (*s & 0200)
  305.                 {    cmpl = 1;
  306.                     tmp  = ~(*s--);
  307.                 }              
  308.                 else
  309.                 {    cmpl = 0;
  310.                     tmp  = (*s--) ^ 0200;
  311.                 }
  312.  
  313.                 if (f->kf_seq == 'D') 
  314.                 {    cmpl ^= 1;
  315.                     *d++  = ~tmp;
  316.                 }
  317.                 else
  318.                     *d++ = tmp;
  319.  
  320.                 for (i=1; i < f->kf_size; i++)
  321.                 {    if (cmpl)
  322.                         *d++ = ~*s--;
  323.                     else
  324.                         *d++ = *s--;
  325.                 }
  326.                                 break;
  327.  
  328.                         default: break;
  329.         }
  330.  
  331.         f = f->kf_next;
  332.     }
  333. }
  334.  
  335. /*
  336.  *    sort_merge  -  Do the merge
  337.  */
  338.  
  339. sort_merge()
  340. {
  341.     if (sort_state != SORT_OPEN)
  342.         sort_error("Merge Called Out of Sequence");
  343.  
  344.         if (!sort_rec_cnt)
  345.         {       sort_state = SORT_EOF;
  346.                 return;
  347.         }
  348.  
  349.     merge_init();
  350.  
  351.         while (sort_state != SORT_DONE)
  352.     {    lseek(sfile2, 0L, 0);
  353.         lseek(sfile3, 0L, 0);
  354.  
  355.         sort_merge_cnt = 0;
  356.         sort_next_fpos = 0;
  357.  
  358.         sbuf3.sb_radr = sbuf3.sb_badr;
  359.         sbuf3.sb_rsiz = sbuf3.sb_bsiz / sort_krec_size;
  360.         sbuf3.sb_rcnt = 0;
  361.  
  362.                 one_merge_pass();
  363.  
  364.         if (sort_merge_cnt != sort_rec_cnt)
  365.             sort_error("Merge Count Error");
  366.  
  367.         if (sort_state != SORT_DONE)
  368.         {    sbuf1.sb_file = sbuf3.sb_file;
  369.             sbuf3.sb_file = sbuf2.sb_file;
  370.             sbuf2.sb_file = sbuf1.sb_file;
  371.         }
  372.     }
  373.  
  374.     sort_merge_cnt = 0;
  375.     sort_next_fpos = 0;
  376.         sbuf1.sb_bsiz += sbuf2.sb_bsiz + sbuf3.sb_bsiz;
  377.         sbuf1.sb_rsiz =  sbuf1.sb_rcnt = 0;
  378.         sbuf1.sb_radr = NULL;
  379.     lseek(sbuf1.sb_file, 0L, 0);
  380.         get_merge_block(&sbuf1);
  381. }
  382.  
  383. static one_merge_pass()
  384. {
  385.         char *r1, *r2, *sort_read();
  386.     long block_size;
  387.  
  388.     while (sort_merge_cnt < sort_rec_cnt)
  389.     {    get_merge_block(&sbuf1);
  390.         get_merge_block(&sbuf2);
  391.  
  392.         if (sbuf1.sb_fcnt >= sort_rec_cnt)
  393.         {    sort_state = SORT_DONE;
  394.             return;
  395.         }
  396.  
  397.         block_size = sbuf1.sb_fcnt + sbuf2.sb_fcnt;
  398.         sort_write(sbuf3.sb_file, &block_size, sizeof(long));
  399.  
  400.         r1 = sort_read(&sbuf1);
  401.                 r2 = sort_read(&sbuf2);
  402.  
  403.         while (r1 && r2)
  404.         {    switch (sort_cmp(r1,r2))
  405.             {    case -1: merge_write(&sbuf1);
  406.                      r1 = sort_read(&sbuf1);
  407.                      break;
  408.  
  409.                 case  0: merge_write(&sbuf1);
  410.                      merge_write(&sbuf2);
  411.                      r1 = sort_read(&sbuf1);
  412.                      r2 = sort_read(&sbuf2);
  413.                      break;
  414.  
  415.                 case  1: merge_write(&sbuf2);
  416.                      r2 = sort_read(&sbuf2);
  417.                      break;
  418.             }
  419.         }
  420.         while (r1)
  421.         {    merge_write(&sbuf1);
  422.             r1 = sort_read(&sbuf1);
  423.         }
  424.  
  425.         while (r2)
  426.         {    merge_write(&sbuf2);
  427.             r2 = sort_read(&sbuf2);
  428.         }
  429.  
  430.         if (sbuf3.sb_rcnt)
  431.         {    sort_write(sbuf3.sb_file, sbuf3.sb_badr, sbuf3.sb_rcnt*sort_krec_size);
  432.             sbuf3.sb_rcnt = 0;
  433.             sbuf3.sb_radr = sbuf3.sb_badr;
  434.         }
  435.         }
  436. }
  437.  
  438. /*
  439.  *    merge_init  -  Merge Initialization
  440.  */
  441.  
  442. merge_init()
  443. {
  444.     unsigned int buf_size;
  445.  
  446.  
  447.     if (sbuf1.sb_rcnt)
  448.     {    qsort(sbuf1.sb_badr, (int)sbuf1.sb_rcnt, sort_krec_size, sort_cmp);
  449.         sort_write(sfile2, &sbuf1.sb_rcnt, sizeof(long));
  450.         sort_write(sfile2, sbuf1.sb_badr, sbuf1.sb_rcnt*sort_krec_size);
  451.         sbuf1.sb_rcnt = 0;
  452.         sbuf1.sb_radr = sbuf1.sb_badr;
  453.     }
  454.  
  455.     buf_size  = sbuf1.sb_bsiz / 3;
  456.     buf_size -= buf_size % sort_krec_size;         
  457.  
  458.     sbuf1.sb_bsiz = buf_size;
  459.     sbuf2.sb_bsiz = buf_size;
  460.     sbuf3.sb_bsiz = buf_size;
  461.  
  462.     sbuf2.sb_badr = sbuf1.sb_badr + buf_size;
  463.     sbuf3.sb_badr = sbuf2.sb_badr + buf_size;
  464.  
  465.         sbuf1.sb_rsiz = sbuf1.sb_rcnt = 0;
  466.         sbuf2.sb_rsiz = sbuf2.sb_rcnt = 0;
  467.         sbuf3.sb_rsiz = sbuf3.sb_rcnt = 0;
  468.  
  469.         sbuf1.sb_radr = NULL;
  470.         sbuf2.sb_radr = NULL;
  471.         sbuf3.sb_radr = NULL;
  472.  
  473.         sbuf1.sb_file = sfile2;
  474.     sbuf1.sb_fcnt = 0;
  475.     sbuf1.sb_fpos = 0L;
  476.  
  477.     sbuf2.sb_file = sfile2;
  478.     sbuf2.sb_fcnt = 0;
  479.     sbuf2.sb_fpos = 0L;
  480.  
  481.     sbuf3.sb_file = sfile3;
  482.     sbuf3.sb_fcnt = 0;
  483.     sbuf3.sb_fpos = 0L;
  484. }
  485.  
  486. /*
  487.  *    sort_return  -    return a record from the sort
  488.  */
  489.  
  490. char *sort_return(buf)
  491.  char *buf;
  492. {      
  493.     long *key;
  494.         char *sort_read();
  495.  
  496.         if (sort_state == SORT_EOF)
  497.     {    sort_close();
  498.         return(NULL);
  499.     }
  500.  
  501.     if (sort_state != SORT_DONE)
  502.         sort_error("Sort Return Sequence Error");
  503.  
  504.         key = (long *) sort_read(&sbuf1);
  505.  
  506.     if (!key)
  507.     {    sort_close();
  508.         return(NULL);
  509.     }
  510.  
  511.         lseek(sfile1, (long)((*key-1)*sort_rec_size), 0);
  512.         if (read(sfile1, buf, sort_rec_size) != sort_rec_size)
  513.         sort_error("Return Read Error");
  514.  
  515.         return(buf);
  516. }
  517.  
  518. /*
  519.  *    sort_read  -  Read record from merge buffer
  520.  */
  521.  
  522. static char *sort_read(buf)
  523.  struct sort_buffer *buf;
  524. {               
  525.     int cnt;
  526.  
  527.     if (buf->sb_rcnt < buf->sb_rsiz)
  528.     {    buf->sb_rcnt++;
  529.         buf->sb_radr += sort_krec_size;
  530.         return(buf->sb_radr);
  531.     }
  532.  
  533.     if (!buf->sb_fcnt) return(NULL);
  534.  
  535.     lseek(buf->sb_file, buf->sb_fpos, 0);
  536.  
  537.     buf->sb_rsiz = buf->sb_bsiz / sort_krec_size;
  538.     if (buf->sb_rsiz > buf->sb_fcnt)
  539.         buf->sb_rsiz = buf->sb_fcnt;
  540.  
  541.     if (read(buf->sb_file, buf->sb_badr, buf->sb_rsiz * sort_krec_size) <= 0)
  542.         sort_error("Temp File Read Error");
  543.     
  544.     buf->sb_fcnt   -= buf->sb_rsiz;
  545.     buf->sb_fpos   += buf->sb_rsiz * sort_krec_size;
  546.     buf->sb_rcnt    = 1;
  547.     buf->sb_radr    = buf->sb_badr;
  548.  
  549.     return(buf->sb_radr);
  550. }
  551.  
  552. /*
  553.  *    get_merge_block  -  Read up the next merge block
  554.  */
  555. get_merge_block(buf)
  556.  struct sort_buffer *buf;
  557. {
  558.     buf->sb_rsiz = 0;
  559.     buf->sb_rcnt = 0;
  560.     buf->sb_radr = 0;
  561.  
  562.         if (sort_merge_cnt >= sort_rec_cnt)
  563.     {    buf->sb_fcnt = 0;
  564.         return;
  565.     }
  566.  
  567.     lseek(buf->sb_file, sort_next_fpos, 0);
  568.     if (read(buf->sb_file, &buf->sb_fcnt, sizeof(long)) <= 0)
  569.         sort_error("Merge Read Error");
  570.  
  571.     buf->sb_fpos    = sort_next_fpos + sizeof(long);
  572.     sort_merge_cnt += buf->sb_fcnt;
  573.     sort_next_fpos += sizeof(long) + buf->sb_fcnt * sort_krec_size;
  574. }
  575.                                          
  576. /*
  577.  *    merge_write  -    merge output
  578.  */
  579.  
  580. static merge_write(buf)
  581.  struct sort_buffer *buf;
  582. {
  583.     memcpy(sbuf3.sb_radr, buf->sb_radr, sort_krec_size);
  584.  
  585.     sbuf3.sb_rcnt++;
  586.     if (sbuf3.sb_rcnt < sbuf3.sb_rsiz)
  587.         sbuf3.sb_radr += sort_krec_size;
  588.     else
  589.     {    sort_write(sbuf3.sb_file, sbuf3.sb_badr, sbuf3.sb_rcnt*sort_krec_size);
  590.         sbuf3.sb_rcnt = 0;
  591.         sbuf3.sb_radr = sbuf3.sb_badr;
  592.     }
  593. }
  594.  
  595. /*
  596.  *    sort_close  -  Cleanup after a sort
  597.  */
  598.  
  599. static sort_close()
  600. {
  601.     struct key_field *f, *t;
  602.  
  603.         if (sort_state == SORT_CLOSED) return;
  604.  
  605.     close(sfile1);
  606.     close(sfile2);
  607.     close(sfile3);
  608.  
  609.     unlink("SORT1.TMP");
  610.     unlink("SORT2.TMP");
  611.     unlink("SORT3.TMP");
  612.  
  613.         f = key_spec;
  614.     while (f)
  615.     {    t = f->kf_next;
  616.         free(f);
  617.         f = t;
  618.     }
  619.  
  620.         free(sort_key_rec);
  621.         free(sbuf1.sb_badr);
  622.  
  623.     sort_state = SORT_CLOSED;
  624. }
  625.  
  626. /*
  627.  *    sort_write  -  Write a reord to temp file
  628.  */
  629.  
  630. static sort_write(fd, buf, cnt)
  631.  int   fd, cnt;
  632.  char *buf;    
  633. {
  634.     if (write(fd, buf, cnt) < cnt)
  635.         sort_error("Write Error, Check Disk Space");
  636. }
  637.  
  638. /*
  639.  *    sort_error  -    Sort Error Exit
  640.  */
  641.  
  642. static sort_error(text)
  643.  char *text;
  644. {
  645.     fprintf(stderr,"\n\nSort Error: %s\7\n\n",text);
  646.     exit(1);
  647. }
  648.