среда, 11 июня 2008 г.

Инстанцирование шаблонов смещениями полей.

Надо сказать, что с шаблонами я как-то не особо дружу, но надо когда-то начинать.

Вот озадачился я одной интересной задачей: Необходимо организовать хранение объектов в списках, с таким рассчетом, чтобы это не вызывало накладных расходов памяти. То есть, информацию о связях должны хранить сами объекты. Для этой цели в объектах предусмотрено специальное поле - линк. Причем в одном объекте может быть несколько таких полей. Первая версия никак не конкретизировала расположение поля, и указывать его было необходимо только при размещении элемента в списке. При этом сам линк кроме ссылочной информации хранил так же указатель на объект, его содержащий.

Но вот решил наконец таки разобраться и сделать по уму. Кто-то спросит - а почему не STL? - потому, что это ядро. нету там STL и не будет. К тому же я понимаю так, что почти любой контейнер STL выделяет память для организации элементов в контейнере, что мне в данном случае не особо нравится. В ядре все должно быть более предсказуемо.

Главная суть идеи заключается в том, что список должен знать, по какому полю ему надлежит связывать элементы. То есть надо каким-то образом хранить смещение поля в объекте. Я о такой стандартной возможности раньше не слышал, к тому же в интренете много советов на тему reinterpret_cast, но это не наш путь.

Шаблоны можно инстанцировать именами типов, или константами. Причем тип у константы может быть любой, главное чтобы ее значение было заранее известно и неизменно. Именно так и происходит с предварительно описанным классом, которым мы инстанцируем шаблон. Поскольку типы объектов заранее не известны, то и List и Link - шаблонные. Здесь я приведу упрощенную модель.
template <typename I>
class Link {
...
I *next;
...
};

template<typename I, Link<I> I::* L>
class List {
...
I *m_first;
...
};

Здесь самое интересное - это второй параметр. Фактически это смещение поля, которое надо использовать с помощью операторов ->* или .* .
class List {
...
void Insert (I *i)
{
(i->*L).next = m_first;
m_first = i;
}
...
}

Инстанциирование осуществляется следующим образом:

class Item {
Link<Item> m_link;
Link<Item> m_link2;
};

List<Item, &Item::m_link> list1;
List<Item, &Item::m_link2> list2;

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

Но зато уже никакие операции не требуют указывать поле по которому производится связывание. Сам список прекрасно это знает и без чужих подсказок.

PS: В принципе тип Link<I> I::* достаточно интересен. ostream принимает его наверное за bool, и на любые, даже нулевые смещения выводит 1. А привести его к чему-то у меня не получилось вообще. Но старый, добрый printf с помощью %p отобразил реальное значение этого типа, которое как и ожидалось является смещением в классе.

PPS: Полем я как-то по старинке называю переменные-члены.