内嵌变长数据结构范例——trbstrmap<mapped>

  

以前的这篇文章介绍了嵌入的变长数据结构（embeded）

 

本文介绍一个使用这种思想实现的通用strmap容器，相当于：

std::map<std::string, Mapped>。

 

实现上使用了我以前写的线索红黑树——相比标准map的实现，节省了一半的结点存储开销，而平均查找时间只付出很小的额外开销，并且没有代码膨胀问题。

 

使用

大多数情况下

trbstrmap<MappedType[, Compare]> // Compare是可选的，allocator 总在类范围，可以修改:

trbstrmap<MappedType[, Compare]>::s_vtab.alloc = ....;

 

为了节省空间，trbstrmap使用一个字节存储strkey_length，因此，strlen(strkey)不可超过255，允许长度为0的key。最大长度255基本上可以应对绝大多数情况。

把key作为变长字段，有一个原因很重要：key一旦插入，就不可改变！因此，整个结点的memblock也就不需要重新分配，可以修改的只有mapped_data。

作为一个比较：如果把key作为一个固定长度的结构，而mapped_data作为变长内嵌数据，当需要修改mapped_data时，就需要重新分配该结点，还需要修改该结点的父节点指向该结点的指针，并且，会破坏“node容器的iterator只有在删除该node以后才失效”的语义！

一旦用在多线程环境中，问题就会变得很复杂，因为修改了父节点。就不能仅lock需要修改数据的那个结点，而是需要lock整个tree，使用数据库的术语，就是一下子从记录锁变成了表锁，本来按key查找时，因为key没改变，就不需要加锁，而这样搞，查找时就需要对整个表加锁，严重影响并发性！

注意事项：

1.         trbstrmap::iterator::value_type 和trbstrmap::value_type都是 mapped_type/Value，*iter也是mapped_type；而不是std::map的pair<Key,Value>。

2.         trbstrmap::key(iter)获得iter对应的key

3.         trbstrmap::klen(iter)获得key_length，当然，strlen(trbstrmap::key(iter))也可以获得key_length，但需要一些时间开销；另外，当key_content中存在\0时，klen就是不可缺少的了（后面将详细介绍这种情况）

4.         再次强调，key_cstr_length最大长度不可超过255，但这个长度不包括末尾的 \0

 

示例代码：

         typedef febird::trbstrmap<int, &trb_compare_tev_inline_cstr_nocase> smap_t;

         smap_t smap, smap2;

 

         smap["1"] = 0;

         smap["2"] = 1;

         smap["3"] = 1;

         smap["4"] = 2;

         smap["1"]++;

         smap["4"] += 2;

         smap.insert("5", 5);

         assert(!smap.insert("5", 6).second);

         // str长度不可超过255

         smap["aabbccddeeffgghhiijjkk====================================="] = 10;

 

         for (typename SMT::iterator i = smap.begin(); i != smap.end(); ++i)

         {

                   printf("smap[%s]=%d, klen=%d\n", smap_t::key(i), *i, smap_t::klen(i));

         }

 

 

在简单的情况下，使用trbstrmap,比std::map可以节省50%~70%的内存。使用的方便程度，基本上没差别。

 

数据结构

Mapped Data 是模板参数，可以是任意struct/class，当然也可以内嵌指针，也可以是复杂对象，没有任何限制。

 

 

复杂情形：任意字符串，字符串中可以包含\0

trbstrmap允许加入内容中存在\0的字符串，这种应用比较罕见，但是仍然允许，只是必须遵循以下注意事项：

1.         在这种情况下，需要传入key_content_length参数：
trbstrmap.probe(key,key_content_length)
trbstrmap.insert(key,key_content_length, val)
key_content_length是整个key_content长度，包括末尾的\0——如果有的话

2.         或者，传入std::string ：
trbstrmap[std::string(…)] = val;
equal to: trbstrmap.probe(s.c_str(), s.size()+1) = val;

3.         trbstrmap.insert(key, klen, val)

4.         这种情况下，应用一般需要传入一个自定义的Compare

5.         trbstrmap::klen(iter)在任何情况下，返回的都是key_content_length – 1，
而不管末尾有没有\0

6.         自定义函数需要获取key_content_length时，应该如下：

int

trb_compare_custom ( const struct trb_vtab* TRB_restrict vtab,

                                          const struct trb_tree* TRB_restrict tree,

                                          const void* TRB_restrict x,

                                          const void* TRB_restrict y)

{

     size_t lx = ((unsigned char*)x)[-1] + 1;

     size_t ly = ((unsigned char*)y)[-1] + 1;

int ret = memcmp(x, y, lx<ly?lx:ly); // 仅示例，不一定非用memcmp

     return 0 == ret ? lx – ly : ret;

}

7.         当给trbstrmap::find/lower_bound/equal_range多传入一个key_content_length时，这些函数会将key和key_content_length打包（这些都在库内部完成），应用须知这会有稍微多一些的开销。

必须这么做，因为compare函数需要找到key_content_length，除此之外，别无他法。

8.         貌似很复杂，但始终坚持剃刀原理：在绝大多数情况下，也就是字符串是cstr，末尾包含\0时，函数的行为符合传统惯例并且高效；在罕见情况下也可用，只是效率有一点下降，使用难度也大一些。

9.         当情况复杂时，记住：只要你明确传入了长度，这个长度就是你真实数据的长度

 

代码：http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/trb_cxx.h

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/trb_cxx.cpp

测试代码：

http://code.google.com/p/febird/source/browse/trunk/febird/vcproj/test_trb/test_trb_cxx.cpp