本节书摘来自华章出版社《深入理解Android》一书中的第3章，第3.4节，作者孟德国 王耀龙 周金利 黎欢，更多章节内容可以访问云栖社区“华章计算机”公众号查看
WTF作为一个基础库存在，它提供的内存管理手段与STL类似，主要是为容器和应用类提供了便捷高效的内存分配接口（当然一些内部使用的内存对齐接口也是必不可少的）。其中，OSAllocator和PageAllocation类只应用于JavaScriptCore（Safari使用的JS引擎）中，这里不做分析。本节重点分析FastAllocator，这里的FastAllocator是指封装FastMalloc得到的WTF_MAKE_FAST_ALLOCATED、FastNew/FastDelete以及FastNewArray/FastDeleteArray。
众所周知，STL中的Allocator在libc提供的malloc之上实现了一个memory pool，以此来实现高效的内存分配和回收（可参考《STL源码剖析》第2章，当然最新STL的allocator的实现跟书中的描述已有较大差别），而WTF则走了另一条路——实现一个高效的malloc。【→Wtf/FastMalloc.cpp : 3823行】
template<bool crashOnFailure> ALWAYS_INLINE void *malloc(size_t size);WTF中使用条件编译宏FORCE_SYSTEM_MALLOC来控制是否使用libc提供的malloc。在FORCE_SYSTEM_MALLOC为0时，上述自定义的malloc在fastMalloc/tryFastmalloc中被调用。该malloc本质上就是TCMalloc的再封装。TCMalloc性能远优于libc malloc，它为每个线程分配thread-local cache。对于尺寸≤32KB的内存分配请求直接从thread-local cache中分配，并且按8的整数倍尺寸分配。而对于>32KB的内存分配请求则从堆中分配，并按照4KB的整数倍分配。此外，TCMalloc还提供了垃圾回收策略。 关于TCMalloc的实现可以参考：http://goog-perftools.sourceforge.net/doc/tcmalloc.html。但Android 4.2版的WebKit没有使用TCMalloc实现的malloc，也就是说fastMalloc/tryFastmalloc最终使用的还是bionic提供的malloc函数。fastMalloc在Android平台没有实现全功能porting。【→FastAllocBase.h】
#define WTF_MAKE_FAST_ALLOCATED \ public: \ void* operator new(size_t, void* p) { return p; } \ void* operator new[](size_t, void* p) { return p; } \ \ void* operator new(size_t size) \ { \ void* p = ::WTF::fastMalloc(size); \ ::WTF::fastMallocMatchValidateMalloc(p, ::WTF::Internal::AllocTypeClassNew); \ return p; \ } \ \ void operator delete(void* p) \ { \ ::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNew); \ ::WTF::fastFree(p); \ } \ \ void* operator new[](size_t size) \ { \ void* p = ::WTF::fastMalloc(size); \ ::WTF::fastMallocMatchValidateMalloc(p, ::WTF::Internal::AllocTypeClassNewArray); \ return p; \ } \ \ void operator delete[](void* p) \ { \ ::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNewArray); \ ::WTF::fastFree(p); \ } \ private: \ typedef int ThisIsHereToForceASemicolonAfterThisMacro在WebKit代码类的声明中，经常看到上述宏。该宏为类定义了标准的operator new和operator delete以及placement new。::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNewArray);在Android 4.2平台上是一个空函数，也就是这里的operator new 直接调用fastMalloc来完成内存的分配，前面分析过fastMalloc内部其实就是直接调用malloc。由此我们也可以得出一个结论，malloc返回的内存指针在对齐性等方面满足operator new的要求。其实STL提供的部分Allocator内部也直接使用malloc分配内存。由于这里定制了类的operator new 和operator delete，因此如果在这个宏中添加log或者统计算法，可以分析声明了WTF_MAKE_FAST_ALLOCATED的类的对象的创建和销毁情况，进而辅助分析内存泄露或其他问题。
WTF提供了为数众多的容器类，比如BlockStack、 ByteArray、 FixedArray、 Deque、 Vector、 HashTable等。本节重点分析Vector和HashTable的实现及使用，以此为基础，其余几种容器的实现及使用，读者可自行分析。
Vector的实现及使用WTF中的Vector与STL中的Vector的行为基本一致，对外呈现的也是动态数组的行为。【→Vector.h】
template<typename T, size_t inlineCapacity = 0> class Vector { WTF_MAKE_FAST_ALLOCATED; private: typedef VectorBuffer<T, inlineCapacity> Buffer; typedef VectorTypeOperations<T> TypeOperations; public: typedef T ValueType； //关键点(1) typedef T* iterator; //关键点(2) typedef const T* const_iterator； explicit Vector(size_t size) : m_size(size) , m_buffer(size) { if (begin()) TypeOperations::initialize(begin(), end()); } ~Vector() { if (m_size) shrink(0); } //关键点(3) size_t size() const { return m_size; } //关键点(4) size_t capacity() const { return m_buffer.capacity();} //关键点(5) T& at(size_t i) ; //关键点(6) T& operator[](size_t i) { return at(i); } //关键点(7) iterator begin() { return data(); } //关键点(8) iterator end() { return begin() + m_size; } 关键点(9) template<typename U> size_t find(const U&) const; void shrink(size_t size); void grow(size_t size); void resize(size_t size); void reserveCapacity(size_t newCapacity); void reserveInitialCapacity(size_t initialCapacity); void shrinkCapacity(size_t newCapacity); void remove(size_t position); private: void expandCapacity(size_t newMinCapacity); const T* expandCapacity(size_t newMinCapacity, const T*); bool tryExpandCapacity(size_t newMinCapacity); const T* tryExpandCapacity(size_t newMinCapacity, const T*); template<typename U> U* expandCapacity(size_t newMinCapacity, U*); size_t m_size; Buffer m_buffer; };上面代码截取的是Vector中重要的实现函数，下面分析Vector的几个重要成员。关键点（1）（2）：由于Vector采用连续存储结构，因此这里的iterator直接使用了原生指针。关键点（3）（4）：函数size()返回的是Vector中已存储的元素数目，而capacity()返回的是Vector所使用的Buffer的容量，这个capacity随元素增删的变化，也就是 Vector内存管理的核心内容。关键点（5）（6）：为Vector提供了数组访问的行为，这也是Vector动态数组行为的关键点。关键点（7）（8）：提供了获取iterator的接口，与使用STL容器的iterator一样，Vector的iterator的begin与end是会随着对Vector的修改而变化的，比如通过iterator完成的一次遍历操作中，若伴随对Vector元素的插入或删除操作，那么每一次操作完毕都要重新获取begin或end。关键点（9）：提供的find操作是一个O(N)的顺序遍历查找操作，如果用Vector来存储大量数据，而用它提供的find操作来查找元素，并不高效。介绍Vector的主要行为后，再来看一下Vector的存储结构，本节不再仔细列举VectorBuffer和VectorTypesOperations的实现，只在宏观上说明这两个类的原理。Vector用VectorBuffer作为内部存储数据的容器，而VectorBuffer的实现是通过fastMalloc来分配内存，用placement new来初始化对象（前面讲过malloc分配的内存满足operator new分配内存的要求），这样将Vector中对象的存储空间分配与对象初始化分开。Vector中元素的初始化、复制、移动等操作由VectorTypesOperations来封装，其中成员函数的行为因数据类型的不同而不同，具体行为由VectorTraits封装的编译时类型计算信息控制。当Vector因append函数或insert函数调用而引起内存空间不足时，间接调用reserveCapacity()来重新分配内存，并释放原来使用的内存空间。当Vector通过remove函数移除掉一些元素时，只是简单析构原来的对象。整个内存原理的示意图为图3-1。图3-1中，begin指针代表begin()返回的iterator，end指针代表end()返回的iteraror。size()表示的范围为Vector中含有元素的部分，capacity表示已经分配的空间。扩展空间部分表示在insert函数或append函数等操作引起额外空间分配时，要重新分配的空间。
HashTable的实现及使用HashMap和HashSet的实现代码非常简单，几乎每一个函数都只有几行代码，原因就在于支撑它们的幕后高手是HashTable。HashTable作为HhashMap和HashSet的m_impl字段帮它们打理好了一切。【→HashTable.h】
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> class HashTable { public: typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; typedef Traits ValueTraits; typedef Key KeyType; typedef Value ValueType; iterator begin() { return makeIterator(m_table); } iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } int size() const { return m_keyCount; } int capacity() const { return m_tableSize; } pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); } iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); } bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); } void remove(const KeyType&); void remove(iterator); void clear(); private: static ValueType* allocateTable(int size); static void deallocateTable(ValueType* table, int size); void expand(); void shrink() { rehash(m_tableSize / 2); } static const int m_minTableSize = 64; static const int m_maxLoad = 2; static const int m_minLoad = 6; ValueType* m_table; int m_tableSize; int m_tableSizeMask; int m_keyCount; int m_deletedCount; #if CHECK_HASHTABLE_ITERATORS public: // All access to m_iterators should be guarded with m_mutex. mutable const_iterator* m_iterators; mutable Mutex m_mutex; #endif };一切的故事都从HashTable的创建说起：通过HashTable的构造函数可知，初创建时HashTable的内容是空的，多数字段都是简单地初始化为0。调用HashTable的add函数添加元素时，add内部通过expand函数来扩张内存空间，expand会调用fastMalloc来分配空间，分配空间的大小为：m_minTableSize = 64（此后再次需要分配空间时，分配的空间为原来空间的大小乘2），然后调用rehash函数，会在其中设置m_tableSizeMask = newTableSize–1，此处的m_tableSizeMask用在了寻址过程中，也就是lookup函数的实现中。HashTable内部有两个lookup函数，一个是有一个参数的普通成员函数：ValueType * lookup(const Key& key) {return lookupIdentifyTranslatorType>(key); } //实现(1)它内部调用了lookup的另一种模板实现：template ValueType* lookup(const T&);//实现(2)实现（1）更频繁地被类外使用，比如在HashMap的get函数就是用了实现（1）。在该应用场景下实现（2）的第二个模板参数为IdentifyTranslatorType，而HashTable的HashFunctions参数为DefaultHash::Hash，这里的KeyArg也就是HashMap的KeyArg参数。因此在lookup函数内部HashTranslator::hash(key)最终使用的是HashFunctions.h文件中定义的DefaultHash::Hash，也就是IntHash::Hash，其作用是将输入的各种宽度的key值折算成unsigned int 类型的散列值，参与寻址运算。下面截取lookup函数的关键点：
unsigned h = HashTranslator::hash(key); int i = h & sizeMask;这里的i作为table的index来存放数据，这也就是真正的寻址算法。如果这一次没有在HashMap上找到合适的位置，那么接下来的动作是调用新的hash算法：
if (k == 0){ k = 1 | doubleHash(h); i = (i + k) & sizeMask; }也就是说HashTable本质上用线性结构存储，而解决hash冲突的方法是二次hash。图3-2中，begin和end表示HashTable使用线性存储空间的起始和结束地址，capacity为存储空间的大小。在存储空间不足时，存储空间尺寸扩展为原来的两倍。
接下来分析HashTable的iterator的实现。HashTable的iterator是在调用begin或end时创建的，最本质的iterator对象是const_iterator, 而const_iterator内部也只是维持了一个指向value_type的指针而已，之所以如此是因为HashTable是线性存储的，进而iterator的自增或者自减操作也是简单的指针自增和自减操作，所以WTF的HashTable的iterator要比STL的HashMap的iterator实现简单（STL的HashMap使用数组加链表存储结构，用链表来解决hash冲突）。
相关资源：敏捷开发V1.0.pptx