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 | template <class Elem> class Dynamic_array |
Dynamic_array api 1
2
3
4
5
6Elem& 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);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
3Prealloced_array
提前申请prealloc size大小的element 的内存, 然后如果使用过程中,
如果element 不够用,再动态扩容, 可以支持push/pop/front/at 等操作1
2
3
4
5
6
7
8
9
10
11
12
13template <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
}1
2
3
4
5
6
7template <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); }
};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; }
};1
2
3
4
5
6
7
8
9
10template <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
25typedef 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;
}