Неосторожное использование шаблонов может вызвать раздувание.Один из способов избежать этого - создать тонкий типобезопасный шаблон, который оборачивает не типизированный не шаблонный код.Чтобы сделать это, оболочка должна предоставить некоторый способ для нешаблонного кода для доступа к вещам, о которых она ничего не знает.
Например, в структуре данных оболочка определяет структуры узла.Небезопасный код должен читать и записывать в узлы, но должен делать это косвенно, через какой-то интерфейс, указанный в оболочке.
Один из способов реализации этого интерфейса - заполнение структуры (определеннойнебезопасным кодом) с такими деталями, как указатели функций и константы, определенные оболочкой.И один соответствующий вид константы - это смещение (в некоторой структуре) определенного поля.Небезопасный код может использовать это смещение (и некоторую арифметику указателя) для прямого доступа к этому полю.
Однако это становится проблематичным - поскольку оптимизаторы становятся более агрессивными, это может привести к проблемам с псевдонимом указателя.Это особенно верно, если узлы могут покинуть библиотеку.Например, узлы могут быть извлечены из двоичного дерева и перекомпонованы для формирования связанного списка.Другой пример, досадно, случается при модульном тестировании.
В настоящее время у меня есть библиотека контейнеров, написанная в том же духе, и в настоящее время она не вызывает ни одной из этих проблем - но это произойдет в ближайшее время.Причина, по которой он избегает этих проблем, заключается в том, что все модульное тестирование применяется к контейнерам (а не к базовому коду) и потому что узлы никогда не покидают контейнеры.То есть к узлам всегда обращаются одним и тем же арифметическим способом с указателями, поэтому проблема оптимизации псевдонимов указателей никогда не возникает.
К сожалению, в скором времени мне понадобится разрешить извлечение узлов из контейнеров, и яВозможно, мне также понадобятся модульные тесты для базового небезопасного кода.
Вместо того, чтобы иметь дело с этой конкретной библиотекой, у меня есть гораздо более простое извлечение из библиотеки старого двоичного дерева, которая страдает от тех же проблем.В VC ++ 9 это просто работает.Используя MinGW GCC 4.4.0, отладочная сборка работает, но сборка выпуска завершается неудачно.Проблема заключается в смеси встраивания и неспособности оптимизатора обнаружить псевдонимы указателей.
Просто чтобы прояснить - я не хочу здесь "WTF - GOTO !!!"или что угодно.Проблема заключается в решении проблемы оптимизации / указателя.Хотя, если вы можете найти способ написать Tree_To_List, который правильно структурирован и не использует скрытые / замаскированные gotos для достижения этого, мне будет интересно.
Кроме того, слой абстракции на основе шаблоновотсутствует (шаблон c_Bin_Tree_Tool не выполняет всю работу - c_Tool завершает перенос, но не для многократного использования, а для каждого использования. Это всего лишь побочный эффект извлечения соответствующего кода.
Этот код создает несбалансированное двоичное дерево, вставляя узлы один за другим, а затем балансирует это дерево. Балансировка выполняется путем преобразования дерева в список (каким он уже есть), а затем преобразования списка обратно.в дерево. Дерево сбрасывается в stdio как до, так и после баланса.
bintree.h ...
inline void* Ptr_Add (void* p1, std::ptrdiff_t p2) { return (void*) (((std::ptrdiff_t) p1) + p2); }
struct c_Bin_Tree_Closure
{
typedef int (*c_Node_Comp) (void* p_Node1, void* p_Node2);
c_Node_Comp m_Node_Comp;
std::ptrdiff_t m_Left, m_Right;
};
class c_BT_Policy_Closure
{
private:
const c_Bin_Tree_Closure* m_Closure;
protected:
void** Left_Of (void* p) { return ((void**) Ptr_Add (p, m_Closure->m_Left )); }
void** Right_Of (void* p) { return ((void**) Ptr_Add (p, m_Closure->m_Right)); }
int Compare_Node (void* p_Node1, void* p_Node2) const
{
return m_Closure->m_Node_Comp (p_Node1, p_Node2);
}
public:
c_BT_Policy_Closure ()
{
m_Closure = 0;
}
void Set_Closure (const c_Bin_Tree_Closure& p_Closure)
{
m_Closure = &p_Closure;
}
};
template<class tc_Policy>
class c_Bin_Tree_Tool : public tc_Policy
{
public:
c_Bin_Tree_Tool ()
{
}
void *List_To_Tree (size_t p_Size, void* &p_List);
void Tree_To_List (void* p_Root, void* &p_First, void* &p_Last, size_t &p_Size);
void Balance (void* &p);
void Insert (void* &p_Tree, void* p_Node);
};
template<class tc_Policy>
void* c_Bin_Tree_Tool<tc_Policy>::List_To_Tree (size_t p_Size, void* &p_List)
{
if (p_Size == 0) return 0;
size_t l_Size = p_Size / 2;
void* l_Ptr = List_To_Tree (l_Size, p_List);
void* l_This = p_List;
p_List = *tc_Policy::Right_Of (l_This);
*tc_Policy::Left_Of (l_This) = l_Ptr;
l_Size = p_Size - (l_Size + 1);
*tc_Policy::Right_Of (l_This) = List_To_Tree (l_Size, p_List);
return l_This;
}
template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Tree_To_List (void* p_Root, void* &p_First, void* &p_Last, size_t &p_Size)
{
// Use left links as prev links and right links as next links
void* l_Start = 0; // first-item-in-list pointer
void* l_Prev = 0; // previous node in list
void** l_Prev_Ptr = &l_Start; // points to the next (ie right) pointer for the next node.
void* l_Pos = p_Root;
void* l_Next;
void* l_Parent = 0;
size_t l_Count = 0;
p_Last = 0;
TOP_OF_LOOP:
l_Next = *tc_Policy::Left_Of (l_Pos);
if (l_Next != 0)
{
*tc_Policy::Left_Of (l_Pos) = l_Parent; // So we can find our way back up the tree
l_Parent = l_Pos;
l_Pos = l_Next;
goto TOP_OF_LOOP;
}
AFTER_STEP_PARENT:
l_Next = *tc_Policy::Right_Of (l_Pos);
*tc_Policy::Left_Of (l_Pos) = l_Prev;
p_Last = l_Pos;
l_Prev = l_Pos;
*l_Prev_Ptr = l_Pos;
l_Prev_Ptr = tc_Policy::Right_Of (l_Pos);
l_Count++;
if (l_Next != 0)
{
l_Pos = l_Next;
goto TOP_OF_LOOP;
}
if (l_Parent != 0)
{
l_Pos = l_Parent;
l_Parent = *tc_Policy::Left_Of (l_Pos);
goto AFTER_STEP_PARENT;
}
*l_Prev_Ptr = 0;
p_First = l_Start;
p_Size = l_Count;
}
template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Balance (void* &p)
{
void *l_First, *l_Last;
size_t l_Count;
Tree_To_List (p, l_First, l_Last, l_Count);
p = List_To_Tree (l_Count, l_First);
}
template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Insert (void* &p_Tree, void* p_Node)
{
void** l_Tree = &p_Tree;
while (*l_Tree != 0)
{
int l_Compare = tc_Policy::Compare_Node (*l_Tree, p_Node);
l_Tree = ((l_Compare < 0) ? tc_Policy::Right_Of (*l_Tree) : tc_Policy::Left_Of (*l_Tree));
}
*l_Tree = p_Node;
*tc_Policy::Right_Of (p_Node) = 0;
*tc_Policy::Left_Of (p_Node) = 0;
};
test_bintree.cpp ...
#include <iostream>
#include "bintree.h"
struct c_Node
{
c_Node *m_Left, *m_Right;
int m_Data;
};
c_Node g_Node0001 = { 0, 0, 1 }; c_Node g_Node0002 = { 0, 0, 2 };
c_Node g_Node0003 = { 0, 0, 3 }; c_Node g_Node0004 = { 0, 0, 4 };
c_Node g_Node0005 = { 0, 0, 5 }; c_Node g_Node0006 = { 0, 0, 6 };
c_Node g_Node0007 = { 0, 0, 7 }; c_Node g_Node0008 = { 0, 0, 8 };
c_Node g_Node0009 = { 0, 0, 9 }; c_Node g_Node0010 = { 0, 0, 10 };
int Node_Compare (void* p1, void* p2)
{
return (((c_Node*) p1)->m_Data - ((c_Node*) p2)->m_Data);
}
c_Bin_Tree_Closure g_Closure =
{
(c_Bin_Tree_Closure::c_Node_Comp) Node_Compare,
offsetof (c_Node, m_Left ), offsetof (c_Node, m_Right)
};
class c_Tool : public c_Bin_Tree_Tool<c_BT_Policy_Closure>
{
protected:
typedef c_Bin_Tree_Tool<c_BT_Policy_Closure> c_Base;
public:
c_Tool () { Set_Closure (g_Closure); }
void Insert (c_Node* &p_Tree, c_Node* p_Node) { c_Base::Insert ((void*&) p_Tree, p_Node); }
void Balance (c_Node* &p) { c_Base::Balance ((void*&) p); }
};
void BT_Dump (size_t p_Depth, c_Node* p_Node)
{
if (p_Node != 0)
{
BT_Dump (p_Depth + 1, p_Node->m_Left);
for (size_t i = 0; i < p_Depth; i++) std::cout << " .";
std::cout << " " << p_Node->m_Data << std::endl;
BT_Dump (p_Depth + 1, p_Node->m_Right);
}
}
int main (int argc, char* argv[])
{
c_Tool l_Tool;
c_Node *l_Root = 0;
l_Tool.Insert (l_Root, &g_Node0001);
l_Tool.Insert (l_Root, &g_Node0002);
l_Tool.Insert (l_Root, &g_Node0003);
l_Tool.Insert (l_Root, &g_Node0004);
l_Tool.Insert (l_Root, &g_Node0005);
l_Tool.Insert (l_Root, &g_Node0006);
l_Tool.Insert (l_Root, &g_Node0007);
l_Tool.Insert (l_Root, &g_Node0008);
l_Tool.Insert (l_Root, &g_Node0009);
l_Tool.Insert (l_Root, &g_Node0010);
BT_Dump (0, l_Root); std::cout << "----------" << std::endl;
l_Tool.Balance (l_Root);
BT_Dump (0, l_Root);
return 0;
}
Ожидаемые результаты: ...
1
. 2
. . 3
. . . 4
. . . . 5
. . . . . 6
. . . . . . 7
. . . . . . . 8
. . . . . . . . 9
. . . . . . . . . 10
----------
. . . 1
. . 2
. 3
. . . 4
. . 5
6
. . . 7
. . 8
. 9
. . 10
Что на самом деле происходит (MinGW GCC 4.4.0, оптимизированная сборка релиза) ...
1
. 2
. . 3
. . . 4
. . . . 5
. . . . . 6
. . . . . . 7
. . . . . . . 8
. . . . . . . . 9
. . . . . . . . . 10
----------
1
Насколько я могускажите, операция Balance выполняется правильно, но BT_DumpФункция не может видеть все изменения в полях m_Left и m_Right.
EDIT Это неправильно - иначе, почему я вижу узел 1 в качестве нового корня.Я думаю, это то, что происходит, когда вы слишком полагаетесь на память о расследовании, которое было проведено несколько месяцев назад.
EDIT На самом деле, узел 1 как root является проблемой, но так как это был старыйroot - хорошо, лучше всего просто игнорировать эту проблему и разрабатывать свои собственные теории; -)
В коде есть ряд вопросов, которые не определены стандартами. Я думаю, что самая большая проблема заключается в том, что ссылки в структуре узла являются c_Node *, но поскольку небезопасный код ничего не знает о c_Node, он обращается к ним (через арифметику указателей) как void *.
Одним из исправлений было бы то, что небезопасный код выполнял все операции чтения и записи через указатели на функции получения и установки, избегая всей арифметики указателей и гарантируя, что весь доступ к экземплярам c_Node осуществляется через указатели c_Node *. Еще лучше - интерфейс становится классом с методами getter / setter и т. Д. В полной библиотеке бинарного дерева у меня есть альтернативные классы политики, которые делают это, хотя, честно говоря, мое настоящее исправление, когда возникла проблема, состояло в том, чтобы бросить весь код в «нежелательная» папка на основании того, что я редко ее использую, и, вероятно, в любом случае следует использовать интрузивные списки boost.
Однако это все еще оставляет другую, более сложную и интенсивно используемую библиотеку контейнеров, которая не исчезнет. Я думаю, что мне просто придется выполнить очень болезненный рефакторинг, чтобы избавиться от арифметики смещения и указателей, но ...
Что именно представляют собой правила C ++ - когда точно разрешено, чтобы компилятор не смог обнаружить возможный псевдоним указателя? И можно ли переписать приведенный выше двоичный код дерева так, чтобы он по-прежнему использовал арифметику указателей, по-прежнему разрешал доступ к узлам и изменял их как внутри, так и вне библиотеки, и при этом был безопасен от этой проблемы оптимизации?