MySQL源码解读之数据结构-LF_DYNARRAY
LF_DYNARRAY数据结构是应用于LF_PINS和LF_HASH数据结构的一种特殊数据结构。该结构不同于DYNAMIC_ARRAY动态数组结构物理分配和逻辑操作，而是一种层级分配管理方式进行组织，对于稀疏、非连续的数组存储可以有效的提高空间利用率。LF_DYNARRAY，它是一个可以多级的、可动态扩充的数组。lf是lock_free的意思，即不使用锁的情况下实现多线程之间的变量同步。
LF_DYNARRAY结构如下图所示：
源码解读
[源码路径：include/lf.h, mysys/lf_dynarray.cc]
#define LF_DYNARRAY_LEVEL_LENGTH 256 #define LF_DYNARRAY_LEVELS 4 typedef struct { std::atomic<void *> level[LF_DYNARRAY_LEVELS]; uint size_of_element; } LF_DYNARRAY;
由上述代码我们可以看到默认LF_DYNARRAY共有四层，每个数组长度为256。所有整个数组结构可以存储 256**4 + 256**3 + 256**2 + 256 = 4311810304个元素。 stomic<void *>是定义 void *指针是原子类型的。即对void *指针的操作都是原子操作（原子操作(atomic operation)指的是由多步操作组成的一个操作。如果该操作不能原子地执行,则要么执行完所有步骤,要么一步也不执行,不可能只执行所有步骤的一个子集）
接下来我们再看一下lf_dynarray.cc文件的具体实现函数
1、lf_dynarray_init 初始化lf_dynarray
void lf_dynarray_init(LF_DYNARRAY *array, uint element_size) { std::fill(begin(array->level), end(array->level), nullptr); array->size_of_element = element_size; }
函数介绍：入参：传入一个LF_DYNARRAY指针，每个元素的大小。对level[4]数组的元素全部用 nullptr 填充。
2、recursive_free 级联释放内存
3、lf_dynarray_destroy 销毁lf_dynarray。 该函数调用了recursive_free函数
4、lf_dynarray_lvalue 获取指定idx位置元素的地址
void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx) { void *ptr; int i; // 定位idx位于哪一层，如果小于256就在level[0],如果大于256小于65792就在level[1] for (i = LF_DYNARRAY_LEVELS - 1; idx < dynarray_idxes_in_prev_levels[i]; i--) /* no-op */; // 将level[i]数组的基址赋值给ptr_ptr std::atomic<void *> *ptr_ptr = &array->level[i]; // idx减去本level之前所有levels的容量总和，得到在本level中的idx idx -= dynarray_idxes_in_prev_levels[i]; // 逐级检查，申请内存，定位到最小那一级的idx for (; i > 0; i--) { if (!(ptr = *ptr_ptr)) { void *alloc = my_malloc(key_memory_lf_dynarray, LF_DYNARRAY_LEVEL_LENGTH * sizeof(void *), MYF(MY_WME | MY_ZEROFILL)); if (unlikely(!alloc)) { return (nullptr); } if (atomic_compare_exchange_strong(ptr_ptr, &ptr, alloc)) { ptr = alloc; } else { my_free(alloc); } } ptr_ptr = ((std::atomic<void *> *)ptr) + idx / dynarray_idxes_in_prev_level[i]; idx %= dynarray_idxes_in_prev_level[i]; } // 此时idx已经确定到了256以内，检查这一级对应的array，如果没有申请，就申请内存 if (!(ptr = *ptr_ptr)) { uchar *alloc, *data; alloc = static_cast<uchar *>( // 多申请了一个指针大小 my_malloc(key_memory_lf_dynarray, LF_DYNARRAY_LEVEL_LENGTH * array->size_of_element + std::max<uint>(array->size_of_element, sizeof(void *)), MYF(MY_WME | MY_ZEROFILL))); if (unlikely(!alloc)) { return (nullptr); } /* reserve the space for free() address */ // 为了释放内存 data指向256个数组 alloc执行前边的void * data = alloc + sizeof(void *); { /* alignment */ // 此处用于内存对齐 intptr mod = ((intptr)data) % array->size_of_element; if (mod) { data += array->size_of_element - mod; } } ((void **)data)[-1] = alloc; /* free() will need the original pointer */ if (atomic_compare_exchange_strong(ptr_ptr, &ptr, static_cast<void *>(data))) { ptr = data; } else { my_free(alloc); } } return ((uchar *)ptr) + array->size_of_element * idx; }
函数介绍：该函数传入一个结构体指针和idx值，然后获取idx值的内存地址。如果地址不存在就从内存申请。
5、lf_dynarray_value 返回指定元素的值
void *lf_dynarray_value(LF_DYNARRAY *array, uint idx)
函数介绍：lf_dynarray_value传入一个idx值，返回该索引的元素值。如果不存在就返回null。
6、lf_dynarray_iterate 对整个动态数组进行迭代，迭代函数需要调用者传入
int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg)