PR2EN7: Dynamic memory allocation

Lab materials

Slides: Dynamic memory 1

Lab tasks

For this week, you will be creating a random data generator as the base task. This task is extended by two extra tasks. Similarly built generators are used in multiple places throughout the course to generate data files.

NB! One recommendation to generate data files has been to use LLMs for this. While good for short files, it doesn’t work well (or gets very costly) if you wish to generate millions of lines of complex data.

Task 1 [W07-1]: Random data file generator

The first task is to generate a program to generate random data files. These are useful for testing other applications without having access to real data.

Download the starter code: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/7_generator_starter.zip

Requirements

Build your application on the starter code provided
Ask the user how many entries they wish to generate. There must be no upper bound!
All entries are stored in a struct array during generation. Struct array itself is generated using dynamic memory allocation.
Pick a random first and last name and curriculum code from the pools of predefined values
Generate admission points as a random number (e.g. 24.7)
- Range must be from 10.0 to 30.0, ends inclusive.
- Precision must be 0.1 points
Sort the generated entries based on the last name. If last names for two entries match, order those by their first name.
Write the output to a file in the following format:
<index> <last name> <first name> <curriculum code> <admission points>
- Index is a unique integer. First entry will have the index as 0, every following one is incremented by one
Make sure that all resources (including memory) is freed when the program exits, use valgrind to make sure.

Workflow

Write the necessary structure declaration for the data in the header file.
Ask the user how many entries they want to generate
Allocate the memory, check for allocation failures
Generate the necessary entries
- Every person will have all their members generated randomly
- For the struct members that are picked out of the pools, you must generate a random number to pick it out
  Hint: you can either copy the name to your struct or only keep a pointer to the name
- Generate the admission points (10.0 <= points <= 30.0, precision 0.1)
  Hint: Think about this mathematically – e.g. what’s the difference between 30 and 300!? rand() function will always give you an int, regardless if what you try to do to it.
Sort the array
- Think why is it bad idea to use bubble/selection/insertion sort here!
Write the results to an output file
Free the dynamically allocated memory

Check with Valgrind for correctness! Not only in the end, but also if you encounter some weirdness, crashes or corruption!

Qsort comparison function

I’m proposing two different comparison function options. Pick the one that you understand better or write your own.

In the first case, the type cast will be done as needed, removing the need for additional variables.

int ComparCandidate(const void *a, const void *b)
{
    // Get comparison for last names
    int ret = strcmp(((candidate *)a)->lName, ((candidate *)b)->lName);
    
    // When last names match, return difference by first name
    if (ret == 0)
        return strcmp(((candidate *)a)->fName, ((candidate *)b)->fName);
    
    // Return difference by last name
    return ret;
}

int ComparCandidate(const void *a, const void *b)

{

// Get comparison for last names

int ret = strcmp(((candidate *)a)->lName, ((candidate *)b)->lName);

// When last names match, return difference by first name

if (ret == 0)

return strcmp(((candidate *)a)->fName, ((candidate *)b)->fName);

// Return difference by last name

return ret;

}

In the second case, temporary pointers are used that take will up some memory, but improve the readability of the code.

int ComparCandidate(const void *a, const void *b)
{
    // Temporary cast pointers for readability
    candidate *pA = (candidate *)a;
    candidate *pB = (candidate *)b;

    // Get comparison for last names
    int ret = strcmp(pA->lName, pB->lName);
    
    // When last names match, return difference by first name
    if (ret == 0)
        return strcmp(pA->fName, pB->fName);
    
    // return difference by last name
    return ret;
}

int ComparCandidate(const void *a, const void *b)

{

// Temporary cast pointers for readability

candidate *pA = (candidate *)a;

candidate *pB = (candidate *)b;

// Get comparison for last names

int ret = strcmp(pA->lName, pB->lName);

// When last names match, return difference by first name

if (ret == 0)

return strcmp(pA->fName, pB->fName);

// return difference by last name

return ret;

}

Testing

The output of your application should be relatively simple and short.

risto@risto-lt3-tux:~/Nextcloud/work/ttu/teaching/_generic/prog2/lab/wk7_generator/generator_solution$ valgrind ./generator
==12389== Memcheck, a memory error detector
==12389== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12389== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==12389== Command: ./generator
==12389==
The database contains:
103 first names
105 last names
3 curriculum codes

How many candidates to generate?
> 500

Successfully generated 500 entries
Successfully written 500 lines to generated_candidates.txt
==12389==
==12389== HEAP SUMMARY:
==12389==     in use at exit: 0 bytes in 0 blocks
==12389==   total heap usage: 6 allocs, 6 frees, 13,016 bytes allocated
==12389==
==12389== All heap blocks were freed -- no leaks are possible
==12389==
==12389== For lists of detected and suppressed errors, rerun with: -s
==12389== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

risto@risto-lt3-tux:~/Nextcloud/work/ttu/teaching/_generic/prog2/lab/wk7_generator/generator_solution$ valgrind ./generator

==12389== Memcheck, a memory error detector

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

==12389== Command: ./generator

==12389==

The database contains:

103 first names

105 last names

3 curriculum codes

How many candidates to generate?

> 500

Successfully generated 500 entries

Successfully written 500 lines to generated_candidates.txt

==12389==

==12389== HEAP SUMMARY:

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

==12389== total heap usage: 6 allocs, 6 frees, 13,016 bytes allocated

==12389==

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

==12389==

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

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

Then take a look at the output file and make sure the results are correct. You will have a different result because all fields will be generated randomly.

0 Aas Heidy IACB 27.9
1 Aas Juhan IACB 29.6
2 Aas Reet IACB 18.2
3 Aasa Anne EARB 10.1
4 Aasa Julia MVEB 13.8
5 Aasa Sven EARB 14.5
6 Aasa Taavi MVEB 16.1
7 Aasa Urve EARB 29.4
8 Aasa Valdo IACB 21.2
9 Allik Ivari IACB 21.3
10 Allik Kerttu MVEB 29.8
11 Allik Kerttu MVEB 21.4
12 Allik Laivi MVEB 24.2
13 Allik Peeter IACB 22.3
14 Allik Rainer IACB 17.5

0 Aas Heidy IACB 27.9

1 Aas Juhan IACB 29.6

2 Aas Reet IACB 18.2

3 Aasa Anne EARB 10.1

4 Aasa Julia MVEB 13.8

5 Aasa Sven EARB 14.5

6 Aasa Taavi MVEB 16.1

7 Aasa Urve EARB 29.4

8 Aasa Valdo IACB 21.2

9 Allik Ivari IACB 21.3

10 Allik Kerttu MVEB 29.8

11 Allik Kerttu MVEB 21.4

12 Allik Laivi MVEB 24.2

13 Allik Peeter IACB 22.3

14 Allik Rainer IACB 17.5

Extra task 1 [W07-2]: Output file formats

In this task, you will need to add CSV as a secondary output format for our application. User must be able to choose which output format they want.

Requirements

Add ability to your program to generate data in the CSV format
- First line of the CSV must be the header with the field names.
- This will be followed by data lines. Each member on a line is separated by a comma. NB! Do not put a space after the comma for CSV file!
Ask the user for which output file format they need (CSV or space delimited). Generate the appropriate type of file.
For the space-delimitted file, the extension must be .txt and for the CSV file, use the extension .csv .
Make sure that the CSV is correctly generated – try to open (or import) it using Libreoffice Calc’i or Microsoft Office and see if they recognize the format correctly.

Extra task 2 [W07-3]: Settings

In this task, you will need to make the generation a bit more flexible. This require adding options to select which fields are generated and what the points range is going to be.

Requirements

All settings must be kept in a structure – create a new structure
All settings must have default values
Program must use the defaults if the user does not wish to change the settings. What the user needs to do to alter the settings is up to you
E.g. you can ask inside of the program if they wish to alter the settings or use command line arguments
User must be able to alter the following settings without editing the source code
- Which data fields are generated (it must be possible to turn each one of them on or off).
- Name of the output file (only the name part. Extension must be chosen automatically based on the output format!)
- Output format (this is from extra task 1, move the location of the setting into the struct).
- Number of items generated (from the base task, move the variable for the setting to the struct)
- Lower rand upper bounds for the admission points
NB! The number of entries generated must be asked regardless if the user wished to change the settings or not. Purpose of this is just to keep all settings neatly in one struct.
User must be shown the settings the generation will be performed under regardless if they chose to edit it or not.

Note: if you wish, you can make a settings file, however it is not necessary. The alterations to the default settings do not need to be stored between executions. However if you do include a settings file, make sure that the user can change those settings within the program without editing the file manually.

Hint: You can make nice use of the ternary operator here
printf("First name: %10s\n", settings.genFirstName ? "Yes": "No");

After this class, you should

Know how to use dynamic memory allocation
Know how to check for memory leaks
Know in which situations it is reasonable to use dynamic memory and in which situations you should not
Know the difference between function call stack and heap
Know the differences between malloc and calloc

Additional materials

Manual memory allocation
https://beej.us/guide/bgc/html/split/manual-memory-allocation.html#manual-memory-allocation
Memory leaks in C
https://www.geeksforgeeks.org/what-is-memory-leak-how-can-we-avoid/
Checking for memory leaks using Valgrind
https://valgrind.org/docs/manual/quick-start.html