A-A+

为MySQL源码添加变长动态数组

2014年04月01日 TenDB 暂无评论

【现状】

MySQL 5.5社区版中已经有一种叫DYNAMIC_ARRAY的数据结构,是一种存储定长元素的动态数组。“定长”说的是数组中每一个元素所占字节数在运行时是恒定不变的;“动态”说的是这个数组的个数可以随着元素的增加而自动扩容。

先来看一下动态数组成员结构:

[cpp]
typedef struct st_dynamic_array {
uchar *buffer; /* 内存首地址 */
uint elements; /* 元素个数 */
uint max_element; /* 是否需要扩容的阀值 */
uint alloc_increment; /* 自动扩容增加元素个数 */
uint size_of_element; /* 每个元素大小 */
} DYNAMIC_ARRAY;[/cpp]

【常用API】

我们总结了关于这个数据结构的常用接口:

[cpp]/* 定义 */
DYNAMIC_ARRAY global_session_event_array;

/* 分配空间 */
my_init_dynamic_array(&global_session_event_array,
sizeof(Log_event*), /* 每个元素是一个指向Log_event对象的指针, 大小为sizeof(Log_event*) */
16, /* 初始分配16个元素 */
16); /* 每次扩容增加16个元素 */

/* 释放数组,相当于free(函数名取得不好)。如果元素是指针,释放数组元素的同时不会释放它们指向的内存。 */
delete_dynamic(&global_session_event_array);

/* 遍历数组。其中DYNAMIC_ARRAY.elements域描述的是数组当前元素个数 */
for (i = 0; i < global_session_event_array.elements; ++i) {
ElemType tmp_elem;
get_dynamic(&some_array, (uchar*)&tmp_elem, i);
}

/* 追加元素 */
insert_dynamic(&some_array, (uchar*)&elem);

/* 相当于clear,并未释放已经分配的空间;已经分配的空间将被重写 */
global_session_event_array.elements = 0;

/* 删除第i个元素 */
delete_dynamic_element(&global_load_event_array, i);
[/cpp]

【需求】

DYNAMIC_ARRAY实现了动态数组的基本需求。但如果存放的元素不是指针,而是对象(C就是内存),那么除非每个对象都是等大小的,否则不能正常工作。为什么不存指针?如果指针元素指向对象的生命周期是和当前动态数组并不是“同步”可见的,那么这些元素随时都可能“被成为”dangling pointer,即悬挂指针。

在TenDB的开发过程中,我们确实有这样的需求:需要存储大小不同的对象本身(内存结构),于是在充分利用现有代码的基础上,实现了一种新的动态数组。底层的内存存储在DYNAMIC_STRING中,这是一种MySQL中的变长字符串。由于我们的对象内容随时可能存在’\0’,所以需要辅助额外的元数据,我们定义了如下结构表明对象(内存结构)在DYNAMIC_STRING中的偏移和长度:
[cpp]
typedef struct st_dynstr_pos_info
{
size_t elem_off;
size_t elem_size;
} dynstr_pos_info;
[/cpp]

每一个对象对应一个dynstr_pos_info。由于其空间是恒定的,所以我们复用了DYNAMIC_ARRAY作为元数据容器。新结构DYNAMIC_STRING_ARRAY的成员声明如下:
[cpp]
typedef struct st_dynamic_string_array
{
DYNAMIC_STRING *dynstr;
DYNAMIC_ARRAY *pos_info_arr;
size_t cur_idx;
} DYNAMIC_STRING_ARRAY;
[/cpp]

QQ截图20140401140819

【实现】

实现代码添加在mysql-version/mysys/array.c

结构体声明都在mysql-version/include/my_sys.h

[cpp]
my_bool init_dynamic_string_array(DYNAMIC_STRING_ARRAY *array,
uint init_alloc,
uint alloc_increment)
{
DBUG_ENTER("init_dynamic_string_array");
if (!array) {
DBUG_RETURN(TRUE);
}

if (!(array->pos_info_arr = (DYNAMIC_ARRAY *) my_malloc(sizeof(DYNAMIC_ARRAY), MYF(0)))) {
// TODO: print err
DBUG_RETURN(TRUE);
}

if (!(array->dynstr = (DYNAMIC_STRING *) my_malloc(sizeof(DYNAMIC_STRING), MYF(0)))) {
// TODO: print err
DBUG_RETURN(TRUE);
}

init_dynamic_array(array->pos_info_arr, sizeof(dynstr_pos_info), init_alloc, alloc_increment);
array->cur_idx = 0;
DBUG_RETURN(init_dynamic_string(array->dynstr, "", 0, 0) ? TRUE : FALSE);
}

my_bool clear_dynamic_string_array(DYNAMIC_STRING_ARRAY *array)
{
DBUG_ENTER("clear_dynamic_string_array");
if (array) {
clear_dynamic_array(array->pos_info_arr);
dynstr_clear(array->dynstr);
array->cur_idx = 0;
DBUG_RETURN(FALSE);
}

DBUG_RETURN(TRUE);
}

my_bool free_dynamic_string_array(DYNAMIC_STRING_ARRAY *array)
{
DBUG_ENTER("free_dynamic_string_array");
if (array) {
delete_dynamic(array->pos_info_arr);
array->pos_info_arr = NULL;

dynstr_free(array->dynstr);
array->dynstr = NULL;

my_free(array->pos_info_arr);
my_free(array->dynstr);
array->pos_info_arr = NULL;
array->dynstr = NULL;
array->cur_idx = 0;
DBUG_RETURN(FALSE);
}

DBUG_RETURN(TRUE);
}

my_bool append_dynamic_string_array(DYNAMIC_STRING_ARRAY *array,
const char *elem,
size_t elem_len)
{

dynstr_pos_info pos_info;
DBUG_ENTER("append_dynamic_string_array");
if (array && elem) {
if (!elem_len) {
DBUG_RETURN(FALSE);
}

pos_info.elem_off = array->dynstr->length;
pos_info.elem_size = elem_len;
if (dynstr_append_mem(array->dynstr, elem, elem_len) || insert_dynamic(array->pos_info_arr, (uchar *) &pos_info)) {
DBUG_RETURN(TRUE);
}
++array->cur_idx;
DBUG_RETURN(FALSE);
}

DBUG_RETURN(TRUE);
}

my_bool get_dynamic_string_array(DYNAMIC_STRING_ARRAY *array,
char **dst,
size_t *dst_len,
size_t idx)
{
dynstr_pos_info pos_info;
DBUG_ENTER("get_dynamic_string_array");
if (!array || !dst || idx >= array->pos_info_arr->elements) {
DBUG_RETURN(TRUE);
}

get_dynamic(array->pos_info_arr, (uchar *) &pos_info, idx);
*dst = array->dynstr->str + pos_info.elem_off;
if (dst_len) {
*dst_len = pos_info.elem_size;
}
DBUG_RETURN(FALSE);
}

my_bool empty_dynamic_string_array(DYNAMIC_STRING_ARRAY *array)
{
DBUG_ENTER("empty_dynamic_array");
if (array) {
DBUG_RETURN(array->cur_idx == 0);
}

DBUG_RETURN(TRUE);
}
[/cpp]

原创文章,转载请注明: 转载自腾讯游戏DBA团队

本文链接地址: 为MySQL源码添加变长动态数组

文章的脚注信息由WordPress的wp-posturl插件自动生成

Copyright © 腾讯游戏DBA团队 保留所有权利.  

用户登录

分享到: