0%

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;
}