Home > Listati di programmi C > Allocazione di stringhe in memoria heap

ALLOCAZIONE DI STRINGHE IN MEMORIA HEAP

Funzioni e programmi per allocare stringhe di varia lunghezza in un unico blocco di memoria heap.


I dati per l'elaborazione sono contenuti in una struct di tipo desc_dati, contenente i seguenti campi:

*p_heap, puntatore alla memoria che conterra' le stringhe;

*p_dati_blocchi, puntatore a memoria per struct di tipo dati_blocco, che memorizza, per ogni blocco occupato da una stringa, posizione iniziale (in p_heap[]) e dimensione;

*p_pila_id, puntatore a interi per gestire una pila dei valori ID assegnabili univocamente ai diversi blocchi;

i_ultimo_id, indice dell'ultimo elemento inserito nella pila (che sara' il prossimo estratto);

*p_primo, *p_ultimo, puntatori inizio-fine di una lista concatenata doppia formata da struct nodo, lista usata per mappare tutti i blocchi;

dim_heap, intero che misura la dimensione totale della memoria assegnata a p_heap;

dim_libera, intero che misura il numero totale di caratteri (byte) liberi presenti in memoria;

n_liberi, n_occupati, interi che memorizzano il numero di blocchi liberi o occupati.


La struct di tipo nodo, usata per costruire una lista doppia che mappi tutti i blocchi di memoria, contiene i seguenti campi:

id_blocco, intero che identifica in modo univoco ogni singolo blocco;

i, intero usato come indice per individuare, in p_heap[], l'inizio del blocco;

dim, intero che memorizza la dimensione del blocco;

libero, intero che indica se il blocco e' libero (1) o occupato da una stringa (0).


All'inizio di un programma deve essere chiamata la funzione iniz_heap() per inizializzare il descrittore dei dati, assegnando la dimensione della memoria che sara' puntata da p_heap e predisponendo le altre variabili; in particolare, viene creata la pila degli ID assegnabili e allocata memoria per p_dati_blocchi[]; inoltre, viene creato il primo nodo della lista-mappa, che inizialmente rappresenta un unico blocco libero, della stessa dimensione della memoria totale disponibile.

Per inserire una stringa in memoria, bisogna trovare un blocco libero della dimensione sufficiente; la ricerca viene fatta con le funzioni del gruppo cerca_blocco_dim_xx() che usano vari algoritmi (first fit, worst fit, best fit); l'inserimento viene fatto con alloca_str(); se il blocco libero scelto e' piu' grande della stringa, viene creato - nella lista - un nuovo nodo, che mappa il blocco libero residuo che si e' formato. Per adesso, ho tralasciato l'algoritmo next fit.

I nodi della lista-mappa si succedono nella lista con lo stesso ordine dei blocchi corrispondenti.

Per deallocare (cioe' cancellare dalla memoria) una stringa si usa dealloca_str(); il nodo corrispondente al blocco rimane, ma viene marcato come libero; i byte del blocco vengono azzerati (ma se ne potrebbe anche fare a meno).

E' anche possibile modificare una stringa gia' presente in memoria, con la funzione cambia_str(); la funzione riceve in input una nuova stringa, che sostituisce la vecchia; sono trattati separatamente i tre casi possibili: la nuova stringa e' piu' lunga della vecchia, ha la stessa lunghezza, e' piu' corta. Il primo caso (stringa nuova piu' lunga della vecchia) e' quello che ha richiesto la soluzione piu' laboriosa: prima si cerca di utilizzare (per i caratteri aggiuntivi) l'eventuale blocco libero successivo; se non e' possibile, si scansiona la lista per vedere se c'e' un blocco libero idoneo a contenere la nuova stringa (e la vecchia si cancella); se non si riesce, si compattano i blocchi liberi in un unico blocco libero iniziale (mentre la vecchia stringa rimane al suo posto), si inserisce la nuova nel blocco e la vecchia si cancella; se anche cosi' non va bene, si cancella la vecchia stringa, si ricompatta e si colloca la nuova stringa nel blocco libero iniziale. Naturalmente, prima di effettuare tutta questa elaborazione si controlla se c'e' memoria libera sufficiente.

Il metodo usato impedisce il formarsi di frammentazione interna, cioe' l'utilizzo di blocchi di memoria di dimensione superiore a quella delle stringhe in essi contenute; nelle mie funzioni ad ogni stringa si assegna un blocco della dimensione strettamente necessaria; la frammentazione interna si forma - invece - quando si usano blocchi di dimensione fissa predeterminata.

Ho pero' dovuto risolvere il problema della frammentazione esterna: dopo vari inserimenti e cancellazioni, si formano vari blocchi liberi, separati da blocchi occupati; si puo' arrivare alla situazione in cui, pur essendoci una memoria complessiva libera sufficiente, non si trova nemmeno un singolo blocco libero utile per contenere una nuova stringa. E' necessario, a questo fine, deframmentare la memoria, cioe' concentrare tutti i byte liberi in un unico blocco, che - nelle mie funzioni - viene messo all'inizio della memoria allocata. Per questo ho creato le funzioni fondi_liberi(), trasla() e compatta_liberi().

fondi_liberi() unisce in un unico blocco libero due blocchi liberi consecutivi; trasla() opera quando, in due blocchi consecutivi, il primo e' occupato ed il secondo libero; la funzione sposta la stringa del blocco occupato, in modo da avere il primo blocco libero e il secondo occupato; la funzione compatta_liberi(), partendo dalla fine della lista effettua la scansione usando le due funzioni precedenti: il risultato finale e' un unico blocco libero posto all'inizio della memoria.

La funzione compatta_liberi() viene chiamata quando si cerca spazio libero per una nuova stringa, ma non ci sono blocchi della dimensione richiesta, pur essendoci, sparpagliata, la memoria necessaria.

Si potrebbe decidere di usarla anche in altri casi, quando - ad esempio - il numero di blocchi liberi supera un certo valore (tenendo conto anche della dimensione totale della memoria allocata).

Ho usato fondi_liberi() anche in sede di cancellazione di una stringa: se il blocco successivo e' libero, viene fuso col blocco appena liberato.

Le elaborazioni suddette implicano uno spostamento dei dati in memoria; la stessa stringa allocata inizialmente in posizione x, puo' trovarsi successivamente nella posizione y; ma il programma chiamante deve poter identificare una stringa con un unico valore, che rimanga costante anche dopo vari spostamenti.

Per questo ho deciso di assegnare ad ogni blocco (sia libero che occupato) un valore identificativo, memorizzato nella variabile id_blocco delle struct nodo. E, almeno per quanto riguarda i blocchi occupati, il valore di id_blocco resta sempre lo stesso, anche quando una stringa viene spostata.

Il collegamento fra id_blocco (di valore costante) e la posizione attuale di un blocco occupato (variabile) viene realizzato con le struct dati_blocco poste nella memoria puntata da p_dati_blocchi; dato un blocco occupato con id_blocco=x, in p_dati_blocchi[x].i viene memorizzato l'indice iniziale della stringa corrispondente. E in p_dati_blocchi[x].dim viene inserita la dimensione del blocco. Tutte le funzioni aggiornano, quando e' il caso, i valori di p_dati_blocchi[]; e fanno in modo che l'ID di un certo blocco occupato "segua" il blocco in tutti i suoi spostamenti.

Per quanto riguarda gli spazi liberi, invece, puo' capitare che i relativi ID cambino durante le varie elaborazioni, ma ritengo la cosa trascurabile. Infatti il programma chiamante e' interessato solo a identificare posizione e dimensione dei blocchi occupati. Tanto che posizione e dimensione degli spazi liberi non sono memorizzati in p_dati_blocchi; i campi corrispondenti a un blocco libero sono azzerati. Detti campi valgono 0 anche per gli ID non ancora assegnati.

Nelle mie strutture dati vi e' una certa ridondanza: posizione iniziale e dimensione dello stesso blocco sono memorizzati sia nella struct nodo corrispondente, sia in p_dati_blocchi; e aggiornare di continuo i dati di p_dati_blocchi ha un certo peso; ma se non ci fosse p_dati_blocchi[], per conoscere posizione e dimensione di un blocco - dato l'ID - bisognerebbe ogni volta fare la scansione della lista; invece con p_dati_blocchi[] l'accesso ai dati e' immediato.

Per la gestione degli ID ho seguito questa politica: due o piu' blocchi non possono avere lo stesso ID; gli ID non ancora assegnati vengono memorizzati nella pila contenuta in p_pila_id[]; il numero massimo di ID assegnabili e' pari al numero di caratteri di tutta la memoria assegnata a p_heap (caso limite in cui tutti i blocchi abbiano la dimensione 1).


Per compilare un programma (con gcc): gcc -o nome_eseguibile nome_sorgente.c heap_str_lib.c


File heap_str.h

File heap_str.c

Programma per inserire stringhe in memoria heap e visualizzare il contenuto delle strutture dati

Ordinamento di stringhe


Home


www.corradodamiano.it a cura di Corrado Damiano

posta@corradodamiano.it