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 two extra tasks
Lab task [W08-1]: 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) of 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.
- String for the curriculum code is static because the length never changes – using dynamic memory here would be wasteful (slower and more complex).
- Single variables such as index and points 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(StudentWrapper stdWrapper); // Good for extra task 2 - Freeing the memory.
123void FreeStudentData(Person *pStudents, int n); // Good for base taskvoid FreeStudentData(Person **ppStudents, int n); // Good for base task using defensive programmingvoid FreeStudentData(StudentWrapper stdWrapper); // Good for extra task 2
Recommended functions to make your life easier
- qsort 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, use the function shown on the slides
1void FreeMemory(void **p);
To make sure you read the file correctly, you might want to have a function that just prints everyone’s data. This is however not a part of the task.
Reading the file using dynamic memory allocation
From now, the reading function takes a new form. We need to get 2 values from the reading function – memory location of the array and number of lines read from the file. I’m proposing a three variants for this function. Choose the one that works for you the best.
Variant 1: Most similar to the previously introduced reading function. It returns the line count and uses a double pointer for for the array.
Variant 2: By returning the array pointer and passing the line count as a pointer, we can avoid the use of a double pointer.
Variant 3: This one uses pointers for both the array and the line count. This allows us to return the status of the function (did it succeed or failed and potentially how it failed). This is also the most similar to the natural style of C functions – many of them return if the function succeeded or not.
Note, that using a wrapper struct (extra task 2) is also effective on cleaning up the parameter list.
Variant 1Variant 2Variant 3
|
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 |
/** * 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; } |
|
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 |
/** * 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; } |
|
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 |
/** * 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; } |
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 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) |
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) |
Extra task 1 [W08-2]: 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).
Extra task 2 [W08-3]: 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 how to use defensive programming to handle memory freeing
- Know the definition of a dangling pointer and how to safely handle dangling pointers
- be able to to structure your code in order to read files that can be of any length
- be able to handle changing the size of a dynamically allocated array
- be able 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 all the steps strdup() does in the background and be able to use it
Additional materials
- 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