UC3M

Telematic/Audiovisual Syst./Communication Syst. Engineering

Systems Architecture

September 2015 - January 2016

Memory leaks in C

Previous activities

Table of Contents

1. Memory Leaks in C
Readings
Work Plan
Assessment
Automatic self-assessment
2. Tree of Strings
Work Plan

1.  Memory Leaks in C

Readings

Work Plan

  1. Solve the four problems included in the second document. Make sure you attend the master session with them fully understood.

Assessment

In the following session you will use these concepts to solve a memory management problem, thus you may use these solutions to answer correctly the questions.

Automatic self-assessment

Check with these questions if you understood this document

Choose the errors found in each piece of code.

  1. 1
2
3
4
5
6
7
8
9
10
11
12
    		 
    int count_element(int id, struct list *inicio)
{
  int cont=0;
  struct list *aux= (struct list *) malloc (sizeof(struct list));
  aux=inicio;
  while (aux!=NULL)
  {
   cont++;
   aux=aux->next;
  }
  return cont;
}

    • No errors.

    • Line 5: There is a memory leak of size sizeof(struct list).

    • Line 8: Uninitialized memory.

    • Line 9: there is a memory leak. The whole list is lost.

  2. 1
2
3
4
5
6
7
8
9
10
11
12
    		 
    int count_element(int id, struct list **inicio)
{
  int cont=0;
  struct list *aux;
  aux=*inicio;
  while (*inicio!=NULL)
  {
   cont++;
   *inicio=(*inicio)->next;
  }
  return cont;
}

    • No errors.

    • Line 5: There is a memory leak of size sizeof(struct list).

    • Line 8: Uninitialized memory.

    • Line 9: there is a memory leak. The whole list is lost.

  3. 1
2
3
4
5
6
7
8
9
10
11
12
    		 
    int count_element(int id, struct list *inicio)
{
  int cont;
  struct list *aux;
  aux=inicio;
  while (aux!=NULL)
  {
   cont++;
   aux=aux->next;
  }
  return cont;
}

    • No errors.

    • Line 5: There is a memory leak of size sizeof(struct list).

    • Line 8: Uninitialized memory.

    • Line 9: there is a memory leak. The whole list is lost.

  4. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    		 
    struct list *del_element(int id, struct list *inicio)
{
  struct list *aux,*ant;
  aux=inicio;
  ant=inicio;
  while ((aux!=NULL)&&(aux->id!=id))
  {
   ant=aux;
   aux=aux->next;
  }
  if (aux == NULL)
    return inicio;
  if (aux == ant)
  {
    free(aux);
    inicio=inicio->next;
  }
  else
  {
    ant->next=aux->next;
    free(aux);
  }
  return inicio;
}

    • No errors

    • Line 16: Accessing memory with a corrupt pointer.

    • Line 20: memory leak.

    • Line 13: Uninitialized memory.

  5. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    		 
    struct list *del_element(int id, struct list *inicio)
{
  struct list *aux,*ant;
  aux=inicio;

  while ((aux!=NULL)&&(aux->id!=id))
  {
   ant=aux;
   aux=aux->next;
  }
  if (aux == NULL)
    return inicio;
  if (aux == ant)
  {
    inicio=inicio->next;
    free(aux);
  }
  else
  {
    ant->next=aux->next;
    free(aux);
  }
  return inicio;
}

    • No errors.

    • Line 15: Accessing memory with a corrupt pointer.

    • Line 20: memory leak.

    • Line 13: Uninitialized memory.

  6. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    		 
    struct list *del_element(int id, struct list *inicio)
{
  struct list *aux,*ant;
  aux=inicio;
  ant=inicio;
  while ((aux!=NULL)&&(aux->id!=id))
  {
   ant=aux;
   aux=aux->next;
  }
  if (aux == NULL)
    return inicio;
  if (aux == ant)
  {
    inicio=inicio->next;
    free(aux);
  }
  else
  {
    ant->next=aux->next;
  }
  return inicio;
}

    • No errors.

    • Line 15: Accessing memory with a corrupt pointer.

    • Line 20: memory leak.

    • Line 13: Uninitialized memory.

  7. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    		 
    struct  vector *create_vector(int number)
{
if (number == 0)
  return NULL;
struct vector *nuevo= (struct vector *) malloc(sizeof(struct vector)*number);
if (nuevo == NULL)
  return NULL;
int i=0;
while (i<=number)
{
  nuevo[i]=i;
  i++;
}
return nuevo;
}

    • No errors.

    • Line 9: Uninitialized memory.

    • Line 11: Overwriting dynamic memory.

  8. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    		 
    struct  vector *create_vector(int number)
{
if (number == 0)
  return NULL;
struct vector *nuevo= (struct vector *) malloc(sizeof(struct vector)*number);
if (nuevo == NULL)
  return NULL;
int i;
while (i<number)
{
  nuevo[i]=i;
  i++;
}
return nuevo;
}

    • No errors.

    • Line 9: Uninitialized memory.

    • Line 11: Overwriting dynamic memory.

How long did this activity take you? mins.

2.  Tree of Strings

Work Plan

A C program needs to store an undetermined number of strings. The selected data structure is a binary tree in which each node stores one string. Furthermore, the tree has the property that the word stored in a node follows lexicographically those in the left sub-tree and precedes those in the right sub-tree. The following figure shows an example of this data structure.

The application needs to manipulate several sets of words independently.

  1. Define the needed data structures to manipulate these trees.

  2. Define the prototypes of the following functions:

    • Function that creates a new empty set.

    • Function that searches a word in a set and returns it (this word can be modified in the future).

    • Function that inserts a word in a tree. If it exists already, nothing is done.

    • Function that destroys a full tree.

    • Function that deletes a word from the tree.

  3. Write the method main containing a loop and using the function getline reads from the keyboard a string and inserts it alternatively in two trees. The program must stop when getline rerutns the value NULL.

  4. Divide the work in teams so that each of them implements either the search method, the insertion or the deletion of the whole tree. The library function strcmp receives two strings and returns an integer that is less than, equal to or greater than zero if the first string preceds, is identical or follows the second lexicographically.

  5. Implement the function to delete a string.

  6. Answer the following questions:

    1. If we compare this data structure with a linked list of words, Which data structure offers the most efficient insertion?

    2. How do these two data structures compare with respect to the search?

    3. Two trees contain exactly the same words. Does this mean they have identical structure?

    4. If in the C application using these functions, 99% of the operations are search operations, Which improvement would you propose in the data structure to gain efficiency?

How long did this activity take you? mins.
© Carlos III University of Madrid | Creative Commons License