а по дороге потихоньку портирую деревья из моего сишного редактора. волевым решением сразу делаю отвратительно: ноды живут вне пространства, управляемого GC. соответственно, в коде хитрый аллокатор и акробатика с кастованием указателей.
вынести ноды я решил потому что у меня есть желание в таких же деревьях потом кэшировать всякое полезное: размеры строк, форматирование, всякие хайлайты, и ты пы. там потенциально может быть офигелиард маленьких нод, все их бедному GC придётся сканировать, и совершенно зря. поэтому пул нод берёт у системы память через `mmap()` (оно неважно, можно `malloc`, или как угодно), и дерево управляет всем само.
в коде нода — расширяемая запись, но указатели на ноды untagged. благо, такие финты делать можно, и зная раскладку в памяти, иметь безопасные касты (и даже финализаторы для нод). конечно, для кастов надо делать свои процедуры: компилятор ругается неприлично, если его попросить кастануть untagged pointer. что, кстати, совершенно зря: не вижу ни одной причины, по которой это запрещено (если явно импортирован SYSTEM, например). надо будет потом компилер подрихтовать.
в оригинальном сишном коде все типы нод были одной записью с флажками и union-ом для user data. в принципе, и здесь так можно было бы, но как-то… совсем уже фи. правда, код всё равно знает про разные типы нод, потому что ему надо чинить всякое: для нод, которые хранят размеры строк, например, эти самые размеры надо чинить тоже.
в принципе, всё это будет интимной механикой текстовых моделей, так что как оно там внутри выглядит — не так уж важно: лишь бы GC не лопался. форматировать текст можно при первом показе: будут небольшие тормоза на открытии документа (если он сотни мегов размером, гыг), зато потом всё lightning fast. плюс вертикальный размер с точностью до пикселя, а не как сейчас. потенциальная проблема — один view в нескольких frame, но об этом я подумаю когда придёт время.
для особо рьяных любителей, кстати, можно поверх текста оверлеем вешать раскраски. оверлей в документ не сохраняется, на кусочки не влияет, просто задаёт цвета (атрибуты?) для регионов текста (в дополнение к существующим). никаких тормозов, никаких попыток рисования поверх документа. правда, наличие кернинга всё усложняет, и я не уверен, что буду делать эту фичу.
а вот оверлей для отметки активных регионов текста — можно. тогда всякие гиперссылки просто будут в этом оверлее отмечать регионы — вместо прыжков с эвристической скакалкой, как сейчас. в принципе, в таких оверлеях даже семантическую информацию об исходнике хранить можно.
так что массивы (эти деревья эмулируют именно массивы span'ов) со временем на поиск позиции/вставку/удаление O(log n), и O(1) на итераторы — очень полезная штука. (worst time is O(2*log n), если что, свойство AA trees.) один раз такое написал — и можно кучу гвоздей этим забить.
|