我的github：codetoys，所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。
这些代码大部分以Linux为目标但部分代码是纯C++的，可以在任何平台上使用。
接上文。
目录
四、树的模板定义
相当晦涩的定义：
template<typename T_DATA, int PI_N, typename T_USER_HEAD = CDemoData, int PART = 0, int VER = 0, typename T_COMP = less<T_DATA>, typename T_HANDLE = T_HANDLE_SET<T_DATA , PI_N > >
class T_SHMSET_NO_MUTEX : public IShmActiveObject
{
public:
typedef T_HANDLE T_ARRAY_HANDLE;
typedef T_TREE_NODE<T_DATA, PI_N, T_HANDLE, T_COMP > TREE_NODE;
。。。。。。先继续往下看吧。
五、定义迭代器
之前我们已经把HANDLE伪装成了迭代器（也不能说“伪装”，既然符合了迭代器概念，那么它就是迭代器）。
每种容器的迭代器其实都是自定义的，从容器节点的指针到客户数据结构的指针通常都需要做计算。
struct iterator
{
T_SHM_SIZE handle;
iterator() :handle(-1) {}
bool operator == (iterator const & tmp)const { return handle == tmp.handle; }
bool operator != (iterator const & tmp)const { return !(*this == tmp); }
T_DATA & operator * ()const
{
return TREE_NODE::at(handle).data;
}
T_DATA * operator -> ()const
{
return &(operator *());
}
iterator & operator ++ ()
{
if (-1 != TREE_NODE::at(handle).hRight)
{//存在右子树，取右子树的begin
handle = TREE_NODE::at(handle).hRight;
handle = TREE_NODE::at(handle)._begin();
}
else if (-1 != TREE_NODE::at(handle).hParent)
{//存在父节点
if (TREE_NODE::at(handle).isRight())
{//是父节点的右子树，向上找到是左子树的节点，取这个节点的父节点
while ((handle = TREE_NODE::at(handle).hParent) != -1 && TREE_NODE::at(handle).isRight()) {}
if (-1 != handle && !TREE_NODE::at(handle).isRight())handle = TREE_NODE::at(handle).hParent;
}
else
{//是父节点的左子树，取父节点
handle = TREE_NODE::at(handle).hParent;
}
}
else
{//根节点且没有右子树，结束
handle = -1;
}
return *this;
}
iterator & operator -- ()
{
if (-1 != TREE_NODE::at(handle).hLeft)
{//存在左子树，取左子树的end
handle = TREE_NODE::at(handle).hLeft;
handle = TREE_NODE::at(handle)._end();
}
else if (-1 != TREE_NODE::at(handle).hParent)
{//存在父节点
if (TREE_NODE::at(handle).isLeft())
{//是父节点的左子树，向上找到是右子树的节点，取这个节点的父节点
while ((handle = TREE_NODE::at(handle).hParent) != -1 && TREE_NODE::at(handle).isLeft()) {}
if (-1 != handle && !TREE_NODE::at(handle).isLeft())handle = TREE_NODE::at(handle).hParent;
}
else
{//是父节点的右子树，取父节点
handle = TREE_NODE::at(handle).hParent;
}
}
else
{//根节点且没有右子树，结束
handle = -1;
}
return *this;
}
};
typedef iterator const_iterator;
这个迭代器应该是个双向迭代器，支持向前和向后，但是不支持加减。
最核心的复杂度是通过索引找到地址，最终是前面介绍的数组通过句柄获得地址的技术。
六、定义树的头结构
树的核心就是头结构和节点结构。
struct TREE_HEAD
{
T_SHM_SIZE hHead;
T_SHM_SIZE size;
//int deep;
//add
T_SHM_SIZE free_head;//空闲地址头指针
T_USER_HEAD user_head;//用户的特殊数据
TREE_HEAD() :hHead(-1), size(0), free_head(-1) {}
//用于输出数据的场合
string & toString(string & str)const
{
char buf[2048];
sprintf(buf, "head %ld size %ld", hHead, size);
return str;
}
//用于表格输出
static bool AddTableColumns(CHtmlDoc::CHtmlTable2 & table)
{
return false;
}
bool AddTableData(CHtmlDoc::CHtmlTable2 & table)const
{
return false;
}
};
其实复杂度都在树节点里面。
七、树的内部实现
树里面直接包含一个数组，其实我很想用继承的，但是写的时候发现很难写。
typedef T_ARRAY<TREE_NODE, PI_N, TREE_HEAD, PART, T_HANDLE > T_SETARRAY;
T_SETARRAY m_array;//内置数组对象，存储实际数据
TREE_HEAD * tree_head;//指向树的头
//insert时如果已经存在保存被覆盖的数据
bool m_OldValueSeted;
T_DATA m_OldValue;
用包含反而清晰很多。
按照set的规则，插入时会直接覆盖旧数据，没有办法在插入的同时获得旧数据。由于这是共享内存，先检索后插入并不能保证一致性（互斥层不提供这么大范围的保护），所以这里在私有内存保存了被覆盖的值（注意是私有内存啊，进程和进程不干扰）。
八、检查树结构
靠人眼看是不行的，得写代码来检查结构：
bool _check_handle(T_SHM_SIZE h)const
{
return h >= -1 && h < m_array.GetHead()->size;
}
//检查数据结构是否正确
bool _check()const
{
thelog << "检查树结构，如果检查过程中发生数据修改则检查可能会出错" << endi;
{
size_t count_data_array = 0;//数组中的有效数据个数
T_SHM_SIZE h;
for (h = 0; h < static_cast<T_SHM_SIZE>(m_array.size()); ++h)
{
if (!TREE_NODE::at(h).deleted)++count_data_array;
}
thelog << "数组容量 " << m_array.capacity() << " 个数 " << m_array.size() << " 有效数据 " << count_data_array << endi;
thelog << "树结构容量 " << capacity() << " 个数 " << size() << endi;
if (count_data_array != size())
{
thelog << "树结构大小与数组统计不符 " << size() << " " << count_data_array << ende;
return false;
}
}
long max_handle = m_array.GetHead()->size - 1;//整个已分配空间的最大句柄
size_t count_free = 0;//未用节点数（删除的）
//获取自由节点数
{
if (!_check_handle(tree_head->free_head))
{
thelog << "free_head error " << tree_head->free_head << ende;
return false;
}
T_SHM_SIZE h = tree_head->free_head;
while (h >= 0)
{
if (!TREE_NODE::at(h).deleted)
{
thelog << "此节点未被标记为删除 " << h << ende;
return false;
}
++count_free;
if (TREE_NODE::at(h).hParent<-1 || TREE_NODE::at(h).hParent>max_handle)
{
thelog << "TREE_NODE::at(h).hParent error " << TREE_NODE::at(h).hParent << ende;
return false;
}
h = TREE_NODE::at(h).hParent;
}
}
if (count_free != m_array.size() - size())
{
thelog << "删除链表总数不正确 " << count_free << " " << m_array.size() - size() << ende;
return false;
}
thelog << "删除链表节点总数 " << count_free << endi;
size_t count_used = 0;//已用节点数
//获取已用节点数
{
T_COMP comp;
iterator it = begin();
iterator it_old = end();
while (it != end())
{
if (!_check_handle(it.handle))
{
thelog << "无效的节点 " << it.handle << ende;
return false;
}
if (TREE_NODE::at(it.handle).deleted)
{
thelog << "此节点被标记为删除 " << it.handle << ende;
return false;
}
if (it_old == it)
{
thelog << "指针循环 [" << it_old.handle << "][" << it.handle << "]" << ende;
return false;
}
if (it_old != end() && !comp(*it_old, *it))
{
string str1, str2;
thelog << "节点数据比较错误 [" << it_old->toString(str1) << "][" << it->toString(str2) << "]" << ende;
}
++count_used;
it_old = it;
++it;
}
}
if (count_used != static_cast<size_t>(tree_head->size))
{
thelog << "begin->end ！= size " << count_used << " " << tree_head->size << ende;
return false;
}
if (count_used != size())
{
thelog << "遍历获得节点数不正确 " << count_used << " " << size() << ende;
return false;
}
thelog << "检查完成，没有错误" << endi;
return true;
}
程序运行过程中发生异常，谁也不知道数据怎么样了，几十G的数据，也不能随随便便就扔了，所以得想办法修复。（用的是小型机，内存比较多）
九、算法
算法就是硬写了，以前用的是平衡二叉树，后来我打算换成红黑树，红黑树写好了，还没替换。
十、快速重建
由于数据量很大，完全遵循树的规则来构建是很缓慢的。如果节点数据正常，仅仅是树结构损坏，可以先对数据排序，然后根据树的规则设置节点，从而快速完成树结构的重建。
（这里是结束）
