CMSC216 Exam 1 Review Exercise

CODE DISTRIBUTION: hw-review-exam1-code.zip

Download the code distribution every HW
See further setup instructions below

CHANGELOG: None

1. Review Problem

1 Review Problem

Below is a simple application which uses functions to convert an array into a linked list, print its elements, and clean it up. This application appears to function correctly but when run under Valgrind to check for memory problems, it is identified as having issues that should be resolved. Study the code and output and answer the following.

What kind of error is Valgrind reporting? What lines of code does it identify as part of the problem?
What lines of code require alteration to resolve the memory problem? Are these the same as those that Valgrind reports?
What does a completely correct version of the code look like?

// list_practice.c: converts an array to a linked list and prints it,
// has memory problems

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// struct for single data node in linked list
typedef struct node_struct {
  char data[128];               // string at this node
  struct node_struct *next;     // pointer to next node
} node_t;                       // type name for struct in programs: node_t nod;

// struct encapsulating entire linked list
typedef struct {
  node_t *head;                 // NULL or pointer to first node in list
  int size;                     // number of nodes in the list
} list_t;                       // type name for struct in programs: list_t lst;


list_t *list_from_array(char *arr[], int count){
  // Creates a linked list of nodes with data copied from `arr[]`.
  // Nodes are ordered as they appear in `arr[]`
  if(count < 0){
    return NULL;
  }
  list_t *list = malloc(sizeof(list_t));
  list->head = NULL;
  list->size = 0;
  if(count==0){
    return list;
  }
  list->head = malloc(sizeof(node_t));
  strcpy(list->head->data, arr[0]);
  list->head->next = NULL;
  list->size++;
  node_t *tail = list->head;
  for(int i=1; i<count; i++){
    tail->next = malloc(sizeof(node_t));
    tail = tail->next;
    strcpy(tail->data, arr[i]);
    tail->next = NULL;
    list->size++;
  }
  return list;
}

void list_print(list_t *list){
  // prints all elements of `list` on their own line
  printf("LIST:\n");
  node_t *ptr = list->head;
  for(int i=0; i<list->size; i++){
    printf("%s\n",ptr->data);
    ptr = ptr->next;
  }
}
  
void list_free(list_t* list){
  // de-allocates memory associated with `list`
  free(list);
}

int main(){
  char *fruits[5] = {
    "Banana",
    "Grape",
    "Kiwi",
    "Orange",
    "Pear",
  };
  list_t *flist = list_from_array(fruits, 5);
  list_print(flist);
  list_free(flist);

  char *veggies[3] = {
    "Carrot",
    "Onion",
    "Potato",
  };
  list_t *vlist = list_from_array(veggies, 3);
  list_print(vlist);
  list_free(vlist);

  return 0;
}

>> gcc -g list_practice.student.c

>> ./a.out
LIST:
Banana
Grape
Kiwi
Orange
Pear
LIST:
Carrot
Onion
Potato

>> valgrind ./a.out
==81104== Memcheck, a memory error detector
==81104== Copyright (C) 2002-2024, and GNU GPLd, by Julian Seward et al.
==81104== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info
==81104== Command: ./a.out
==81104== 
LIST:
Banana
Grape
Kiwi
Orange
Pear
LIST:
Carrot
Onion
Potato
==81104== 
==81104== HEAP SUMMARY:
==81104==     in use at exit: 1,088 bytes in 8 blocks
==81104==   total heap usage: 11 allocs, 3 frees, 2,144 bytes allocated
==81104== 
==81104== LEAK SUMMARY:
==81104==    definitely lost: 272 bytes in 2 blocks
==81104==    indirectly lost: 816 bytes in 6 blocks
==81104==      possibly lost: 0 bytes in 0 blocks
==81104==    still reachable: 0 bytes in 0 blocks
==81104==         suppressed: 0 bytes in 0 blocks
==81104== Rerun with --leak-check=full to see details of leaked memory
==81104== 
==81104== For lists of detected and suppressed errors, rerun with: -s
==81104== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

# Re-run with more information lines that allocate blocks
>> valgrind --leak-check=full ./a.out
==81109== Memcheck, a memory error detector
==81109== Copyright (C) 2002-2024, and GNU GPLd, by Julian Seward et al.
==81109== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info
==81109== Command: ./a.out
==81109== 
LIST:
Banana
Grape
Kiwi
Orange
Pear
LIST:
Carrot
Onion
Potato
==81109== 
==81109== HEAP SUMMARY:
==81109==     in use at exit: 1,088 bytes in 8 blocks
==81109==   total heap usage: 11 allocs, 3 frees, 2,144 bytes allocated
==81109== 
==81109== 408 (136 direct, 272 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 4
==81109==    at 0x48457A8: malloc (vg_replace_malloc.c:446)
==81109==    by 0x1091D4: list_from_array (list_practice.student.c:30)
==81109==    by 0x1093D3: main (list_practice.student.c:77)
==81109== 
==81109== 680 (136 direct, 544 indirect) bytes in 1 blocks are definitely lost in loss record 4 of 4
==81109==    at 0x48457A8: malloc (vg_replace_malloc.c:446)
==81109==    by 0x1091D4: list_from_array (list_practice.student.c:30)
==81109==    by 0x109385: main (list_practice.student.c:68)
==81109== 
==81109== LEAK SUMMARY:
==81109==    definitely lost: 272 bytes in 2 blocks
==81109==    indirectly lost: 816 bytes in 6 blocks
==81109==      possibly lost: 0 bytes in 0 blocks
==81109==    still reachable: 0 bytes in 0 blocks
==81109==         suppressed: 0 bytes in 0 blocks
==81109== 
==81109== For lists of detected and suppressed errors, rerun with: -s
==81109== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

SOLUTION

What kind of error is Valgrind reporting? What lines of code does it identify as part of the problem?

Valgrind identifies that there is a Memory Leak: there are blocks allocated via malloc() that do not have a corresponding free() to de-allocate them. The second run of Valgrind uses the option --leak-check=full to give more insight into where the leaked blocks were allocated which is in the list_from_array() function.
What lines of code require alteration to resolve the memory problem? Are these the same as those that Valgrind reports?

The memory blocks allocated during list_from_array() and appear to be correct: there are no pointers lost, no uninitialized data created, etc. However, there blocks are not de-allocated properly in the list_free() function which would require iterating over the list of nodes calling free() on each of them. This function should be changed to fix the problem.
What does a completely correct version of the code look like?

The code below is a typical solution which adjusts list_free() to first de-allocate all nodes then calls free() on the list struct itself.

// list_practice.c: SOLUTION, correctly de-allocates all nodes in
// lists to prevent a memory leak

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// struct for single data node in linked list
typedef struct node_struct {
  char data[128];               // string at this node
  struct node_struct *next;     // pointer to next node
} node_t;                       // type name for struct in programs: node_t nod;

// struct encapsulating entire linked list
typedef struct {
  node_t *head;                 // NULL or pointer to first node in list
  int size;                     // number of nodes in the list
} list_t;                       // type name for struct in programs: list_t lst;


list_t *list_from_array(char *arr[], int count){
  // Creates a linked list of nodes with data copied from `arr[]`.
  // Nodes are ordered as they appear in `arr[]`
  if(count < 0){
    return NULL;
  }
  list_t *list = malloc(sizeof(list_t));
  list->head = NULL;
  list->size = 0;
  if(count==0){
    return list;
  }
  list->head = malloc(sizeof(node_t));
  strcpy(list->head->data, arr[0]);
  list->head->next = NULL;
  list->size++;
  node_t *tail = list->head;
  for(int i=1; i<count; i++){
    tail->next = malloc(sizeof(node_t));
    tail = tail->next;
    strcpy(tail->data, arr[i]);
    tail->next = NULL;
    list->size++;
  }
  return list;
}

void list_print(list_t *list){
  // prints all elements of `list` on their own line
  printf("LIST:\n");
  node_t *ptr = list->head;
  for(int i=0; i<list->size; i++){
    printf("%s\n",ptr->data);
    ptr = ptr->next;
  }
}
  
void list_free(list_t* list){   // NEEDS A FIX
  // de-allocates memory associated with `list`; must iterate through
  // all nodes to free() them, then free() the list_t
  node_t *ptr = list->head;
  while(ptr != NULL){
    node_t *freeit = ptr;
    ptr = ptr->next;
    free(freeit);
  }
  free(list);
}

int main(){
  char *fruits[5] = {
    "Banana",
    "Grape",
    "Kiwi",
    "Orange",
    "Pear",
  };
  list_t *flist = list_from_array(fruits, 5);
  list_print(flist);
  list_free(flist);

  char *veggies[3] = {
    "Carrot",
    "Onion",
    "Potato",
  };
  list_t *vlist = list_from_array(veggies, 3);
  list_print(vlist);
  list_free(vlist);

  return 0;
}

CMSC216 Exam 1 Review Exercise

CODE DISTRIBUTION: hw-review-exam1-code.zip

CHANGELOG: None

Table of Contents

1 Review Problem

SOLUTION