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
modificaI 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
modificaSotto 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:
This is the way [ ]out.
L'utente inserisce del nuovo testo:
This is the way the world started [ ]out.
L'utente sposta il cursore prime di "started"; il sistema sposta "started " dal primo buffer al secondo.
This is the way the world [ ]started out.
L'utente aggiunge del testo riempiendo il gap; il sistema crea un nuovo gap:
This is the way the world as we know it [ ]started out.
Voci correlate
modificaCollegamenti esterni
modifica- GNU emacs malloc memory working set gap editor (TXT), su djmnet.org. URL consultato il 7 settembre 2006 (archiviato dall'url originale il 28 settembre 2007).
- Rapida introduzione ed esempi di codice in C (inglese), su lazyhacker.com.
