Zoom Icon

Classi di memorizzazione

From UIC Archive

Classi di memorizzazione (parte 1)

Contents


Classi di memorizzazione
Author: anonymous
Email: .
Website: .
Date: 05/07/2008 (dd/mm/yyyy)
Level: Some skills are required
Language: Italian Flag Italian.gif
Comments: Non credo di voler lasciare commenti



Introduzione

Riprendo, con questa lezione, l’ormai famigerato corso di ANSI C per la UIC. Lo scopo di questa lezione è mostrare nel dettaglio il funzionamento e le metodologie di utilizzo delle varie classi di memorizzazione che il linguaggio C ci mette a disposizione. In particolare riprenderemo molto rapidamente il concetto di variabile e poi studieremo le struct e le union.


Le struct

Se ancora non lo è, deve diventare familiare il fatto che, concettualmente, in C, la seguente variabile

int a = -56;

in memoria virtuale (da ora MV, per ulteriori chiarimenti si veda la lezione sui puntatori) si rappresenta con un disegnino del genere:

Memorizzazione variabile.jpg

in cui, a è il nome della variabile intera, -56 è il valore ad essa associato e 1500 è il suo indirizzo in MV. Si tratta dunque della classe di memorizzazione elementare, da cui deriveranno tutte le altre. Infatti, le strutture dati che andremo a costruire, non sono altro che composizioni di strutture di memorizzazione più piccole, magari organizzate secondo una certa logica o disposte secondo un ordine che possa essere in qualche modo utile al programmatore. La prima classe di memorizzazione che andiamo ad analizzare è la struct. Anche intuitivamente, giudicandola dal nome, è una struttura che incapsula uno spazio che possiamo utilizzare per memorizzare diversi attributi. Ad esempio, sempre restando sulle variabili di tipo intero, se volessimo una struttura che rappresenti una data del calendario, la potremmo dichiarare in questo modo:

struct mydate { unsigned int year; unsigned int month; unsigned int day; };

Prima di tutto vi faccio notare che, alla fine della sua definizione, dopo la chiusura della parentesi graffa, c’è un punto e virgola (;). Va messo sempre, altrimenti non compilate nulla.  La struttura consta di tre campi di tipo intero senza segno, che rappresentano rispettivamente l’anno, il numero che identifica il mese (chessoio.. un numero in [1..12] magari) e il numero del giorno. A ogni modo questa è una definizione di una struct, ovvero il suo modello. Se volessimo utilizzare questo tipo di dato nei nostri programmi, oltre alla definizione, dovremmo istanziare tutte quelle che ci occorrono. Supponiamo, ad esempio, di voler utilizzare tre strutture di questo tipo per memorizzare tre giornate diverse. Il codice assume questa forma:

.. struct mydate giorno1; struct mydate giorno2; struct mydate giorno3; ..

Quello che avete appena letto istanzia tre strutture, giorno1, giorno2 e giorno3 distinte tra loro, ognuna delle quali occupa un certo spazio in MV. Appena esse sono istanziate, i valori dei campi al loro interno sono non significativi. Procediamo allora a una loro inizializzazione (sempre casuale, sto inventando tutto): supponiamo di voler memorizzare la mia data di nascita, il giorno di Natale e.. la festa di San Valentino:

.. /* istanzio le strutture dati */ struct mydate giorno1; struct mydate giorno2; struct mydate giorno3;

/* memorizzo la mia data di nascita in ‘giorno1’ */ giorno1.year = 1985; giorno1.month = 6; giorno1.day = 26;

/* memorizzo il giorno di natale in ‘giorno2’ */ giorno2.year = 2008; giorno2.month = 12; giorno2.day = 25;

/* memorizzo la festa di San Valentino in ‘giorno3’ */ giorno3.year = 2008; giorno3.month = 2; giorno3.day = 14; ..

Quello che avete visto fino ad ora è un banale esempio (ma del tutto funzionante) di come possano essere utilizzate le strutture dati complesse. Ovviamente, dovete modellare le vostre strutture in funzione di quello che vi serve. Se, ad esempio, state costruendo una vostra agenda degli appuntamenti, avete la necessità di memorizzare diversi tipi di informazione per ogni appuntamento che dovete memorizzare. Per esempio, una struttura dati per appuntamenti di questo tipo potrebbe essere:

  1. define MAXLOAD 1024

struct mydate { unsigned int year; unsigned int month; unsigned int day; };

struct appointment { char subject[MAXLOAD]; char where[MAXLOAD]; struct mydate when; };

Ecco, in questo esempio ho utilizzato anche una struct annidata. La struttura appointment ha diversi campi: uno per l’oggetto dell’appuntamento (può essere, ad esempio, “cena con il capo”), uno per indicare un eventuale luogo d’appuntamento (ad esempio “ristorante MangiaTanto”) e infine la data dell’appuntamento, ottenuta proprio piazzando una struttura mydate nel modello strutturale di appointment. Una banale memorizzazione di appuntamento potrebbe essere la seguente:

.. /* istanzio */ struct appointment mioapp;

/* riempio */ strncpy(mioapp.subject, “Cena con il capo”, MAXLOAD); strncpy(mioapp.where, “Ristorante MangiaTanto”, MAXLOAD); mioapp.when.year = 2008; mioapp.when.month = 6; mioapp.when.day = 30; ..

Se doveste inserire nella vostra agenta questo appuntamento, vi indicherebbe che avete una cena con il vostro capo, nel ristorante MangiaTanto il 30 giugno 2008.



Un primo esempio pratico

Ovviamente, dato che state seguendo questo corso di C, non siete ancora in grado (o, se lo siete, scusatemi: non è mia intenzione offendere la vostra intelligenza, ma questo corso non darà cose per scontate) di sviluppare applicazioni di dimensioni spropositate, però dovreste riuscire a capire in che modo costruirò, nei paragrafi successivi, una piccola agenda elettronica che utilizzerà le strutture dati che ho dichiarato prima. Dopo aver ripetuto il concetto che si tratterà di un’applicazione puramente dimostrativa (e dunque veramente molto elementare), iniziamo a progettarla. Faremo un programmino che gira in console, in grado di inserire, eliminare e cercare degli appuntamenti salvati nell’agenda (tre funzioni che realizzeremo in maniera molto semplice). Per la rappresentazione dei dati, utilizzeremo un array con una capacità iniziale di N posizioni. Gli appuntamenti verranno inseriti nella prima posizione libera a sinistra (questo è molto inefficiente e soprattutto utilizza un sacco di spazio in memoria che si potrebbe risparmiare… però è molto facile da programmare e si adatta benissimo allo scopo della lezione). Nel caso in cui non ci siano posizioni libere, la dimensione dell’array viene raddoppiata. Per realizzare tutto questo userò qualche malloc e qualche free; se ancora non conoscete queste due funzioni, non allarmatevi, per due motivi: 1) Per ora potete anche pensarle in senso intuitivo come allocazione dinamica della memoria (malloc) e de allocazione (free) della stessa; 2) Anche se non capite esattamente quello che fanno, non è questo il punto cruciale che l’applicazione vuole mostrare. Lo stesso discorso vale per qualsiasi altro concetto venga applicato di seguito, che non è ancora stato studiato. Partiamo dall’entry point del programma per poi sviluppare le operazioni di contorno

  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <string.h>
  1. define MAXLOAD 1024
  2. define SEL_NEXT_LOOP 0
  3. define SEL_INSERT 1
  4. define SEL_SEARCH 2
  5. define SEL_DELETE 3
  6. define SEL_QUIT 4
  7. define BOOL int
  8. define FALSE 0
  9. define TRUE 1 /* attenzione a non usarlo impropriamente */

struct mydate { unsigned int year; unsigned int month; unsigned int day; };

struct appointment { char subject[MAXLOAD]; char where[MAXLOAD]; struct mydate when; };

/* Entry point */ int main(int argc, char **argv) { /* dati per la rappresentazione dell’agenda */ size_t capacity = 0; struct appointment **agenda; size_t posti_liberi;

/* inizializzazione */ alloca_agenda(&agenda, &capacity); posti_liberi = capacity;

/* main-loop */ int select; do { /* visualizza un menu principale */ select = visualizza_menu(); printf("\n\n"); switch(select) { case SEL_INSERT: { if(posti_liberi == 0) { alloca_agenda(&agenda, &capacity); posti_liberi = capacity/2; }

if(aggiungi_appuntamento(agenda, capacity)) posti_liberi--;

break; }

case SEL_DELETE: { if(elimina_appuntamento(agenda, capacity)) posti_liberi++; break; }

case SEL_SEARCH: { cerca_appuntamento(agenda, capacity); break; }

case SEL_QUIT: break;

default: select = SEL_NEXT_LOOP; break; } printf("\n\n"); } while(select != SEL_QUIT);

/* il programma termina; in questa lezione non ci preoccupiamo di salvare tutto su disco; liberiamo le risorse e terminiamo. */ distruggi_agenda(agenda, capacity); return EXIT_SUCCESS; }

Una volta che è stata definita la struttura del programma principale, possiamo passare all’implementazione di tutte le funzioni mancanti per farlo funzionare. Attenzione, un approccio di questo genere, pur essendo veramente ottimale (sia nel senso che il programma esce molto lineare e comprensibile, sia nel senso che si abbassa moltissimo la sua complessità di progettazione e implementazione) è difficile da realizzare, soprattutto per chi non è abituato a programmare in qualsiasi linguaggio e soprattutto se il programma da realizzare ha dimensioni molto grosse (non è questo il caso chiaramente). Tuttavia ci sono dei programmatori che, per progettare, iniziano sistematicamente dal main. L’altro approccio consiste nel pensare alle singole funzioni che deve realizzare il programma, svilupparle e poi adattarle (eventualmente modificandole) all’interno di una funzione main che, prima d’ora, non esisteva nemmeno. Dato che io ho seguito la prima metodologia, continuiamo con questa e dunque ricaviamo la specifica di ogni funzione da implementare secondo il ruolo che questa ricopre del main. Una volta che abbiamo le specifiche, possiamo implementare facilmente. Iniziando dall’alto verso il basso (e da sinsitra verso destra :P) la prima funzione che incontriamo è alloca_agenda.

void alloca_agenda(struct appointment ***agenda, size_t *capacity) { struct appointment **new_agenda; size_t new_capacity; int i;

/* calcolo la nuova capacità */ new_capacity = *capacity*2; if(new_capacity == 0) new_capacity = 3;

/* alloco la nuova agenda */ new_agenda = (struct appointment **) malloc( new_capacity * sizeof(struct appointment *));

/* inizializzazione della nuova agenda, preservando i vecchi contatti */ for(i=0; i < (int) new_capacity; i++) { if(i < (int) *capacity) new_agenda[i] = (*agenda)[i]; else new_agenda[i] = NULL; }

/* distruggo la vecchia agenda e la rimpiazzo con la nuova, più grande */ free(*agenda) *agenda = new_agenda; *capacity = new_capacity; }

Credo che si tratti della procedura più complicata di tutto il programma (non perché sia complicata ma perché ha un puntatore triplo.. e io so che a voi fanno ribrezzo i puntatori, soprattutto quelli tripli :P) quindi ci spendo un po’ di paroline per addolcirvi un po’ la zuppa. In sostanza, la funzione alloca lo spazio necessario per poter utilizzare la nostra agenda. All’inizio dei tempi, dobbiamo creare ex-novo un’agenda vuota; per questo motivo dobbiamo utilizzare la funzione alloca_agenda in questo modo:

size_t capacity = 0; struct appointment **agenda; alloca_agenda(&agenda, &capacity);

Il fatto che, inizialmente, capacity valga 0, fa si che venga creata un’agenda ex-novo con 3 posizioni libere. Allora, prima di tutto la funzione calcola di che dimensione deve essere creata l’agenda, quindi la alloca. Nel caso in cui stiamo usando alloca_agenda per ampliare la dimensione di un’agenda precedente, il ciclo for esegue il salvataggio dei riferimenti ai contatti presenti nella agenda vecchia. Fatto questo, viene liberata la memoria usata dalla vecchia struttura e viene fatto in modo che la nostra variabile agenda punti alla nuova. Il punto cruciale è proprio questo: noi abbiamo il puntatore agenda fuori dalla funzione alloca_agenda.. ma quest’ultima deve essere in grado di modificarne il riferimento, per farlo puntare alla nuova struttura allocata. Per fare ciò, abbiamo bisogno di passare, alla funzione di allocazione, non la semplice agenda ma l’indirizzo, in memoria virtuale, in cui si trova il valore della variabile che punta alla struttura, precisamente, vogliamo l’indirizzo della variabile agenda dichiarata nel corpo del main. In questo modo, con le istruzioni

  • agenda = new_agenda;
  • capacity = new_capacity;

prima diciamo che MV[agenda] = new_agenda, modificando così la variabile agenda che si trova nel corpo del main, e poi facciamo la stessa cosa con la variabile capacity, sempre dichiarata nel corpo del main. Se tutto questo non vi è chiaro, andate a rileggervi la lezione sui puntatori e fatevi un bel disegnino anche per questo semplice scenario. E’ importante, osservando il corpo del main e ora anche quello della funzione alloca_agenda, notare che la struttura agenda è un array di puntatori a struttura. Questo esempio è diverso da quello fatto nella lezione dei puntatori perché questa volta abbiamo la necessità di sapere se un posto riservato agli appuntamenti è effettivamente utilizzato oppure no. Se questo “posto” fosse direttamente una struttura, dovremmo avere un campo, all’interno di appointment che ci fornisca la “presenza” effettiva nell’agenda. Invece di fare ciò, stabiliamo che ogni posizione punta a una struttura appointment. In questo modo, la presenza ci è data dalla condizione agenda[index] != NULL, dove index è proprio la posizione in questione. La seconda funzione che incontriamo è aggiungi_appuntamento:

BOOL aggiungi_appuntamento(struct appointment **agenda, size_t capacity) { size_t index = 0; char buffer[MAXLOAD];

/* cerco la prima posizione libera nell'array */ while(index < capacity && agenda[index] != NULL) index++; if(index == capacity) return FALSE;

/* allocazione della struttura di memorizzazione */ agenda[index] = (struct appointment *) malloc(sizeof(struct appointment)); if(agenda[index] == NULL) return FALSE;

/* chiedo l'input all'utente e riempio la struttura */ printf("Oggetto: "); fgets(agenda[index]->subject, MAXLOAD, stdin); printf("Luogo: "); fgets(agenda[index]->where, MAXLOAD, stdin); printf("Data (gg/mm/yyyy): "); fgets(buffer, MAXLOAD, stdin); buffer[2] = '\0'; buffer[5] = '\0'; agenda[index]->when.day = atoi(buffer+0); agenda[index]->when.month = atoi(buffer+3); agenda[index]->when.year = atoi(buffer+6);

return TRUE; }

Concentriamoci sulla parte relativa all’inserimento vero e proprio. Vogliamo inserire un nuovo appuntamento alla posizione index della nostra agenda. Subito mallochiamo lo spazio necessario per l’inserimento dei valori. Fatto questo, abbiamo in agenda[index] il puntatore (quindi bisogna accedervi con la freccina) a tutti i campi che interessano l’appuntamento. Come vedete, agenda[index] è di tipo struct appointment * per via della soluzione al succitato problema delle “presenze effettive”. Prossima funzione: elimina_appuntamento:

BOOL elimina_appuntamento(struct appointment **agenda, size_t capacity) { char buffer[MAXLOAD]; int index;

/* chiedo l'input */ printf("Oggetto dell'appuntamento da eliminare:\n"); fgets(buffer, MAXLOAD, stdin);

/* effettuo la ricerca */ index = search_by_subject(agenda, capacity, buffer); if(index != -1) { /* libero la memoria ed elimino */ free(agenda[index]); agenda[index] = NULL; }

return (index != -1); }

La funzione chiede all’utente di digitare l’oggetto dell’appuntamento da eliminare e dunque elimina un appuntamento (il primo in ordine di scansione da sinistra a destra) che ha tale oggetto. La funzione restituisce TRUE se ha effettivamente eliminato un elemento; FALSE altrimenti. Per effettuare la ricerca ho usato una funzione ausiliaria chiamata search_by_subject. Ho scritto una funzione perché la utilizzo anche in cerca_appuntamento. Vediamo come è fatta, è molto semplice:

int search_by_subject(struct appointment **agenda, size_t capacity, char *subject) { int index = 0; BOOL found = false;

while(!found && index < (int) capacity) { if(agenda[index] != NULL) { found = (strncmp(agenda[index]->subject, subject, MAXLOAD) == 0); if(!found) index++; } else { index++; } }

if(!found) index = -1; return index; }

E’ una semplicissima ricerca lineare che restituice -1 nel caso in cui non sia presente un elemento avente l’oggetto uguale a subject. In modo molto intuitivo, come parametri prende proprio l’agenda (struct appointment **) e la sua capacità per poter eseguire la scansione dall’inizio alla fine. Questo perché, come avrete intuito, visto che gli array in C non hanno una proprietà che ne indichi la lunghezza, qualsiasi operazione operante su array che abbia la necessità di scandirlo fino alla fine o più in generale di conoscerne il limite destro, oltre all’array stesso deve per forza prendere in input qualcosa che ne esprima la lunghezza. Comunque nulla di difficile. Funzione cerca_appuntamento

void cerca_appuntamento(struct appointment **agenda, size_t capacity) { char buffer[MAXLOAD]; int index;

/* chiedo input all'utente */ printf("Oggetto da cercare:\n"); fgets(buffer, MAXLOAD, stdin);

/* cerco e stampo */ index = search_by_subject(agenda, capacity, buffer); if(index != -1) stampa_appuntamento(agenda[index]); else printf("Nessun appuntamento trovato!\n"); }

E’ un’altra situazione in cui usiamo search_by_subject. Questa volta, dopo aver chiesto all’utente l’oggetto dell’appuntamento da individuare, effettuiamo la ricerca e, se questa va a buon fine (risultato diverso da -1), stampiamo a video le informazioni dell’appuntamento individuato. Per fare questo, ho usato un’altra funzioncina ausiliaria chiamata stampa_appuntamento veramente elementare:

void stampa_appuntamento(struct appointment *app) { printf("Oggetto: %s", app->subject); printf("Luogo:  %s", app->where); printf("Data:  %d/%d/%d", app->when.day, app->when.month, app->when.year); printf("\n"); }

Questa volta ho usato una funzione esterna per motivi puramente stilistici. Se il codice è sufficientemente modularizzato, chi lo legge (e in questo caso la cosa mi sembra piuttosto importante, essendo questo un tutorial :D) riesce a capirne il significato con uno sforzo decisamente basso. L’ultima funzione che ci resta da guardare è la distruggi_agenda:

void distruggi_agenda(struct appointment **agenda, size_t capacity) { size_t i; for(i=0; i < capacity; i++) if(agenda[i] != NULL) free(agenda[i]); free(agenda); }

Eseguo la free di ciascun elemento (appuntamento) che sia diverso da NULL e poi eseguo la free della struttura che conteneva tali elementi. Dopo ciò, dovrei avervi fornito tutta una serie di esempi legati all’utilizzo delle struct come parametri di funzioni da permettervi di pensare a quello che ho fatto e farvi capire il perché ho usato queste scritture. Nel paragrafo successivo parleremo della memoria occupata dalle struct e da come queste possono essere utilizzate per la manipolazione di dati strutturati in modo persistente.


Dimensione di una struct

Una caratteristica molto importante delle struct è che esse sono allocate dal compilatore lasciando i campi nella stessa posizione in cui sono stati disposti dal programmatore. Questo fa sì che possano essere utilizzate per dei giochetti che scopriremo tra poco. Inoltre, ogni struct, in funzione del numero di campi che contiene e dunque dalla dimensione che ha ciascuno di essi, ha una certa dimensione. Se ad esempio considerassimo la struct mydate, vedendo che contiene tre interi e sapendo che ogni intero occupa 4 byte, sappiamo che l’intera struct occuperà 3*4 = 12 byte; e il discorso vale sia in MV che su disco. Facciamo un altro esempio considerando la struttura appointment vista sopra:

struct appointment { char subject[MAXLOAD]; char where[MAXLOAD]; struct mydate when; };

MAXLOAD, nel nostro caso, vale 1024. Quindi subject pesa 1024 byte, così come where; mentre per quel che riguarda when, abbiamo appena detto che pesa 12 byte. Il peso complessivo della struttura sarà allora 1024+1024+12 byte = 2060 byte, salvo arrotondamenti fatti da qualche compilatore (alcuni fanno sì che una struttura abbia una dimensione multipla di 4). E’ molto importante notare che questa struttura occupa 2060 byte perché contiene due stringhe grandi 1K; queste non sono puntatori a stringa ma sono proprio 2048 byte complessivi che fanno parte del peso della struttura. Per chiarirvi meglio il concetto, facciamo un esempio diverso. Se io avessi la seguente struttura:

struct persona { char *nome; char *cognome; char *indirizzo; unsigned int eta; struct mydate *data_di_nascita; /* anche questo e’ un puntatore */ };

occuperebbe molto meno della precedente. In particolare, nome, cognome, indirizzo e data_di_nascita non sono allocate direttamente nella struttura ma sono dei puntatori che andranno inizializzati al momento del loro utilizzo rispettivamente con tre stringhe e una struttura mydate, dichiarate al di fuori della struct in questione e che comunque non contribuiranno ad ingrandirne le dimenioni. Dato che ogni puntatore della nostra architettura occupa 4 byte, persona occuperà sempre 4*4 byte (quattro byte per ogni puntatore) + 4 byte (quattro byte per l’intero senza segno) = 20 byte; ripeto: qualsiasi sia la dimensione delle stringhe che vengono assegnate a tali puntatori, la dimensione di persona sarà sempre di 20 byte. Potete in ogni modo verificare quale sia la dimensione di una struttura con l’operatore sizeof, nel seguente modo (per la gioia del papero :P):

size_t dd = sizeof(struct persona); printf(“La dimensione di persona e’ %d\n”, dd);

A conferma di quanto ho scritto poco fa, vi faccio notare che sizeof può essere usato anche sul nome del tipo (oltre che sul nome dell’istanza del tipo). Questo vi indica che persona ha una propria dimensione, indipendente dal valore assunto dai puntatori che contiene.


Persistenza di un tipo di dato strutturato

Per chi non lo sapesse, il termine persistenza sta ad indicare il fatto che qualsiasi forma di dato è di memorizzazione permanente anche dopo la terminazione del programma che ne fa uso. Una bitmap salvata su disco, ad esempio, è una forma di dato permanente. Se spegnete il computer e poi lo riaccendete, la succitata bitmap sarà ancora al suo posto. Questa cosa non succede nel programma che abbiamo progettato prima. In particolare, se voi memorizzate 30 appuntamenti, all’uscita del programma questi vengono volatilizzati senza essere salvati (ad esempio su disco). Se noi volessimo salvarli? Beh.. in linea di principio non è difficile.. basterebbe, prima della chiusura del programma, creare un file che contenga tutte le informazioni relative a tutti gli appuntamenti memorizzati. In questo modo, il software, al momento dell’avvio, potrebbe recuperare i dati dell’agenda. Però però però… quello di cui voglio parlarvi ora, è un caso un po’ particolare dell’utilizzo delle strutture. Facendo veramente poca fatica, potremmo creare una funzione, per eseguire questo salvataggio su disco, che salvi su di un file tutti gli appuntamenti memorizzati nell’agenda proprio sotto forma di struttura. Nel paragrafo precedente abbiamo detto che ogni struttura ha una sua dimensione; nel nostro caso, appointment è poco più grande di 2 KB. Mettiamo di aver memorizzato 10 appuntamenti? Beh.. se mettessimo su file le 10 strutture, esattamente così come sono disposte in memoria virtuale, avremmo un file di circa 20 KB. Facciamolo subito: vi faccio vedere il codice e poi ve ne commento i pro e i contro.

BOOL save_to_file(struct appointment **agenda, size_t capacity) { int index = 0;

/* apro il file agenda.dat in scrittura */ FILE *f = fopen("agenda.dat", "wb"); if(f == NULL) return FALSE;

/* per ogni elemento dell'array */ for(index = 0; index < (int) capacity; index++) { /* se l'appuntamento corrente è diverso da NULL */ if(agenda[index] != NULL) { /* lo scrivo su file */ fwrite(agenda[index], sizeof(struct appointment), 1, f); } } fclose(f); return TRUE; }

In sostanza è molto semplice: apro un file in scrittura (“agenda.dat”) e poi inizio a scorrere lungo tutto l’array che rappresenta la mia agenda; per ogni elemento consistente (diverso da NULL) dell’agenda, eseguo una scrittura su file, piazzandoci dentro esattamente tutta la struct che mi descrive l’appuntamento. Finita l’iterazione, chiudo il file. Ora, dualmente, vediamo come si fa, partendo questa volta dal file che contiene le strutture, a ricavare un’agenda con queste:

BOOL load_from_file(struct appointment ***agenda, size_t *capacity) { FILE *f; unsigned int n_app; int i; long file_size;

/* ottengo la dimensione del file da leggere */ f = fopen("agenda.dat", "rb"); if(f == NULL) return FALSE; fseek(f, 0, SEEK_END); file_size = ftell(f)+1; fseek(f, 0, SEEK_SET);

/* ottengo il numero di appuntamenti da leggere */ n_app = file_size/sizeof(struct appointment); if(n_app == 0) { /* nessun appuntamento */ fclose(f); return FALSE; }

/* alloco l'agenda di dimensioni sufficienti, con 3 posti vuoti */ *capacity = n_app+3; *agenda = (struct appointment **) malloc(*capacity * sizeof(struct appointment *));

/* procedo al suo riempimento con i dati forniti dal file */ for(i=0; i < (int) n_app; i++) { (*agenda)[i] = (struct appointment *) malloc(sizeof(struct appointment)); fread((*agenda)[i], sizeof(struct appointment), 1, f); }

/* chiudo il file e termino */ fclose(f); return TRUE; }

Dato che la nostra struct ha dimensione fissa, se faccio dimensione_file/dimensione_struct, ottengo esattamente il numero di strutture che sono state scritte nel file. Dunque salvo questo numero nella variabile n_app e la uso (sommandoci 3, per avere comunque un po’ di posti liberi nell’agenda) per mallocare una dimensione di memoria sufficiente a contenerla. Fatto questo, leggo, una alla volta, tutte le struct che sono dentro al file e le assegno a agenda[i], dove i è la variabile indice che corre in [0, n_app). Vantaggi derivati dall’uso di queste due procedure: 1) Nessuna operazione di parsing per leggere le strutture dal file; 2) Codice molto leggibile e lineare; 3) Nessuna necessità di avere una struttura di heading nel file per il salvataggio degli appuntamenti; 4) Anche se in questo caso non abbiamo usato questa caratteristica, sarebbe possibile (sempre grazie al fatto che le struct hanno tutte la stessa dimensione) operare direttamente su file, oppure leggere struct a indici diverse semplicemente spostado di sizeof(struct appointment) il puntatore di I/O associato al file aperto (con fseek, ad esempio). Svantaggi: 1) Abbondante spreco di spazio su disco: soprattutto per quanto riguarda il caso specifico degli appuntamenti, generalmente oggetto e luogo sono stringhe di pochi caratteri; la nostra struct però prevede stringhe di 1024 byte, che vengono necessariamente scritti su file anche se sono non significativi; 2) Inefficienza di lettura e scrittura legata alle grosse dimensioni della nostra struct, dato che, ogni volta che leggiamo (scriviamo) una struttura da (su) disco, preleviamo (salviamo) sempre 2 KB, a prescindere dall’effettiva dimensione delle stringhe (ad esempio la stringa “visita a Firenze”, contando 16 caratteri, è molto lontana dall’essere grande 1024 byte). Insomma.. è chiaro che si potrebbe fare di meglio. Come fare allora? Vediamo due procedure che, rispetto a queste che vi ho appena mostrato, risparmiano mediamente molto spazio su disco, sacrificando qualche operazioncina di parsing molto facili. Iniziamo con l’operazione di scrittura su file perché è un po’ più facile:

BOOL save_to_file_2(struct appointment **agenda, size_t capacity) { int index = 0; size_t size = 0;

/* apro il file agenda.dat in scrittura */ FILE *f = fopen("agenda.dat", "wb"); if(!f) return FALSE;

/* lascio uno spazio vuoto all'inizio del file */ fwrite(&size, sizeof(size_t), 1, f);

/* per ogni elemento dell'array */ for(index = 0; index < (int) capacity; index++) { /* se l'elemento corrente è consistente */ if(agenda[index] != NULL) { size++;

/* scrivo subject */ fwrite(agenda[index]->subject, strlen(agenda[index]->subject)+1, 1, f);

/* scrivo where */ fwrite(agenda[index]->where, strlen(agenda[index]->where)+1, 1, f);

/* scrivo when */ fwrite(&(agenda[index]->when), sizeof(struct mydate), 1, f); } }

/* uso lo spazio vuoto che ho lasciato prima, per memorizzare su file il numero di appuntamenti che ho effettivamente memorizzato. */ fseek(f, 0, SEEK_SET); fwrite(&size, sizeof(size_t), 1, f);

/* chiudo */ fclose(f); return TRUE; }

La sostanziale differenza, rispetto al caso di prima, è che non salvo su disco l’intera struttura ma ne scrivo i singoli campi, uno per volta. Così facendo, sia per subject che per where, ho la possibilità di calcolarne la lunghezza da scrivere su file, tralasciando, questa volta, i byte di padding che facevano parte della dimensione delle stringhe della struttura. L’unica cosetta un attimo diversa rispetto a prima è che, oltre alle strutture degli appuntamenti, uso, in cima al file, quattro byte per salvare il numero degli appuntamenti che ho memorizzato nel file. In questo modo, nella fase di lettura sarà estremamente più semplice ottenere le dimensioni della struttura da mallocare. Iniziamo allora a parlare di questa fase di lettura. Prima di tutto, leggo i primi quattro byte, che mi indicano quanto deve essere grande (quantità espressa in numero di appuntamenti) la struttura dati per contenere tutti i dati memorizzati; fatto questo, si procede alla lettura di ogni singolo appuntamento e al suo piazzamento nell’agenda. Per fare questo occorre, a differenza di prima, fare un parsing dei dati, perché stavolta una struttura salvata su disco non occupa affatto 2 KB. Le stringhe sono molto corte, dunque occorre leggerle come si deve. Questo è un parsing lineare, che può essere fatto con un automa a stati finiti (tra l’altro adesso vi mostro una tecnica che vi permette di fare questo tipo di parser annullandone del tutto la complessità di progettazione.. non fa parte del corso.. però visto che questo lo sto scrivendo io, deve pur insegnarvi qualche ganzata no? :D). Il parsing funzionerà così: • Inizialmente ci troviamo a leggere i byte che compongono il campo subject. Se in questo stadio troviamo il byte EOF, vuol dire che c’è qualche problema (errore di parsing dunque) nella struttura del file. Continuiamo a restare in questo stato (che chiamiamo (0)) fino a quando non incontriamo il terminatore di stringa ‘\0’. Appena lo incontriamo, passiamo allo stato successivo (1); • Nello stato (1) dobbiamo leggere i byte che compongono il campo where. Anche in questo caso, se incontriamo EOF, finiamo in uno stato di errore, e anche in questo caso, continuiamo a restare in (1) fino a quando non incontriamo il terminatore che ci fa andare in (2); • Lo stato (2) è quello che, con un colpo solo, legge la struttura mydate. Dopo la lettura, finisce l’esecuzione dell’automa di parsing. L’automa che vi ho descritto a parole pocanzi è il seguente:

Memorizzazione automa1.jpg

Quando avete a che fare con automi a stati finiti, potete passare molto facilmente dal loro disegno alla loro realizzazione seguendo una semplicissima struttura. Ve la faccio vedere direttamente con il codice dell’automa perché è più difficile a dirsi che a farsi:

BOOL autom_parse(struct appointment *app, FILE *f) { int state = 0; char ch; int ind_sub = 0; int ind_whe = 0; /* le variabili son gratis, non vi fate scrupoli */

while(1) { switch(state) { case 0: ch = (char) fgetc(f); if(ch == EOF) state = 7; else if(ch == '\0') state = 1; else app->subject[ind_sub++] = ch; break;

case 1: app->subject[ind_sub] = '\0'; ch = (char) fgetc(f); if(ch == EOF) state = 7; else if(ch == '\0') state = 2; else app->where[ind_whe++] = ch; break;

case 2: app->where[ind_whe] = '\0'; fread(&(app->when), sizeof(struct mydate), 1, f); return TRUE;

case 7: return FALSE; } } return FALSE; }

Siamo in un ciclo while infinito; questo significa che per uscirne ci dovrà essere un break riferito al ciclo o un return che faccia terminare tutta la funzione. Molte volte i break messi in mezzo al codice solleticano la suscettibilità dei programmatori integralisti che dicono che poi il codice non si capisce. Facendo salvo il fatto che il comando break esiste ed è utilizzato in tutti i kernel del mondo, possiamo dire che, in questo caso, questa sciocchezza non ci riguarda: dopo aver fornito un disegno o una spiegazione dell’automa che vogliamo implementare, salta subito all’occhio quali sono gli stati di uscita e quali sono invece gli stati che vogliono effettuare delle transizioni. Lo stato di errore di parsing l’ho chiamato (7), mentre quello di uscita regolare (2). Guardando il codice infatti si capisce subito che 2 e 7 sono gli stati di uscita (c’è il return). Tutti gli altri stati hanno dei break che però sono riferiti allo switch e non al while. Appare chiaro dunque che sono degli stati che vogliono fare delle transizioni (che si fanno semplicemente assegnando un nuovo valore alla variabile state). Per chi fosse uno di quei tipi isterici a cui non piacciono le cose mai viste, è inutile che vi concentriate cercando bachi o costi computazionali pazzeschi. E’ un modo elegante e di costo lineare per implementare un automa a stati finiti. Funziona sempre, senza alcuna eccezione. Ah.. dimenticavo: VI ODIO, non capite nulla, siete anti-tecnologici. Ora che abbiamo l’automa (restituisce TRUE se il parsing è andato a buon fine, FALSE altrimenti) possiamo usarlo nella funzione di lettura da file (che a questo punto diventa piuttosto facile; era l’automa la parte rompiscatole):

BOOL load_from_file_2(struct appointment ***agenda, size_t *capacity) { FILE *f; size_t size; int index = 0;

/* apro il file in lettura */ f = fopen("agenda.dat", "rb"); if(!f) return FALSE;

/* quanti appuntamenti devo leggere? */ fread(&size, sizeof(size_t), 1, f);

/* memoria.. */ *agenda = (struct appointment **) malloc((size + 3)*sizeof(struct appointment *)); if(!*agenda) return FALSE;

/* inizializzazione */ for(index=0; index<(int) size+3; index++) (*agenda)[index] = NULL;

*capacity = (size + 3); index = 0;

/* prelevo i dati dal file */ while(size > 0) { if((*agenda)[index] == NULL) (*agenda)[index] = (struct appointment *) malloc(sizeof(struct appointment)); if(autom_parse((*agenda)[index], f)) index++; size--; }

/* chiudo */ fclose(f); return TRUE; }

Come vedete, all’inizio del mondo leggo, in un intero, il numero di appuntamenti da prelevare dal file (che abbiamo preventivamente salvato e citato nella funzione save_to_file_2). In questo modo so quanto spazio allocare. Ho comunque deciso di allocare sempre 3 posti liberi per non faultare subito in caso di inserimenti in agenda (nei casi reali, queste cose devono essere razionalizzate: bisogna pensare all’uso tipico di un’agenda.. in teoria, in questo caso sarebbe meglio ottimizzare la ricerca visto che tendenzialmente e mediamente vengono fatte molte più ricerce rispetto agli inserimenti, comunque non è una cosa che riguarda questo corso; sappiatelo e basta). La conclusione di questo discorso è che comunque le due alternative non sono sempre o vantaggiose o svantaggiose. Nel caso che abbiamo visto, le stringhe erano pre-allocate in uno spazio di 1 KB, quindi per risparmiare spazio abbiamo fatto tutto quel lavoro. Esistono però casi in cui è la prima ad essere l’alternativa favorita. Un caso proprio eclatante è l’header (o intestazione, o PCB, o come vi pare) dei file eseguibili dei sistemi microsoft. Includendo nei vostri programmi il file “windows.h” potete sfruttare le struct IMAGE_DOS_HEADER e IMAGE_NT_HEADERS per navigare nelle complesse (?) strutture dei file eseguibili. Finisco il lavoro sulle struct facendovi dunque vedere un programmino che stampa poche informazioni principali di qualsiasi file eseguibile Windows ([b]per mostrarvi questo piccolo esempio però mi discosterò un po’ dalla versione ANSI del C e userò il paradigma di programmazione proprio dei sistemi windows; concentrate la vostra attenzione sulla parte relativa all’uso di IMAGE_DOS_HEADER E IMAGE_NT_HEADERS che, anche se forse non sembra, sono delle struct[/b]):

  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <windows.h>
  1. define MAXLOAD 1024

int main(int argc, char **argv) { char FileName[MAXLOAD]; HANDLE hFile; DWORD FileSize, junk; IMAGE_DOS_HEADER *mz; IMAGE_NT_HEADERS *pe;

/* chiedo l'input all'utente */ printf("Inserisci il percorso completo del file PE da aprire:\n"); fgets(FileName, MAXLOAD, stdin); FileName[strlen(FileName)-1] = '\0';

/* apro il file */ hFile = CreateFileA(FileName, GENERIC_READ, 0, NULL, OPEN_EXISTING, 0, 0); if(hFile == INVALID_HANDLE_VALUE) { printf("E: Impossibile aprire il file specificato.\n"); return -1; }

/* leggo tutto il file in memoria e lo rilascio */ FileSize = GetFileSize(hFile, NULL); mz = (IMAGE_DOS_HEADER *) VirtualAlloc(NULL, sizeof(char)*FileSize, MEM_COMMIT, PAGE_READWRITE); ReadFile(hFile, mz, FileSize, &junk, NULL); CloseHandle(hFile);

/* verifica sulla firma DOS */ if(mz->e_magic != IMAGE_DOS_SIGNATURE) { VirtualFree(mz, FileSize*sizeof(char), MEM_DECOMMIT); printf("E: Il file specificato non è un eseguibile windows.\n"); return -2; }

/* raggiungo l'header windows */ pe = (IMAGE_NT_HEADERS *)(mz->e_lfanew + (long) mz); if(pe->Signature != IMAGE_NT_SIGNATURE) { VirtualFree(mz, FileSize*sizeof(char), MEM_DECOMMIT); printf("E: Il file specificato non è un eseguibile windows.\n"); return -3; }

/* stampo le principali caratteristiche */ printf("\n"); printf("Characteristics: 0x%08X\n", pe->FileHeader.Characteristics); printf("Machine: 0x%04X\n", pe->FileHeader.Machine); printf("Number of sections: %d\n", pe->FileHeader.NumberOfSections); printf("Number of symbols: %d\n", pe->FileHeader.NumberOfSymbols); printf("Timedate stamp: 0x%08X\n", pe->FileHeader.TimeDateStamp); printf("\n");

/* libero la memoria */ VirtualFree(mz, FileSize*sizeof(char), MEM_DECOMMIT);

/* ciao a tutti */ return EXIT_SUCCESS; }


Note Finali

Con questo termino la prima parte della lezione sull’uso delle struct. Probabilente scriverò più in là un’appendice per parlare delle variabili che occupano un certo numero prestabilito di bit ma non nell’immediato futuro. Nella parte 2 della lezione vedremo che cosa sono le union e, anche per quelle, parecchi esempi di applicazione concreti che possano farvi apprendere in pieno quale sia la loro utilità.



Disclaimer

I documenti qui pubblicati sono da considerarsi pubblici e liberamente distribuibili, a patto che se ne citi la fonte di provenienza. Tutti i documenti presenti su queste pagine sono stati scritti esclusivamente a scopo di ricerca, nessuna di queste analisi è stata fatta per fini commerciali, o dietro alcun tipo di compenso. I documenti pubblicati presentano delle analisi puramente teoriche della struttura di un programma, in nessun caso il software è stato realmente disassemblato o modificato; ogni corrispondenza presente tra i documenti pubblicati e le istruzioni del software oggetto dell'analisi, è da ritenersi puramente casuale. Tutti i documenti vengono inviati in forma anonima ed automaticamente pubblicati, i diritti di tali opere appartengono esclusivamente al firmatario del documento (se presente), in nessun caso il gestore di questo sito, o del server su cui risiede, può essere ritenuto responsabile dei contenuti qui presenti, oltretutto il gestore del sito non è in grado di risalire all'identità del mittente dei documenti. Tutti i documenti ed i file di questo sito non presentano alcun tipo di garanzia, pertanto ne è sconsigliata a tutti la lettura o l'esecuzione, lo staff non si assume alcuna responsabilità per quanto riguarda l'uso improprio di tali documenti e/o file, è doveroso aggiungere che ogni riferimento a fatti cose o persone è da considerarsi PURAMENTE casuale. Tutti coloro che potrebbero ritenersi moralmente offesi dai contenuti di queste pagine, sono tenuti ad uscire immediatamente da questo sito.

Vogliamo inoltre ricordare che il Reverse Engineering è uno strumento tecnologico di grande potenza ed importanza, senza di esso non sarebbe possibile creare antivirus, scoprire funzioni malevole e non dichiarate all'interno di un programma di pubblico utilizzo. Non sarebbe possibile scoprire, in assenza di un sistema sicuro per il controllo dell'integrità, se il "tal" programma è realmente quello che l'utente ha scelto di installare ed eseguire, né sarebbe possibile continuare lo sviluppo di quei programmi (o l'utilizzo di quelle periferiche) ritenuti obsoleti e non più supportati dalle fonti ufficiali.