home *** CD-ROM | disk | FTP | other *** search
/ gdead.berkeley.edu / gdead.berkeley.edu.tar / gdead.berkeley.edu / pub / cad-tools / ciftomann.tar / sort_dir / fmerge.c < prev    next >
C/C++ Source or Header  |  1988-01-28  |  2KB  |  125 lines
  1. #include "sort.h"
  2. #include "sort_thing.h"
  3. #include <stdio.h>
  4.  
  5. #define OK 1
  6.  
  7. #define READ_ITEM(i)\
  8. ( fread( &value[i].item, sizeof(thing), 1, value[i].desc )\
  9.         != 0 ? OK : EOF )
  10.  
  11. #define FILE_INDEX(ptr) (((ptr) - value))
  12.  
  13. typedef struct {
  14.     FILE *desc;
  15.     thing item;
  16. } value_type;
  17.  
  18. value_type value[MAX_FILES + 1];
  19. value_type *heap[MAX_FILES + 1];
  20.  
  21. int ourcomparer();
  22. FILE *open_file();
  23.  
  24. extern FILE *outfile_desc;
  25.  
  26.     /*
  27.      *    merge the files start through end into one single file using
  28.      *    a heap sort to do the merging
  29.      */
  30.  
  31. merge(start,end)
  32. int start,end;
  33. {
  34.     
  35.     int index,num_files;
  36.     value_type *top;
  37.  
  38.     num_files = 1;
  39.  
  40.     for(index = start; index <= end; index++) {
  41.  
  42.     value[num_files].desc = open_file(index);
  43.     heap[num_files] = &value[num_files];
  44.  
  45.     if ( READ_ITEM(num_files) == OK ) {
  46.         num_files++;
  47.     }
  48.     }
  49.  
  50.     num_files--;
  51.  
  52.     qsort((char *) &(heap[1]),num_files,sizeof(thing *),ourcomparer);
  53.  
  54.     while (num_files > 0) {
  55.     
  56.     top = heap[1];
  57.     index = FILE_INDEX(top);
  58.  
  59.     fwrite(&(top->item), sizeof(thing), 1, outfile_desc);
  60.  
  61.     if ( READ_ITEM( index ) == EOF) {
  62.         heap[1] = heap[num_files];
  63.         num_files--;
  64.     }
  65.  
  66.     reheap(num_files);
  67.     }
  68.  
  69.     remove_files(start,end);
  70. }
  71.  
  72. value_type *temp;
  73.  
  74. #define EXCHANGE(a,b) {temp = (a); (a) = (b); (b) = temp;}
  75.  
  76.     /*
  77.      * reorder the heap after the insertion of a new element at 
  78.      * the top 
  79.      */
  80.  
  81. reheap(num_files)
  82. int num_files;
  83. {
  84.  
  85.     int current,child;
  86.  
  87.     current = 1;
  88.     child = 2;
  89.  
  90.     while ( child <= num_files ) {
  91.     
  92.     if (child+1 <= num_files) {
  93.         if (comparer(&heap[child]->item,&heap[child+1]->item) > 0) {
  94.         child++;
  95.         }
  96.     }
  97.  
  98.     if (comparer(&heap[current]->item,&heap[child]->item) <= 0) {
  99.         break;
  100.     }
  101.  
  102.     EXCHANGE(heap[child],heap[current]);
  103.  
  104.     current = child;
  105.     child = 2*current;
  106.     }
  107. }
  108.  
  109. ourcomparer(aptr_ptr,bptr_ptr)
  110. value_type **aptr_ptr,**bptr_ptr;
  111. {
  112.     return(comparer(&(*aptr_ptr)->item,&(*bptr_ptr)->item));
  113. }
  114.  
  115. remove_files(first,last)
  116. int first,last;
  117. {
  118.     int index;
  119.  
  120.     for (index = first; index <= last; index++) {
  121.     remove_file(index);
  122.     fclose(value[index - first + 1].desc);
  123.     }
  124. }
  125.