Memoria dinamica e operatori bitwise

Matteo Spanio

spanio@dei.unipd.it

Centro di Sonologia Computazionale

Dipartimento di Ingegneria dell’Informazione

Università degli Studi di Padova

23 aprile 2024

Strutture dati

Le strutture sono molto utili per definire… strutture dati.

Per esempio si possono definire array dinamici, liste concatenate, alberi, pile, code…

Array con strutture

Gli array in C sono molto limitati, infatti dobbiamo gestire la loro lunghezza a mano…

Si può creare una struttura che contenga un array e la sua lunghezza:

#define MAX 1024

typedef struct intarray {
    int array[MAX];
    int length;
} IntArray;

Array con strutture

Adesso si può passare la struttura come argomento di una funzione:

void stampa_array(IntArray a) {
    for (int i = 0; i < a.length; i++) {
        printf("%d ", a.array[i]);
    }
    printf("\n");
}

Si nota subito che non abbiamo più bisogno di passare la lunghezza dell’array come argomento.

Array con strutture

int append(IntArray *a, int value) {
    if (a->length < MAX) {
        a->array[a->length] = value;
        a->length++;
        return 0;
    }
    return 1;
}

Array con strutture

L’implementazione che abbiamo visto ha due grossi problemi:

la dimensione dell’array è fissa
la struttura IntArray funziona solo con array di interi, per fare array di float, char, ecc. bisogna creare ogni volta una nuova struttura

Memoria dinamica

Le strutture dati in C hanno dimensione fissa. Infatti gli array vengono inizializzati con un valore costante.
Esistono però dei comandi che permettono di allocare dinamicamente zone di memoria, permettendo di fare strutture che crescono o si rimpiccioliscono durante l’esecuzione del programma.

Memoria dinamica

Le operazioni per gestire la memoria dinamica si trovano nella libreria stdlib.h e sono:

malloc (memory allocation): alloca una zona di memoria di una certa dimensione
calloc (clear allocation): alloca una zona di memoria di una certa dimensione e la inizializza a 0
realloc (reallocate): cambia la dimensione di una zona di memoria già allocata

Puntatore a void

malloc, calloc e realloc restituiscono un puntatore a void, che è un puntatore generico.

Questo puntatore non fa riferimento a un certo tipo di dato, ma solo a un indirizzo di memoria.

`malloc`

void* malloc(size_t size);

Supponendo di voler creare un array di interi di dimensione variabile, c’è bisogno di creare un puntatore ad interi e poi assegnargli l’indirizzo della nuova zona di memoria:

int *a;
a = malloc(10 * sizeof(int));

La funzione malloc accetta come argomento il numero di byte da allocare. L’esempio crea 10 cellette di memoria, ciascuna grande quanto un intero (4 byte).

`calloc`

void* calloc(size_t num, size_t size);

Per inizializzare array torna comoda anche la funzione calloc, che ha due parametri: numero di membri e dimensione (in byte) dei membri
Inoltre ha come effetto aggiuntivo di porre a zero tutti i byte interessati (quindi tutti i membri dell’array che creo)

double *a;
a = calloc(10, sizeof(double));

L’effetto di questo codice è lo stesso del precedente (con la malloc), ma con tutti i membri dell’array inizializzati a 0.

`realloc`

void* realloc(void* ptr, size_t size);

Questa funzione cambia la dimensione di uno spazio allocato dinamicamente.
L’argomento ptr deve essere un puntatore ottenuto da una funzione ..alloc, altrimenti porta a comportamento non definito.
I dati già presenti nella zona di memoria vengono mantenuti.

NULL

Quando si usa la memoria dinamica, è importante controllare che l’allocazione sia andata a buon fine.
Se malloc, calloc o realloc non riescono a trovare spazio in memoria, restituiscono NULL.
NULL è una costante che rappresenta un puntatore all’indirizzo 0x0. NULL è definito in stdlib.h.

`malloc`, `calloc`, `realloc`

Queste funzioni scrivono in una zona di memoria nota come heap;
Le variabili locali e i parametri delle funzioni sono invece memorizzati nello stack;
Usando ricorsione e molta memoria dinamica si può esaurire la memoria disponibile
Occorre quindi fare uso oculato della memoria e pulire quella usata che non serve più

`free`

void free(void* ptr);

La funzione free permette di liberare un blocco di memoria (e quindi renderlo disponibile per un’altra allocazione)
ptr dopo l’esecuzione di free continua a puntare alla stessa zona di memoria, ma il contenuto di quella zona non è più garantito, si chiama dangling pointer
Occorre, subito dopo la free, assegnare a ptr il valore NULL (oppure una nuova memoria)
accedere un blocco deallocato è un gravissimo errore

Array dinamico

Un array dinamico è un array la cui dimensione può cambiare durante l’esecuzione del programma.

Per implementare un array dinamico si può usare una struttura che contiene un puntatore all’array e la sua lunghezza:

typedef struct {
    int *array;
    int capacity;
    int length;
} ArrayList;

`ArrayList`

Il nuovo tipo ArrayList ha tre membri:

array è un puntatore ad interi, che punta all’array dinamico
capacity è la dimensione massima dell’array
length è il numero di elementi attualmente presenti nell’array

Quando length raggiunge capacity, bisogna riallocare la memoria per l’array, aumentando la sua dimensione.

Scarica l’implementazione dell’arraylist

Linked list

Una lista concatenata è una struttura dati composta da nodi, ciascuno dei quali contiene un valore e un puntatore al nodo successivo.
La differenza con un array è che i nodi non sono memorizzati in posizioni contigue di memoria.
La lista concatenata è una struttura ricorsiva: un nodo contiene un valore e un puntatore al nodo successivo.

Linked list

L’implementazione classica della lista concatenata in C è:

typedef struct node {
    int value;
    struct node *next;
} Node;

Scarica l’implementazione della linked list

Esercizio: lista concatenata

Dato il file con il main e i prototipi delle funzioni, implementare:

recursive_list_print
recursive_list_delete

Operazioni bitwise

Operatori bitwise

Gli operatori bitwise permettono di effettuare calcoli al livello dei bit delle variabili.

Gli operatori bitwise in C sono:

& AND
| OR
^ XOR
~ NOT
<< Shift a sinistra
>> Shift a destra

Calcoli

Questi operatori applicano le regole dell’algebra booleana, pertanto sarà importante conoscere le tabelle di verità delle operazioni AND, OR e XOR.

A	B	A & B	A	B	A ^ B
0	0	0	0	0	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	1	0	1

La rappresentazione dei numeri

Per effettuare le operazioni bitwise conviene sempre cercare di rappresentare i numeri in binario.

C permette di dichiarare numeri in binario utilizzando il prefisso 0b:

unsigned char switches = 0b00001000;
// è equivalente a
unsigned char switches = 8;

OR

L’operatore OR viene spesso usato per unire due insiemi di bit. Ad esempio, se si ha una variabile switches che rappresenta lo stato di accensione di 8 interruttori, si può accendere un interruttore utilizzando l’operatore OR:

// switches = 0b00001000
switches = switches | 0b00000100;
// oppure
switches = switches | 4;

Ora il valore di switches sarà 0b00001100. Il che rappresenta il fatto che gli interruttori 3 e 4 sono accesi.

AND

Per spegnere tutti gli interruttori si può utilizzare l’operatore AND:

switches = switches & 0b00000000;
// oppure
switches = switches & 0;
// switches: 0b00000000

Esercizio

Scrivere un programma che stampi a monitor il valore del bit meno significativo di un numero intero.

#include <stdio.h>
void print_lsb(int n);

int main(void)
{
    int a = 127, b = 128;

    print_lsb(a);
    print_lsb(b);
}

void print_lsb(int n)
{
    printf("The least significant bit of %d is: ", n);
    printf("%d\n", n & 1);
}

Esercizio

Scrivere una funzione che dato un numero intero \(n\), restituisca true se \(n\) è pari, false altrimenti. Usare l’operatore AND per verificare se un numero è pari.

#include <stdbool.h>
bool is_even(int n);

int main(void) {
    int a = 55, b = 48;

    printf("%d is even: %d\n", a, is_even(a));
    printf("%d is even: %d\n", b, is_even(b));
}

XOR

L’operatore XOR è molto utile per invertire lo stato di un bit.

Nota

Eseguire l’operazione di XOR due volte su un bit restituisce il valore originale.

char c = 'A';
c = c ^ 'h';
c = c ^ 'h';
// c: 'A'

Esempio

65: 0b01000001

73: 0b01001001

08: 0b00001000

65 ^ 73 = 8

8 ^ 73 = 65

‘A’ ^ ‘I’ = ’

Esempio

#include <stdio.h>
#define KEY 'h'

int main(void)
{
    char c = 'A';
    c = c ^ KEY;
    printf("%c\n", c);

    c = c ^ KEY;
    printf("%c\n", c);
}

Esercizi

Scrivere un programma di semplice crittografia in grado di cifrare e decifrare una stringa utilizzando l’operatore XOR.

Scarica il main dell’esercizio

Shift

Gli operatori di shift permettono di spostare i bit di una variabile a sinistra o a destra.

unsigned char c = 0b00000001;
c = c << 1;
// c: 0b00000010
c = c << 3;
// c: 0b00010000
c = c >> 2;
// c: 0b00000100

Esempio Shift

Scrivere un programma che moltiplichi un numero intero per 2 utilizzando l’operatore di shift.

#include <stdio.h>

int main(void)
{
    int n = 5;
    n = n << 1;
    printf("%d\n", n);
}

Esercizi

Scrivere un programma che stampi a monitor la codifica in binario di un unsigned char.

Ad esempio, se il valore di c è 5, il programma dovrà stampare 00000101.

Esercizi

Immaginando che una serie di 8 bit rappresenti lo stato di accensione di 8 led, scrivere un programma che:

Accenda il led più a destra;
Accenda il led più a sinistra;
Inverta lo stato di tutti i led;
Spenga tutti i led.

Scarica il main dell’esercizio

Memoria dinamica e operatori bitwise

Strutture dati

Strutture dati

Array con strutture

Array con strutture

Array con strutture

Array con strutture

Memoria dinamica

Memoria dinamica

Memoria dinamica

Puntatore a void

malloc

calloc

realloc

NULL

malloc, calloc, realloc

free

Array dinamico

ArrayList

Linked list

Linked list

Esercizio: lista concatenata

Operazioni bitwise

Operatori bitwise

Calcoli

La rappresentazione dei numeri

OR

AND

Esercizio

Esercizio

XOR

Esempio

Esempio

Esercizi

Shift

Esempio Shift

Esercizi

Esercizi

`malloc`

`calloc`

`realloc`

`malloc`, `calloc`, `realloc`

`free`

`ArrayList`