SOFT3410 Tutorial 3 Dynamic Memory and Data Structures
Today’s lab will involve constructing a few common data structures and getting familiar with dynamic memory
Question 1: Malloc and Free
Unlike Java, C’s heap allocation is explicit and depends on standard library functions. The functions we will be using for heap allocation are malloc and free. Lets build a two-dimensional jagged array.
…
int** rows = ….
….
for(int i = 0; i < 4; i++) {
for(int j = 0; j < lens[i]; j++) { *((*(rows+i))+j) = j+1;
} }
for(int i = 0; i < 4; i++) {
for(int j = 0; j < lens[i]; j++) {
printf("%d ", rows[i][j]);
}
puts(""); }
...
Given this segment, how could we allocate memory for rows, how is the data accessed and do we need to allocate memory for for each individual row? Use this code segment and provide the correct allocation scheme.
What happens at the end of your program? Do we need to use free?
1
SOFT3410 Dynamic Memory and Data Structures
Question 2: Stack
Given the following struct definitions and function declaration, implement the logic for a linked stack.
struct stack_node {
void* val;
struct stack_node* next;
};
struct stack {
struct stack_node* top; size_t size;
};
void* stack_pop_object(struct stack* s);
void stack_push_copy(struct stack* s, void* data, size_t nbytes); void* stack_peek(struct stack* s);
Question 3: Queue and sorting
Construct a queue which complies with the following function signatures. Afterwards, construct a sorting function that will utilise a queue and retrieve the next minimum through the dequeue function. Simply implement a linked queue and follow on to develop a min-heap.
struct queue;
struct queue* queue_new();
void queue_enqueue(struct queue*, void* element); void* queue_dequeue(struct queue*);
void queue_destroy(struct queue*);
Concurrency
Page 2 of 4
SOFT3410 Dynamic Memory and Data Structures
Question 4: Homework - Linked List Map
Getting acquainted with basic data structures in C is a great way to get acquainted with memory ownership and reference semantics. You have been tasked with constructing a variation of a linked list that will couple keys and values.
Your linked list map must not include duplicate keys and can support a variety of key and value types. Use the following declarations to construct your map.
struct linkedlist_map_entry; struct linkedlist_map;
struct linkedlist_map* linkedlist_map_new(int (*cmp)(void*, void*), void (*keydel)(void*), void(*valdel)(void*));
void linkedlist_map_put(struct linkedlist_map* map, void* key void* value); void* linkedlist_map_get(struct linkedlist_map* map, void* key);
void* linkedlist_map_remove(struct linkedlist_map* map, void* key);
size_t linkedlist_map_size(struct linkedlist_map* map);
void linkedlist_map_destroy(struct linkedlist_map* n); You must comply with the following
• No VLAs
• Minimise code repetition
• No global or static variables
• No invalid memory access
• Data structure store code should not contain a main function, use a separate file to directly test your code
You can safely assume the following.
• keys and values given the map via put will take ownership of the data
• When remove is called, value will be transferred to caller but key will be deallocated • When get is called, it will provide a reference but will not transfer ownership to caller • Any keys and values stored in the map must be deallocated
For your submission, create a github repository with the following name soft3410hw3 and invite your tutor to your repository.
You will need to supply the following as part of your submission. • Place all .c source files in your src folder
Concurrency Page 3 of 4
SOFT3410 Dynamic Memory and Data Structures
• Test cases must be in a folder called test
• Supply a makefile or a script to compile your program
• You must supply a README.md file that specifies how to build your program and a small description of your project and how it solves the problem
• You must ensure that it compiles and executes correctly on linux
You must make a submission to the master branch by 11:59pm, 20th September, 2020. Please make sure your last commit and push occurs before this time.
Concurrency Page 4 of 4