Как организовать память для текстового редактора?

[esl]

еще раз: только когда знаешь, что искать. ну, и про остальное Barmaley_m уже сказал.[/QUOTE]

:-)
Ещё раз:
Мне огромные логи удобнее чистить скриптами
После их прохода и сильной чистке лога гораздо легче искать глазами в редакторе

По работе постоянно надо искать в логах инфу
Так правильные скрипты легко из 10ка гиг делают 10к

[bigral]

Для редактора я бы кучу организовал.
Максимальную длину строки ограничил бы 1024 байта, например.
Тогда всё довольно просто - пока в пределах одной строки редактируешь - всё в буфере. Как строку бъёшь - так в куче место выделяется-освбождается. Для 48К накладно, а 128 уже прекрасно.

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

Т.е. текст при загрузке попадает в массив элементов (в массиве все элементы одного размера), каждая строка имеет свой собственный буфер редактирования (это типа как отдельный текстовый редактор для каждой строки, даже парралельно 2 и больше процессора могут редактировать разные строки). Памяти жрет такое решение уйму и ограничивает длинну строки. Ну и наверное строки хранить тут имеет смысл в том же виде как и предложенно ранее - строка идет сначала елемента массива и до курсора потом пустое место и остаток строки в конце элемента массива.

[vinxru]

памяти море? скорости много?

Вчера залез почитать. DDR4 с частотой 4.3 ГГц имеет скорость обмена 34 Гб/c. Офигеть.

[SfS]

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

Дорогой Критик, я Кучу реализовывал для AVR 4MГЦ c внешним ОЗУ. Очень даже хорошо получилось. На элемент кучи - динамический заголовок (от 1 до 3 байт). Этого достаточно для хранении всей информации об элементе, даже если побить память на странички по 16К.

Это сильно большие расходы - 3 байта на длинную стоку? ИМХО - нет, скорость выделения памяти и освобождения всё это оправдывает.

Принцип такой:
Каждый элемент хранит заголовок, в котором указаны длина элемента, занят он или свободен.
После инициализации - каждая страница кучи состоит из одного элемента, размером "Размер страницы-Размер элемента".
Старшие два бита (6 и 7) указывают размер заголовка - 1,2 или 3 байта.
Бит 5 - показывает занят элемент или свободен.
Бит 4 - резерв
Биты [3..0] - размер элемента для 1байтового заголовка.

Что получаем? Очень просто -
для эл-тов кучи от 0 до 15 байт - заголовок 1байт,
для 16-255 байт - 4095 байт.
и для эл-тов 4096-16381 байт (размер страницы 16К - 3б) - 3 байта

Где тут нужно "море памяти"? Где тут "мегатактовые частоты"? На АВР 4 МГЦ в реалтайме работает и не глючит.

При таком хранении как раз память выделяется крайне быстро. Алгоритм прост и прозрачен. Работает автоосвобождение памяти (объединение нескольких свободных элементов подряд в 1 большой свободный элемент).

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

Т.е. текст при загрузке попадает в массив элементов (в массиве все элементы одного размера), каждая строка имеет свой собственный буфер редактирования (это типа как отдельный текстовый редактор для каждой строки, даже парралельно 2 и больше процессора могут редактировать разные строки).

Какой "свой собственный буфер"? Один буфер на все строки. Переместился на строку - она в буфер, ушёл на другую - другая в буфер. Скопировать килобайт байт - спек может быстро и незаметно для юзера. Хотя.. Где ты видел килобайтовые строки в реальных текстах?! Обычно не более 80 байт при спековском разрешении.

Памяти жрет такое решение уйму и ограничивает длинну строки.

В чём накладыне расходы? на пустую строку - 1 байт. На среднюю строку ( 30-150 байт) - 2 байта.

Ну и буфер 1024 байта - это более чем достаточно. Мало - выделяй динамически. Или сделай 16384 байта. Только я живу в реальном мире, где тексты пишутся, чтобы читать, а не чтобы мучаться.

Для текстового редактора реально ещё нужен массив адресов строк - 3 байта на строку (с учётом банки). Тогда - если 1 банка под массив - то максимальный размер текста - 5450 строк примерно. Часто ты такие тексты пишешь в одном файле?

Мне кажется - исходить надо из удобства и скорости. Пользователю пофиг как там у вас чего организовано. Но если при вставлении символа текста он по 3 секунды ждать будет - то заплюёт.

[vinxru]

Что бы найти блок, необходимо проверить все блоки кучи. Было бы организовано дерево, потребовалось бы LOG(N) операций.

То есть у каждого блока два укзателя. На правую ветвь (блоки большего размера) и на левую ветвь (блоки меньшего размера).

[alone]

на 8080 ldir одного байта - 48 тактов

Что-то многовато.
Можно же развернуть последовательность типа
ld a,(hl)
inc hl
ld (de),a
inc de

[Advertiser]

[jerri]

Что-то многовато.
Можно же развернуть последовательность типа
ld a,(hl)
inc hl
ld (de),a
inc de

bc проверять будем?

[SfS]

Что бы найти блок, необходимо проверить все блоки кучи. Было бы организовано дерево, потребовалось бы LOG(N) операций.

То есть у каждого блока два укзателя. На правую ветвь (блоки большего размера) и на левую ветвь (блоки меньшего размера).

Найти свободный блок? Не всё - а до первого свободного с длиной не менее заданной.

Я проще делал. Искал сначала кучи. Чем больше элементов в куче - тем медленнее поиск. Но реально - всё равно быстро. Там же просто - проверил бит - если занят - к следующему. если свободен - проверяем длину. если длины хватает - то выделяем, если нет - опять к следующему.

В пределе - файл из 16384 элементов 0й длины Это фантастика)

[vinxru]

POP DE
MOV M, E
INX H
MOV M, D
INX H

17 тактов на байт.

BC проверять будем один раз на 8 операций (или больше). Причем даже просто C. Эта функция будет копировать блоки по 16 байт, а вызывающая функция будет сначала копировать блоки по 16 байт, а потом остаток медленным способом.

---------- Post added at 11:38 ---------- Previous post was at 11:34 ----------

Найти свободный блок? Не всё - а до первого свободного с длиной не менее заданной.

Это не рационально. Это очень сильно фрагментирует ОЗУ, из за чего половина будет пропадать.

[alone]

Защитники буферизации строк забыли про одну важную проблему: если строку буферизировать для редактирования, то длина строки будет ограничена. Обычно в таких редакторах это 256 байт. В ACEdit было сделано именно так с самых первых версий. Потом добавлена (глючная) подгрузка остатка строки в буфер при ломании строки Enter'ом. В реальном тексте строки могут быть любой длины. Бывает так, что строка=абзац. А бывает так, что надо отредактировать строку в бинарнике.

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

Но для этого пришлось бы переписать половину редактора.

Вариант с разрезанием по курсору пока самый лучший. При движении на страницу назад или вперёд всё равно требуется пройтись по каждому символу (чтобы отсчитать нужное число строк), так что их переброска не сильно затруднит. К тому же, это один из немногих методов, где сохранение на диск не требует предварительной обработки. Сохранение идёт прямо из памяти, мгновенно. А в случае хранения строк в куче перед сохранением потребуется безумная дефрагментация, которая займёт немалое время. Либо придётся сохранять через промежуточный буфер по 1-2 сектора, что тоже не быстро.

---------- Post added at 11:46 ---------- Previous post was at 11:44 ----------

bc проверять будем?

Не будем. Вход в развёрнутый код с нужного места, а зацикливание - в конце кода. Можно по 8-битному счётчику.