Google之Chromium浏览器源码学习——base公共通用库(三)

　　本节将介绍base公共通用库中的containers，其包含堆栈、列表、集合、以及Most Recently Used cache(最近使用缓存模板)。

　　linked_list.h：一个简单的列表类型，通过模板实现，内部采用双链表的形式，有区别于c++标准模板库的std::list<T*>,它的使用方式为：base::LinkedList<T>;

　　相对std::list<T*>，其优点有：

　　1. 删除一个元素，操作复杂度为O(1),而std::list<T*>为O(n)，因其内部需要获取一个T*的元素的迭代器；

　　2. 插入一个元素不需要堆分配器。

　　该模板链表其内置节点：base::LinkNode<T>；链表:base::LinkedList<T>

　　节点示例：

　　class MyNodeType : public base::LinkNode<MyNodeType>

　　{

　　};

　　创建链表实例示例：LinkedList<MyNodeType> list;

　　具体使用示例：

 class Node : public LinkNode<Node>
 {
  public:

   explicit Node(int id) : id_(id) {}

   int id() const { return id_; }

  private:

   int id_;
 };

　　

 LinkedList<Node> list;
 Node n1();
 Node n2();
 Node n3();
 Node n4();
 Node n5();
 list.Append(&n1);
 list.Append(&n2);
 list.Append(&n3);
 list.Append(&n4);
 list.Append(&n5);

 n3.RemoveFromList();

 list.Append(&n3);
 n3.InsertBefore(&n2);
 n4.InsertAfter(&n1);

 for (const LinkNode<Node>* node = list.head(); node != list.end(); node = node->next() )
  {
        printf("id = %d," ,node->value()->id() );
   }

 for (const LinkNode<Node>* node = list.tail(); node != list.end(); node = node->previous() )
  {
        printf("id = %d," ,node->value()->id() );
   }

　　以上代码包含，节点自定义类型、链表对象定义、创建，节点追加、节点移除、节点再追加、节点插入、移动、前向遍历、后向遍历；
　　执行到第12行时，链表内容为：1,2,3,4,5；执行13行后：1,2,4,5；执行15行后：1,2,4,5,3；执行16行后：1,3,2,4,5（暂不执行该行）；执行17行后：1,4,3,2,5；

　　前向遍历：id = 1,id = 4,id = 3,id = 2,id = 5;后向遍历：id = 5,id = 2,id = 3,id = 4,id = 1.；

　　似乎实际上与预计结果不一致，请注意：第15行、16行其实会引入BUG，导致遍历产生无限循环，使用时避免出现相同元素地址被写入链表以及注意节点生存期的情况；

　　总结链表：

　　节点LinkNode<T>含LinkNode<T>* previous_和LinkNode<T>* next_指针成员，分别保存指向当前元素的前一个和后一个元素地址，base::LinkedList<T>中含成员LinkNode<T> root_，为整个链表的根节点，也作为遍历中最后一个节点的指示灯；维护链表，并采用后向插值的方式追加元素至链表。

　　基本上实现比较简单，相对std::list更快速且基于元素地址，但也可能因不谨慎的操作引入上面的BUG。

　　stack_container.h：分配器StackAllocator，采用继承于std::allocator<T>；其内部维护一个原始申请堆缓冲区对象StackAllocator::Source，用以为分配器备份存储内容，减少再次在堆中申请或其他操作，其他采用该分配器可以共享同一存储空间；可以看出StackAllocator::Source采用base::AlignedMemory分配对齐的原始堆栈缓冲区stack_buffer_以及一个保存当前缓冲区是否被使用的标识used_stack_buffer_；

　　分配器StackAllocator，内部含可重新指定类型的rebind；可共享存储缓冲区的复制构造函数；显式的构造函数；申请空间的allocate，当Source未被其他使用时，可直接分配该缓冲区，否则则直接通过std::allocator<T>::allocate为其分配，同样的deallocate，当Source为被释放的缓冲区时，直接释放（实际上只是简单的used_stack_buffer_ = false），否则认为是通过std::allocator<T>::allocate为其分配的，则通过std::allocator<T>::deallocate，释放该缓冲区；注意：StackAllocator在使用的时候模板参数int stack_capacity应至少大于或等于元素的大小，否则可能出现溢出。

　　StackContainer堆模板容器，其主要为对vertor的作包装的，内部包含Allocator和该模板对象的成员，使得模板对象使用Allocator分配的缓冲区；内部重载了operator->()，container函数分别获取对象的指针地址和对象的引用地址；此外对其禁止了赋值构造和复制拷贝；注意：模板对象应必须支持reserve操作。

　　StackString和StackString16：均继承于StackContainer，实际上就是对basic_string的模板特化，只是不再使用std::basic_string内置的分配器，而是使用StackAllocator；StackString针对char，StackString16针对宽字节(wchar_t)；可以认为StackString<stack_capacity>约等价于StackVector<char, stack_capacity>;StackString16<stack_capacity>约等价于StackVector<w_chart, stack_capacity>。

　　StackVector：继承于StackContainer，对std::vector的模板特化，但支持默认构造、赋值构造、复制拷贝，（实际上不可以支持赋值构造、复制拷贝，但是使用了std::vector的assign），内部重载了T& operator[]，operator=。

　　使用示例：

　　

 StackVector<wchar_t, > text;
 text->push_back(L'A');

 StackVector<double, > doubles;
 doubles->push_back(1.0);

 const int stack_size = ;
 StackVector<int, stack_size> vect;
 vect.container().push_back();
 vect.container().push_back();
 vect.container().push_back();

 vect.container()[];
 vect.container().resize(stack_size);
 vect.container().reserve(stack_size * );

 //    支持赋值构造共享同一个内部缓冲区
 std::vector<int, StackAllocator<int, stack_size> > other(vect.container());

　　总结堆栈容器：

　　因实际上内部使用堆栈作为缓冲区，第一次使用时将采用内部堆栈缓冲区，但使用时务必小心作为参数的空间大小应合适，已避免堆栈空间不够；

　　small_map.h：一个类似于STL的关联容器，开始时通过一个简单的数组实现，当超过其指定大小时将切换到其他容器类型；有区别于c++标准模板库std::map

　  std::map：一般使用红黑树作为底层结构，将产生很多的代码，此外对于int或string将产生副本，对每个元素将会产生堆分配。

　　事实上，对于选择保持一对元素且为简单使用，可以考虑使用vector且蛮力搜索将会更有效的话，毕竟将产生更少的堆分配和快速的查找而不是使用std::map;

　　base:hash_map：查找复杂度为O(1)，内部哈希表将会产生更多的空间资源，并且也将会容易地写出看似正确的代码对于默认的哈希函数，SmallMap的方式：当实例小的时候，将采用vector的蛮力搜索(不会产生额外的堆分配器)，比较高效，且节省空间资源；但是当追加更多的数据项元素的时候，产生的代码将会变得比std::map更多(对于操作符[]至少160字节)，很多时候可以考虑可选择其他的方式而不是base:hash_map。

　　SmallMap：从底层的map映射类型获取比较器，微软版本的std::map仅支持less <操作符；SmallMap提供了默认重载通用映射类型以避免双重比较，故需要自己提供operator<和自己的版本的operator==，示例：base::SmallMap<std::map<MyKey, MyValue>, 4, std::equal_to<KyKey> >，以下分别对内部细节说明。

　　SmallMapDefaultInit：映射默认初始化模板类，重载了operator(),参数为ManualConstructor手动构造器指针对象，主要对该对象的初始化Init，事实上是对内部堆栈的placement new，反复使用一块较大的分配成功的内存来构造不同类型的对象；只为为内部使用的，作为SmallMap的映射初始化参数。

　　has_key_equal：是否有键值比较M::key_equal，内部通过两个静态的重载test函数，一个返回char，一个返回char[2]，共同来测试是否调用相应的函数确定M::key_equal的存在，(sizeof(test<M>(0)) == sizeof(big))在编译时确定，若存在，则has_key_equal<M>::value为true，否则为false，为smallmap内部的select_equal_key的元功能使用。

　　select_equal_key：比较模板，重载operator(),该模板针对有M:key_cmpare比较函数的版本，内部是一个严格的弱序列比较器；此外还有特化版本，模板参数std::map和base::hash_map，并重载operator(),内部采用模板参数类型提供的operator==比较器；

　　再谈SmallMap：template <typename NormalMap,
          　　　　　　　　　　　　int kArraySize = 4,
          　　　　　　　　　　　　typename EqualKey = typename internal::select_equal_key<NormalMap,internal::has_key_equal<NormalMap>::value>::equal_key,
          　　　　　　　　　　　　typename MapInit = internal::SmallMapDefaultInit<NormalMap> >
　　　　　　　　　　class SmallMap{}；

　　可以看到，NormalMap为模板映射参数，可以提供自己的或是std::map,base::hash_map的基础容器，kArraySize为初始化array数组大小而不是分配堆，不过当超过kArraySize时，则会使用map类型的；EqualKey则为以上提到的比较器，MapInit为映射容器初始化方式（内部采用ManualConstructor手动构造器，其内部也是采用对齐的堆数组作为缓冲区）；参数kArraySize不可为负数；

　　内部函数比较多：

　　1.默认构造函数SmallMap()提供默认的MapInit模板参数的初始化方式，显式的构造函数explicit SmallMap(const MapInit& functor)，则采用functor的初始化方式；

　　2.支持拷贝构造函数和复制分配函数，内部采用辅助函数InitFrom和Destroy实现初始化和销毁，里面有个小细节array_，很可能出现数组溢出的情形；

　　3.内置迭代器和常迭代器支持以及对各迭代器内部实现（前置++，后置++，前置--和后置--，operator->，operator*，operator==，operator!=），find查找、operator[]，insert和支持迭代器的insert插入，clear清空，erase和迭代器erase删除，count查找计数(实际上只为0或1)，size容器内容大小，empty是否为空，UsingFullMap是否可使用底层映射表示，map返回原始手动构造器容器对象。

　　部分接口使用示例：

　　

 SmallMap<hash_map<int, int> > m;
 m[] = ;
 m[] = ;

 SmallMap<hash_map<int, int> >::iterator iter(m.begin());
 const SmallMap<hash_map<int, int> >& ref = m;
 bool res = ref.find() != m.end();

 SmallMap<hash_map<std::string, int> > ms;
 ms["monday"] = ;
 ms["tuesday"] = ;
 ms["wednesday"] = ;

 SmallMap<std::map<int, int>, , std::equal_to<int> > mmap;
 mmap[] = ;
 mmap[] = ;

 SmallMap<std::map<int, int>, , std::equal_to<int> >::iterator iter(
       mmap.begin());

　　mru_cache.h:最近使用缓冲区模板,允许通过一个键值在常数时间内访问一个元素项，并且容易识别将要删除的最近最少使用元素项，每个键每次只能关联一个有效载荷项；另外因键对象可能被多次保存，因此应提供比较高效的拷贝操作；所有操作复杂度均O(1)，内部实现便于阅读但不是最高效的，以下将详细介绍内部结构。

　　MRUCacheStandardMap：内部重声明了一个标准std::map类型的模板，主要用在MRUCacheBase，仅仅作为标准化映射类型容器；

　　MRUCacheBase：作为MRU缓存基类，template <class KeyType, class PayloadType, class DeletorType, template <typename, typename> class MapType = MRUCacheStandardMap>

　　　　　　　　　　　　　　　　　　　　class MRUCacheBase；

　　首先说说数据成员：ordering_：类型为std::list<std::pair<KeyType, PayloadType> >，一个以键类型和负载类型为键值对作为模板参数类型的列表容器(PayloadList)对象；index_：类型为std::map<KeyType,PayloadList::iterator>，一个以键类型和PayloadList迭代器类型为模板参数的map映射对象；max_size_：列表容器数据长度，指定当到达某个最大数量时将删除自己的元素项；deletor_：一种销毁器对象，由模板提供销毁参数类型，从内部实现看出该销毁器需要提供operator()实现；注意内部有个参数NO_AUTO_EVICT，当以NO_AUTO_EVICT作为容器构造函数的参数时，即max_size_ = NO_AUTO_EVICT时，为不限制缓冲区大小，这样在后面的Put操作时，不被控制容器最大长度的限制，避免后面的ShrinkToSize的操作。

　　成员函数：

　　1. 不支持拷贝赋值和复制分配操作；

　　2. 提供了显式的参数为列表最大数据容器长度的构造函数和以列表最大容器长度与销毁器为参数的构造函数；

　　3. 提供max_size：返回最大列表容器长度；Put插入以给予的键值的载荷项并返回该项的迭代器，若已存在该键值，则从早期的数据项中删除该键值项（类似于插入删除的操作），若不存在，若新的项插入大于最大数时则删除最旧的（实际上从尾部删除）（新项于列表前插入，此外也插入了键值和列表迭代器的首部 -> 这样做目标是每次删除列表前的数据和列表尾部最旧的数据；

　　4. 提供Get操作：获取指定的key的内容(荷载)，若获取失败返回end()，成功则调整内部列表将找到的key移动到列表表首并返回该key的内容迭代器，调整列表使用了list的splice方法，可能该方法会有效率问题(以不同的STL实现版本不同)；Peek操作同Get，但内部不对列表排序移动操作；

　　5. 提供Earse操作：参数为荷载迭代器对象，使用提供的销毁器对象deletor_销毁，此外销毁key与荷载map映射，key与荷载迭代器对象；此外也提供了Erase的反向销毁操作版本；

　　6. ShrinkToSize：提供删除至指定new_size的大小容器的操作，以保持容量为new_size；内部采用反向迭代器Earse版本删除操作；当new_size大于当前勇气容量，则什么也不操作；。

　　7. Clear：清空Cache操作；empty：是否为空；

　　8. 提供了begin,end,rbegin,rend迭代器操作(返回迭代器对荷载列表的对象)。

　　以上为MRUCacheBase相关实现，下面针对其周遭设施、继承类、特化类分别说明；

　　MRUCacheNullDeletor：MRUCache的销毁器默认模板参数，其内部重载operator(PayloadType& payload),但未做任何实现操作。　

　　MRUCache：继承于MRUCacheBase，作为一般操作的容器；内部提供一显式的构造函数，参数max_size指定列表数据容器长度；此外不允许赋值构造和复制拷贝。

　　MRUCachePointerDeletor：同MRUCacheNullDeletor，作为OwningMRUCache的销毁器，内部做了delete payload操作，删除荷载指针对象；

　　OwningMRUCache：继承于MRUCacheBase，销毁器模板参数MRUCachePointerDeletor；这种缓冲区容器，主要是容纳非常量指针类型的荷载对象，以允许被移除、替代、销毁时刻被删除。其他同MRUCache。

　　以上两种cache的容器类型均使用的是MapType = MRUCacheStandardMap，作为模板参数（实际上为std::map），下面将要提到的HashingMRUCache容器，将采用google自己实现的base::hash_map作为容器模板参数MRUCacheHashMap（实际上base::hash_map只是针对不同平台微软和GNU等不同版本的封装，已支持跨平台）；

　　HashingMRUCache：同前两个容器显式的构造函数以及不被允许的复制拷贝和赋值构造，唯一不同的就是最后一个模板参数为base::hash_map作为基础映射容器。