Sistemi operativi, A.A. 2011/2012 (M. Cesati)
Scaletta esercitazione #5, 12.04.2012

1 API per la gestione delle stringhe di caratteri
   1.1 Differenza tra stringa di caratteri e vettore di caratteri
   1.1 La funzione strlen
   1.2 La funzione str[n]cmp
   1.3 La funzione str[n]cpy
   1.4 La funzione str[n]cat

2 API per l'allocazione dinamica della memoria
   2.1 La funzione malloc()
   2.2 La funzione free()
   2.3 La funzione calloc()
   2.4 La funzione realloc()
   2.5 La funzione alloca()

3 Esercizio: scrivere un programma per stampare in ordine lessicografico
  le parole passate come argomenti sulla linea comando (non devono esistere
  limiti al numero di parole gestibili)
  +---------------------------------------------------------------------------+
  |#include <stdio.h>                                                         |
  |#include <stdlib.h>                                                        |
  |#include <string.h>                                                        |
  |                                                                           |
  |char ** alloca_memoria(int n)                                              |
  |{                                                                          |
  |    char **pp;                                                             |
  |                                                                           |
  |    pp = malloc(n * sizeof(char *));                                       |
  |    if (pp == NULL) {                                                      |
  |        fprintf(stderr, "Memory allocation error\n");                      |
  |        exit(EXIT_FAILURE);                                                |
  |    }                                                                      |
  |    return pp;                                                             |
  |}                                                                          |
  |                                                                           |
  |void scambia(char **v, int x1, int x2)                                     |
  |{                                                                          |
  |    char *temp;                                                            |
  |                                                                           |
  |    temp = v[x1];                                                          |
  |    v[x1] = v[x2];                                                         |
  |    v[x2] = temp;                                                          |
  |}                                                                          |
  |                                                                           |
  |void ordina_parole(int n, char **orig, char **sorted)                      |
  |{                                                                          |
  |    int i, j;                                                              |
  |                                                                           |
  |    /* copia il vettore di puntatori originale */                          |
  |    for (i=0; i<n; ++i)                                                    |
  |        sorted[i] = orig[i];                                               |
  |                                                                           |
  |    /* bubble sort */                                                      |
  |    for (i=n; i>=0; --i)                                                   |
  |        for (j=0; j<i-1; ++j)                                              |
  |            if (strcmp(sorted[j], sorted[j+1]) > 0)                        |
  |                scambia(sorted, j, j+1);                                   |
  |}                                                                          |
  |                                                                           |
  |void stampa_parole(int n, char **parole)                                   |
  |{                                                                          |
  |    int i;                                                                 |
  |                                                                           |
  |    for (i=0; i<n; ++i)                                                    |
  |        printf("%s ", parole[i]);                                          |
  |    printf("\n");                                                          |
  |}                                                                          |
  |                                                                           |
  |int main(int argc, char *argv[])                                           |
  |{                                                                          |
  |    char **sorted_str;                                                     |
  |                                                                           |
  |    if (argc < 2) {                                                        |
  |        fprintf(stderr, "Usage: %s <parola> [<parola> [<parola> ...]]\n",  |
  |                 argv[0]);                                                 |
  |        return EXIT_FAILURE;                                               |
  |    }                                                                      |
  |                                                                           |
  |    --argc; /* numero di parole */                                         |
  |                                                                           |
  |    sorted_str = alloca_memoria(argc);                                     |
  |    ordina_parole(argc, argv+1, sorted_str);                               |
  |    stampa_parole(argc, sorted_str);                                       |
  |    return EXIT_SUCCESS;                                                   |
  |}                                                                          |
  +---------------------------------------------------------------------------+

4 Utilizzo del comando make
   4.1 Un file Makefile elementare
   +--------------------------------------------------------------------------+
   |# questo e' un commento                                                   |
   |                                                                          |
   |# definizione delle variabili: NOME=VALORE                                |
   |CC=gcc                    # compilatore                                   |
   |CFLAGS=-Wall -Wextra -O2  # flag di compilazione                          |
   |CFILES=$(shell ls *.c)    # tutti i file con estensione .c                |
   |PROGS=$(CFILES:%.c=%)     # gli stessi file senza estensione              |
   |                                                                          |
   |# formato di una regola:                                                  |
   |# NOME: PREREQUISITI                                                      |
   |# [TAB] COMANDO                                                           |
   |                                                                          |
   |# il primo target e' il default se make non ha argomenti                  |
   |all: $(PROGS)             # i prerequisiti sono tutti i file eseguibili   |
   |                                                                          |
   |# la regola per derivare un file eseguibile da un file ".c" e' automatica |
   |# equivale a:                                                             |
   |# %: %.c                                                                  |
   |# [TAB] $(CC) $(CFLAGS)  -o $@       $^                                   |
   |#                        target   prerequisiti                            |
   |                                                                          |
   |# la regola "clean" cancella tutti i file generati dal compilatore        |
   |clean:                                                                    |
   |	rm -f $(PROGS) *.o                                                    |
   +--------------------------------------------------------------------------+

5 Realizzazione di una struttura di dati dinamica: la lista semplice
  5.1 Lista come struttura di dati ricorsiva
             +----+       +----+       +----+
       >---->|  --------->|  --------->|  ------>|
             +----+       +----+       +----+
  5.2 Definizione dell'elemento base della lista:
      +------------------------------+
      |struct node_t {               |
      |      int val;                |
      |      struct node_t *next;    |
      |};                            |
      +------------------------------+
  5.3 Allocazione di un elemento della lista
     +------------------------------------------------------+
     |struct node_t *alloc_node(void)                       |
     |{                                                     |
     |    struct node_t *p;                                 |
     |    p = malloc(sizeof(struct node_t));                |
     |    if (p == NULL) {                                  |
     |        fprintf(stderr, "Memory allocation error\n"); |
     |        exit(EXIT_FAILURE);                           |
     |    }                                                 |
     |    return p;                                         |
     |}                                                     |
     +------------------------------------------------------+
  5.4 Deallocazione di un elemento della lista
      +-----------------------------------------------------+
      |void free_node(struct node_t *p)                     |
      |{                                                    |
      |    free(p);                                         |
      |}                                                    |
      +-----------------------------------------------------+
  5.5 Inserimento di un elemento in una lista
      +-----------------------------------------------------------------+
      | void insert_after_node(struct node_t *new, struct node_t *prev) |
      | {                                                               |
      |     new->next = prev->next;                                     |
      |     prev->next = new;                                           |
      | }                                                               |
      +-----------------------------------------------------------------+
  5.6 Cancellazione di un elemento da una lista
      +-----------------------------------------------------------------+
      |struct node_t *remove_after_node(struct node_t *prev)            |
      |{                                                                |
      |    struct node_t *d = prev->next;                               |
      |    prev->next = d->next;                                        |
      |    return d;                                                    |
      |}                                                                |
      +-----------------------------------------------------------------+
  5.7 Le ultime due funzioni hanno un grave problema: quale?
      5.7.1 Non funzionano correttamente per inserire un elemento in testa ad
           una lista o cancellare l'elemento di testa

================