Die unvorsichtige Verwendung von Vorlagen kann zu einer Aufblähung führen. Eine Möglichkeit, diese Aufblähung zu vermeiden, ist eine dünne, typsichere Vorlage, die nicht-typsicheren Nicht-Vorlagen-Code umhüllt. Dazu muss der Wrapper dem Nicht-Template-Code eine Möglichkeit bieten, auf Dinge zuzugreifen, von denen er nichts weiß.
In einer Datenstruktur definiert die Verschalung beispielsweise die Knotenstrukturen. Der unsichere Code muss die Knoten lesen und schreiben, aber er muss dies indirekt tun, über eine Art Schnittstelle, die vom Wrapper festgelegt wird.
Eine Möglichkeit, diese Schnittstelle zu implementieren, besteht darin, eine (durch den unsicheren Code definierte) Struktur mit Details wie Funktionszeigern und Konstanten zu füllen, die vom Wrapper bestimmt werden. Eine relevante Art von Konstanten ist der Offset (innerhalb einer Struktur) eines bestimmten Feldes. Der unsichere Code kann diesen Offset (und etwas Zeigerarithmetik) verwenden, um direkt auf dieses Feld zuzugreifen.
Dies ist jedoch problematisch - da Optimierer immer aggressiver werden, kann dies zu Zeiger-Alias-Problemen führen. Dies ist insbesondere dann der Fall, wenn Knoten der Bibliothek entkommen können. Zum Beispiel können Knoten aus einem Binärbaum extrahiert und neu verknüpft werden, um eine verknüpfte Liste zu bilden. Ein weiteres, ärgerliches Beispiel tritt bei Unit-Tests auf.
Ich habe derzeit eine Containerbibliothek, die nach diesem Schema geschrieben wurde, und sie verursacht derzeit keines dieser Probleme - aber das wird sie in Kürze. Der Grund, warum sie diese Probleme vermeidet, ist, dass alle Unit-Tests auf Container angewendet werden (nicht auf den zugrundeliegenden Code) und dass die Knoten niemals aus den Containern entkommen. Das heißt, auf die Knoten wird immer auf die gleiche Weise zugegriffen, so dass das Problem der Zeiger-Alias-Optimierung nie auftritt.
Leider muss ich in Kürze zulassen, dass Knoten aus den Containern extrahiert werden, und ich werde wahrscheinlich auch Unit-Tests für den zugrunde liegenden unsicheren Code benötigen.
Anstatt sich mit dieser speziellen Bibliothek zu beschäftigen, habe ich hier einen viel einfacheren Auszug aus einer alten Binärbaum-Bibliothek, die unter denselben Problemen leidet. In VC++9 funktioniert es einfach. Mit MinGW GCC 4.4.0 funktioniert ein Debug-Build, aber ein Release-Build schlägt fehl. Das Problem ist eine Mischung aus Inlining und dem Versagen des Optimierers, Zeiger-Aliasse zu erkennen.
Nur um das klarzustellen - ich will hier nicht "WTF - GOTO!!!" oder ähnliches hören. Das Problem ist die Lösung des Optimierungs-/Zeigerproblems. Obwohl, wenn Sie einen Weg finden können, zu schreiben Tree_To_List die richtig strukturiert ist und keine versteckten/verschleierten Gotos verwendet, um dies zu erreichen, bin ich interessiert.
Außerdem fehlt eine Abstraktionsebene auf der Grundlage von Vorlagen (die Vorlage c_Bin_Tree_Tool erledigt nicht die ganze Arbeit - c_Tool erledigt das Wrapping, aber auf eine Art und Weise, die nur für die jeweilige Verwendung gilt, und nicht in wiederverwendbarer Form. Das ist nur ein Nebeneffekt der Extraktion des relevanten Codes.
Mit diesem Code wird ein unausgewogener Binärbaum erstellt, indem ein Knoten nach dem anderen eingefügt wird, und dieser Baum dann ausgeglichen. Der Ausgleich erfolgt durch Umwandlung des Baums in eine Liste (was er in gewisser Weise bereits ist) und anschließende Rückumwandlung der Liste in einen Baum. Der Baum wird sowohl vor als auch nach dem Ausgleichen nach stdio ausgegeben.
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;
}Die erwarteten Ergebnisse sind...
1
. 2
. . 3
. . . 4
. . . . 5
. . . . . 6
. . . . . . 7
. . . . . . . 8
. . . . . . . . 9
. . . . . . . . . 10
----------
. . . 1
. . 2
. 3
. . . 4
. . 5
6
. . . 7
. . 8
. 9
. . 10Was tatsächlich passiert (MinGW GCC 4.4.0, optimierter Release-Build)...
1
. 2
. . 3
. . . 4
. . . . 5
. . . . . 6
. . . . . . 7
. . . . . . . 8
. . . . . . . . 9
. . . . . . . . . 10
----------
1Soweit ich das beurteilen kann, läuft die Operation Balance korrekt, aber die Funktion BT_Dump kann nicht alle Änderungen an der m_Left y m_Right Felder.
EDIT Das ist falsch - warum würde ich sonst Knoten 1 als neue Wurzel sehen. Ich schätze, das passiert, wenn man sich zu sehr auf die Erinnerung an eine Untersuchung verlässt, die vor Monaten durchgeführt wurde.
EDIT Eigentlich ist Node 1 als Root ein Problem, aber da es die alte Root war - naja, am besten ignoriert man dieses Was-ist-das-Problem-Zeug einfach und stellt seine eigenen Theorien auf ;-)
Der Code weist eine Reihe von Problemen auf, die nicht durch Standards definiert sind. Ich denke, das größte Problem ist, dass die Links in der Knotenstruktur c_Node* sind, aber da der unsichere Code nichts über c_Node weiß, greift er auf sie (über Zeigerarithmetik) als void* zu.
Eine Lösung wäre, dass der unsichere Code alle Lese- und Schreibvorgänge über Getter- und Setter-Funktionszeiger durchführt, wodurch die gesamte Zeigerarithmetik vermieden und sichergestellt wird, dass alle Zugriffe auf c_Node-Instanzen über c_Node*-Zeiger erfolgen. Noch besser - die Schnittstelle wird zu einer Klasse mit Getter/Setter-Methoden usw. In der kompletten Binärbaum-Bibliothek habe ich alternative Policy-Klassen, die dies tun, obwohl, um ehrlich zu sein, meine wirkliche Lösung, als das Problem auftauchte, war, den ganzen Code in einen "Junk"-Ordner zu werfen, auf der Basis, dass ich ihn selten benutze und wahrscheinlich sowieso aufdringliche Boost-Listen verwenden sollte.
Damit bleibt aber immer noch die andere, viel komplexere und viel genutzte Containerbibliothek übrig, die nicht verschwinden wird. Ich denke, ich bin nur zu tun haben, die sehr schmerzhaft Refactoring, um loszuwerden, die offsetof und Zeiger Arithmetik Zeug, aber...
Was genau sind die C++-Regeln - wann genau darf der Compiler einen möglichen Zeiger-Alias nicht erkennen? Und könnte der obige Binärbaumcode so umgeschrieben werden, dass er immer noch Zeigerarithmetik verwendet, immer noch erlaubt, dass auf die Knoten sowohl innerhalb als auch außerhalb der Bibliothek zugegriffen/geändert wird, und dennoch sicher vor diesem Optimierungsproblem ist?
