Управление памятью редактирования текста

Моей первой реакцией было бы использовать большую внешнюю оперативную память для хранения редактируемых данных. Но вместо того, чтобы делать прямую копию изображения, я бы предварительно выделил блоки оперативной памяти в связанном списке. Каждый блок будет иметь прямой указатель, обратный указатель, используемый размер и буфер данных фиксированного размера.

Сделайте каждый блок размером в два байта. Это означает, что несколько младших битов адреса для каждого блока, как известно, равны 0, поэтому их не нужно сохранять. В этом случае прямой и обратный указатели могут иметь длину 16 бит, а используемая длина — 1 байт, что в сумме дает 5 байтов накладных расходов на блок. Например, для 32-байтовых блоков это составляет 16 % служебных данных. 1 Мбайт ОЗУ даст 885 кбайт фактического хранилища данных, что намного больше, чем 300 кбайт, которые вы просили.

По сути, эта схема создает линейную память, в которую можно вставлять или удалять данные в произвольных местах с небольшими накладными расходами. При добавлении или удалении вам не нужно смотреть за соседние блоки в цепочке, поэтому это можно легко сделать мгновенно в человеческое время.

Вы сохраняете две цепочки: одну для блоков, содержащих данные, и одну для неиспользуемых блоков. Просто правильное редактирование в нужных местах может привести к таким большим накладным расходам на фрагментацию, что память будет казаться намного меньше, и в конечном итоге она не сможет вместить 300 килобайт. Однако такое специфическое редактирование маловероятно, и вы всегда можете выполнить простые локальные рекомбинации (если два соседних блока содержат меньше данных, чем один блок, затем объединить два и вернуть один в список свободных), что в большинстве случаев будет сохраняться. фрагментация вниз достаточно хорошо. Фрагментация на самом деле не имеет значения, пока вам не понадобится свободный блок, а его нет. Когда это происходит, вы выполняете дефрагментацию, и пользователю приходится ждать несколько секунд, но это бывает очень редко. Хорошей стратегией было бы выполнять автоматическую дефрагментацию в фоновом режиме в течение неизбежных длительных периодов времени (с точки зрения процессора), когда пользователь ничего не делает. Я думаю, что с этой стратегией очень маловероятно, что у вас когда-нибудь закончатся свободные блоки и вам придется дефрагментировать, пока пользователь ждет.

Этой схемой легко управлять даже на небольшом микроконтроллере, пользователь быстро реагирует на операции редактирования, а доступ к SD-карте осуществляется только в начале и в конце сеансов редактирования.

Добавлен:

Я больше думал о фрагментации после написания поста, и я думаю, что можно показать, что, пока вы выполняете простую локальную дефрагментацию при любой операции вставки или удаления, вы никогда не потеряете более 1/2 доступной памяти. Снова используя пример с памятью 1 Мбайт с блоками по 32 байта, вам гарантировано не менее 442 кбайт хранилища.

После удаления вы объединяете блок, в котором был удален байт, с одним из его соседей, если они теперь содержат один блок данных или меньше. При добавлении байта вы передаете данные из текущего блока в соседний блок, чтобы освободить место, вместо захвата нового блока, если только оба соседа (и, конечно, текущий блок) полностью не заполнены.

Все эти операции никогда не охватывают более 3 блоков, поэтому выполняются мгновенно в человеческом времени. Если вы можете жить с неиспользованной половиной доступной памяти, вам не нужно ничего делать дальше. Выполнение дефрагментации в фоновом режиме не принесет большого вреда, если ничего другого не происходит.

Это базовая задача программирования, которую вы можете более комфортно решить на ПК, не беспокоясь сразу о PIC, хотя, очевидно, вам нужно небольшое эффективное решение!

Другой подход - жизнеспособный, если вы можете указать символ или последовательность, которые не могут встречаться в тексте, - это заменить несколько байтов в вашем текстовом буфере (который может быть внешней оперативной памятью) этой последовательностью, за которой следует число. Это действует как программная точка останова в отладчике: когда File/Save увидит эту точку останова, найдите номер в списке изменений. Он будет содержать символы, которые вы удалили, а также любые модификации.

Если список изменений заполнен, вам необходимо повторно синхронизировать документ, чтобы очистить список; это также может быть операция автосохранения. (До этого момента у вас также есть возможность отмены!)

Вы хотите свести к минимуму количество операций записи на SD-карту — поэтому только автосохранения и пользовательские операции с файлами/сохранениями, а не запись каждого изменения на SD-карту.

Для простого текстового редактора метод буфера пробела очень эффективен. Я использовал его, когда писал редактор для своего компьютера Ferguson Big Board (CP/M на базе Z80) в начале 1980-х, и мне было очень легко с ним работать. Конечно, я смог использовать некоторые низкоуровневые инструкции Z80, которые сделали очень эффективным перемещение текста через промежутки.

Этот метод также прекрасно подходит для одновременного редактирования нескольких файлов, при условии, что все они помещаются в доступной оперативной памяти. Вы просто объединяете их вместе, и разрыв существует только в файле, который в данный момент находится в фокусе редактирования. Вам нужно сохранить некоторые указатели (или маркеры) для границ файла и обращаться с ними по мере необходимости при перемещении промежутка.

Использование внешней оперативной памяти, безусловно, лучшая схема. Буфер промежутков может разделить тестовый поток на нижнюю половину на одном конце пула памяти и верхнюю половину на другом конце пула памяти. Затем локальные вставки и удаления можно выполнять по всему промежутку, просто перемещая небольшие объемы данных через поля промежутка в ту или иную сторону.

Использование буфера промежутка может быть хорошей стратегией для динамического использования. Вы можете сосредоточиться на открытии дыры в текущем местоположении фокуса редактирования, чтобы новым данным было куда идти. Первоначально вы можете разместить тег перенаправления в фокусе, удалив существующий текст ровно настолько, чтобы осталось место для вставки тега. Затем в отдельном рабочем буфере, на который указывает тег, вы можете захватить первоначально удаленный текст, а затем добавить любой новый вводимый текст. С умным программированием вы можете выполнить параллельный процесс, который разбивает изображение в памяти, чтобы обновить пробел и затем удаляет тег перенаправления и временный буфер редактирования, связанный с ним.

Эта схема позволяет динамически восстанавливать список тегов перенаправления (и их рабочих буферов), чтобы вы редко получали состояние «список заполнен». Предпосылка, конечно, заключается в том, что во время сеанса редактирования средняя скорость поступления новых данных медленнее, чем программа может перемещать область пробела и восстанавливать теги перенаправления.

Еще одно замечание относительно идеи вставки тегов в поток текста. Теги также могут использоваться для других целей, кроме как для обозначения места, где вы разместили тег перенаправления. Может быть хорошей идеей пометить теги таким образом, чтобы вы могли найти их в текстовом потоке, просматривая текст вперед или назад. Самым простым, конечно, является встраивание тега с одним и тем же индикатором тега на каждом конце.

Многое будет зависеть от типов операций, которые вам необходимо выполнить. Если вы можете временно хранить данные в виде списка строк фиксированной длины, вы можете использовать распределитель фрагментов фиксированного размера для хранения отдельных строк в произвольной последовательности, а затем использовать массив ОЗУ или буфер промежутков (возможно, во внешнем устройстве ОЗУ). ) для преобразования линейных номеров строк в местоположения фрагментов. Можно также использовать строки переменной длины с распределителем фрагментов переменной длины или использовать фрагменты фиксированного размера, но каждый фрагмент должен содержать число, которое указывает либо количество используемых байтов, либо длину следующего фрагмента. Используйте буфер RAM для хранения текущей строки, чтобы доступ к массиву фрагментов требовался только тогда, когда курсор перемещается за его пределы. SD-карты достаточно велики, поэтому даже если каждая строка во временном файле будет увеличена до 256 байт, это, вероятно, не должно t представляют слишком большую трудность. Каждые 256 байтов будут содержать либо байт FF и длину, либо двухбайтовый номер блока; это позволит использовать файлы размером до 8 мегабайт и 32767 строк.