Ultima modifica:
String Interning: Introduzione
Ciao a tutti, oggi volevo fare una piccola guida sullo string interning ovvero un metodo che ci permette di memorizzare una sola copia di ogni stringa distinta.Per capire meglio il conetto, procediamo con un esempio concreto.
Consideriamo il seguente prototipo di funzione:
C:
char *strintern(char *s);Vogliamo che quando chiamiamo la funzione
strintern ci venga ritornato un puntatore ad un'altra stringa uguale memorizzata in un nostro "database".Ad esempio, se scriviamo:
C:
char *str1 = strintern("ciao");Viene chiamata la funzione
strintern con argomento "ciao", ovvero viene memorizzata una copia di quel "ciao" all'interno di un nostro "database" (che vedremo, sarà una linked list). Viene restituito il puntatore al "ciao" che abbiamo memorizzato. Di consiguenza str1 punterà ad esso.Se, successivamente, scriviamo:
C:
char *str2 = strintern("ciao");Viene chiamata di nuovo la funzione
strintern che cercherà all'interno del "database" per verificare se ci sia già la stringa "ciao". La trova, perché l'abbiamo aggiunta prima. E restituisce il puntatore al "ciao" che già esiste.Di conseguenza, avremo che
str1 sarà uguale a str2.Ovvero, avremo il vantaggio di comparare due stringhe "interned" semplicemente tramite una comparazione tra puntatori ovvero:
C:
str1 == str2In questo modo non occorre confrontare carattere per carattere per verificare se due stringhe sono uguali.
Inoltre, come vedremo, avremo il vantaggio di non calcolare ogni volta la lunghezza di una stringa, ovvero non ci sarà bisogno di contare i caratteri della stringa.
Interfaccia
L'interfaccia del modulo che vogliamo sviluppare consiste in due sole funzioni, di conseguenza questo sarà il file
strintern.h:
C:
extern char *strintern(char *s);
extern unsigned int strinternlen(char *s);La prima è quella che, data in input una strina, cerca nel database se esiste una copia identica:
- se esiste, restituisce il puntatore alla copia memorizzata nel database
- se non esiste, crea prima una copia uguale nel database e poi ne restituisce il puntatore ad essa
La seconda, invece, ci restituisce la lunghezza (ovvero il numero di caratteri fino al terminatore, quest'ultimo escluso) di una stringa che è già stata internata.
Perché fare questa funzione se esiste già lo
strlen della libreria standard C?Perché come vedremo, sarà una funzione più rapida che non avrà bisogno di contare carattere per carattere.
Questa è l'interfaccia, molto semplice. L'implementazione che vedremo, invece, sarà leggermente più complicata.
Implementazione Test Driven
Vogliamo implementare le due funzioni di sopra. Bene. Vogliamo seguire, però, un approccio test-driven, ovvero vogliamo scrivere prima il codice del test dell'implementazione e successivamente l'implementazione stessa.
In poche parole, vogliamo che quando chiamiamo la seguente funzione, non vi sia alcun errore:
C:
#include <assert.h>
#include "strintern.h"
void test_strintern(void)
{
assert(strintern(0) == 0);
assert(strintern("") == 0);
assert(strinternlen(strintern(0)) == 0);
assert(strintern("ciao") != 0);
assert(strintern("ciao") == strintern("ciao"));
assert(strinternlen(strintern("ciao")) == 4);
assert(strintern("ciao a tutti") == strintern("ciao a tutti"));
assert(strintern("ciao a tutti") != strintern("ciao"));
assert(strinternlen(strintern("ciao a tutti")) == 12);
}Ovviamente, si può ottimizzare questo codice, ma per il momento lo lasciamo così, è solo un codice di test scritto di getto.
Abbiamo scritto, quindi, la funzione
test_strintern che, quando chiamata, ci dice se e quale assert ha fallito. Se nessun assert fallisce vuol dire che la nostra implementazione è corretta.Bene, procediamo con l'implementazione.
Prima di tutto abbiamo bisogno di un nostro "database" in cui creare e cercare le stringhe interned. Per il momento va bene una lista concatenata (linked list). Magari in un'altra guida spiegherò come ottimizzare, perché le linked list sono molto lenta per la ricerca.
Abbiamo bisogno quindi della seguente struct:
C:
typedef struct strinterned strinterned;
struct strinterned
{
strinterned *next;
unsigned int len;
char str[1];
};Abbiamo i seguenti campi:
nextche punta alla prossima stringa interned (roba standard delle liste concatenate)lenche contiene la lunghezza della stringa, accederemo a questo campo nella funzionestrinternlenanziché contare i caratteri e per questo avremo prestazioni miglioristr[1]è un array che di default contiene un solo carattere ma che, in pratica, conterràlen + 1caratteri (il +1 è per il carattere terminatore'\0').
Ci serve quindi il nostro database, ovvero la linked list. E anche due funzioni che ci permettono di creare una
strinterned e di aggiungerla alla linked list.
C:
/* Questo è il nostro database. Per il momento è una linked list, ma occorre "trasformarla"
* in qualcosa di più performante perché la ricerca all'interno delle linked list può
* risultare molto lenta. */
static strinterned *_strinterns;
#include <stdlib.h> /* For malloc() */
#include <string.h> /* For strlen() and strcpy() */
static strinterned *make_strintern(char *s)
{
strinterned *new_strintern;
unsigned int s_len = strlen(s);
new_strintern = (strinterned *)malloc(sizeof(strinterned) + s_len);
new_strintern->next = 0;
new_strintern->len = s_len;
strcpy(new_strintern->str, s);
new_strintern->str[s_len] = '\0';
return new_strintern;
}
static void add_strintern(strinterned *new_strintern)
{
/* Se la linked list è ancora vuota, il primo elemento sarà new_strintern */
if(!_strinterns)
{
_strinterns = new_strintern;
}
/* Se la linked list non è vuota, aggiungi il nuovo elemento in coda */
else
{
strinterned *s = _strinterns;
while(s->next) s = s->next;
s->next = new_strintern;
}
}La funzione
make_strintern crea dinamicamente una strinterned, mentre la funzione add_strintern aggiunge un elemento in coda alla linked list _strinterns.Procediamo ora con l'implementazione dei due prototipi dichiarati nell'interfaccia.
Iniziamo prima con
strinternlen che è la più semplice:
C:
extern unsigned int strinternlen(char *s)
{
if(!s) return 0;
strinterned *tmp = (strinterned *)(s - offsetof(strinterned, str));
return tmp->len;
}Ovvero, sappiamo che il campo
str[1] si trova alla fine della struct strinterned, quindi andiamo indietro di offsetof(strinterned, str) ed arriviamo al primo campo, quindi abbiamo il nostro puntatore strinterned *tmp che punta all'elemento della linked list. Da lì è semplice recupare la lunghezza della stringa, basta accedere al campo tmp->len.Quindi, anziché contare i caratteri, abbiamo restituito il campo che conteneva già il valore della lunghezza della stringa.
Ora passiamo al cuore di questa mini-libreria di string interning, ovvero alla funzione
strintern:
C:
#include <string.h> /* For strcmp() */
extern char *strintern(char *s)
{
if(!s) return 0;
if(!*s) return 0;
/* Cerchiamo nel database per verificare se già esiste una copia di s */
int found = 0;
strinterned *ptr = _strinterns;
while(!found && ptr)
{
found = (strcmp(ptr->str, s) == 0);
if(!found)
{
ptr = ptr->next;
}
}
/* Se non è stata trovata una copia, la si crea e la si aggiunge al database */
if(!found)
{
ptr = make_strintern(s);
add_strintern(ptr);
}
/* Ritorna la stringa copiata o creata */
return (char *)ptr->str;
}Sviluppi futuri
Intanto mi scuso di eventuali bug o errori di battitura, anche se ho testato e sembra essere tutto ok.Questa libreria può essere ottimizzata utilizzando l'hashing ovvero una metodologia che ci permette di cercare all'interno del nostro "database" di stringhe più rapidamente e quindi rendere la funzione
strintern più rapida.Fatemi sapere se questa guida è stata abbastanza chiara, interessante, ecc... e se volete che prosegua scrivendo una guida sull'hashing in modo da ottimizzare questa libreria.
