Gestión de la memoria de edición de texto

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

Haga que cada bloque tenga 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 entonces 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 una sobrecarga del 16 %. 1 Mbyte de RAM produciría 885 kBytes de almacenamiento de datos real, 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 se puede hacer fácilmente de forma instantánea en tiempo humano.

Mantienes 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 causar una sobrecarga de fragmentación que haría que la memoria pareciera mucho más pequeña y, finalmente, incapaz de contener 300 kBytes. Sin embargo, es poco probable que ocurra una edición tan específica, y siempre puede hacer recombinaciones locales simples (si dos bloques adyacentes contienen menos datos que un bloque, luego fusione los dos y vuelva a colocar uno en la lista libre) que la mayoría de las veces mantendrá la fragmentación lo suficientemente bien. La fragmentación en realidad no importa hasta que necesite un bloque libre y no lo haya. Cuando eso sucede, realiza una desfragmentación y el usuario tiene que esperar unos segundos, pero esto será muy raro. Una buena estrategia sería realizar una desfragmentación automática en segundo plano durante los inevitables largos períodos de tiempo (desde el punto de vista del procesador) en los que el usuario no hace nada. Con esta estrategia, creo que es muy poco probable que te quedes sin bloques libres y tengas que desfragmentar mientras el usuario espera.

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

Agregado:

Estaba considerando más la fragmentación después de escribir la publicación, y creo que se puede demostrar 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. Usando el ejemplo de memoria de 1 Mbyte con bloques de 32 bytes nuevamente, tiene garantizado al menos 442 kBytes de almacenamiento.

Después de una eliminación, fusiona el bloque del que se eliminó un byte con uno de sus vecinos si los dos juntos ahora contienen un bloque de datos o menos. En un byte agregado, transfiere datos del bloque actual 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 involucran más de 3 bloques, por lo que son instantáneas en tiempo humano. Si puede vivir con hasta la mitad de la memoria disponible sin usar, entonces no necesita hacer nada más. Sin embargo, hay poco daño en hacer una desfragmentación de fondo cuando no está pasando nada más.

Este es un problema básico de programación que puedes resolver más cómodamente en una PC sin preocuparte inmediatamente por el PIC, ¡aunque obviamente estarás buscando una pequeña solución 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 una memoria RAM externa) con esa secuencia seguida de un número. Esto actúa como un punto de interrupción de software en un depurador: cuando File/Save vea 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, debe volver a sincronizar el documento para vaciar la lista; esto también podría ser una operación de guardado automático. (¡Hasta ese punto, también tiene una función de deshacer!)

Desea minimizar la cantidad de escrituras en la tarjeta SD, por lo que solo guarda automáticamente y las operaciones de archivo/guardado del usuario en lugar de escribir cada cambio en SD.

Para un editor de texto simple, el método de búfer de espacios es muy efectivo. Lo usé cuando escribí un editor para mi computadora Ferguson Big Board (CP/M basada 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 Z80 de bajo nivel que lo hicieron muy eficiente para mover el texto a través del espacio.

Este método también se expande muy bien para editar varios archivos simultáneamente, suponiendo que todos encajen en la memoria RAM disponible. Simplemente los concatena, y la brecha existe solo en el archivo que actualmente tiene el "foco" de edición. Necesita mantener algunos punteros (o marcadores) para los límites del archivo y manejarlos según sea necesario al mover el espacio.

El uso de RAM externa es sin duda el mejor esquema. Un búfer de brecha 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. Las inserciones y eliminaciones locales se pueden realizar a lo largo 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 gap buffer puede ser una buena estrategia para usar de forma dinámica. Puede enfocarse en abrir un agujero en la ubicación de enfoque de edición actual para que los nuevos datos tengan un lugar para ir. Inicialmente, puede colocar una etiqueta de redirección en la ubicación de enfoque eliminando solo el texto existente suficiente para dejar espacio para la inserción de la etiqueta. Luego, en un búfer de trabajo separado señalado por la etiqueta, puede capturar el texto eliminado inicialmente y luego agregar cualquier texto nuevo que se esté ingresando. 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 redirección y el búfer de edición temporal asociado con ella.

Este esquema permite reclamar dinámicamente una lista de etiquetas de redirección (y sus búferes de trabajo) para que rara vez obtenga una condición de "lista llena". La premisa es, por supuesto, que durante una sesión de edición, la tasa promedio de llegada de nuevos datos es más lenta de lo que el programa puede mover la región de brecha y recuperar las etiquetas de redirección.

Otra nota sobre la idea de insertar etiquetas en el flujo de texto. Las etiquetas también se pueden usar para otras cosas además de marcar dónde ha colocado una etiqueta de redirección. Puede ser una buena idea marcar las 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. Por supuesto, lo más simple 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 espacio (posiblemente en un dispositivo de RAM externo ) para convertir números de línea lineales en ubicaciones de fragmentos. También se podrían usar líneas de longitud variable con un asignador de fragmentos de longitud variable, o usar fragmentos de tamaño fijo pero hacer que cada fragmento contenga un número que especifique el número de bytes utilizados o la longitud del siguiente fragmento. Use un búfer de RAM para contener la línea actual, de modo que solo se necesite 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, eso probablemente no debería No plantea 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 unos 8 megabytes y 32767 líneas.