home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c160 / 1.ddi / SOURCE / U4SORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-22  |  10.5 KB  |  415 lines
  1. /* (c)Copyright Sequiter Software Inc., 1987-1990. All rights reserved.
  2.  
  3.   u4sort.c
  4.  
  5.   Sort and Spool Module
  6. */
  7.  
  8. #include "p4misc.h"
  9. #include "d4all.h"
  10. #include "u4error.h"
  11.  
  12. #include <string.h>
  13. #include <stdio.h>
  14. #ifndef UNIX
  15. #include <io.h>
  16. #endif
  17.  
  18. #define  MAX_SPOOLS 300 
  19.  
  20. typedef struct spool_st
  21. {
  22.    char H_PTR  ptr ;       /* Pointer to the current buffer position */
  23.    char H_PTR  end ;       /* Pointer to the end buffer position */
  24.    long        disk ;      /* Current Disk Position, Offset from start of 'spool'
  25.                   >= 'spool_bytes' means nothing is on disk. */
  26.    short       spool_i ;   /* The spool number of this spool */
  27.    short       dummy ;     /* To make 0x10000 divisiable by sizeof(SPOOL) */
  28. }  SPOOL ;
  29.  
  30. static unsigned  width_sort ;     /* The width of each records sort information. */
  31. static unsigned  width_add ;      /* The width of additional information */
  32. static unsigned  width_total ;    /* The total spool record width */
  33.  
  34. static long  spool_num_rec; /* The number of records in each spool set */
  35. static long  spool_bytes ;  /* The number of bytes in each spool record set */
  36. static short spool_num ;    /* The number of spools */
  37. static short spool_i ;      /* The spool currently being written to. */
  38. static int   spool_handle = -1 ; /* The handle to the spool file */
  39. static char  spool_name[9]; /* The name of the spool file */
  40. SPOOL H_PTR  spool ;        /* Each element of the spool array describes a 'spool' */
  41.  
  42. static long  sub_bytes ;    /* The number of bytes in each sub-spool */
  43. static long  sub_num_rec ;  /* The number of spool records in each sub-spool */
  44. static short sub_index ;    /* An index into 'spool' of the smallest value */
  45. static short first_spool_get ;
  46.  
  47. static char H_PTR        huge_buffer = 0 ;
  48. static char H_PTR H_PTR  huge_pointers = 0 ; /* A huge array of huge pointers */
  49. static long              i_pointers = 0L ;
  50.  
  51. static int  u4spool( long, int ) ;
  52. static int  u4spool_read(short) ;
  53. static int  u4sort_alloc( short, long, int ) ;
  54.  
  55. static  H4BUF  saved_status = { -1L, -1L, -1L, 0 } ;
  56.  
  57. extern int  v4cur_base ;
  58.  
  59. /* Generic Spool and Merge,  
  60.  
  61.    Format: Sort Data, Related Info. 
  62.  
  63.    Sorted information comes first.
  64. */
  65.  
  66. int  u4sort_init( long num_records, int sort_width, int info_width )
  67. {
  68.    short  i ;
  69.  
  70.    d4buf_save_status( &saved_status ) ;
  71.  
  72.    /* Sort Initialization Starts Now */
  73.    width_sort =  sort_width ;
  74.    width_add  =  info_width ;
  75.    width_total=  sort_width + info_width ;
  76.  
  77.    first_spool_get =  1 ;
  78.    spool_handle  = -1 ;
  79.    i_pointers = 0L ;
  80.  
  81.    if ( u4sort_alloc( 0, num_records, width_total) == 0 )  return 0 ;
  82.  
  83.    for( i = 2; i <= MAX_SPOOLS; i++ )
  84.    {
  85.       d4buf_restore_status( &saved_status ) ;
  86.       if ( u4sort_alloc( i, num_records, width_total) == 0 )  return i ;
  87.    }
  88.  
  89.    u4sort_free() ;
  90.    return -2 ;
  91. }
  92.  
  93. static int  u4sort_alloc( short num_spools, long tot_records, int tot_width )
  94. {
  95.    long  i_rec ;
  96.    union
  97.    {
  98.       char H_PTR  p ;
  99.       char H_PTR H_PTR  pp ;
  100.    } ptr ;
  101.  
  102.    spool_i   = 0 ;
  103.    spool_num =  num_spools ;
  104.    if ( num_spools <= 1 )
  105.       spool_num_rec =  tot_records ;
  106.    else
  107.       spool_num_rec =  (tot_records+num_spools-1)/num_spools ;
  108.    spool_bytes   =  spool_num_rec * width_total ;
  109.  
  110.    /* Note: One extra record of space for the quick sort algorithim. */
  111.    ptr.p =  (char H_PTR) d4buf_alloc( spool_num_rec+1, sizeof(char H_PTR) ) ;
  112.    if ( ptr.p == (char H_PTR) 0 )  return -1 ;
  113.    huge_pointers =  ptr.pp ;
  114.  
  115.    spool =  (SPOOL H_PTR) d4buf_alloc( (long) spool_num, sizeof(SPOOL)) ;
  116.    if ( spool == (SPOOL H_PTR) 0)  return -1 ;
  117.  
  118.    huge_pointers[0] =
  119.    huge_buffer = (char H_PTR) d4buf_alloc((long) (spool_num_rec+1)*tot_width, 1);
  120.    if ( huge_buffer == (char H_PTR) 0 )  return -1 ;
  121.  
  122.    for ( i_rec = 1L; i_rec <= spool_num_rec; i_rec++ )
  123.       huge_pointers[i_rec] =  (char *) u4huge_norm(huge_pointers[i_rec-1] + tot_width) ;
  124.  
  125.    d4buf_sub_set() ;
  126.    return 0 ;
  127. }
  128.  
  129.  
  130. int  u4sort_add( char *sort_data_ptr, char *info_ptr )
  131. {
  132.    if ( i_pointers < spool_num_rec )
  133.    {
  134.       memcpy( (char *) huge_pointers[i_pointers], sort_data_ptr, (size_t) width_sort ) ;
  135.       memcpy( (char *)(huge_pointers[i_pointers++]+width_sort), info_ptr, (size_t) width_add ) ;
  136.    }
  137.    else
  138.    {
  139.       if ( u4spool( spool_num_rec, 0 ) < 0 )  return -1 ;
  140.       i_pointers = 0L ;
  141.       u4sort_add( sort_data_ptr, info_ptr ) ;
  142.    }
  143.  
  144.    return 0 ;
  145. }
  146.  
  147.  
  148. /*  u4spool
  149.  
  150.    -  'ptr' points to a big block of memory which is to be spooled.
  151.    -  'num_items' must always be less than or equal to the first
  152.       'num_items' value.
  153. */
  154.  
  155. static int  u4spool( long num_rec, int is_last )
  156. {
  157.    long   write_bytes, i_on, i_free ;
  158.    char   H_PTR i_on_ptr, H_PTR free_pointer ;
  159.    short  i ;
  160.  
  161.    spool_i++ ;
  162.  
  163.    /* Sort the spool items. */
  164.    u4sort_quick( huge_pointers, num_rec, width_sort );
  165.  
  166.    if ( is_last )
  167.    {
  168.       if ( spool_i == 1)
  169.       {
  170.          /* First and Last time through 'u4spool' */
  171.          /* No need to spool to disk.  Initialize for 'u4sort_get' */
  172.      spool_num =  0 ;
  173.          spool_num_rec =  i_pointers ;
  174.      return 0 ;
  175.       }
  176.  
  177.       sub_index =  0 ;
  178.    }
  179.  
  180.    write_bytes =  i_pointers * width_total ;
  181.  
  182.    if ( spool_i > spool_num )
  183.    {
  184.       u4error( E_SORT_ADD, (char *) 0 ) ;
  185.       u4sort_free() ;
  186.       return -1 ;
  187.    }
  188.  
  189.    if ( spool_i == 1 )
  190.    {
  191.       /* First time through 'u4spool' */
  192.       /* Open the temporary File */
  193.       strcpy( spool_name, "T4" ) ;
  194.       if ( (spool_handle =  u4temp_create(spool_name)) < 0 )
  195.       {
  196.      u4sort_free() ;
  197.          return -1 ;
  198.       }
  199.       lseek( spool_handle, 0L, 0) ;
  200.    }
  201.  
  202.    /* Make the Sorted Values Consecutive in Memory */
  203.    for( i_on = 0L, i_on_ptr = huge_buffer; i_on < i_pointers; )
  204.    {
  205.       if ( huge_pointers[i_on] == i_on_ptr )
  206.       {
  207.          i_on_ptr += width_total ;
  208.      i_on++ ;
  209.      continue ;
  210.       }
  211.  
  212.       u4huge_cpy( huge_pointers[spool_num_rec], huge_pointers[i_on], (long) width_total) ;
  213.  
  214.       free_pointer =  huge_pointers[i_on] ;
  215.       huge_pointers[i_on] =  huge_pointers[spool_num_rec] ;
  216.  
  217.       do
  218.       {
  219.          i_free =  (free_pointer - huge_buffer) / width_total ;
  220.      u4huge_cpy( free_pointer, huge_pointers[i_free], (long) width_total) ;
  221.      free_pointer =  huge_pointers[i_free] ;
  222.      huge_pointers[i_free] =  huge_buffer + i_free*width_total ;
  223.       }    while ( free_pointer != huge_pointers[spool_num_rec] ) ;
  224.    }
  225.  
  226.    if ( u4huge_write( spool_handle, huge_buffer, write_bytes) < 0)
  227.    {
  228.       u4sort_free() ;
  229.       return -1 ;
  230.    }
  231.  
  232.    if ( is_last )
  233.    {
  234.       spool_num  =  spool_i ;
  235.       sub_bytes  =  spool_bytes / spool_num ;
  236.       sub_num_rec=  sub_bytes / width_total ;
  237.       sub_bytes  =  sub_num_rec * width_total ;
  238.  
  239.       if ( sub_num_rec == 0L )
  240.       {
  241.      u4error( E_MEMORY, "Reindexing a File", (char *) 0 ) ;
  242.      u4sort_free() ;
  243.      return -1 ;
  244.       }
  245.  
  246.       /* Initialize for the calls to 'u4sort_get' */
  247.       for ( i=0; i< spool_num; i++ )
  248.       {
  249.      spool[i].disk =  0L ;
  250.      spool[i].spool_i =  i ;
  251.      if ( u4spool_read(i) < 0 )  return -1 ;
  252.       }
  253.    }
  254.    return 0 ;
  255. }
  256.  
  257.  
  258. /*  u4spool_read
  259.  
  260.    Returns
  261.  
  262.        0  OK
  263.       -1  Error
  264. */
  265.  
  266. static  int u4spool_read(short sub_index)
  267. {
  268.    long  bytes_read, ask_read ;
  269.  
  270.    /* Is there anything still on disk ? */
  271.    if ( spool[sub_index].disk >= spool_bytes )
  272.    {
  273.       if ( spool_num > 0)
  274.       {
  275.      /* Nothing left for Buffer */
  276.      u4huge_cpy( spool+sub_index, spool+sub_index+1,
  277.                   (long) sizeof(SPOOL)*(spool_num-sub_index-1) ) ;
  278.      spool_num-- ;
  279.       }
  280.       return( 0) ;
  281.    }
  282.  
  283.    spool[sub_index].ptr = (char H_PTR) u4huge_norm( huge_buffer+ spool[sub_index].spool_i*sub_bytes) ;
  284.  
  285.    ask_read =  spool_bytes - spool[sub_index].disk ;
  286.    if (ask_read > sub_bytes)  ask_read =  sub_bytes ;
  287.  
  288.    /* Read in the rest of the buffer from disk */
  289.    lseek( spool_handle, 
  290.           spool[sub_index].spool_i*spool_bytes+ spool[sub_index].disk, 0) ;
  291.    bytes_read = u4huge_read( spool_handle, spool[sub_index].ptr, ask_read ) ;
  292.    if ( bytes_read < 0L)  
  293.    {
  294.       u4sort_free() ;
  295.       return -1 ;
  296.    }
  297.  
  298.    /* Check for Error */
  299.    if ( bytes_read % width_total  != 0 )
  300.    {
  301.       u4error( E_READ, "Temporary Spool File:", spool_name, (char *) 0 ) ;
  302.       u4sort_free() ;
  303.       return -1 ;
  304.    }
  305.  
  306.    if ( bytes_read < sub_bytes )
  307.    {
  308.       spool[sub_index].disk =  spool_bytes ; /* Flag nothing on disk. */
  309.  
  310.       if ( bytes_read == 0L )
  311.          /* Nothing on disk and nothing in memory. */
  312.          return( u4spool_read(sub_index) ) ;
  313.    }
  314.    else
  315.       spool[sub_index].disk +=  bytes_read ;
  316.  
  317.    spool[sub_index].end =  spool[sub_index].ptr + bytes_read ;
  318.  
  319.    return 0 ;
  320. }
  321.  
  322.  
  323. /* u4sort_get
  324.  
  325.    Returns
  326.  
  327.       0 -  OK
  328.      -1 -  Error
  329.      -2 -  None Left
  330. */
  331.  
  332. int  u4sort_get( char H_PTR *ptr_ptr ) 
  333. {
  334.    char H_PTR  current ;
  335.    int      i ;
  336.  
  337.    if ( first_spool_get )
  338.    {
  339.       first_spool_get =  0 ;
  340.       if ( u4spool( i_pointers, 1 ) < 0 )  return -1 ;
  341.  
  342.       i_pointers = 0L ;
  343.    }
  344.  
  345.    *ptr_ptr = (char H_PTR) 0 ;
  346.    if ( spool_num < 0 )   return 0 ;
  347.  
  348.    if ( spool_num == 0 )
  349.    {
  350.       /* Get from the memory buffer which has never been spooled */
  351.       if (i_pointers >= spool_num_rec )
  352.       {
  353.      spool_num =  -1 ;
  354.      u4sort_free() ;
  355.       }
  356.       else
  357.          *ptr_ptr =  huge_pointers[i_pointers++] ;
  358.  
  359.       return  0 ;
  360.    }
  361.  
  362.    /* Check to make sure the last buffer accessed is up to date. */
  363.    if ( (char H_PTR) spool[sub_index].ptr >= (char H_PTR) spool[sub_index].end )
  364.       if ( u4spool_read(sub_index) < 0 )   return  -1 ;
  365.  
  366.    if ( spool_num <= 0 )
  367.    {
  368.       u4sort_free() ;
  369.       return 0 ;  /* Nothing left */
  370.    }
  371.  
  372.    /* Search for the smallest value.  If the values are equal, use the
  373.       first spool value. */
  374.  
  375.    current   =  spool[0].ptr ;
  376.    sub_index =  0 ;
  377.  
  378.    for ( i= 1; i< spool_num; i++ )
  379.    {
  380.       if ( u4huge_cmp( (unsigned char H_PTR) current, 
  381.                        (unsigned char H_PTR) spool[i].ptr, width_sort) > 0 )
  382.       {
  383.      current   =  spool[i].ptr ;
  384.      sub_index =  i ;
  385.       }
  386.    }
  387.  
  388.    *ptr_ptr =  spool[sub_index].ptr ;
  389.    spool[sub_index].ptr +=  width_total ;
  390.  
  391.    return 0 ;
  392. }
  393.  
  394.  
  395. void  u4sort_free()
  396. {
  397.    if ( spool_handle >= 0 )
  398.    {
  399.       close( spool_handle ) ;
  400.       spool_handle =  -1 ;
  401.       u4remove(spool_name) ;
  402.    }
  403.  
  404.    if ( saved_status.len >= 0L )
  405.    {
  406.       d4buf_restore_status( &saved_status ) ;
  407.       saved_status.len = -1L ;
  408.    }
  409.  
  410.    huge_pointers =  (char H_PTR H_PTR) 0 ;
  411.    spool_num =  -1 ;
  412. }
  413.  
  414.  
  415.