Universidad Carlos III de Madrid

Grado en Ing. Telemática/Sist. Audiovisuales/Sist. de Comunicaciones

Arquitectura de Sistemas

Septiembre 2012 - Enero 2013

11. Problemas sobre fugas de memoria.

Los siguientes problemas asumen que conoces las llamadas al sistema para reservar y liberar memoria dinámica.

  1. Considera el siguiente programa en C:

    #define SIZE 100
    int main(int argc, char *argv[]) 
    {
      int i, j;
      int *ptr;
    
      for (i = 0; i < SIZE; i++) 
      {
        ptr = (int *)malloc(SIZE * sizeof(int));
        for (j = 0; j < SIZE; j++) 
        {
          ptr[j] = j;
        }
      }
      ptr = NULL;
    }

    ¿Cuántas fugas de memoria tiene este fragmento de código? ¿Cuánta memoria en total se fuga?

  2. Un programador trabaja con una lista encadenada de palabras. Cada elemento de la lista tiene un puntero a una cadena y el puntero a la siguiente. La lista se representa por el puntero a su primer elemento. El código de la función de borrado de una lista es el siguiente:

    struct list_node 
    {
      char *word;
      struct list_node *next;
    };
    
    void delete(struct list_node *l) 
    {
      struct list_node *tmp;
      while (l->next != NULL) 
      {
        tmp = l;
        free(l->word);
        l = l->next;
        free(l);
      }
    }

    Tras utilizar un programa de detección de fugas, el informe dice que hay bloques de memoria sin liberar. El programador ha detectado que el problema está en esta función, pero ¿dónde exactamente? (Pista: Dibuja primero un ejemplo de lista encadenada y de cómo esta función realiza la liberación de memoria)

    ¿Qué sucede si se intenta liberar una lista vacía? Es decir, que l es NULL.

  3. Un programa necesita manipular un árbol binario (todo nodo tiene dos y sólo dos hijos). La estructura que se utiliza para esto es la siguiente:

    struct tree_node 
    {
      int value;
      struct tree_node *left;
      struct tree_node *right;
    };

    Un nodo sin hijos se representa con los dos punteros a NULL.

    1. Escribe una función que dado un entero devuelve un nodo terminal (sin hijos) con ese valor almacenado. La función debe crear ese nodo. El prototipo de la función es el siguiente:

      struct tree_node *node(int v);
    2. Escribe una función que dado un entero y dos punteros a nodos (ya creados), devuelve un nuevo nodo con el entero almacenado como valor y los dos punteros como hijos. El prototipo de la función es el siguiente:

      struct tree_node *create_node(int v, struct tree_node *left, struct tree_node *right);
    3. Escribe ahora la función main que utilice las dos anteriores para crear el árbol que se muestra en la siguiente figura:

    4. Escribe una función que dado un puntero a un nodo, libera el espacio que ocupa. No se realiza operación alguna sobre los punteros de los hijos, se asume que ya se han liberado. El prototipo de la función es:

      void delete(struct tree_node *t);
    5. Utilizando la función anterior escribe una función que, dado un puntero a un nodo, libere todos los nodos de ese árbol (cuidado, esta función no es trivial, si no logras escribirla, consúltanos). El prototipo de la función es:

      void delete_tree(struct tree_node *t);
  4. Una aplicación que ejecuta en tu móvil tiene una estructura creada basada en las siguientes definiciones:

    struct vendor 
    {
      char *vendor_name;
      int installation_date;
      int price;
    };
    struct program 
    {
      char *path;
      struct stats 
      {
        int uses;
        int last_use;
      } statistics;
      struct vendor *vendor_info;
    };
    struct program *installed_applications;
    int number_of_installed_applications;

    El programa ha reservado dinámicamente (a través de malloc) un array para tantas estructuras de tipo program como contiene la variable number_of_installed_applications y ha almacenado ese puntero en installed_applications. Cada elemento del tipo struct program tiene sus campos path y vendor_info reservados de forma dinámica. Así mismo cada elemento del tipo struct vendor tiene su campo vendorname reservado de forma dinámica

    Escribe una función que recibe un puntero de tipo struct program * a una tabla como la que hay almacenada en installed_applications y su tamaño como un entero y libera todo el espacio que ocupa la estructura de datos. El prototipo de esta función es:

    void delete(struct program *table, int size);