В предыдущей части обсуждалась проблема создания композитных элементов, состоящих из нескольких связанных между собой примитивов:
Если сам механизм был более-менее реализован, то осталась другая проблема: как задавать эти элементы в коде? К примеру, чтобы создать композитный ползунок с двумя кнопками, нужно описать его так:
Здесь чётко видно, где ползунок и где кнопки, но также видно, что это скорее штучная работа, так как всё делается вручную.
Поэтому в то место дерева, где должен быть ползунок, хотелось бы вставлять не такое развесистое описание, а например функцию:
GUI_slider_create(...)
которая и возвращала бы вышеописанную структуру.
Рассмотрим требования к такой функции.
Допустим, она создаёт структуру внутри себя и возвращает её. Созданные функцией данные на стеке будут потеряны после выхода из функции, но возвращать их можно, потому что они будут скопированы в момент возврата, а не использованы напрямую.
Однако эти данные содержат указатели: узел дерева GUI_ItemTree ссылается на узлы детей, а структуры GUI_Item ссылаются на конкретные элементы через поле element.
В записи, которая используется сейчас:
&(GUI_Button) { .command_type = GUI_CMD_DECVAL, .text = "-" }
Данные элемента создаются прямо по месту (в стеке функции main()), и на них сразу же делается указатель, который находится на том же уровне вложенности, что и сами данные. Если сделать это внутри другой функции, данные естественно расположатся на стеке в фрейме функции и указатель на них попадёт в возвращаемый результат, но вот сами данные туда не попадут, и следовательно не будут скопированы. Но и копирование бы тут не помогло, потому что указатели будут вести на уже потерянный фрейм стека функции.
Из этого следует, что в функции можно создать что угодно, что на возврате скопируется, но нельзя делать указатели, ведущие на стек функции (кроме main()). Значит, указатели должны быть на что-то снаружи, чей срок жизни будет не меньше, чем срок жизни указателя (спасибо, Rust).
Одно из решений это выделение памяти из кучи с помощью malloc(). В этом случае мы получаем именно внешний указатель, который никуда не денется. Но выделение через malloc() имеет свои недостатки: нужно строго следить за освобождением памяти, а также это не очень быстро (зависит от фрагментации).
Условие, что любые указатели должны быть внешними по отношению к функции, обойти нельзя, поэтому единственное решение здесь это передавать в функцию уже готовые указатели на уже выделенную память, чтобы она использовала их. К примеру, можно скрупулёзно статически описать каждый используемый элемент:
static GUI_Button win1_button1 = { ... };
static GUI_Button win1_button2 = { ... };
...
И потом пользоваться указателями на win1_button1 и т.д.
Существует, однако, вариант, который всё это рушит.
У нас есть окно, а в нём кнопка. Когда мы нажимаем на кнопку, в окне появляется ещё одна кнопка. И так далее.
При составлении, например, опроса, есть кнопка "добавить новый ответ", которая ровно это и делает.
Так что с такой ситуацией мы всё равно столкнёмся, и обратим внимание, как она будет происходить. После нажатия на кнопку мы попадём в функцию-обработчик кнопки, которая должна создать новую кнопку. Создать на какой памяти? Мы не можем её передать извне, потому что даже не знаем, какая она по счёту, ведь кнопки можно клонировать бесконечно.
Очевидно, остаётся только воспользоваться malloc().
И вот тут я хочу заморочиться дополнительно,
сделав malloc() единичным. А именно, пусть диспетчер сразу выделит кусок памяти под будущие данные. Все создаваемые элементы будут храниться в этом куске. Назовём его хранилищем.
Преимущество в том, что я не буду постоянно дёргать malloc() и free(), следить за жизнью указателей и беспокоиться о фрагментации.
С другой стороны, теперь эти проблемы перекладываются на голову диспетчера. Но диспетчер, используя свои знания о структуре элементов, может во-первых минимизировать фрагментацию, а во-вторых, ускорить работу с выделением и освобождением памяти в своём хранилище.
Алло, диспетчерская
Начнём проектировать методы работы с хранилищем. Когда нам нужен указатель на данные кнопки &(GUI_Button) { ... }, мы уже не будем эти данные описывать в декларативном виде, а запросим у диспетчера, вроде того:
GUI_dispatcher_allocate_button(...)
Но чтобы не писать функцию allocate_* для каждого типа элемента, можно попросить просто нужный размер памяти:
GUI_dispatcher_allocate_element(sizeof(GUI_Button))
У диспетчера, естественно, будет список занятых областей хранилища. После получения запроса он добавляет в список ещё одну занятую область указанного размера.
Но интереснее, что будет после удаления (освобождения) элемента. Очевидно, образуется разрыв в списке.
Стягивать этот разрыв будет нехорошо, так как мы уже отдали указатели на выделенные области и перемещать их нельзя (можно и указатели обновить, но это как-то муторно).
Оставлять его как есть тоже нехорошо, так как будет расходоваться память.
Переиспользовать можно, когда требуемая порция меньше или равна освобождённой. Но это приведёт к фрагментации и сопутствующим проблемам, от которых хотели уйти.
GUI-суперпозиция
Интерфейс приложения содержит некие формы, которые могут присутствовать на экране по очереди или одновременно, но их количество уже предопределено. К примеру, всего может быть 8 окон, 117 кнопок, 13 чекбоксов и т.д. В зависимости от действий пользователя какие-то элементы могут появляться на экране часто, а какие-то могут вообще не появиться. Тем не менее, пределом конкретной конфигурации GUI является вывод на экран всех предусмотренных элементов одновременно.
Следовательно, теоретически существует разметка хранилища под все эти элементы, и эта разметка будет фиксированной, не требующей выделения или освобождения памяти. У каждого возможного элемента будет своё личное место.
Но так как подсчитывать общее количество элементов каждого типа слишком лениво, можно сделать динамическое заполнение хранилища. Оно изначально будет пустым, но элемент, который однажды был зарезервирован, там и остаётся.
Таким образом, в абсолютном пределе хранилище будет содержать все элементы, как и описывалось выше, а в обычном случае – только те, которые хоть раз использовались.
Переиспользование
Из вышеизложенного может показаться, что переиспользовать элементы в хранилище вообще не нужно, так как память под них всё равно уже зарезервирована.
Но представим ситуацию, когда мы в цикле создаём и удаляем один и тот же элемент. Изначально под него была выделена область памяти, но если её не переиспользовать, то при повторных созданиях элемента будут выделяться всё новые и области, пока память не закончится.
Решение здесь такое: оставляем эту область в хранилище, ничего не трогая, но помечаем её как свободную. При добавлении элемента с размером N мы смотрим, есть ли свободная зарезервированная область ровно такого размера. Если есть, отдаём её под этот элемент. Если нет, резервируем новую в конце списка.
Представим такой случай: в интерфейс было добавлено 100 кнопок, затем все они освободились. Имеем 100 свободных областей в хранилище. После этого добавляем, к примеру, чекбоксы, которые не совпадают по размеру (памяти) с кнопками. Поэтому ни один чекбокс не попадёт в область освобождённых кнопок. Получается, что эта обширная область из 100 элементов будет пропадать зря. Но это допустимо. Во-первых, как только появится нужда в новой кнопке, пустующее место будет переиспользовано. Во-вторых, как известно из предыдущего пункта, в пределе хранилище будет содержать все возможные элементы GUI, но не более того. Так вот он, этот предел.
Навигация по хранилищу
Диспетчер должен уметь быстро искать, резервировать и освобождать области нужного размера. В силу специфики GUI есть конечное число фиксированных размеров элементов, к примеру кнопка это 32 байта, чекбокс это 8 байт и т.д. Некоторые элементы могут иметь одинаковый размер, поэтому нас интересует не их тип, а только размер.
Максимальный практический размер элемента установим в 256 байт (если понадобится больше, сделаем больше, непринципиально).
Тогда в диспетчере можно сделать простую хэш-таблицу размером 256 записей с индексами, соответствующими размерам элементов. Каждая запись содержит информацию о том, сколько таких элементов находится в хранилище, и сколько из них свободны.
Теперь предположим, что нужно зарезервировать элемент размером 20 байт. Диспетчер смотрит в хэш-таблицу по индексу 20. Если в записи отсутствуют свободные элементы, он резервирует новую область в хранилище. Если же есть свободные, то находит свободный и резервирует его.
Так как элементы разных типов по мере добавления размещаются в хранилище без какого-либо порядка, каждый элемент внутри своей группы должен иметь связь со следующим/предыдущим элементом, чтобы поддерживать всю цепочку поиска.
Значит, нужен связный список элементов каждого типа (размера).
Посмотрим, как это будет работать.
- У каждого элемента есть ссылка на предыдущий и следующий.
- При добавлении элемента он добавляется в конец связного списка занятых, и диспетчер сохраняет его адрес как адрес последнего занятого элемента.
- При освобождении элемента он добавляется в конец списка свободных, и диспетчер сохраняет его адрес как адрес последнего свободного элемента.
Таким образом, добавление и освобождение работают за время O(1).
Реализация
Структура выделяемого элемента хранения:
Такая структура выделяется непосредственно в памяти хранилища, но кроме неё выделяется собственно сам элемент определённого размера, к примеру 20 байт. Элемент идёт сразу за структурой. То есть его адрес вычисляется как адрес структуры + размер структуры. Размер элемента сохраняется в структуре в поле size для служебных целей, которые рассмотрим позже. Поле status показывает, свободна или занята структура, и хотя оно не нужно, но тоже будет служить для кое-чего.
Структура записи в хэш-таблице хранилища:
И само хранилище:
Поле mem это выделенная с помощью malloc() память, само "тело" хранилища. А поле last_mem это последний свободный адрес, начиная с которого можно добавлять новый элемент. Поле size это объём выделенной памяти, чтобы при добавлении очередного элемента мы не могли его превысить.
Добавление элемента в хранилище:
Возвращается указатель не на запись в хранилище, а именно на выделенную для элемента память, которая идёт сразу после записи.
Удаление элемента из хранилища:
Тут надо осветить пару моментов. Во-первых, для освобождения передаётся тот же адрес, который ранее был получен. Его надо преобразовать обратно в адрес записи хранилища, отняв от него размер записи. Далее, я не предполагаю никаких хакерских атак на GUI, но было бы неплохо хотя бы для диагностики ошибок, чтобы диспетчер проверял валидность переданного указателя. Для начала можно проверить, попадает ли адрес в диапазон адресов хранилища.
Затем можно прочитать запись и проверить валидность самой записи. Например, у неё есть поле status, которое в освобождаемом элементе должно иметь значение "занято", поле size, равное размеру элемента, и поля prev и next, указывающие на предыдущую и следующую запись. Можно проверить size на минимальное и максимальное значение, проверить, что поля prev и next также показывают в хранилище, получить записи из этих полей и проверить, чтобы у них был такой же size, и т.п., в зависимости от степени паранойи. В общем, я пока этого не делаю.
Но вот поле size важно для того, чтобы найти индекс в хэш-таблице и далее поправить там информацию. Именно поэтому оно сохраняется вместе с записью.
Использование
Наконец я могу написать искомую функцию создания кнопки:
Она вернёт структуру GUI_ItemTree, которая будет содержать ссылки на хранилище.
Теперь декларативные методы можно заменить функциями:
Аналогичным образом я сделал функции создания ползунков, чекбоксов и некоторых других элементов, но описывать их здесь уже не буду.
Теперь можно инициализировать несколько ползунков вместе с кнопками, не затрачивая больших усилий:
Всё, что было сделано – не просто облегчение ввода, но и ступень к дальнейшей цели: выпадающему списку. В следующей части посмотрим, какие вызовы он бросает.
Код на гитхабе:
Читайте дальше:
