Longda's Interesting World

Longda's Interesting World

MySQL 源码解读 -- list

MySQL 源码解读 -- list

List 系列

Dynamic_array

Dynamic_array & DYNAMIC_ARRAY 比较简单, 其核心就是类似内存池算法, 但比内存池重, 申请一块内存, 这块内存可以取出一个Elem, 如果释放一个Elem, 会将这个elem 后面的数据向前挪, 当elem 不够时, 会realloc 内存进行扩容. DYNAMIC_STRING 可以 为DYNAMIC_ARRAY 的特殊类

Dynamic_array 有一个问题, 这里没有考虑线程安全性

在8.0 中, Dynamic_array 已经被取消, 取代它的是Prealloced_array


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class Elem> class Dynamic_array
{
  DYNAMIC_ARRAY  array;  核心类
  //API
}

struct DYNAMIC_ARRAY {
  uchar *buffer{nullptr};
  uint elements{0}, max_element{0};
  uint alloc_increment{0};
  uint size_of_element{0};
  PSI_memory_key m_psi_key{PSI_NOT_INSTRUMENTED};
};

struct DYNAMIC_STRING {
  char *str;
  size_t length, max_length, alloc_increment;
};

Dynamic_array api

1
2
3
4
5
6
Elem& at(int idx)    ---------> 取内存池中第n 个elem
Elem *front()        --> 取出第一个elem
Elem *back()         --> 取出最后一个elem
bool append(const Elem &el)   --> 插入一个elem, 核心调用 insert_dynamic(&array, &el);
Elem& pop()          --> 弹出一个elem 位置, 核心调用 *((Elem*)pop_dynamic(&array));
del(uint idx)        --> 删除某个elem, delete_dynamic(&array);

DYNAMIC_ARRAY api

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 申请一块内存(init_alloc * element_size), 然后把相关变量设进DYNAMIC_ARRAY
 */
my_bool init_dynamic_array2(DYNAMIC_ARRAY *array, uint element_size,
                            void *init_buffer, uint init_alloc, 
                            uint alloc_increment)
/**
 如果原先内存池够, 将elem 设到对应的位置
 如果原先内存池不够, 对内存池进行扩容, 扩容alloc_increment个elem
 */
my_bool insert_dynamic(DYNAMIC_ARRAY *array, const void *element)

/*扩容alloc_increment个elem */
void *alloc_dynamic(DYNAMIC_ARRAY *array)
/* 扩容到(max_elements + array->alloc_increment)/array->alloc_increment; 个elem*/
my_bool allocate_dynamic(DYNAMIC_ARRAY *array, uint max_elements)

/*把最后一个elem 返回*/
void *pop_dynamic(DYNAMIC_ARRAY *array)

/* 将第idx(从0开始)个elem 拷贝到element */
void get_dynamic(DYNAMIC_ARRAY *array, void *element, uint idx)

/*清空内存池*/
void delete_dynamic(DYNAMIC_ARRAY *array)

/*清除第idx个elem, 并把后面的elem 向前挪*/
void delete_dynamic_element(DYNAMIC_ARRAY *array, uint idx)

/* 把后面不用的elem的内存释放掉 */
void freeze_size(DYNAMIC_ARRAY *array)
1
2
3
Prealloced_array
提前申请prealloc size大小的element 的内存, 然后如果使用过程中,
如果element 不够用,再动态扩容, 可以支持push/pop/front/at 等操作

I_P_List

其实就是类似普通的List操作, mysql 这个实现做的比较general, 实现一个链表操作

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T, typename B, typename C = I_P_List_null_counter,
          typename I = I_P_List_no_push_back<T>>
class I_P_List : public C, public I {
  T *m_first;
  // api
  
  inline void push_front(T* a) --> 插入a 到列表头
  inline void push_back(T *a)  --> 插入a 到列表尾
  inline void insert_after(T *pos, T *a)  将a 插入到pos 之后
  inline void remove(T *a)
  inline T* pop_front()  -->  把front 给弹出来, 然后在list 去掉front
  
}

typename B 必须实现类似如下接口

1
2
3
4
5
6
7
template <typename T, T* T::*next, T** T::*prev>
struct I_P_List_adapter
{
  static inline T **next_ptr(T *el) { return &(el->*next); }
  static inline const T* const* next_ptr(const T *el) { return &(el->*next); }
  static inline T ***prev_ptr(T *el) { return &(el->*prev); }
};

I_P_List_null_counter 不会做统计, 推荐使用I_P_List_counter 会进行统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class I_P_List_counter
{
  uint m_counter;
protected:
  I_P_List_counter() : m_counter (0) {}
  void reset() {m_counter= 0;}
  void inc() {m_counter++;}
  void dec() {m_counter--;}
  void swap(I_P_List_counter &rhs)
  { swap_variables(uint, m_counter, rhs.m_counter); }
public:
  uint elements() const { return m_counter; }
};

如果使用I_P_List_no_push_back , 则不可以使用push back 操作, 只能插入到头

1
2
3
4
5
6
7
8
9
10
template <typename T>
class I_P_List_fast_push_back {
  T **m_last;

 protected:
  I_P_List_fast_push_back(T **a) : m_last(a) {}
  void set_last(T **a) { m_last = a; }
  T **get_last() const { return m_last; }
  void swap(I_P_List_fast_push_back<T> &rhs) { std::swap(m_last, rhs.m_last); }
};


使用角度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef I_P_List<MDL_ticket,
                   I_P_List_adapter<MDL_ticket,
                                    &MDL_ticket::next_in_context,
                                    &MDL_ticket::prev_in_context> >
  Ticket_list;

  typedef Ticket_list::Iterator Ticket_iterator;
  
  Ticket_list m_tickets[MDL_DURATION_END];
  
  template <typename T, T* T::*next, T** T::*prev>
struct I_P_List_adapter
{
  static inline T **next_ptr(T *el) { return &(el->*next); }
  static inline const T* const* next_ptr(const T *el) { return &(el->*next); }
  static inline T ***prev_ptr(T *el) { return &(el->*prev); }
};

class MDL_ticket : public MDL_wait_for_subgraph
{
public:

  MDL_ticket *next_in_context;
  MDL_ticket **prev_in_context;
}