Один элемент в нескольких двусвязных списках - вопросы безопасности эффективной реализации
Иногда возникает ситуация, когда один объект должен являться элементом одновременно в нескольких двусвязных списках (например, это может быть объект окна или виджета в каком-нибудь оконном интерфейсе, которой одновременно может входить в список сортировки по Z для упорядоченной отрисовки, список группы виджетов для последовательного переключения между ними клавишей TAB, список дочерних окон родительского окна, и т.д...). Можно для этой задачи, конечно, использовать стандартные в C++ списки std::list с указателями или ссылками на соответствующие элементы. Однако в этом случае реализация окажется не очень эффективной, т.к. для добавления ссылки в каждый список будет происходить дополнительное выделение памяти под соответствующую запись списка, это помимо выделения памяти под сам объект. А хотелось бы, чтобы оператор new вызывался только один раз - для создания самого объекта, который бы потом добавлялся в списки с помощью простого связывания указателей.
В общем, моя идея в том, чтобы связывать элементы с помощью записей, которые являются полями самого класса-элемента. Списки этих записей классически закольцованы, т.е. указатель на следующую запись последнего элемента и указатель на предыдущую запись первого элемента указывают на сам класс-список. А класс-список, в свою очередь, "знает" смещение своих записей в классе-элементе, благодаря чему способен конвертировать указатель на запись в указатель на элемент и обратно путём вычитания или добавления смещения поля записи. Для облегчения понимания мною написанного привожу схему данной идеи:
+---------+ +---------+ +---------+
| ELEMENT | | ELEMENT | | ELEMENT |
| ... | | ... | | ... |
| | | | | |
--> +-------+ ----> |+-------+| -> |+-------+| -> -> |+-------+| -->
+--- ...from last NODE1 | LIST1 | || NODE1 || || NODE1 || ... || NODE1 || to LIST1... ---+
| <-- +-------+ <---- |+-------+| <- |+-------+| <- <- |+-------+| <-- |
| | | | | | | |
| --> +-------+ ----> |+-------+| -> |+-------+| -> -> |+-------+| --> |
+-->+ ...from last NODE2 | LIST2 | || NODE2 || || NODE2 || ... || NODE2 || to LIST2... +-->+
| | <-- +-------+ <---- |+-------+| <- |+-------+| <- <- |+-------+| <-- | |
| | ... | ... | | ... | | ... | | |
| | | | | | | | | |
| | --> +-------+ ----> |+-------+| -> |+-------+| -> -> |+-------+| --> | |
| +--- ...from last NODEn | LISTn | || NODEn || || NODEn || ... || NODEn || to LISTn... ---+ |
| <-- +-------+ <---- |+-------+| <- |+-------+| <- <- |+-------+| <-- |
| +---------+ +---------+ +---------+ |
| |
| |
+---------------------------------------------------------------------------------------------------------------------+
Однако на пути реализации этой идеи стоит такая мерзкая штука, как strict aliasing, которую мне надо умудриться не нарушить, чтобы не получилось вот так, как в прошлый раз!
В правилах, если я правильно понял, есть два ключевых момента: 1) разрешается приводить указатель на что угодно к char* или void*, и char* или void* к указателю на что угодно; 2) разрешается приводить указатель на класс-родитель к указателю на класс-потомок и, соответственно, наоборот. Основываясь на них, я написал следующий код - основу в первом приближении для реализации таких "множественных" списков:
/*
* File: List.h
*/
#ifndef List_h__included__
#define List_h__included__
#include <assert.h>
#include <stdexcept>
#ifndef INLINE
#define INLINE __attribute__ ((always_inline)) inline
#endif
class CListNode;
/*
* Base class for both: lists and nodes
*/
class CListBase
{
protected:
union
{
CListNode* m_pNext;
CListNode* m_pFirst;
};
union
{
CListNode* m_pPrev;
CListNode* m_pLast;
};
public:
INLINE CListBase() {}
INLINE CListBase(CListNode* pNext, CListNode* pPrev): m_pNext(pNext), m_pPrev(pPrev) {}
};
/*
* The list node that's a field of the list element data class
*/
class CListNode: public CListBase
{
friend class CListCommon;
public:
INLINE bool dbg_is_linked() const
{
#ifndef NDEBUG
return m_pNext != NULL;
#else
throw std::runtime_error("The debug check function was called not in the debug mode!");
#endif
}
INLINE void dbg_unlink()
{
#ifndef NDEBUG
m_pNext = NULL;
#endif
}
INLINE CListNode() {dbg_unlink();}
INLINE CListNode& operator =(CListNode& r) {dbg_unlink(); return *this;}
INLINE CListNode(CListNode&) {dbg_unlink();}
INLINE ~CListNode() {assert (!dbg_is_linked());}
INLINE CListNode* GetNext() const {return m_pNext;}
INLINE CListNode* GetPrev() const {return m_pPrev;}
INLINE void InsertBefore(CListNode* pNode)
{
assert (!dbg_is_linked());
assert (pNode && pNode->dbg_is_linked());
CListNode* pPrev = pNode->m_pPrev;
m_pNext = pNode;
m_pPrev = pPrev;
pPrev->m_pNext = this;
pNode->m_pPrev = this;
}
INLINE void InsertAfter(CListNode* pNode)
{
assert (!dbg_is_linked());
assert (pNode && pNode->dbg_is_linked());
CListNode* pNext = pNode->m_pNext;
m_pNext = pNext;
m_pPrev = pNode;
pNode->m_pNext = this;
pNext->m_pPrev = this;
}
INLINE void CutSelf()
{
assert (dbg_is_linked());
m_pNext->m_pPrev = m_pPrev;
m_pPrev->m_pNext = m_pNext;
dbg_unlink();
}
};
/*
* The list common class that implements the list's basical functionality
*/
class CListCommon: public CListBase
{
public:
INLINE CListCommon(): CListBase((CListNode*)this, (CListNode*)this) {}
INLINE ~CListCommon() {assert(IsEmpty());}
INLINE void dbg_force_empty()
{
#ifndef NDEBUG
m_pFirst = (CListNode*)this;
//m_pLast = (CListNode*)this;
#endif
}
INLINE void dbg_unlink_all()
{
#ifndef NDEBUG
CListNode* pNode = m_pFirst;
while (!IsEnd(pNode))
{
CListNode* pNext = pNode->m_pNext;
pNode->dbg_unlink();
pNode = pNext;
}
dbg_force_empty();
#endif
}
INLINE bool IsEmpty() const {return m_pFirst == (CListNode*)this;}
INLINE bool IsEnd(CListNode* pNode) const {return pNode == (CListNode*)this;}
INLINE CListNode* GetFirst() const {return m_pFirst;}
INLINE CListNode* GetLast() const {return m_pLast;}
INLINE void Append(CListNode* pNode)
{
assert (pNode && !pNode->dbg_is_linked());
pNode->m_pNext = (CListNode*)this;
pNode->m_pPrev = m_pLast;
m_pLast->m_pNext = pNode;
m_pLast = pNode;
}
};
/*
* The final data-based list templated class
*/
template <class TData, CListNode TData::*nodeField>
class CList: public CListCommon
{
public:
INLINE constexpr static size_t GetOffset() {return (char*)&(((TData*)NULL)->*nodeField) - (char*)NULL;}
INLINE static CListNode* GetNode(TData* pData) {return (CListNode*)((char*)pData + GetOffset());}
INLINE static TData* GetData(CListNode* pNode) {return (TData*)((char*)pNode - GetOffset());}
INLINE void Append(TData* pData) {CListCommon::Append(GetNode(pData));}
};
//macro for convenient declaration of the list variable
#define LIST_TYPE(TData, nodeField) CList<TData, &TData::nodeField>
#endif //List_h__included__
А вот программа для тестирования/демонстрации того, как работает идея:
/*
* File: main.cpp
*/
#include <stdio.h>
#include <string>
#include "List.h"
/*
* The test data class for testing the lists' functionality
*/
class CTestData
{
std::string m_strName;
int m_num;
public:
CListNode node1;
CListNode node2;
public:
INLINE CTestData(const char* pcszName, int num): m_strName(pcszName), m_num(num) {}
void print()
{
printf("(\"%s\":%d)", m_strName.c_str(), m_num);
}
};
/*
* Templated function: prints the list content
*/
template <class TList>
__attribute__((noinline,noclone)) void print_list(TList& rList, const char* pcszPromt)
{
printf("%s: ", pcszPromt);
for (CListNode* pNode = rList.GetFirst(); !rList.IsEnd(pNode); pNode = pNode->GetNext())
{
rList.GetData(pNode)->print();
printf(" ");
}
puts("");
}
/*
* main: testing the lists
*/
int main()
{
//tested elements
CTestData t1("A",1), t2("B",2), t3("C",3);
//tested lists
LIST_TYPE(CTestData, node1) list1;
LIST_TYPE(CTestData, node2) list2;
//linking list1
list1.Append(&t1);
list1.Append(&t2);
list1.Append(&t3);
//linking list2
list2.Append(&t3);
list2.Append(&t2);
list2.Append(&t1);
print_list(list1, "List1");
print_list(list2, "List2");
puts("");
printf("Something insert and cut...\n\n");
//new tested elements
CTestData t4("ab",12), t5("D",5);
t4.node1.InsertBefore(&t2.node1); //insert t4 before t2 in the list1
t2.node2.CutSelf(); //cut t2 from the list2
t5.node2.InsertAfter(&t1.node2); //insert t5 after t1 in the list2
print_list(list1, "List1");
print_list(list2, "List2");
puts("");
//unlink all nodes in the debug mode (to avoid asserts)
list1.dbg_unlink_all();
list2.dbg_unlink_all();
return 0;
}
А вот результат программы, который говорит о том, что всё вроде работает:
List1: ("A":1) ("B":2) ("C":3)
List2: ("C":3) ("B":2) ("A":1)
Something insert and cut...
List1: ("A":1) ("ab":12) ("B":2) ("C":3)
List2: ("C":3) ("A":1) ("D":5)
В общем, если я правильно понял (в общих чертах) strict aliasing, то мой код их вроде бы не нарушает, и его со спокойной душой можно развивать и использовать. Или нарушает? Меня всё ещё не покидают сомнения, не закралось ли тут где неопределённое поведение? Не подставит ли мне оптимизатор подношку однажды снова? Насколько надёжна такая реализация с точки зрения компиляции и оптимизации?
Ответы (1 шт):
И так, самым критикуемым местом в моей реализации оказался метод GetOffset(), который возвращает смещение поля узла списка в классе. Потому, что в его теле присутствует разыменование указателя nullptr, что хоть и работает, но с точки зрения стандарта приводит к неопределённому поведению. Что ж, вот моя попытка избавиться от разыменования nullptr в этом методе:
template <class TData, CListNode TData::*nodeField>
class CList: public CListCommon
{
public:
//redesigned method without using of nullptr
INLINE constexpr static size_t GetOffset()
{
char tmp[sizeof(TData)] = {0,}; //"initialize" to exclude another supposed formal UB
return (char*)&(((TData*)tmp)->*nodeField) - tmp;
}
INLINE static CListNode* GetNode(TData* pData) {return (CListNode*)((char*)pData + GetOffset());}
INLINE static TData* GetData(CListNode* pNode) {return (TData*)((char*)pNode - GetOffset());}
INLINE void Append(TData* pData) {CListCommon::Append(GetNode(pData));}
};
Результат получился тот же самый. Массив tmp оказался выкинут и метод GetOffset() посчитан на этапе компиляции/оптимизации - что и требовалось.
Буду благодарен за очередную порцию критики, а так же за освещение других вероятных проблем в коде...