-
Notifications
You must be signed in to change notification settings - Fork 347
/
List.h
129 lines (125 loc) · 2.27 KB
/
List.h
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
* predixy - A high performance and full features proxy for redis.
* Copyright (C) 2017 Joyield, Inc. <joyield.com@gmail.com>
* All rights reserved.
*/
#ifndef _PREDIXY_LIST_H_
#define _PREDIXY_LIST_H_
template<class T, class P = T*, int Size = 1>
class ListNode
{
public:
typedef P Ptr;
ListNode()
{
for (int i = 0; i < Size; ++i) {
mNext[i] = nullptr;
}
}
~ListNode()
{
for (int i = 0; i < Size; ++i) {
mNext[i] = nullptr;
}
}
void reset(int idx = 0)
{
mNext[idx] = nullptr;
}
void concat(T* obj, int idx = 0)
{
mNext[idx] = obj;
}
P next(int idx = 0) const
{
return mNext[idx];
}
private:
P mNext[Size];
};
template<class N, int Idx = 0>
class List
{
public:
typedef typename N::Value T;
typedef typename N::ListNodeType Node;
typedef typename Node::Ptr P;
public:
List():
mSize(0),
mHead(nullptr),
mTail(nullptr)
{
}
~List()
{
while (mSize > 0) {
pop_front();
}
}
P next(T* obj)
{
return node(obj)->next(Idx);
}
void push_back(T* obj)
{
N* p = static_cast<N*>(obj);
if (mTail) {
static_cast<Node*>((T*)mTail)->concat(p, Idx);
mTail = p;
} else {
mHead = mTail = p;
}
++mSize;
}
void push_front(T* obj)
{
N* p = static_cast<N*>(obj);
if (mHead) {
node(obj)->concat(mHead, Idx);
mHead = p;
} else {
mHead = mTail = p;
}
++mSize;
}
P pop_front()
{
P obj = mHead;
if (obj) {
Node* n = node((T*)obj);
mHead = n->next(Idx);
if (--mSize == 0) {
mTail = nullptr;
}
n->reset(Idx);
}
return obj;
}
P front() const
{
return mHead;
}
P back() const
{
return mTail;
}
int size() const
{
return mSize;
}
bool empty() const
{
return mSize == 0;
}
private:
static Node* node(T* obj)
{
return static_cast<N*>(obj);
}
private:
int mSize;
P mHead;
P mTail;
};
#endif