InnoDB源码解析-基础数据结构
typedef FutexMutex ib_mutex_t;
UT_MUTEX_TYPE(TTASFutexMutex, GenericPolicy, FutexMutex); 这个宏定义展开是 typedef PolicyMutex<TTASFutexMutex<GenericPolicy>> FutexMutex;
PolicyMutex是个mutex框架，具体实现依赖模板参数MutexImpl。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
template<typename MutexImpl> struct PolicyMutex { typedef MutexImpl MutexType; typedef typename MutexImpl::MutexPolicy Policy; MutexImpl m_impl; // 申请互斥锁 void enter(uint32_t n_spins, uint32_t n_delay, const char *name, uint32_t line) |-- policy().enter(m_impl, name, line); |-- m_impl.entry(n_spins, n_delay, name, line); |-- policy().locked(m_impl, name, line); void exit() |-- policy().release(m_impl); |-- m_impl.exit(); }; |
TTASFutexMutex 有一个字段代表锁状态，用CAS指令实现spinlock，如果spin次数超过阈值，使用SYS_futex。
typedef int lock_word_t; lock_word_t TTASFutexMutex::m_lock_word;
双向链表 ut_list
源码位置：include/ut0lst.h
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// list node 类型 // 这里Type是业务类型，比如 buf_page_t。 template<typename Type> struct ut_list_node { Type *prev; Type *next; }; // list 类型 template<typename Type, typename NodePtr> struct ut_list_base { typedef Type elem_type; typedef NodePtr node_ptr; ulint count; elem_type *start; elem_type *end; // 内嵌到业务数据结构（如buf_page_t）里面的node对象（buf_page_t::list字段）的对象内偏移量。 node_ptr node; }; |
用于声明一个列表的宏 #define UT_LIST_BASE_NODE_T(t) ut_list_base<t, ut_list_node<t> t::*>
比如
UT_LIST_BASE_NODE_T(buf_page_t) flush_list; 展开后为
ut_list_base<buf_page_t, ut_list_node<ut_list_node> buf_page_t::*>。其中，
ut_list_node<ut_list_node> buf_page_t::*是buf_page_t的成员变量指针的类型，即buf_page_t内成员偏移量的变量类型。
node字段的初始化在UT_LIST_INIT宏中，例如 UT_LIST_INIT(buf_pool->flush_list, &buf_page_t::list)中将node初始化为buf_page_t的list字段（即ut_list_node类型字段）的对象内偏移量
基本操作接口：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
UT_LIST_ADD_FIRST(LIST, ELEM); UT_LIST_ADD_LAST(LIST, ELEM); UT_LIST_INSERT_AFTER(LIST, ELEM1, ELEM2); UT_LIST_REMOVE(LIST, ELEM); UT_LIST_GET_NEXT(NAME, N); // 返回双向链表NAME的N节点的后继 UT_LIST_GET_PREV(NAME, N); // 返回双向链表NAME的N节点的前驱 UT_LIST_REVERSE(LIST); // 逆序 UT_LIST_MOVE_TO_FRONT(LIST); ut_list_map(const List& list, Fucntor &functor); // 遍历，functor(elem_type) ut_list_exist(List &list, typename List::elem_type *elem); |
向量 ib_vector_t
ib_vector_t自带了一个内存分配器，默认是heap_allocator。
|
1 2 3 4 5 6 7 8 |
struct ib_vector_t { ib_alloc_t *allocator; // 分配器 void *data; // elemtns ulint used; // ulint total; // ulint sizeof_value; }; |
ib_alloc_t是内存分配器的抽象接口，里面定义了 申请、释放、resize三个函数指针。
|
1 2 3 4 5 6 |
struct ib_alloc_t { ib_mem_alloc_t mem_malloc; ib_mem_free_t mem_release; ib_mem_resize_t mem_resize; void *arg; }; |
具体的子类有heap_alloc/sync_heap/self_heap等等。
以heap_alloc为例：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
heap_alloc->arg = heap; // mem_heap_t* heap_alloc->mem_malloc = ib_heap_malloc; heap_alloc->mem_release = ib_heap_free; heap_alloc->mem_resize = ib_heap_resize; 其中, mem_heap_t 定义： typedef mem_block_t mem_heap_t; typedef struct mem_block_info_t mem_block_t; void* ib_heap_malloc(ib_alloc_t *allocator /* 底层分配器*/, ulint size) { mem_heap_t *heap = (mem_heap_t*) allocator->arg; return mem_heap_alloc(heap, size); // 略 } |
回到ib_vector_t的相关函数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
ib_vector* ib_vector_create(ib_alloc_t *allocator, ulint sizeof_value, ulint size) |-- ib_vector_t *vec; |-- vec = (ib_vector_t*)allocator->mem_alloc(allocator, sizeof(*vec)); |-- vec->used = 0; |-- vec->total = size; |-- vec->data = (void*)allocator->mem_alloc(allocator, sizeof_value * size); ib_vector_push(ib_vector_t *vec, const void* elem) |-- if (vec->used >= vec->total) |---|-- ib_vector_resize(vec); |---|---|-- new_total = vec->total * 2; |---|---|-- vec->data = vec->allocator->mem_resize(vec->allocator, vec->data, old_size, new_size); |-- last = vec->data + IB_VEC_OFFSET(vec, vec->used); |-- memcpy(last, elem, vec->sizeof_value); |-- vec->used++; |
工作队列 ib_wqueue_t
ib_wqueue_t 是一个支持并发访问的阻塞队列。
|
1 2 3 4 5 6 |
struct ib_wqueue_t { ib_mutex_t mutex; // 线程安全 ib_list_t *items; // 链表 os_event_t event; // 条件变量 }; |
哈希表 hash_table_t
|
1 2 3 4 |
typedef struct hash_table_struct { ib_ulint_t n_cells; hash_cell_t *array; } hash_table_t; |
哈希表，冲突串链，hash_cell_t 即桶对象。
以HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA) 的一个具体操作例子，HASH_INSERT(buf_page_t, hash, buf_pool->page_hash, b->id.fold(), b); 参数各字段含义是：
|
1 2 3 4 5 |
TYPE = buf_pool_t NAME = hash 即buf_pool_t::hash字段，是用于hash冲突串链的next字段。 TABLE = buf_pool->page_hash hashtable对象本身。 FOLD = b->id.fold() 计算hash值 DATA = b 要插入的对象 |
注：看实现代码，HASH_SEARCH是先根据哈希值找到桶，然后在桶内查找。