home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / maint / part01 / sort.c < prev   
Encoding:
C/C++ Source or Header  |  1992-05-13  |  10.2 KB  |  410 lines
  1. /******************************************************************************
  2. *******************************************************************************
  3.  
  4.    Site:    Western Michigan University Academic Computer Center
  5.  
  6.    System:    Directory/File System Maintenance
  7.   
  8.    Program:    maint
  9.  
  10.    Version=01    Level=00    01/24/92    Leonard J. Peirce
  11.  
  12.    Purpose:    Sort routines for the different sort options.
  13.  
  14.    Arguments:    See individual routines.
  15.  
  16.    External variables:    None
  17.  
  18.    External functions:
  19.  
  20.           Defined:    date_qsort, name_qsort, size_qsort, sort_files
  21.  
  22.           Called:    None
  23.  
  24.    Files accessed:    See individual routines.
  25.  
  26.    Return codes:    See individual routines.
  27.  
  28.    Compiling instructions:    See Makefile
  29.  
  30.    Linking instructions:    See Makefile
  31.  
  32.    Other information:    (C) Copyright 1992, Leonard J. Peirce
  33.  
  34. ********************************************************************************
  35. *******************************************************************************/
  36.  
  37. /******************************************************************************/
  38. /*                                                                            */
  39. /*                        # I N C L U D E   F I L E S                         */
  40. /*                                                                            */
  41. /******************************************************************************/
  42.  
  43. #include <string.h>
  44. #include "maint.h"
  45.  
  46. /******************************************************************************/
  47. /*                                                                            */
  48. /*                             # D E F I N E S                                */
  49. /*                                                                            */
  50. /******************************************************************************/
  51.  
  52. /******************************************************************************/
  53. /*                                                                            */
  54. /*          S T R U C T U R E S ,   U N I O N S ,   T Y P E D E F S           */
  55. /*                                                                            */
  56. /******************************************************************************/
  57.  
  58. /******************************************************************************/
  59. /*                                                                            */
  60. /*   E X T E R N A L   D E F I N I T I O N S   &   D E C L A R A T I O N S    */
  61. /*                                                                            */
  62. /******************************************************************************/
  63.  
  64. extern     ENT_DEF  *baseptr;
  65.  
  66.      void      date_qsort(),
  67.           size_qsort(),
  68.           name_qsort(),
  69.           sort_files();
  70.  
  71. /******************************************************************************/
  72. /*                                                                            */
  73. /*     S T A T I C   D E F I N I T I O N S   &   D E C L A R A T I O N S      */
  74. /*                                                                            */
  75. /******************************************************************************/
  76.  
  77. static     void      swap_entries();
  78.  
  79. /*******************************************************************************
  80. ********************************************************************************
  81.  
  82.   Function:    size_qsort
  83.  
  84.   Purpose:    Sort the directory entries by size.
  85.  
  86.         Algorithm for quicksort from "Fundamentals of Data Structures",
  87.         Ellis Horowitz and Sartaj Sahni, page 137.
  88.  
  89.   Global variables:
  90.  
  91.     Name            Examine/Modify/Use/Read/Write
  92.     ----            -----------------------------
  93.     baseptr                    X
  94.  
  95.   Return Codes:
  96.  
  97.     Code            Reason
  98.     ----            ------
  99.     none
  100.  
  101. ********************************************************************************
  102. *******************************************************************************/
  103.  
  104. void size_qsort(m,n)
  105.                     /*******   FORMAL  PARAMETERS   *******/
  106. register short      m,            /* lower-bound of sub-array to be     */
  107.                     /* sorted                  */
  108.           n;            /* upper-bound of sub-array to be     */
  109.                     /* sorted                  */
  110.  
  111. {    /*** size_qsort ***/
  112.                     /********   LOCAL  VARIABLES   ********/
  113. register short      i,            /* loop and array index              */
  114.           j;            /*  "    "    "     "              */
  115. static     u_long      key;            /* key size entry for sorting          */
  116.  
  117.  
  118.    if(m < n)
  119.    {
  120.       i = m;
  121.       j = n + 1;
  122.       key = baseptr[m].size;
  123.  
  124.       for(;;)
  125.       {
  126.      do
  127.      {
  128.         ++i;
  129.      }
  130.      while(baseptr[i].size < key);
  131.  
  132.      do
  133.      {
  134.         --j;
  135.      }
  136.      while(baseptr[j].size > key);
  137.  
  138.      if(i < j)
  139.      {
  140.         /* swap the file entries */
  141.  
  142.         swap_entries(&baseptr[i],&baseptr[j]);
  143.      }
  144.      else
  145.         break;
  146.  
  147.       } /* for(;;) */
  148.  
  149.       swap_entries(&baseptr[m],&baseptr[j]);
  150.       size_qsort(m,j-1);
  151.       size_qsort(j+1,n);
  152.  
  153.    } /* if(m < n) */
  154.  
  155.    return;
  156.  
  157. }    /*** size_qsort ***/
  158.  
  159. /*******************************************************************************
  160. ********************************************************************************
  161.  
  162.   Function:    date_qsort
  163.  
  164.   Purpose:    Sort the directory entries by last access date.
  165.  
  166.         Algorithm for quicksort from "Fundamentals of Data Structures",
  167.         Ellis Horowitz and Sartaj Sahni, page 137.
  168.  
  169.   Global variables:
  170.  
  171.     Name            Examine/Modify/Use/Read/Write
  172.     ----            -----------------------------
  173.     baseptr                    X
  174.  
  175.   Return Codes:
  176.  
  177.     Code            Reason
  178.     ----            ------
  179.     none
  180.  
  181. ********************************************************************************
  182. *******************************************************************************/
  183.  
  184. void date_qsort(m,n)
  185.                     /*******   FORMAL  PARAMETERS   *******/
  186. register short      m,            /* lower-bound of sub-array to be     */
  187.                     /* sorted                  */
  188.           n;            /* upper-bound of sub-array to be     */
  189.                     /* sorted                  */
  190.  
  191. {    /*** date_qsort ***/
  192.                     /********   LOCAL  VARIABLES   ********/
  193. register short      i,            /* loop and array index              */
  194.           j;            /*  "    "    "     "              */
  195. static     time_t      key;            /* key size entry for sorting          */
  196.  
  197.  
  198.    if(m < n)
  199.    {
  200.       i = m;
  201.       j = n + 1;
  202.       key = baseptr[m].time;
  203.  
  204.       for(;;)
  205.       {
  206.      do
  207.      {
  208.         ++i;
  209.      }
  210.      while(baseptr[i].time < key);
  211.  
  212.      do
  213.      {
  214.         --j;
  215.      }
  216.      while(baseptr[j].time > key);
  217.  
  218.      if(i < j)
  219.      {
  220.         /* swap the file entries */
  221.  
  222.         swap_entries(&baseptr[i],&baseptr[j]);
  223.      }
  224.      else
  225.         break;
  226.  
  227.       } /* for(;;) */
  228.  
  229.       swap_entries(&baseptr[m],&baseptr[j]);
  230.       date_qsort(m,j-1);
  231.       date_qsort(j+1,n);
  232.  
  233.    } /* if(m < n) */
  234.  
  235.    return;
  236.  
  237. }    /*** date_qsort ***/
  238.  
  239. /*******************************************************************************
  240. ********************************************************************************
  241.  
  242.   Function:    swap_entries
  243.  
  244.   Purpose:    Swap two file entries.
  245.  
  246.   Global variables:
  247.  
  248.     Name            Examine/Modify/Use/Read/Write
  249.     ----            -----------------------------
  250.     none
  251.  
  252.   Return Codes:
  253.  
  254.     Code            Reason
  255.     ----            ------
  256.     none
  257.  
  258. ********************************************************************************
  259. *******************************************************************************/
  260.  
  261. static void swap_entries(a,b)
  262.                     /*******   FORMAL  PARAMETERS   *******/
  263.      ENT_DEF  *a,            /* first to be swapped               */
  264.           *b;            /* other entry to be swapped          */
  265.  
  266. {    /*** swap_entries ***/
  267.                     /********   LOCAL  VARIABLES   ********/
  268. static     ENT_DEF  temp;            /* temporary entry for swapping          */
  269.  
  270.    memcpy((char *) &temp,(char *) a, sizeof(temp));
  271.    memcpy((char *) a,(char *) b, sizeof(temp));
  272.    memcpy((char *) b,(char *) &temp, sizeof(temp));
  273.  
  274. }    /*** swap_entries ***/
  275.  
  276. /*******************************************************************************
  277. ********************************************************************************
  278.  
  279.   Function:    name_qsort
  280.  
  281.   Purpose:    Sort the directory entries by filename.
  282.  
  283.         Algorithm for quicksort from "Fundamentals of Data Structures",
  284.         Ellis Horowitz and Sartaj Sahni, page 137.
  285.  
  286.   Global variables:
  287.  
  288.     Name            Examine/Modify/Use/Read/Write
  289.     ----            -----------------------------
  290.     baseptr                    X
  291.  
  292.   Return Codes:
  293.  
  294.     Code            Reason
  295.     ----            ------
  296.     none
  297.  
  298. ********************************************************************************
  299. *******************************************************************************/
  300.  
  301. void name_qsort(m,n)
  302.                     /*******   FORMAL  PARAMETERS   *******/
  303. register short      m,            /* lower-bound of sub-array to be     */
  304.                     /* sorted                  */
  305.           n;            /* upper-bound of sub-array to be     */
  306.                     /* sorted                  */
  307.  
  308. {    /*** name_qsort ***/
  309.                     /********   LOCAL  VARIABLES   ********/
  310. register short      i,            /* loop and array index              */
  311.           j;            /*  "    "    "     "              */
  312. static     char      *key;            /* pointer to key value              */
  313.  
  314.  
  315.    if(m < n)
  316.    {
  317.       i = m;
  318.       j = n + 1;
  319.       key = (baseptr+m)->filename;    /* get pointer to filename key          */
  320.  
  321.       for(;;)
  322.       {
  323.      do
  324.      {
  325.         ++i;
  326.      }
  327.      while(strcmp((baseptr+i)->filename,key) < 0);
  328.  
  329.      do
  330.      {
  331.         --j;
  332.      }
  333.      while(strcmp((baseptr+j)->filename,key) > 0);
  334.  
  335.      if(i < j)
  336.      {
  337.         /* swap the pointers to the filenames and the flags that indicate
  338.          * whether or not the filename is too long for all of it to be
  339.          * displayed on the screen
  340.          */
  341.  
  342.         swap_entries(&baseptr[i],&baseptr[j]);
  343.      }
  344.      else
  345.         break;
  346.  
  347.       } /* for(;;) */
  348.  
  349.       swap_entries(&baseptr[m],&baseptr[j]);
  350.       name_qsort(m,j-1);
  351.       name_qsort(j+1,n);
  352.  
  353.    } /* if(m < n) */
  354.  
  355.    return;
  356.  
  357. }    /*** name_qsort ***/
  358.  
  359. /*******************************************************************************
  360. ********************************************************************************
  361.  
  362.   Function:    sort_files
  363.  
  364.   Purpose:    Sort the directory based on the sort type.
  365.  
  366.   Global variables:
  367.  
  368.     Name            Examine/Modify/Use/Read/Write
  369.     ----            -----------------------------
  370.     baseptr                    X
  371.  
  372.   Return Codes:
  373.  
  374.     Code            Reason
  375.     ----            ------
  376.     none
  377.  
  378. ********************************************************************************
  379. *******************************************************************************/
  380.  
  381. void sort_files(num_file,sort_type)
  382.                     /*******   FORMAL  PARAMETERS   *******/
  383.     short      num_file,        /* number of files in directory          */
  384.           sort_type;        /* field to sort on              */
  385.  
  386. {    /*** sort_files ***/
  387.  
  388.  
  389.    switch(sort_type)
  390.    {
  391.       case(FILENAME):
  392.      name_qsort(0,num_file);
  393.      break;
  394.  
  395.       case(DATE):
  396.      date_qsort(0,num_file);
  397.      break;
  398.  
  399.       case(SIZE):
  400.      size_qsort(0,num_file);
  401.      break;
  402.  
  403.       default:
  404.      break;
  405.    }
  406.  
  407.    return;
  408.  
  409. }    /*** sort_files ***/
  410.