Buffer gap
# Buffer gap

Un buffer gap, in informatica, rappresenta una struttura dati utilizzata per memorizzare lunghi vettori in modo compatto, mantenendo efficienti le operazioni di inserimento e rimozione, a condizione che queste siano eseguite intorno alla stessa posizione.

## Utilizzo

I buffer gap sono specialmente comuni negli editor di testo, dove vi sono molti cambiamenti al testo o vicino alla corrente posizione del cursore. Il testo viene memorizzato in un grande buffer in due segmenti contigui, con un gap tra loro per l'inserimento del nuovo testo. Lo spostamento del cursore produce una copia del testo da un lato del gap all'altro (qualche volta la copia rimane in attesa fino alla prossima operazione di modifica del testo). L'inserimento aggiunge il nuovo testo alla fine del primo segmento. L'eliminazione incrementa la dimensione del gap.

Il vantaggio di usare un buffer gap rispetto alle più sofisticate strutture dati (tipo le liste concatenate) è che il testo è rappresentato semplicemente come due stringhe literali, quali prendono spazio extra molto piccolo e quali possono essere cercate e visualizzate molto velocemente.

Lo svantaggio è che le operazioni in differenti locazioni del testo e quelle relative al riempimento del gap (richiedendo che un nuovo gap sia creato) richiedono un'ulteriore copia di molto testo, la quale è particolarmente inefficiente per grandi file. L'uso dei buffer gap è basato sulla supposizione che questo tipo di copia si verifichi abbastanza raramente e che il suo costo possa essere ammortizzato da operazioni più comuni.

Il buffer gap è ampiamente usato nell'editor GNU Emacs.

## Esempi

Sotto ci sono alcuni esempi di operazioni con i buffer gap. Il gap è rappresentato in maniera "pittoresca" dallo spazio vuoto tra le parentesi quadre. Questa rappresentazione è un po' confusionaria: in una tipica implementazione gli endpoint (punti finali) del gap sono tracciati usando dei puntatori, e il contenuto del gap viene ignorato; questo consente, per esempio, di effettuare un'eliminazione aggiustando un puntatore senza cambiare il testo nel buffer.

Stato iniziale:

L'utente inserisce del nuovo testo:

L'utente sposta il cursore prime di "started"; il sistema sposta "started " dal primo buffer al secondo.

L'utente aggiunge del testo riempiendo il gap; il sistema crea un nuovo gap:

