Gestión de memoria de edición de texto

Mi primera reacción sería usar una memoria RAM externa grande para mantener los datos que se están editando. Pero en lugar de hacer una copia de imagen directa, asignaría previamente bloques de RAM en una lista vinculada. Cada bloque tendría un puntero hacia adelante, un puntero hacia atrás, un tamaño utilizado y un búfer de datos de tamaño fijo.

Haz de cada bloque una potencia de dos bytes de tamaño. Eso significa que se sabe que los pocos bits de dirección bajos para cada bloque son 0, por lo que no es necesario almacenarlos. Los punteros hacia adelante y hacia atrás podrían ser de 16 bits y la longitud utilizada de 1 byte, para un total de 5 bytes de sobrecarga por bloque. Con bloques de 32 bytes, por ejemplo, esto representa un 16% de sobrecarga. 1 Mbyte de RAM daría 885 kBytes de almacenamiento de datos reales, mucho más que los 300 kBytes que solicitó.

En efecto, este esquema crea una memoria lineal que puede tener datos insertados o eliminados en lugares arbitrarios con poca sobrecarga. Al agregar o eliminar, no tiene que mirar más allá de los bloques adyacentes en la cadena, por lo que puede hacerse de manera instantánea en tiempo humano.

Mantiene dos cadenas, una para los bloques que contienen los datos y otra para los bloques no utilizados. El tipo correcto de edición en los lugares correctos podría ocasionar tanta sobrecarga de fragmentación como para hacer que la memoria se vea mucho más pequeña y, en última instancia, no pueda contener 300 kBytes. Sin embargo, es improbable que se produzca dicha edición específica, y siempre puede hacer simples combinaciones locales (si dos bloques adyacentes contienen menos datos que un bloque, luego fusione los dos y vuelva a colocar uno en la lista gratuita), que la mayoría de las veces mantendrá fragmentación bastante bien abajo. La fragmentación en realidad no importa hasta que necesite un bloque libre y no haya uno. Cuando eso sucede, haces una desfragmentación y el usuario tiene que esperar unos segundos, pero esto será muy raro. Una buena estrategia sería hacer una desfragmentación automática en segundo plano durante los inevitables largos períodos de tiempo (desde el punto de vista del procesador) donde el usuario no está haciendo nada. Con esta estrategia, creo que es muy improbable que alguna vez te quedes sin bloques libres y debas desfragmentar mientras el usuario espera.

Este esquema es fácil de administrar incluso en un pequeño microcontrolador, la respuesta del usuario a las operaciones de edición es rápida y solo se accede a la tarjeta SD al inicio y al final de las sesiones de edición.

Añadido:

Estaba considerando la fragmentación más después de escribir la publicación, y creo que se puede mostrar que siempre que realice una desfragmentación local simple en cualquier operación de inserción o eliminación, nunca perderá más de la mitad de la memoria disponible. Utilizando de nuevo el ejemplo de la memoria de 1 Mbyte con bloques de 32 bytes, tiene garantizados al menos 442 kBytes de almacenamiento.

Después de una eliminación, fusiona el bloque que tenía un byte eliminado con uno de sus vecinos si los dos juntos ahora contienen un bloque de datos o menos. En un agregado de bytes, los datos del bloque actual se transfieren a un vecino para hacer espacio en lugar de tomar un nuevo bloque a menos que ambos vecinos (y, por supuesto, el bloque actual) estén completamente llenos.

Todas estas operaciones nunca envuelven más de 3 bloques, por lo que son instantáneas en el tiempo humano. Si puede vivir con la mitad de la memoria disponible sin usar, entonces no necesita hacer nada más. Sin embargo, no hay nada de malo en realizar la desfragmentación de fondo cuando no ocurre nada más.

Este es un problema de programación básico que puede resolver más cómodamente en una PC sin preocuparse inmediatamente por el PIC, aunque obviamente, ¡estará buscando una solución pequeña y eficiente!

Otro enfoque, viable si puede especificar un carácter o secuencia que no puede aparecer en el texto, es reemplazar algunos bytes en su búfer de texto (que podría ser RAM externa) con esa secuencia seguida por un número. Esto actúa como un punto de interrupción de software en un depurador: cuando Archivo / Guardar ve ese punto de interrupción, busque el número en una lista de cambios. Contendrá los caracteres que eliminó más cualquier modificación.

Si la lista de cambios se llena, necesita volver a sincronizar el documento para vaciar la lista; Esto también podría ser una operación de guardado automático. (Hasta ese momento, también tiene una función de deshacer).

Desea minimizar el número de escrituras en la tarjeta SD, así que solo guarda automáticamente las operaciones de Archivo / Guardar del usuario en lugar de escribir cada cambio en la SD.

Para un editor de texto simple, el método de búfer de brecha es muy efectivo. Lo utilicé cuando escribí un editor para mi computadora Ferguson Big Board (CP / M basado en Z80) a principios de la década de 1980, y me resultó muy fácil trabajar con él. Por supuesto, pude usar algunas instrucciones de bajo nivel de Z80 que hicieron muy eficiente mover el texto a través de la brecha.

Este método también se expande muy bien para editar múltiples archivos simultáneamente, asumiendo que todos encajan en la RAM disponible. Solo los concatena juntos, y la brecha existe solo en el archivo que actualmente tiene el "enfoque" de edición. Es necesario mantener algunos punteros (o marcadores) para los límites de los archivos y tratarlos cuando sea necesario al mover el espacio.

El uso de RAM externa es sin duda el mejor esquema. Un búfer de separación puede dividir el flujo de prueba en la mitad inferior en un extremo de su grupo de memoria y la mitad superior en el otro lado del grupo de memoria. Luego se pueden realizar inserciones y eliminaciones locales a lo largo del intervalo de la brecha simplemente moviendo pequeñas cantidades de datos a través del margen de la brecha de una forma u otra.

El uso de un buffer de brecha puede ser una buena estrategia para usar de forma dinámica. Puede concentrarse en abrir un agujero en la ubicación actual del foco de edición para que los nuevos datos tengan un lugar donde ir. Inicialmente, puede colocar una etiqueta de reorientación en la ubicación de enfoque eliminando solo el texto existente para dejar espacio para la inserción de la etiqueta. Luego, en un búfer de trabajo separado al que apunta la etiqueta, puede capturar el texto que se quitó inicialmente y luego agregar cualquier texto nuevo que se esté escribiendo. Con una programación inteligente puede ejecutar un proceso paralelo que divide la imagen en memoria para actualizar el espacio y luego elimina la etiqueta de redireccionamiento y el búfer de edición temporal asociado a ella. Si el movimiento del punto de enfoque de edición cambia antes de que el proceso paralelo haya tenido la oportunidad de hacer lo suyo actualizando el espacio, simplemente puede crear una nueva etiqueta de reorientación y asignar otro búfer de trabajo de una lista disponible.

Este esquema permite que una lista de etiquetas de re-dirección (y sus buffers de trabajo) sean reclamadas dinámicamente para que rara vez obtenga una condición de "lista completa". La premisa es, por supuesto, que durante una sesión de edición, la tasa promedio de llegada de nuevos datos llega más lenta de lo que el programa puede mover la región de la brecha y recuperar las etiquetas de reorientación.

Otra nota sobre la idea de insertar etiquetas en el flujo de texto. Las etiquetas también pueden usarse para otras cosas que no sean solo marcar el lugar donde colocó una etiqueta de reorientación. Puede ser una buena idea marcar etiquetas de tal manera que pueda encontrarlas en el flujo de texto, ya sea escaneando hacia adelante o hacia atrás a través del texto. El más simple, por supuesto, es incrustar la etiqueta con el mismo indicador de etiqueta en cada extremo.

Mucho dependerá de los tipos de operaciones que necesite realizar. Si puede almacenar datos temporalmente como una lista de líneas de longitud fija, puede usar un asignador de fragmentos de tamaño fijo para almacenar las líneas individuales en una secuencia arbitraria, y luego usar una matriz de RAM o un búfer de separación (posiblemente en un dispositivo de RAM externo) ) para convertir números de línea lineales a ubicaciones de trozos. También se pueden usar líneas de longitud variable con un asignador de fragmentos de longitud variable, o usar fragmentos de tamaño fijo, pero cada fragmento contiene un número que especifica el número de bytes utilizados o la longitud del siguiente fragmento. Use un búfer de RAM para mantener la línea actual, de modo que solo sea necesario acceder a la matriz de fragmentos cuando el cursor se mueva fuera de ella. Las tarjetas SD son lo suficientemente grandes como para que incluso si cada línea se rellena a 256 bytes en un archivo temporal, probablemente no suponga demasiada dificultad. Cada 256 bytes contendría un byte FF y una longitud, o un número de bloque de dos bytes; eso permitiría archivos de hasta 8 megabytes y 32767 líneas.