brpc之container

2019年1月20日星期天, 发表于深圳

如果你对本文有任何的建议或者疑问, 可以在这里给我提 Issues, 谢谢! :)

brpc 提供了一些容器（数据结构）用来处理业务，本文学习一下brpc的相关数据结构。

如文章有任何冒犯之处，例如侵权或者未标明引用，请邮件联系删除。
本人水平有限，如有错误之处，请不吝赐教。

1. BoundedQueue 有限队列
2. flatmap
- 2.1 flatmap操作符 operator[]实现
3. 双缓冲数据 DoublyBufferedData
4. hash_tables
5. linked_list 双向链表

1. BoundedQueue 有限队列

brpc使用了一个数组维护了一个有限队列，非线程安全；

BoundedQueue大量使用了placement new的方式，避免内存的分配和构造，看一个例子：

void elim_push(const T& item) {
    if (_count < _cap) { //内存足够
        new ((T*)_items + _mod(_start + _count, _cap)) T(item);
        ++_count;
    } else { //内存不够
        ((T*)_items)[_start] = item;
        _start = _mod(_start + 1, _cap);//防止到最前面
    }
}

内存足够，直接拷贝到最新的位置，数组位置是 (_start+_count)%_cap，否则放置到最前面，使用了取模和两个游标方式，很巧妙；

2. flatmap

flatmap是一个hashmap，官方文档说的很清楚：https://github.com/brpc/brpc/blob/master/docs/cn/flatmap.md

flatmap实现为一个模板类，可以穿入5个模板参数，看定义；

template <typename _K, typename _T,
          typename _Hash = DefaultHasher<_K>,
          typename _Equal = DefaultEqualTo<_K>,
          bool _Sparse = false>

其中 _K,_T分别是key和value的类型，_Hash，_Equal 分别是hash和比较的仿函数，_Sparse指定是否为稀疏map，如果是稀疏map，则使用bitmap对key进行管理；

2.1 flatmap操作符 operator[]实现

代码在 flat_map_ini.h 中；

template <typename _K, typename _T, typename _H, typename _E, bool _S>
_T& FlatMap<_K, _T, _H, _E, _S>::operator[](const key_type& key) {

先对key进行Hash，然后取模桶数；
判断取到的桶的第一个元素是否合法（默认创建的桶是非法的，可以使用），如果为空，则说明key无值，使用placement new创建值，并且返回；
如果桶已经有值，则判断第一个元素的hash值是否和key一致，如果是，直接返回value;
判断first element的next指针是否有值，如果没有值，放入该位置（需要判断拥塞）；
循环链表，找到一个element的next指针为空，加入进去；

3. 双缓冲数据 DoublyBufferedData

官方参考资料：https://github.com/brpc/brpc/blob/master/docs/cn/lalb.md

csdn参考文档： https://blog.csdn.net/hintonic/article/details/81475076

DoublyBufferedData 和普通的双缓冲本质上没有区别，使用两个缓冲区，一个用来给读取，一个用来写数据，_index保存读下表，bg_index保存写下表；

上面csdn中的文章介绍的说的很清楚，不赘述；不过这段代码写的有技术含量，值得学习；

4. hash_tables

兼容了windows平台和GNU实现的hash_map，允许所有平台使用 butil::hash_map和butil::hash_set，并且提供了两个组队hash（将两个int32或者int64的数hash成一个）的函数

5. linked_list 双向链表

注释中有很好的解释，使用场景及实现原理

// Q. Should I use std::list or butil::LinkedList?
//
// A. The main reason to use butil::LinkedList over std::list is
//    performance. If you don't care about the performance differences
//    then use an STL container, as it makes for better code readability.
//
//    Comparing the performance of butil::LinkedList<T> to std::list<T*>:
//
//    * Erasing an element of type T* from butil::LinkedList<T> is
//      an O(1) operation. Whereas for std::list<T*> it is O(n).
//      That is because with std::list<T*> you must obtain an
//      iterator to the T* element before you can call erase(iterator).
//
//    * Insertion operations with butil::LinkedList<T> never require
//      heap allocations.
//
// Q. How does butil::LinkedList implementation differ from std::list?
//
// A. Doubly-linked lists are made up of nodes that contain "next" and
//    "previous" pointers that reference other nodes in the list.
//
//    With butil::LinkedList<T>, the type being inserted already reserves
//    space for the "next" and "previous" pointers (butil::LinkNode<T>*).
//    Whereas with std::list<T> the type can be anything, so the implementation
//    needs to glue on the "next" and "previous" pointers using
//    some internal node type.

Q: 何时使用LinkedList，而不是std:list?
A: 关注性能的时候：

LinkedList 删除是O(1)时间复杂度，而std::list是O(n)，因为std::list在删除之前，必须先要获取到指向元素的指针；
插入操作不需要堆空间分配；

Q: linkedList和std::list 实现差别?
A: 使用双向链表实现；通过root节点串联起链表的头和尾；

illx10000