|
1. 动态数组概述
动态数组涉及的文件是innodb存储引擎的三个文件：dyn0dyn.h、dyn0dyn.ic以及dyn0dyn.c。
这是一个基本的组件功能，是作为一个动态的虚拟线性数组。数组的基本元素是byte。动态数组dyn主要用来存放mtr的锁定信息以及log。Dyn在实现上，如果block需要分裂节点，则会使用一个内存堆。每个blok块存储数据的数据字段的长度是固定的(默认值是512)，但是不一定会完全用完。假设需要存储的数据项的尺寸大于数据块时，该数据项被分拆，这种情况主要用于log的缓冲。
2. 数据结构
|
typedef struct dyn_block_struct dyn_block_t;
typedef dyn_block_t dyn_array_t;
#define DYN_ARRAY_DATA_SIZE 512
struct dyn_block_struct{
mem_heap_t* heap;
ulint used;
byte data[DYN_ARRAY_DATA_SIZE];
UT_LIST_BASE_NODE_T(dyn_block_t) base;
UT_LIST_NODE_T(dyn_block_t) list;
#ifdef UNIV_DEBUG
ulint buf_end;
ulint magic_n;
#endif
};
//下面两个是公共宏定义，见ut0lst.h
#define UT_LIST_BASE_NODE_T(TYPE)\
struct {\
ulint count; /* count of nodes in list */\
TYPE * start; /* pointer to list start, NULL if empty */\
TYPE * end; /* pointer to list end, NULL if empty */\
}\
#define UT_LIST_NODE_T(TYPE)\
struct {\
TYPE * prev; /* pointer to the previous node,\
NULL if start of list */\
TYPE * next; /* pointer to next node, NULL if end of list */\
}\ |
字段解释：
1) heap
从字面上理解，heap是内存堆的意思。从上面的结构体中，我们可以看出，dyn_array_t就是dyn_block_struct。这个结构体里面的字段date用来存放数据，used显示已经使用的字节数量，假设这时候还要存储一个大小为长度为x的数据，这时候data里面已经存储不了，所以就需要再分配一个新的block节点。那么分配结构所需要的内存从哪里来了，就从第一个节点里面的heap里面分配。
这里面，我们还需要主意一点。虽然数据结构用的是同一个dyn_block_struct，但是我们称第一个节点为arr，表明这个是动态数据的头节点。其它的节点，我们称为block节点。
我们这里面先来看看，刚开始创立dyn的函数是怎么实现的：
|
UNIV_INLINE
dyn_array_t*
dyn_array_create(
/*=============*/
/* out: initialized dyn array */
dyn_array_t* arr) /* in: pointer to a memory buffer of
size sizeof(dyn_array_t) */
{
ut_ad(arr);
ut_ad(DYN_ARRAY_DATA_SIZE < DYN_BLOCK_FULL_FLAG);
arr->heap = NULL;
arr->used = 0;
#ifdef UNIV_DEBUG
arr->buf_end = 0;
arr->magic_n = DYN_BLOCK_MAGIC_N;
#endif
return(arr);
}
|
其中的ud_ad是属于红判断，相当于assert。这个我们暂时不表。这个函数是在mtr创建的时候来调用的，在调用的时候已经分配了arr指针。
在dyn_array_create函数中，系统将heap字段设置为NULL，Used设置为0。Buf_end和magic_n是调试的时候使用的，每个结构体定义都会唯一的对应一个magic_n值。这样在调试的时候，就可以快速进行问题的跟踪。
下面一个问题是，既然heap在起初的设置为NULL，那么什么时候分配给它值?是第一次分配block成员的时候?还是每次分配block成员的时候?
我们这里暂不分析如何插入，我们先看看，当dyn数组已经数据不够用的时候，我们怎么给这个arr增加一个新的block。代码如下：
|
dyn_block_t*
dyn_array_add_block(
/*================*/
/* out: created block */
dyn_array_t* arr) /* in: dyn array */
{
mem_heap_t* heap;
dyn_block_t* block;
ut_ad(arr);
ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N);
if (arr->heap == NULL) {
UT_LIST_INIT(arr->base);
UT_LIST_ADD_FIRST(list, arr->base, arr);
arr->heap = mem_heap_create(sizeof(dyn_block_t));
}
block = dyn_array_get_last_block(arr);
block->used = block->used | DYN_BLOCK_FULL_FLAG;
heap = arr->heap;
block = mem_heap_alloc(heap, sizeof(dyn_block_t));
block->used = 0;
UT_LIST_ADD_LAST(list, arr->base, block);
return(block);
} |
代码中，我们可以看出，第一次增加block的时候，因为“arr->heap == NULL”条件为真，就会创建一个heap堆，在以后的再增加block时，就会使用的该堆直接分配。所以，我们可以得知，对于dyn动态数组，只有首节点的heap才是有效的。
好，那我们通过图形来看下，增加新节点之后的图形变化。
图1表示的是只有一个节点时的情况，当节点分裂时的变化，见图2。
通过图2，并集合前面的代码，我们可以发现，从第一个节点，变为两个节点的时候，首节点先把自己挂到base链表中，并分配一个新的节点，挂在base的最后一个节点。链表中的节点通过list进行互连。同样，如果还需要再增加一个节点，那么就在base链表的结尾再增加一个。因为是新增节点，所以设置该节点的used值为0。
我们在关注一下这一行代码：
block->used = block->used | DYN_BLOCK_FULL_FLAG;
从这一行代码，我们可以猜想一下该行代码的含义：
a) FULL表明该节点已经完全使用完，不可以再使用其中的空间。所以，链表只有最后一个节点才是可以使用的。每增加一个节点，总要设置前面一个节点的DYN_BLOCK_FULL_FLAG。
b) 每个块，data数组的预设值是DYN_ARRAY_DATA_SIZE(值为512)，
#define DYN_BLOCK_FULL_FLAG 0x1000000UL
所以，use的值小于等于512，那么该节点为尾节点。因为非尾节点的值肯定大于512，它与DYN_BLOCK_FULL_FLAG进行了或操作。
2)used
used表示data[DYN_ARRAY_DATA_SIZE]字段中已经使用的字节的数量，假设需要申请len字节的长度，在使用之前需要判断的是，尾 block中的可用空间是否够用。也就是判断判断下used+len是否满足used+len<= DYN_ARRAY_DATA_SIZE，如果满足就可以放进该block，并将已使用的字节数used加上len。
如果，该block空间不够，那么就会申请一个新的block，这里我们就可以明白了，为什么需要满足len的长度小于等于DYN_ARRAY_DATA_SIZE。
好，我们下面先看下分配空间的函数。
|
/*************************************************************************
Makes room on top of a dyn array and returns a pointer to the added element.
The caller must copy the element to the pointer returned. */
UNIV_INLINE
void*
dyn_array_push(
/*===========*/
/* out: pointer to the element */
dyn_array_t* arr, /* in: dynamic array */
ulint size) /* in: size in bytes of the element */
{
dyn_block_t* block;
ulint used;
ut_ad(arr);
ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N);
ut_ad(size <= DYN_ARRAY_DATA_SIZE);
ut_ad(size);
block = arr;
used = block->used;
if (used + size > DYN_ARRAY_DATA_SIZE) {
/* Get the last array block */
block = dyn_array_get_last_block(arr);
used = block->used;
if (used + size > DYN_ARRAY_DATA_SIZE) {
block = dyn_array_add_block(arr);
used = block->used;
}
}
block->used = used + size;
ut_ad(block->used <= DYN_ARRAY_DATA_SIZE);
return((block->data) + used);
} |
在这里面，我们要关注一下：
|
block = arr;
used = block->used; |
首先得到arr的首节点，在前面的内容中，我们描述过，在只有一个节点的时候(参考图1)，arr本身就是block，如果是多个节点，这个代码相当于获得的是链表的首节点。
那么如果是只有一个节点，那么很容易理解。假设链表是多个节点，这里面的used肯定是大于DYN_ARRAY_DATA_SIZE。因为每次生成一个block，就会调用dyn_array_add_block函数，在该函数中，会将前一个block的used进行置位操作。
block->used = block->used | DYN_BLOCK_FULL_FLAG;
所以，当arr存在多个block的时候，首节点的条件“used + size > DYN_ARRAY_DATA_SIZE”必为真。这时候，我们就去获取尾节点。
|
block = dyn_array_get_last_block(arr);
used = block->used;
if (used + size > DYN_ARRAY_DATA_SIZE) {
block = dyn_array_add_block(arr);
used = block->used;
}
|
尾节点的used肯定没有进行过置位操作。然后判断是否需要新增block节点。
回过头来，函数dyn_array_push的返回值，是一个指针，指向新增加元素的指针，然后用户对该指针进行操作赋值。我们来看下，系统中的一个使用实例。
|
/*******************************************************
Pushes an object to an mtr memo stack. */
UNIV_INLINE
void
mtr_memo_push(
/*==========*/
mtr_t* mtr, /* in: mtr */
void* object, /* in: object */
ulint type) /* in: object type: MTR_MEMO_S_LOCK, ... */
{
dyn_array_t* memo;
mtr_memo_slot_t* slot;
ut_ad(object);
ut_ad(type >= MTR_MEMO_PAGE_S_FIX);
ut_ad(type <= MTR_MEMO_X_LOCK);
ut_ad(mtr);
ut_ad(mtr->magic_n == MTR_MAGIC_N);
memo = &(mtr->memo);
//分配大小为sizeof(mtr_memo_slot_t)的动态数组空间
slot = dyn_array_push(memo, sizeof(mtr_memo_slot_t));
slot->object = object; //对返回的指针进行操作
slot->type = type; //对返回的指针进行操作
} |
通过上文的描述，我们可以使用dyn进行操作。分配一个元素，然后进行赋值。那么我们再思考下，有没有优化的可能?
假设现在一个应用场景:
我们需要插入三个元素，我们插入一个元素，就需要修改一次used,再插入，又得调用push函数进行操作。频繁的对dyn的数据结构进行操作。这样的效率是很低的。
这时候我们，会想到，为什么不直接一次申请大小长度为三个需要使用的总长度。假设这个总长度为len，那么我们是否就直接通过mtr_memo_push进行分配长度为len的空间?
好，这是可以的，但是，我们再假想一种情况，这三个元素的长度是变长的，我们没法预先知道这样的一个长度。假设可能需要10个字节，也可能需要12个字节，如果是分配了12个字节给它，那么就会多余两个。所以，我们可以事先通过一个新函数dyn_array_open来分配足够大的字节数，然后通过dyn_array_close进行重设used。
|
/*************************************************************************
Makes room on top of a dyn array and returns a pointer to a buffer in it.
After copying the elements, the caller must close the buffer using
dyn_array_close. */
UNIV_INLINE
byte*
dyn_array_open(
/*===========*/
/* out: pointer to the buffer */
dyn_array_t* arr, /* in: dynamic array */
ulint size) /* in: size in bytes of the buffer; MUST be
smaller than DYN_ARRAY_DATA_SIZE! */
{
dyn_block_t* block;
ulint used;
ut_ad(arr);
ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N);
ut_ad(size <= DYN_ARRAY_DATA_SIZE);
ut_ad(size);
block = arr;
used = block->used;
if (used + size > DYN_ARRAY_DATA_SIZE) {
/* Get the last array block */
block = dyn_array_get_last_block(arr);
used = block->used;
if (used + size > DYN_ARRAY_DATA_SIZE) {
block = dyn_array_add_block(arr);
used = block->used;
ut_a(size <= DYN_ARRAY_DATA_SIZE);
}
}
ut_ad(block->used <= DYN_ARRAY_DATA_SIZE);
#ifdef UNIV_DEBUG
ut_ad(arr->buf_end == 0);
arr->buf_end = used + size;
#endif
return((block->data) + used);
} |
留意下，函数的英文注释“After copying the elements”，说明是赋值多元组的。而且和dyn_array_push函数相比，函数体里面没有对used进行重新赋值。这个重新赋值的工作留给了dyn_array_close函数，我们看下该函数的实现。
/*************************************************************************
Closes the buffer returned by dyn_array_open. */
UNIV_INLINE
void
dyn_array_close(
/*============*/
dyn_array_t* arr, /* in: dynamic array */
byte* ptr) /* in: buffer space from ptr up was not used */
{
dyn_block_t* block;
ut_ad(arr);
ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N);
block = dyn_array_get_last_block(arr);
ut_ad(arr->buf_end + block->data >= ptr);
block->used = ptr - block->data;
ut_ad(block->used <= DYN_ARRAY_DATA_SIZE);
#ifdef UNIV_DEBUG
arr->buf_end = 0;
#endif
}
在该函数里面通过下面的一行代码进行赋值。
block->used = ptr - block->data;
其中ptr是dyn_array_open函数返回指针并使用之后的调整值。假设dyn_array_open返回的是ptr，赋值第一个长度len1的元素后，ptr得加上len1，继续len2长度的元素，ptr加上len2，以此类推。ptr指示下一个赋元组时的指针。所以通过block->used = ptr - block->data;就能够计算出偏移量，这个偏移量就是used。
看下代码的实际应用场景。
|
/************************************************************
Writes 8 bytes to a file page buffered in the buffer pool.
Writes the corresponding log record to the mini-transaction log. */
void
mlog_write_dulint(
/*==============*/
byte* ptr, /* in: pointer where to write */
dulint val, /* in: value to write */
mtr_t* mtr) /* in: mini-transaction handle */
{
byte* log_ptr;
if (ptr < buf_pool->frame_zero || ptr >= buf_pool->high_end) {
fprintf(stderr,
"InnoDB: Error: trying to write to a stray memory location %p\n", ptr);
ut_error;
}
ut_ad(ptr && mtr);
mach_write_to_8(ptr, val);
//分配空间
log_ptr = mlog_open(mtr, 11 + 2 + 9);
/* If no logging is requested, we may return now */
if (log_ptr == NULL) {
return;
}
log_ptr = mlog_write_initial_log_record_fast(ptr, MLOG_8BYTES,
log_ptr, mtr);
mach_write_to_2(log_ptr, ptr - buf_frame_align(ptr));
log_ptr += 2;
log_ptr += mach_dulint_write_compressed(log_ptr, val);
//重设used值
mlog_close(mtr, log_ptr);
} |
动态数组的主要内容就是这些，还有一些关于获取长度、元素等的函数，建议参考源代码进行理解。
|
