Quelle est la meilleure structure de données appropriée pour mettre en œuvre l'éditeur comme le bloc-notes?
Lequel la structure de données/s est utilisé dans la mise en œuvre d'éditeurs de texte comme le bloc-notes. Cette structure de données doit être extensible, et devrait soutenir les diverses fonctionnalités comme l'édition, la suppression, le défilement, la sélection de la gamme de texte etc?
source d'informationauteur | 2009-03-16
Vous devez vous connecter pour publier un commentaire.
Nous avons écrit un éditeur pour une vieille machine (gardez à l'esprit que ce est tout à l'heure, à propos de 1986, c'est donc à partir de la mémoire, et l'état de l'art a progressé un peu depuis) qui nous ont permis d'obtenir de crier au long, de la performance sage, par fixe à l'aide de blocs de mémoire de l'auto-géré piscines.
Il y avait deux piscines, chacune contenant un nombre fixe de spécifique-la taille des blocs (une piscine en été, pour les structures de lignes, l'autre pour les structures du segment). Il s'agissait essentiellement d'une liste de listes liées.
Mémoire a été pré-alloué, pour chaque région de) à partir d'un '
malloc()
'-comme les appellent, et nous avons utilisé des blocs de 65 535 (de 0 à 65,534 inclusive, le numéro de bloc de 65 535 a été considérée comme nulle bloc, une fin-de-indicateur de liste).Cela a permis à chacun de 65 ans, 535 lignes (384 KO ou 512 KO pour le collier de version) et d'environ 1,6 G de la taille du fichier (la prise de 2G de l'espace alloué), qui était assez grande. C'était le théorique limite de taille de fichier - je ne pense pas que nous ayons jamais approché que, en réalité, puisque nous n'avons jamais affecté l'ensemble du segment des structures.
Ne pas avoir à appeler
malloc()
pour chaque petit bloc de mémoire nous a donné une énorme augmentation de la vitesse, d'autant que nous avons pu optimiser nos propres routines d'allocation de mémoire par blocs de taille fixe (y compris l'in-lining, les appels à la dernière version optimisée).Les structures dans les deux piscines ont été comme suit, chaque ligne étant un seul octet):
où:
x
point à la ligne segment de la piscine.N
était un numéro de bloc pour la ligne suivante (null sens c'était la dernière ligne du fichier).P
le numéro de bloc de la ligne précédente (null sens c'était la première ligne du fichier).b
était le numéro de bloc pour le premier segment de cette ligne (null sens de la ligne est vide)..
était réservé de rembourrage (à la bosse de la structure à 8 octets).n
était le numéro de bloc pour le prochain segment de ligne (null sens c'était le dernier segment de la ligne).p
était le numéro de bloc pour le précédent segment de ligne (null sens cela a été le premier segment de la ligne).L
était le numéro de bloc pour le segment de la ligne de bloc.x
était le 26 caractères dans ce segment de ligne.La raison de la structure de la ligne a été rembourré était d'accélérer la conversion des numéros de bloc dans les emplacements de mémoire (décalage à gauche par 3 bits a été beaucoup plus rapide que de multiplier par 6 en particulier de l'architecture et de la mémoire supplémentaire a été utilisé seulement 128K, minime par rapport à la capacité totale de stockage utilisé) bien que nous n'ayons fournir la version la plus lente pour ceux qui se souciaient plus de la mémoire.
Nous avons également eu un tableau de 100 valeurs de 16 bits qui contient le segment de ligne (et le numéro de ligne de sorte que nous pourrions accéder rapidement à des lignes spécifiques), à peu près à ce pourcentage (de sorte que tableau[7] est la ligne qui a été d'environ 7% dans le fichier) et deux pointeurs à maintenir la liberté de liste dans chaque piscine (ce qui était un très simple chemin de liste où
N
oun
dans la structure indiqué le prochain bloc libre et gratuit de blocs ont été attribués à partir de, et de remettre, la façade de ces listes).Il n'y avait pas besoin de garder un nombre de caractères dans chaque segment de ligne depuis 0-octets ne sont pas valables dans les fichiers. Chaque segment de la ligne a été autorisé à avoir 0-octets à la fin qui ont été totalement ignorés. Les lignes ont été compressés (c'est à dire, les segments ont été combinées) chaque fois qu'ils ont été modifiés. Ce qui a maintenu l'utilisation des blocs du bas (sans peu fréquents et de longue garbage collection) et aussi grandement accéléré de recherche et remplacer des opérations.
L'utilisation de ces structures a permis très rapide de l'édition, de l'insertion, de suppression, de la recherche et de la navigation autour du texte, qui est l'endroit où vous êtes susceptible d'obtenir la plupart de vos problèmes de performances dans un simple éditeur de texte.
L'utilisation de sélections (nous n'avons pas de mettre en œuvre ce que c'était un mode de texte de l'éditeur de celle utilisée vi-les commandes telles que
3d
à supprimer 3 lignes ou6x
supprimer 6 caractères) pourrait être mise en œuvre en ayant un{line#/block, char-pos}
tuple pour marquer les positions dans le texte, et utiliser deux de ces n-uplets d'une sélection de la gamme.Découvrez Cordes. Poignées rapide insérer/supprimer/modifier des chaînes de caractères. Les plages sont généralement pris en charge dans le Corde de mise en œuvre, le défilement peut être fait avec un index inversé à la corde.
Wikipédia dit que de nombreux éditeurs utilisent un L'Écart De La Mémoire Tampon. Il est essentiellement un tableau avec un espace inutilisé dans le milieu. Le curseur se trouve juste à l'avant de l'espace, donc, de suppression et d'insertion à l'emplacement du curseur est O(1). Il devrait être assez facile à mettre en œuvre.
Regardant le code source de Notepad++ (comme Chris Ballance proposé dans ce fil ici) montre qu'ils utilisent également un écart de tampon. Vous pourriez obtenir certains de la mise en œuvre d'idées.
Il y a un excellent article sur Pièce De Chaînes par James Brown, auteur de HexEdit.
En un mot: Pièce de chaînes de vous permettre d'enregistrer les modifications apportées au texte. Après le chargement, vous avez un morceau de la chaîne qui s'étend sur l'ensemble du texte. Maintenant, vous insérer quelque part au milieu.
Au lieu d'allouer un nouveau tampon, de copier le texte autour, etc., vous créez deux nouvelles pièces et de modifier l'existant: L'un contient le texte jusqu'à le point d'insertion (c'est à dire que vous venez de modifier la longueur de la pièce), alors vous avez un morceau avec le nouveau texte, et après qu'un nouveau morceau avec tout le texte après l'insertion. Le texte original reste inchangé.
Pour annuler/refaire, vous simple, rappelez-vous quelles pièces vous avez ajouté/supprimé/modifié.
Les plus complexes de la zone lors de l'utilisation de pièce de chaînes est qu'il n'est plus un mappage 1:1 entre le décalage dans le texte visible et la structure de la mémoire. Soit vous avez à la recherche à la chaîne ou vous devez maintenir un arbre binaire la structure d'une certaine sorte.
Vérifier la mise en œuvre de Notepad++, vous pouvez voir la source sur SourceForge
Le truc habituel pour avoir quelque chose comme une liste ou un tableau de tableaux de caractères. Il y a eu beaucoup de choses sur ce fil des ans: vous pourriez avoir un coup d'oeil à cette recherche de google.