home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / smapp100.zip / sm10.zip / smgsortf.c < prev    next >
C/C++ Source or Header  |  2000-05-14  |  15KB  |  508 lines
  1. /* ------------------------------------------------------------------------
  2.  *
  3.  *        File: smgsortf.c
  4.  *     Project: Source Mapper.
  5.  *     Created: June 8, 1992.
  6.  * Description: Modul for å sortere elementer i fil.
  7.  *
  8.  * Copyright (C) 2000 Leif-Erik Larsen.
  9.  * This file is part of the Source Mapper source package.
  10.  * Source Mapper is free software; you can redistribute it and/or modify
  11.  * it under the terms of the GNU General Public License as published
  12.  * by the Free Software Foundation, in version 2 as it comes in the
  13.  * "COPYING" file of the XWorkplace main distribution.
  14.  * This program is distributed in the hope that it will be useful,
  15.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17.  * GNU General Public License for more details.
  18.  *
  19.  * ------------------------------------------------------------------------ */
  20.  
  21.  
  22.  
  23.  
  24. #include "smg.h"
  25.  
  26.  
  27.  
  28.  
  29. static int  construct        ( FILE *stream, uint16 size );
  30. static int  destruct         ( FILE *stream );
  31. static int  get1element_file ( FILE *stream, uint16 nr, char *buff );
  32. static int  put1element_file ( FILE *stream, uint16 nr, char *buff );
  33. static void get1element_buff ( uint16 nr, char *buff );
  34. static void put1element_buff ( uint16 nr, char *buff );
  35. static int  sort_file        ( FILE *stream );
  36. static void sort_buff        ( void );
  37. static int  sort_file_buff   ( FILE *stream );
  38.  
  39.  
  40.  
  41.  
  42. static char  *mainbuff;        /* Hovedbuffer for lagring av fildata */
  43. static char  *buff1, *buff2;   /* Buffer for mellomlagring ved sammenlikning */
  44. static long   buffsize;        /* Antall byte som er allokert til buffer */
  45. static uint16 tot_elements;    /* Totalt antall elementer i filen */
  46. static uint16 element_size;    /* Antall byte i hvert element */
  47. static uint16 buff_elements;   /* Antall elementer som er lagret i bufferet */
  48. static int    all_data_in_buff;/* TRUE hvis hele filen er lagret i bufferet */
  49.  
  50.  
  51.  
  52.  
  53. static int construct ( FILE *stream, uint16 size )
  54. /* Opprettet: Fredag 16. oktober 1992.
  55.    Parameter: "stream" Filen som skal sorteres.
  56.               "size"   Antall byte i hvert element i filen.
  57.    Retur    : E/O.
  58.    Beskriv  : Initierer globale variable til denne modulen. I initieringen
  59.               inngår også tildeling av hukommelse fra far hop til buffer,
  60.               samt å stille filpeker til stream til start av filen.
  61. */
  62. {
  63.    unsigned long memfree;              /* Ledig RAM */
  64.    long          flen;                 /* Antall byte i fil */
  65.  
  66.    buff1 = NULL;
  67.    buff2 = NULL;
  68.    mainbuff = NULL;
  69.  
  70.    if (!Rewind (stream))               /* Sett filpeker til start av filen */
  71.    {
  72.       return (ERROR);
  73.    }
  74.  
  75.    element_size = size;                /* Antall byte i hvert element */
  76.  
  77.    buff1 = Alloc (size + 1);           /* Buffer1 for mellomlager */
  78.    buff2 = Alloc (size + 1);           /* Buffer2 for mellomlager */
  79.  
  80.    if (buff1 == NULL || buff2 == NULL)
  81.    {
  82.       if (buff1) Free (buff1);
  83.       if (buff2) Free (buff2);
  84.       RETERR (14, NULL);               /* Out of memory! */
  85.    }
  86.  
  87.    memfree = MemLeft ();               /* Ledig RAM */
  88.  
  89.    if (memfree < 4000L)                /* Hvis for lite ledig RAM */
  90.    {
  91.       mainbuff = NULL;
  92.       buffsize = 0;
  93.       buff_elements = 0;
  94.       all_data_in_buff = FALSE;
  95.  
  96.       return (OK); /* Ingen feil, men sortering må gj¢res på disk */
  97.    }
  98.  
  99.    if (memfree > 65535L * size)
  100.       memfree = 65535L * size;
  101.  
  102.    buffsize = memfree - 1000;          /* Antall byte som er allokert */
  103.    mainbuff = Alloc (buffsize);        /* Alloker hukommelse fra heap */
  104.    flen     = FLength (stream);        /* Antall byte i filen */
  105.  
  106.    if (flen == -1L)                    /* Hvis feil ved lesing av fillengde */
  107.    {
  108.       return (ERROR);
  109.    }
  110.  
  111.    tot_elements = (uint16) (flen / size); /* Antall elementer i fil */
  112.  
  113.    /* Hvis det er plass til samtlige filelementer i buffer: */
  114.    if (tot_elements * size <= buffsize)
  115.    {
  116.       buff_elements    = tot_elements;
  117.       all_data_in_buff = TRUE;
  118.    }
  119.  
  120.    /* Hvis det ikke er plass til samtlige filelementer i buffer: */
  121.    else
  122.    {
  123.       buff_elements    = (uint16) (buffsize / size);
  124.       all_data_in_buff = FALSE;
  125.    }
  126.  
  127.    return (OK);
  128. } /* construct (); */
  129.  
  130.  
  131.  
  132.  
  133. static int destruct ( FILE *stream )
  134. /* Opprettet: Fredag 16. oktober 1992.
  135.    Parameter: "stream" Filen hvor filpeker skal stilles til filstart.
  136.    Retur    : E/O.
  137.    Beskriv  : Frigj¢r allokert hukommelse, og stiller filpeker til
  138.               oppgitt fil til filstart.
  139. */
  140. {
  141.    if (mainbuff) Free (mainbuff);
  142.    if (buff2)    Free (buff2);
  143.    if (buff1)    Free (buff1);
  144.  
  145.    mainbuff = NULL;
  146.    buff1    = NULL;
  147.    buff2    = NULL;
  148.  
  149.    if (!Rewind (stream))
  150.    {
  151.       return (ERROR);
  152.    }
  153.  
  154.    return (OK);
  155. } /* destruct (); */
  156.  
  157.  
  158.  
  159.  
  160. static int get1element_file ( FILE *stream, uint16 nr, char *buff )
  161. /* Opprettet: Tirsdag 2. juni 1992.
  162.    Parameter: "stream" Filen som element skal leses fra.
  163.               "nr"     Element nummer (1..).
  164.               "buff"   Buffer hvor elementet leses inn.
  165.    Retur    : E/O.
  166.    Beskriv  : Brukes når sorteringen gj¢res på disk.
  167.               Leser inn et oppgitt element fra fil.
  168.               Filpeker forlates uten å stilles tilbake til det sted den
  169.               stod ved start.
  170. */
  171. {
  172.    if (!FSeek (stream, (nr - 1) * element_size, SEEK_SET))
  173.    {
  174.       return (ERROR);
  175.    }
  176.  
  177.    if (FRead (buff, element_size, 1, stream) != 1)
  178.    {
  179.       return (ERROR);
  180.    }
  181.  
  182.    return (OK);
  183. } /* get1element_file (); */
  184.  
  185.  
  186.  
  187.  
  188. static int put1element_file ( FILE *stream, uint16 nr, char *buff )
  189. /* Opprettet: Tirsdag 2. juni 1992.
  190.    Parameter: "stream" Filen som element skal lagres til.
  191.               "nr"     Element nummer (1..).
  192.               "buff"   Buffer som lagrer aktuelt element.
  193.    Retur    : E/O.
  194.    Beskriv  : Brukes når sorteringen gj¢res på disk.
  195.               Skriver et oppgitt element til fil.
  196.               Filpeker forlates uten å stilles tilbake til det sted den
  197.               stod ved start.
  198. */
  199. {
  200.    if (!FSeek (stream, (nr - 1) * element_size, SEEK_SET))
  201.    {
  202.       return (ERROR);
  203.    }
  204.  
  205.    if (FWrite (buff, element_size, 1, stream) != 1)
  206.    {
  207.       return (ERROR);
  208.    }
  209.  
  210.    return (OK);
  211. } /* put1element_file (); */
  212.  
  213.  
  214.  
  215.  
  216. static void get1element_buff ( uint16 nr, char *buff )
  217. /* Opprettet: Fredag 16. oktober 1992.
  218.    Parameter: "nr"   Element nummer (1..).
  219.               "buff" Buffer hvor oppgitt elementet kopieres til.
  220.    Retur    :
  221.    Beskriv  : Brukes når sorteringen gj¢res på buffer.
  222.               Returnerer oppgitt element fra buffer.
  223. */
  224. {
  225.    memcpy (buff, ADRESS (mainbuff, nr - 1, element_size), element_size);
  226. } /* get1element_buff (); */
  227.  
  228.  
  229.  
  230.  
  231. static void put1element_buff ( uint16 nr, char *buff )
  232. /* Opprettet: Fredag 16. oktober 1992.
  233.    Parameter: "nr"   Element nummer (1..).
  234.               "buff" Buffer som skal kopieres til hovedbuffer.
  235.    Retur    :
  236.    Beskriv  : Brukes når sorteringen gj¢res på buffer.
  237.               Kopierer oppgitt element til hovedbuffer.
  238. */
  239. {
  240.    memcpy (ADRESS (mainbuff, nr - 1, element_size), buff, element_size);
  241. } /* put1element_buff (); */
  242.  
  243.  
  244.  
  245.  
  246. static int sort_file ( FILE *stream )
  247. /* Opprettet: Fredag 16. oktober 1992.
  248.    Parameter: "stream" Filen som skal sorteres.
  249.    Retur    : E/O.
  250.    Beskriv  : Sorterer elementene i filen.
  251.               Sorteringen utf¢res direkte på filen, uten bruk av andre
  252.               buffere enn mellomlagring av innleste elementer.
  253.               Denne metoden brukes dersom det ikke er nok ledig RAM til
  254.               å allokere noe buffer i det hele tatt.
  255. */
  256. {
  257.    int  cmpres;                        /* Resultat av elementsammenlikning */
  258.    long gap, i, j, k;                  /* For shell-sorteringen */
  259.  
  260.    gap = tot_elements / 2;
  261.    while (gap > 0)
  262.    {
  263.       for (i = gap + 1; i <= tot_elements; i++)
  264.       {
  265.          j = i - gap;
  266.  
  267.          while (j > 0)
  268.          {
  269.             k = j + gap;
  270.  
  271.             if (!get1element_file (stream, (uint16) j, buff1) ||
  272.                 !get1element_file (stream, (uint16) k, buff2))
  273.             {
  274.                 return (ERROR);
  275.             }
  276.  
  277.             cmpres = memcmp (buff1, buff2, element_size);
  278.  
  279.             if (cmpres <= 0)           /* Hvis buff1 <= buff2 */
  280.             {
  281.                j = 0;
  282.             }
  283.  
  284.             else                       /* Hvis buff1 > buff2 */
  285.             {
  286.                if (!put1element_file (stream, (uint16) j, buff2) ||
  287.                    !put1element_file (stream, (uint16) k, buff1))
  288.                {
  289.                    return (ERROR);
  290.                }
  291.  
  292.                j -= gap;
  293.             }
  294.          }
  295.       }
  296.  
  297.       gap /= 2;
  298.    }
  299.  
  300.    return (OK);
  301. } /* sort_file (); */
  302.  
  303.  
  304.  
  305.  
  306. static void sort_buff ( void )
  307. /* Opprettet: Fredag 16. oktober 1992.
  308.    Parameter:
  309.    Retur    :
  310.    Beskriv  : Sorterer elementene i "mainbuff".
  311.               Denne metoden brukes dersom samtlige filelementer får
  312.               plass i bufferet, eller for å sortere innholdet i bufferet når
  313.               bare deler av filelementene får plass.
  314.               Merk: Filelementene må være lest in til "mainbuff" på forrhånd.
  315.                     Det sorterte buffer må dessuten skrives til filen
  316.                     utenfor denne funksjonen.
  317. */
  318. {
  319.    int  cmpres;                        /* Resultat av elementsammenlikning */
  320.    long gap, i, j, k;                  /* For shell-sorteringen */
  321.  
  322.    gap = buff_elements / 2;
  323.    while (gap > 0)
  324.    {
  325.       for (i = gap + 1; i <= buff_elements; i++)
  326.       {
  327.          j = i - gap;
  328.  
  329.          while (j > 0)
  330.          {
  331.             k = j + gap;
  332.  
  333.             get1element_buff ((uint16) j, buff1);
  334.             get1element_buff ((uint16) k, buff2);
  335.  
  336.             cmpres = memcmp (buff1, buff2, element_size);
  337.  
  338.             if (cmpres <= 0)           /* Hvis buff1 <= buff2 */
  339.             {
  340.                j = 0;
  341.             }
  342.  
  343.             else                       /* Hvis buff1 > buff2 */
  344.             {
  345.                put1element_buff ((uint16) j, buff2);
  346.                put1element_buff ((uint16) k, buff1);
  347.  
  348.                j -= gap;
  349.             }
  350.          }
  351.       }
  352.  
  353.       gap /= 2;
  354.    }
  355. } /* sort_buff (); */
  356.  
  357.  
  358.  
  359.  
  360. static int sort_file_buff ( FILE *stream )
  361. /* Opprettet: Fredag 16. oktober 1992.
  362.    Parameter:
  363.    Retur    : E/O.
  364.    Beskriv  : Sorterer elementene i filen.
  365.               Sorteringen utf¢res på f¢lgende måte:
  366.               F¢rst:    Blokker av filen sorteres i buffer.
  367.               Deretter: Hele filen sorteres direkte på disk.
  368.                         Nå er allerede det meste av filen sortert, og
  369.                         sorteringen på disk går raskere.
  370.               Denne metoden brukes dersom det allokerte buffer bare er
  371.               stort nok for deler av filementene om gangen.
  372. */
  373. {
  374.    long   lastfpos;                    /* For å huske gammel filposisjon */
  375.    uint16 max_buffelements = buff_elements;
  376.    uint16 elements_left = tot_elements;/* Antall gjennværende ellementer */
  377.    uint16 elements_read;               /* Antall elementer som skal leses */
  378.  
  379.    if (!Rewind (stream))
  380.    {
  381.       return (ERROR);
  382.    }
  383.  
  384.    while (elements_left)               /* Så lenge det er elementer igjen */
  385.    {
  386.       /* Finn hvor mange elementer som skal leses i ved neste lesing: */
  387.       if (elements_left > max_buffelements)
  388.       {
  389.          /* Fyll opp buffer: */
  390.          elements_read = max_buffelements;
  391.       }
  392.       else
  393.       {
  394.          /* Resten av elementene: */
  395.          elements_read = elements_left;
  396.       }
  397.  
  398.       /* Husk filposisjon, og fyll opp buffer: */
  399.       if ((lastfpos = FTell (stream)) == -1L)
  400.       {
  401.          return (ERROR);
  402.       }
  403.  
  404.       if (FRead (mainbuff, element_size,
  405.                            elements_read, stream) != elements_read)
  406.       {
  407.          return (ERROR);
  408.       }
  409.  
  410.       buff_elements = elements_read;   /* Antall elementer i bufferet */
  411.       sort_buff ();                    /* Sorter innholdet i bufferet */
  412.  
  413.       /* Plasser filpeker tilbake til der buffer ble lest fra: */
  414.       if (!FSeek (stream, lastfpos, SEEK_SET))
  415.       {
  416.          return (ERROR);
  417.       }
  418.  
  419.       /* Skriv sortert blokk til fil: */
  420.       if (FWrite (mainbuff, element_size,
  421.                             elements_read, stream) != elements_read)
  422.       {
  423.          return (ERROR);
  424.       }
  425.  
  426.       elements_left -= elements_read;
  427.    }
  428.  
  429.    return (OK);
  430. } /* sort_file_buff (); */
  431.  
  432.  
  433.  
  434.  
  435. int sortfile ( FILE *stream, uint16 size )
  436. /* Opprettet: Tirsdag 2. juni 1992.
  437.    Parameter: "stream"  Filen som skal sorteres.
  438.               "size"    Antall byte til hvert element i filen.
  439.    Retur    : E/O.
  440.    Beskriv  : Sorterer elementene i oppgitt fil. Filen forutsettes åpnet,
  441.               for både skriving og lesing i binært mode.
  442.               Filpeker til "stream" plasseres helt i starten av filen,
  443.               etter vellykket sortering i denne funksjon. Sorteringen
  444.               utf¢res med den kjente shell-allgoritmen.
  445.               Merk: Funksjonen kan ikke sortere fler enn 65535 elementer!
  446. */
  447. {
  448.    /* Initier globale variable og alloker minne til buffere fra hop,
  449.       samt still filpeker til stream til filstart: */
  450.    if (!construct (stream, size))
  451.    {
  452.       destruct (stream);
  453.       return (ERROR);
  454.    }
  455.  
  456.    if (buffsize == 0)                  /* Hvis ingen buffer er allokert */
  457.    {
  458.       /* Sorter filen direkte på disk: */
  459.       if (!sort_file (stream))
  460.       {
  461.          goto END_ERR;
  462.       }
  463.    }
  464.  
  465.    else
  466.    if (all_data_in_buff)               /* Hele filen får plass i buffer */
  467.    {
  468.       /* Sorter filen direkte i allokert buffer: */
  469.       if (!Rewind (stream) ||
  470.           FRead  (mainbuff, element_size, tot_elements, stream) != tot_elements)
  471.       {
  472.          goto END_ERR;
  473.       }
  474.  
  475.       sort_buff ();
  476.  
  477.       if (!Rewind (stream) ||
  478.           FWrite (mainbuff, element_size, tot_elements, stream) != tot_elements)
  479.       {
  480.          goto END_ERR;
  481.       }
  482.    }
  483.  
  484.    else                                /* Bare deler av filen får plass */
  485.    {
  486.       /* Sorter filen delvis i buffer og delvis på disk: */
  487.       if (!sort_file_buff (stream))
  488.       {
  489.          goto END_ERR;
  490.       }
  491.    }
  492.  
  493.    /* Frigj¢r allokert hukommelse, og plasser filpeker til start av fil: */
  494.    if (!destruct (stream))
  495.    {
  496.       return (ERROR);
  497.    }
  498.  
  499.    return (OK);
  500.  
  501. END_ERR:
  502.  
  503.    destruct (stream);
  504.  
  505.    RETURN_ERR;
  506. } /* sortfile (); */
  507.  
  508.