PR2ET8: Dünaamiline mälu 2

Labori materjal

Slaidid: Dünaamiline mälujaotus 2
Täiendav näide: ümbris-struktuur (wrapper struct) dünaamilisele massiivile

Laboriülesanded

Selles laboris on üks ülesanne, mida laiendab kaks lisaülesannet

Ülesanne [W08-1]: Faili lugemine kasutades dünaamilist mälu

Selle ülesande eesmärgiks on tutvuda kuidas lugeda teadmata pikkusega faile sedasi, et me kasutame täpselt nii palju mälu kui failis olevate andmete hoiustamiseks vaja on.

Andmefail

Andmefaili struktuur on järgnev: <indeks> <perenimi> <eesnimi> <õppekava kood> <punktide arv>

Indeks (täisarv)
Ees- ja perenimi – erineva pikkusega sõned
Õppekava kood – 4-tähemärgi pikkune sõne
Punktide arv – kümnendmurd vahemikus 10,0 kuni 30,0 täpsusega 0,1.

Võid kasutada andmefailide loomiseks oma eelmise nädala laboriülesande lahendust. Testimiseks on antud siiski kindlad failid, et saaksid oma väljundit võrrelda.

Andmefailid mille väljundi näited on ka testimine osas: https://blue.pri.ee/ttu/files/iax0584/andmefailid/8_scholarship_data.zip

Nõuded

Loe teadmata pikkusega andmefaili sisu mällu
- Lugemiseks kasuta realloc() funktsiooni, laiendades mäluala suurust jooksvalt lugemise käigus.
- Andmed salvesta dünaamiliselt loodud struktuurimassiivi
- Lugemise lõpuks peab küsitud mälumaht olema täpselt nii suur kui on vaja failis olevate andmete hoiustamiseks.
- Faili tohib vaid ühel korral lugeda (korduv lugemine keelatud! Ka lihtsalt reavahetuste arvu lugemine ei ole lubatud!)
- Arvesta, et faili pikkus võib muutuda! St faili pikkus selgub lugemise käigus!
Kõik muutuva pikkusega sõned tuleb mälus hoida täpse pikkusega.
- Lugemise ajal kasuta staatilist puhvrit, struktuuris hoidmiseks kasuta dünaamilist mälu!
Failis on stipendiumile kandideerivate tudengite loetelu. Stipendiumi saavad:
- Igast järgnevast erialast kuni 7 kõige kõrgema punktisummaga tudengit: IACB, EARB ja MVEB.
Kuva stipendiumi saajate nimekiri ning näita mitu tudengit igalt erialalt stipendiumi sai.
Veendu, et programm ei tekita mälulekkeid!

Andmestruktuur ülesandele

Selles ülesandes läheme üle dünaamilisele mälule struktuuri liikmete hulgas mille pikkus on muutuv (sõned ja teised massiivid) – see säästab meil mälu ja suurendab paindlikkust. Struktuur võtab järgneva kuju:

typedef struct
{
    int index;
    char *fName;
    char *lName;
    char curriculum[LEN_CURRICULUM + 1];
    float points;
} Person;

typedef struct

{

int index;

char *fName;

char *lName;

char curriculum[LEN_CURRICULUM + 1];

float points;

} Person;

Märkused:

Soovi korral võid nimetusi endale sobilikumaks muuta
fName ja lName on nüüd viidad, mis vajavad dünaamilist mälu enne kui nendesse midagi salvestada saab – seda kuna nime pikkus on muutuv inimeselt inimesele.
Õppekava koodi massiiv on staatiline sest see on alati täpselt sama pikk – dünaamiline mälu siin oleks raiskav.
Üksikud täisarvud, murdarvud jne jäävad samuti staatiliseks – jällegi, dünaamiline mälu siin teeks programmi põhjendamatult aeglasemaks ja keerukamaks.

Soovituslik loetelu funktsioonidest

NB! Funktsioonide tegelik kuju sõltub kuidas otsustad ülesannet lahendada ja struktureerida.

Minimaalselt on sul vaja kolme funktsiooni:

Andmete lugemise funktsioon failist (vali välja järgmisest peatükist).
Vastuste väljastamise funktsiooni.

void PrintScholarships(Person *pStudents, int n); // Good for base task void PrintScholarships(StudentWrapper stdWrapper); // Good for advanced task 2

1
2

void PrintScholarships(Person *pStudents, int n); // Good for base task
void PrintScholarships(StudentWrapper stdWrapper); // Good for advanced task 2

Andmete vabastamise funktsiooni

void FreeStudentData(Person *pStudents, int n); // Good for base task
void FreeStudentData(Person **ppStudents, int n); // Good for base task with defensive programming
void FreeStudentData(StudentWrapper stdWrapper); // Good for advanced task 2

void FreeStudentData(Person *pStudents, int n); // Good for base task

void FreeStudentData(Person **ppStudents, int n); // Good for base task with defensive programming

void FreeStudentData(StudentWrapper stdWrapper); // Good for advanced task 2

Soovituslikud funktsioonid enda elu lihtsamaks tegemiseks

qsordi võrdlusfunktsioon

int ComparStudentByPoints(const void *a, const void *b);

1

int ComparStudentByPoints(const void *a, const void *b);
Ühe tudengi andmete printimise funktsioon (kasulik kui prindid tudengi andmeid, kes stipendiumi saab.

void PrintStudent(Student *s);

1

void PrintStudent(Student *s);
Kaitsva programmeerimisstiili jaoks kulub ära ka slaididel näidatud vabastamisfunktsioon

void FreeMemory(void **p);

1

void FreeMemory(void **p);

Lugemise kontrollimiseks võib olla mõistlik luua ka funktsioon, mis trükib kõigi tudengite andmed välja mis failist kätte saadi. See aga pole ülesande osa.

Funktsioon andmete lugemiseks

Sel korral võtab andmete lugemise funktsioon veidi teistsuguse kuju. Funktsioonist on meil vaja saada kätte 2 uut väärtust – dünaamilise massiivi asukoht ja failist loetud ridade arv. Selleks pakun välja kolm erinevat funktsiooni kuju, mille hulgast saad valida endale meelepärase!

Variant 1 on kõige sarnasem varasemalt tuttavale faili lugemise funktsiooni kujule. Funktsiooni tagastuseks on ridade arv ning mäluviida saame kätte kasutades topeltviita.

Variant 2 vahetab andmete liikumise ümber – ridade arv tuleb nüüd kasutades viita ning tagastusena anname mäluaadressi dünaamilisele massiivile. Sedasi saab vältida topeltviida kasutamist, kui see liiga keerukaks osutub.

Variant 3 liigutab kogu andmevahetuse viitadele. See lubab meil funktsioonist tagastada funktsiooni töö oleku – st kas lugemine töötas edukalt või ebaõnnestus. See on ka kõige lähedasem suurele osale C keelsetele funktsioonidele – suur osa neist tagastab nulli kui töö oli edukas ning mittenullise väärtuse kui juhtus viga.

NB! Kasutades lisaülesandes 2 tutvustatud ümbrisstruktuuri ideed saab parameetrite loetelu veelgi puhtamaks!

Variant 1Variant 2Variant 3

/**
 * Description:   Reads data from a file. During reading, a dynamic
 *                struct array will be created and expanded using realloc()
 * Parameters:    ppStudentData - Stores the location of the allocated array
 *                fileName - name of the input file to read
 * Return:        Number of lines read from the file
 */
int ReadData(Person **ppStudentData, char *fileName)
{
    // Current line counter
    int count = 0;

    // Main pointer for the allocated array
    Person *pData = NULL;

    // Declare temporary buffers for reading (all variables you intend to read!)


    // Read a record at a time in a loop into buffer(s)
    while ()
    {
        // Rellocate memory to fit the latest line, using a temporary variable
        Person *pTemp = realloc(pData, /* Calculate number of bytes required */);

        // Check allocation was successful
        if (pTemp == NULL)
        {
            /* Write error behavior here */
        }

        // Allocation success, make sure both pointers point at memory
        pData = pTemp;

        // 1. Allocate all dynamic buffers (strings in this task)
        // 2. Copy the data from buffers to struct array


        // Increment number of records successfully read
        count++;
    }


    // Store the allocated array trough the double pointer
    *ppStudentData = pData;

    // Return the number of lines read
    return count;
}

/**

* Description: Reads data from a file. During reading, a dynamic

* struct array will be created and expanded using realloc()

* Parameters: ppStudentData - Stores the location of the allocated array

* fileName - name of the input file to read

* Return: Number of lines read from the file

int ReadData(Person **ppStudentData, char *fileName)

{

// Current line counter

int count = 0;

// Main pointer for the allocated array

Person *pData = NULL;

// Declare temporary buffers for reading (all variables you intend to read!)

// Read a record at a time in a loop into buffer(s)

while ()

{

// Rellocate memory to fit the latest line, using a temporary variable

Person *pTemp = realloc(pData, /* Calculate number of bytes required */);

// Check allocation was successful

if (pTemp == NULL)

{

/* Write error behavior here */

}

// Allocation success, make sure both pointers point at memory

pData = pTemp;

// 1. Allocate all dynamic buffers (strings in this task)

// 2. Copy the data from buffers to struct array

// Increment number of records successfully read

count++;

}

// Store the allocated array trough the double pointer

*ppStudentData = pData;

// Return the number of lines read

return count;

}

/**
 * Description:   Reads data from a file. During this, a dynamic
 *                struct array will be created and expanded using realloc()
 * Parameters:    pLineCount - pointer to store the read line count
 *                fileName - name of the input file to read
 * Return:        Pointer to the allocated data array
 */
Person * ReadData(int *pLineCount, char *fileName)
{
    // Current line counter
    int count = 0;

    // Main pointer for the allocated array
    Person *pData = NULL;

    // Declare temporary buffers for reading (all variables you intend to read!)


    // Read a record at a time in a loop into buffer(s)
    while ()
    {
        // Rellocate memory to fit the latest line, using a temporary variable
        Person *pTemp = realloc(pData, /* Calculate number of bytes required */);

        // Check allocation was successful
        if (pTemp == NULL)
        {
            /* Write error behavior here */
        }

        // Allocation success, make sure both pointers point at memory
        pData = pTemp;

        // 1. Allocate all dynamic buffers (strings in this task)
        // 2. Copy the data from buffers to struct array


        // Increment number of records successfully read
        count++;
    }


    // Store the number of lines trough the pointer
    *pLineCount = count;

    // Return the pointer to the data
    return pData;
}

/**

* Description: Reads data from a file. During this, a dynamic

* struct array will be created and expanded using realloc()

* Parameters: pLineCount - pointer to store the read line count

* fileName - name of the input file to read

* Return: Pointer to the allocated data array

Person * ReadData(int *pLineCount, char *fileName)

{

// Current line counter

int count = 0;

// Main pointer for the allocated array

Person *pData = NULL;

// Declare temporary buffers for reading (all variables you intend to read!)

// Read a record at a time in a loop into buffer(s)

while ()

{

// Rellocate memory to fit the latest line, using a temporary variable

Person *pTemp = realloc(pData, /* Calculate number of bytes required */);

// Check allocation was successful

if (pTemp == NULL)

{

/* Write error behavior here */

}

// Allocation success, make sure both pointers point at memory

pData = pTemp;

// 1. Allocate all dynamic buffers (strings in this task)

// 2. Copy the data from buffers to struct array

// Increment number of records successfully read

count++;

}

// Store the number of lines trough the pointer

*pLineCount = count;

// Return the pointer to the data

return pData;

}

/**
 * Description:   Read data from a file. During this, a dynamic
 *                struct array will be created and expanded using realloc()
 * Parameters:    ppStudentData - Stores the location of the allocated array
 *                pLineCount - pointer to store the read line count
 *                fileName - name of the input file to read
 * Return:        0 if data is read successfully
 *                1 if error is encountered
 */
int ReadData(Person **ppStudentData, int *pLineCount, char *fileName)
{
    // Current line counter
    int count = 0;

    // Main pointer for the allocated array
    Person *pData = NULL;

    // Declare temporary buffers for reading (all variables you intend to read!)


    // Read a record at a time in a loop into buffer(s)
    // Note: if you encounter an error, return a NON-ZERO value!
    while ()
    {
        // Rellocate memory to fit the latest line, using a temporary variable
        Person *pTemp = realloc(pData, /* Calculate number of bytes required */);

        // Check allocation was successful
        if (pTemp == NULL)
        {
            /* Write error behavior here */
        }

        // Allocation success, make sure both pointers point at memory
        pData = pTemp;

        // 1. Allocate all dynamic buffers (strings in this task)
        // 2. Copy the data from buffers to struct array


        // Increment number of records successfully read
        count++;
    }

    // Store the allocated array trough the double pointer
    *ppStudentData = pData;

    // Store the number of lines trough the pointer
    *pLineCount= count;

    // Everything OK
    return 0;
}

/**

* Description: Read data from a file. During this, a dynamic

* struct array will be created and expanded using realloc()

* Parameters: ppStudentData - Stores the location of the allocated array

* pLineCount - pointer to store the read line count

* fileName - name of the input file to read

* Return: 0 if data is read successfully

* 1 if error is encountered

int ReadData(Person **ppStudentData, int *pLineCount, char *fileName)

{

// Current line counter

int count = 0;

// Main pointer for the allocated array

Person *pData = NULL;

// Declare temporary buffers for reading (all variables you intend to read!)

// Read a record at a time in a loop into buffer(s)

// Note: if you encounter an error, return a NON-ZERO value!

while ()

{

// Rellocate memory to fit the latest line, using a temporary variable

Person *pTemp = realloc(pData, /* Calculate number of bytes required */);

// Check allocation was successful

if (pTemp == NULL)

{

/* Write error behavior here */

}

// Allocation success, make sure both pointers point at memory

pData = pTemp;

// 1. Allocate all dynamic buffers (strings in this task)

// 2. Copy the data from buffers to struct array

// Increment number of records successfully read

count++;

}

// Store the allocated array trough the double pointer

*ppStudentData = pData;

// Store the number of lines trough the pointer

*pLineCount= count;

// Everything OK

return 0;

}

Testimine

Esimeses näites kasutame pikemat andmefaili, kus kõik loetelud said täis.

risto@risto-lt3-tux:~/Nextcloud/work/ttu/teaching/_generic/prog2/lab/wk8_scholarships$ valgrind ./scholarships v1.txt
==14380== Memcheck, a memory error detector
==14380== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==14380== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==14380== Command: ./scholarships v1.txt
==14380==
Ind   fName        lName        Code   Points
 13   Laivi        Kaasik       IACB    30.0
 75   Julia        Saal         MVEB    30.0
  3   Kerttu       Allik        MVEB    29.8
 25   Ingrid       Kukk         MVEB    29.8
  5   Valdo        Heinsoo      IACB    29.7
 77   Jaan         Saar         IACB    29.7
  9   Kristi       Hunt         IACB    29.5
 20   Doris        Vares        IACB    29.5
 76   Annika       Saar         EARB    29.5
 36   Veljo        Lepp         MVEB    29.4
 10   Hendrik      Ivanov       IACB    29.1
 38   Monika       Leppik       MVEB    29.1
 22   Anna         Kruuse       MVEB    29.0
 51   Mare         Paas         IACB    28.2
 80   Rainer       Sepp         EARB    27.8
 59   Kristiina    Petrov       MVEB    27.6
 45   Tatjana      Orav         EARB    26.7
 74   Anneli       Saal         EARB    26.3
 69   Tiina        Raud         EARB    25.1
  8   Anna         Herkel       EARB    23.0
 65   Denis        Purga        EARB    21.7


EARB: 7 / 7 scholarsips assigned
IACB: 7 / 7 scholarsips assigned
MVEB: 7 / 7 scholarsips assigned
==14380==
==14380== HEAP SUMMARY:
==14380==     in use at exit: 0 bytes in 0 blocks
==14380==   total heap usage: 175 allocs, 175 frees, 20,396 bytes allocated
==14380==
==14380== All heap blocks were freed -- no leaks are possible
==14380==
==14380== For lists of detected and suppressed errors, rerun with: -s
==14380== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

risto@risto-lt3-tux:~/Nextcloud/work/ttu/teaching/_generic/prog2/lab/wk8_scholarships$ valgrind ./scholarships v1.txt

==14380== Memcheck, a memory error detector

==14380== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info

==14380== Command: ./scholarships v1.txt

==14380==

Ind fName lName Code Points

13 Laivi Kaasik IACB 30.0

75 Julia Saal MVEB 30.0

3 Kerttu Allik MVEB 29.8

25 Ingrid Kukk MVEB 29.8

5 Valdo Heinsoo IACB 29.7

77 Jaan Saar IACB 29.7

9 Kristi Hunt IACB 29.5

20 Doris Vares IACB 29.5

76 Annika Saar EARB 29.5

36 Veljo Lepp MVEB 29.4

10 Hendrik Ivanov IACB 29.1

38 Monika Leppik MVEB 29.1

22 Anna Kruuse MVEB 29.0

51 Mare Paas IACB 28.2

80 Rainer Sepp EARB 27.8

59 Kristiina Petrov MVEB 27.6

45 Tatjana Orav EARB 26.7

74 Anneli Saal EARB 26.3

69 Tiina Raud EARB 25.1

8 Anna Herkel EARB 23.0

65 Denis Purga EARB 21.7

EARB: 7 / 7 scholarsips assigned

IACB: 7 / 7 scholarsips assigned

MVEB: 7 / 7 scholarsips assigned

==14380==

==14380== HEAP SUMMARY:

==14380== in use at exit: 0 bytes in 0 blocks

==14380== total heap usage: 175 allocs, 175 frees, 20,396 bytes allocated

==14380==

==14380== All heap blocks were freed -- no leaks are possible

==14380==

==14380== For lists of detected and suppressed errors, rerun with: -s

==14380== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Teises näites on andmefail lühem.

risto@risto-lt3-tux:~/Nextcloud/work/ttu/teaching/_generic/prog2/lab/wk8_scholarships$ valgrind ./scholarships v2.txt
==14397== Memcheck, a memory error detector
==14397== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==14397== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==14397== Command: ./scholarships v2.txt
==14397==
Ind   fName        lName        Code   Points
  5   Laivi        Kaasik       IACB    30.0
  0   Kerttu       Allik        MVEB    29.8
  3   Hendrik      Ivanov       IACB    29.1
  6   Kristi       Kalda        IACB    27.0
  9   Jevgeni      Kuusk        MVEB    25.0
  2   Anna         Herkel       EARB    23.0
 11   Tiina        Laas         IACB    22.4
  4   Milvi        Jakobson     IACB    19.5
  7   Mati         Kruuse       IACB    17.3
 10   Liis         Kuusk        MVEB    17.2
  1   Sirje        Helme        EARB    12.9
  8   Mihkel       Kruuse       MVEB    10.6


EARB: 2 / 7 scholarsips assigned
IACB: 6 / 7 scholarsips assigned
MVEB: 4 / 7 scholarsips assigned
==14397==
==14397== HEAP SUMMARY:
==14397==     in use at exit: 0 bytes in 0 blocks
==14397==   total heap usage: 29 allocs, 29 frees, 6,947 bytes allocated
==14397==
==14397== All heap blocks were freed -- no leaks are possible
==14397==
==14397== For lists of detected and suppressed errors, rerun with: -s
==14397== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

risto@risto-lt3-tux:~/Nextcloud/work/ttu/teaching/_generic/prog2/lab/wk8_scholarships$ valgrind ./scholarships v2.txt

==14397== Memcheck, a memory error detector

==14397== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info

==14397== Command: ./scholarships v2.txt

==14397==

Ind fName lName Code Points

5 Laivi Kaasik IACB 30.0

0 Kerttu Allik MVEB 29.8

3 Hendrik Ivanov IACB 29.1

6 Kristi Kalda IACB 27.0

9 Jevgeni Kuusk MVEB 25.0

2 Anna Herkel EARB 23.0

11 Tiina Laas IACB 22.4

4 Milvi Jakobson IACB 19.5

7 Mati Kruuse IACB 17.3

10 Liis Kuusk MVEB 17.2

1 Sirje Helme EARB 12.9

8 Mihkel Kruuse MVEB 10.6

EARB: 2 / 7 scholarsips assigned

IACB: 6 / 7 scholarsips assigned

MVEB: 4 / 7 scholarsips assigned

==14397==

==14397== HEAP SUMMARY:

==14397== in use at exit: 0 bytes in 0 blocks

==14397== total heap usage: 29 allocs, 29 frees, 6,947 bytes allocated

==14397==

==14397== All heap blocks were freed -- no leaks are possible

==14397==

==14397== For lists of detected and suppressed errors, rerun with: -s

==14397== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Lisaülesanne 1 [W08-2]: Optimaalne mäluhõive

Selles ülesandes muudame oma dünaamilise mälu hõivamise mõistlikumaks kasutades optimaalsemat mälu laiendamise strateegiat.

Nõuded

Muuda oma faili lugemist sedasi, et lugemisek kasutaksid (n * 2) strateegiat
- St iga kord kui küsitud mälumaht saab otsa, laiendatakse mäluala 2x võrreldes olemasolevaga
Alustamiseks vali n mis on suurem kui 1 (vali siiski vähemalt 3x väiksem kui pikima faili pikkus

Lisaülesanne 2 [W08-3]: ümbris-struktuur

Selles ülesandes muudame oma koodi veelgi loetavamaks ja seotumaks, pannes oma andmestruktuuri ja selle omadused ühte ümbritsevasse struktuuri.

Nõuded

Pane oma struktuurimassiiv teise struktuuri ehk ümbrise sisse (wrapper struct),
Ümbrises peaks olema 3 muutujat – viide struktuurile, struktuuri suurus ja struktuuri kasutatud liikmete arv.
Muuda oma funktsioonide parameetreid nii, et nüüd need kasutaksid uut vastloodud ümbrisstruktuuri.
NB! Mõtle läbi mis funktsiooni on mõistlik viit ümbrisele anda, millisesse pole seda mõtet teha!

Vihje: Kuna nüüd on iga välja poole pöördumisel vaja ümbrisstrukuturist valida välja õige liige, siis võib loetavuse huvides olla see mõistlik “lahti pakkida” eraldi muutujasse vastava funktsiooni või tsükli sees. Näiteks

void PrintData(StudentWrapper stdWrap)
{
    int len = stdWrap.used;

    for (int i = 0; i < len; i++)
    {
        student *s = &stdWrap.studentDB[i];

    }
}

void PrintData(StudentWrapper stdWrap)

{

int len = stdWrap.used;

for (int i = 0; i < len; i++)

{

student *s = &stdWrap.studentDB[i];

}

Pärast seda tundi peaksid

teadma erinevaid võimalusi kuidas struktureerida ja lugeda faile mille pikkus võib erineda
oskama dünaamiliselt oma massiivide suurust muuta
oskama lugeda faile dünaamilist mälu kasutades jooksvalt ja täpselt
teadma kõiki võimalike realloci tagastuste võimalus
teadma kahte laiendamise strateegiat (n + 1) ja (n * 2) ning oskama neid kahte võrrelda
oskama struktuuri liikmetele mälu küsida
teadma ja oskama rakendada ohutu programmeerimise tehnikat mälu vabastamisel.
teadma kõiki samme mida strdup() funktsioon taustal teeb

Täiendav materjal

cppreference: Realloc documentation
https://en.cppreference.com/w/c/memory/realloc
Beej’s guide: Changing allocated size
https://beej.us/guide/bgc/html/split/manual-memory-allocation.html#changing-allocated-size-with-realloc