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)