Разбор кода Nebula Device2. Часть3. Контейнеры (статья 1 - Списки)

Автор: graveman

Списки

Сегодня я буду рассказывать о списках. Списки - очень распространенный контейнер в пределах кода Небулы. На его основе созданы более специализированные версии типа nStrList и другие. Разобраться в них было необходимо. Списки представлены двумя классами: nList, собственно представляющим сам список, и nNode, который описывает узел (или нод) этого списка.

В движке Nebula списки реализованы немного необычным образом.
Для того, чтобы разобраться в их работе, начнем с анализа кода конструктора. Строка

this->head = (nNode*)&(this->tail);

помещает в указатель head класса nList адрес указателя tail так как будто по адресу tail расположен некоторый объект типа nNode. То есть подразумевается, что в ячейках памяти, которые заняты указателями tail и tailpred, расположен объект класса nNode. Будем обозначать этот подразумеваемый объект как nTail. В объекте nTail указатель succ класса nNode будет занимать то же место в памяти, которое занимает указатель tail класса nList, а указатель pred класса nNode займет место в памяти, в котором размещен указатель tailpred класса nList.

Точно так же строка

this->tailpred = (nNode*)&(this->head);

помещает в указатель tailpred класса nList адрес указателя head так как будто по этому адресу расположен некоторый объект типа nNode, который обозначим через nHead. В объекте nHead указатель succ класса nNode будет занимать то же место в памяти, которое занимает указатель head класса nList, а указатель pred класса nNode займет место в памяти, в которое размещен указатель tail класса nList.

Указатель tail класса nList содержит 0 и так и будет его содержать до конца жизни объекта класса nList, служа неким сторожевым флагом. Таким образом nTail.succ всегда будет содержать ноль.

На рисунке ниже показано состояние членов списка nList после работы конструктора.

Инициализация списка | Разбор кода Nebula Device2. Часть3. Контейнеры (статья 1 - Списки)

Рассмотрим процесс добавления узлов методом AddHead() класса nList. Как видно из исходного кода:

n->InsertAfter((nNode*)&(this->head));

над объектом n типа nNode вызывается операция InsertAfter(), в которую передается указатель на подразумеваемый объект nHead. Посмотрим на InsertAfter(), чтобы посмотреть, что произойдет с указателями:

this->pred = pred;

Поскольку pred указывает на nHead, то указатель pred объекта n содержит теперь адрес nHead. Строка

this->succ = pred->succ;

немногим тяжелее. Операция pred->succ читается так: «взять значение поля succ в объекте, адрес которого содержится в pred». Поскольку pred содержит адрес nHead, то значение pred->succ содержит адрес подразумеваемого объекта nTail. Поэтому указатель succ объекта n теперь указывает на nTail.
Легко понять, что строка

pred->succ = this;

помещает в nHead.succ адрес объекта n. Так как теперь this->succ указывает на nTail, то строка

this->succ->pred = this;

помещает в nTail.pred адрес объекта n.
Состояние после первого добавления AddHead():

gamedev2 | Разбор кода Nebula Device2. Часть3. Контейнеры (статья 1 - Списки)

Нетрудно видеть, что последовательные вызовы метода AddHead() приводят к такой последовательности:

nHead->…->nk->nk-1->…->n2->n1->nTail.

Рассмотрим удаление методом RemHead().
Указатель this->head – это nHead.succ. Поэтому this->head указывает на объект nNode, первый объект за головой списка. У добавленных объектов nNode указатель succ всегда на что-то указывает, а у nTail в поле succ всегда содержится 0. Проще говоря, метод RemHead() вынуждает первый объект nNode за головой списка (объектом nHead) самоудалиться, после чего RemHead() возвратит указатель на него. А если объектов не осталось, то ничего не произойдет и будет возвращен нуль

Метод GetHead() возвращает указатель на первый объект nNode за головой списка. Если же объектов нет, то будет возвращен нуль.

Метод AddTail() действует аналогично, но объекты располагаются перед хвостом:

nHead->n1->n2->…->nTail.

Методы AddTail(), GetTail(), RemTail() аналогичны методам AddHead(), GetHead(), RemHead().

Со списками типа nList и объектами nNode нужно соблюдать следующие предосторожности (из анализа ассертов):

очищать список от нодов перед разрушением объекта списка;
не вызывать GetSucc(), GetPred(), Remove() для нодов, не содержащихся в каком-либо списке;
удалять нод из списка перед разрушением объекта нода;
не вызывать InsertAfter(), InsertBefore() через ноды, не содержащиеся в каком-либо списке.

А теперь демонстрационный код:

+ Показать