Lab materials
- Slides: Dynamic memory allocation 2
- Additional example: wrapper-struct for dynamic array
Lab tasks
This lab has one task that is extended by 2 advanced tasks
Lab task: Reading a file dynamically
The purpose of this task is to introduce how to read an unknown length file and allocate the structure array for it dynamically in the exact length required.
Data file
Data file structure for the task: <index> <last name> <first name> <curriculum code> <points>
- Index (integer)
- First and last name – strings with varying length
- Curriculum code – string with exactly 4 characters
- Points – floating point value from 10.0 to 30.0 with a precision of 0.1.
You can use the data file generator from last week for this. To test, we’ve also provided files so you can compare your output.
Download data files here that we used in the testing part.: https://blue.pri.ee/ttu/files/iax0584/andmefailid/8_scholarship_data.zip
Requirements
- Read an unknown length data file into memory
- Use realloc() to read the data, expanding your memory as you are reading the file
- Store the data into a dynamically created structure array
- Once the reading is finished, you allocated memory size must match the exactly to how many were read from the file
- You can only read the file once (repeat reading is forbidden, this includes just checking for newline count!)
- The length of the file can change – the exact length is determined during reading.
- All variable length strings must be stored in memory exactly (using dynamic memory allocation).
- During reading, use a static buffer and then use dynamic memory to store it into the struct.
- The file contains students competing for a scholarship. Scholarships are given
- For 7 best students (highest points count) for the following curriculums: IACB, EARB, MVEB
- Print the list of students who will receive the scholarship and also print the number of students who got it from each curriculum.
- Make sure there are no memory leaks!
Data structure for the task
For this task, we will transition into using dynamic memory for variable length strings (and other arrays) inside of our structure in order to save memory. The struct will now take the following form:
|
1 2 3 4 5 6 7 8 |
typedef struct { int index; char *fName; char *lName; char curriculum[LEN_CURRICULUM + 1]; float points; } person; |
Note:
- You can alter the naming to your liking.
- The fName and lName are now pointers that need dynamic memory allocation due to the length being variable from person to person.
- Array for curriculum stayed as static because it never changes – using dynamic memory here would be a waste.
- Single ints, floats… remain static because again, using dynamic for those members would be making the program purposefully slower and more complex.
Recommended list of functions
NB! The actual form the functions take depends on how you tackle the task.
At minimum, you need three functions:
- Reading the data (check the next subheading).
- Printing the results.
12void PrintScholarships(person *pStudents, int n); // Good for base taskvoid PrintScholarships(student_wrapper stdWrapper); // Good for advanced task 2 - Freeing the memory.
123void FreeStudentData(person *pStudents, int n); // Good for base taskvoid FreeStudentData(person **ppStudents, int n); // Good for base task with defensive programmingvoid FreeStudentData(student_wrapper stdWrapper); // Good for advanced task 2
Recommended functions to make your life easier
- qsordi compare function
1int ComparPersonByPoints(const void *a, const void *b); - Printing the data of a single student (useful for printing the students who get the scholarship).
1void PrintStudent(student *s); - For defensive programming, the function shown on the slides
1void FreeMemory(void **p);
To make sure everything got into the memory fine, you might want to have a function that just prints everyone data. This is however not a part of the task.
Updates to reading a file function
From now, the reading function takes a new form. We need to get 2 values from the reading function – location of the array and number of lines. I’m proposing a three options for this different function.
First variant will return the number of lines and passes the location of the memory as a double pointer.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/** * 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; // Temporary pointer used for reallocating the array person *pTemp = NULL; // TODO: 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 // Check allocation was successful // Make both pointers point at the memory location // Allocate memory for the struct members fName and lName, check allocation! // Copy data in from the buffers into the 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; } |
Second variant returns the pointer to the allocated array and passes the line number through a pointer.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/** * 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; // Temporary pointer used for reallocating the array person *pTemp = NULL; // TODO: 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 // Check allocation was successful // Make both pointers point at the memory location // Allocate memory for the struct members fName and lName, check allocation! // Copy data in from the buffers into the 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; } |
I’m also proposing a third option. The benefit in this one is that the function can convey information about the status of the reading to the caller (e.g. successful read, error reading). If you want, you can add more codes to be more precise on the errors.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/** * 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; // Temporary pointer used for reallocating the array person *pTemp = NULL; // TODO: Temporary buffers for reading // 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 // Check allocation was successful // Make both pointers point at the memory location // Allocate memory for the struct members fName and lName, check allocation! // Copy data in from the buffers into the 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; } |
Testing
In the first file, we’re using the longer data file where all scholarships got assigned. Notice the heap summary!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
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 SeppMikser 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) |
In the second example, I’m using the shorter data file.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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) |
Advanced task 1: Optimal algorithms for allocation
In this task we’re changing the algorithm how we are allocating memory to a more reasonable one.
Requirements
- Change the file reading in a way that you would be using the (n * 2) expansion strategy
- Every time you run out of memory, you reallocate to a 2x higher amount that you have right now.
- To start, pick an initial allocation that is greater than 1 (pick a size that would be 3x lower than the file length just so you can observe the correctness).
Advanced task 2: wrapper struct
In this task, we’re making our code a bit more readable and contained. We will put both the struct and its properties into a wrapper to keep everything tightly integrated.
Requirements
- Put your structure array pointer into the other struct (wrapper)
- In your wrapper, you should have 3 variables – pointer to the struct, number of structs allocated, number of structs used
- Change your function parameters for the existing functions to use the new wrapper struct
- NB! Think through for which functions it is required to pass a pointer to the wrapper where it is unnecessary.
Hint: Now you will need an extra access layer to get from the wrapper to the struct itself. To help with readability, you might want to “unpack” those variables when you need to use them. See the following example.
|
1 2 3 4 5 6 7 8 9 10 |
void PrintData(student_wrapper stdWrap) { int len = stdWrap.used; for (int i = 0; i < len; i++) { student *s = &stdWrap.studentDB[i]; } } |
After this class, you should
- know different ways to structure your code in order to read files that can be of any length
- Know how to dynamically alter your array size
- Know how to read data into an expanding array using dynamic memory allocation
- know all possible ways realloc works
- know the difference between (n + 1) and (n * 2) allocation strategies and be able to implemetn at least one of the two
- be able to allocate memory to members of structures
- know about defensive programming idea for freeing memory
- Know all the steps strdup() does in the background and be able to use it.