一个链表的实现
【摘要】 参考:https://github.com/webcoyote/coho/blob/master/Base/List.h数据和link的转换逻辑迷了好久,参考上面的仓里的测试用例才想明白,"embedded"Links照着这个还原了一下WC里面的TSList实现如下:Linktemplate<typename T>class TSLink{public: TSLink(){ m_nextN...
WC中Hash表的接口形式，后面有空再填填实现
template<typename T,typename TKey>
class TSHashTable{
public:
TSHashTable();;
~TSHashTable();
int* Ptr(int a2,int* a3);
int Initialize();
int GrowListArray(unsigned int a2);
int MonitorFullness(int a2);
int InternalNewNode(int a2,int a3,int a4);
int InternalLinkNode(int a2,int a3);
int InternalClear(int a2);
void Unlink(int a2);
int Delete(int a2);
int DeleteNode(int a2);
unsigned int * New(void* a2,int a3,int a4);
int Insert(int a2,int a3);
int Next(int a2);
int Head();
public:
//IntPtr vtable; // 4
TSExplicitList<T,?> m_fulllist; // 12
int m_fullnessIndicator; // 4
TSGrowableArray<TSExplicitList<T,?>,TSCD<TSExplicitList<T,?>>> m_slotlistarray; // 20
int m_slotmask; // 4
};/*==============================分割线===================================*/
内存池
https://stackoverflow.com/questions/1885849/difference-between-new-operator-and-operator-new
https://stackoverflow.com/questions/6500313/why-should-c-programmers-minimize-use-of-new
https://softwareengineering.stackexchange.com/questions/162614/compilable-modern-alternatives-to-c-c
https://stackoverflow.com/questions/519808/call-a-constructor-on-a-already-allocated-memory
https://docs.microsoft.com/en-us/cpp/cpp/new-operator-cpp?redirectedfrom=MSDN&view=vs-2019
https://bbs.csdn.net/topics/200069137
https://isocpp.org/wiki/faq/dtors#placement-new
https://www.geeksforgeeks.org/placement-new-operator-cpp/+&cd=1&hl=en&ct=clnk&gl=sg
https://stackoverflow.com/questions/3763846/what-is-an-in-place-constructor-in-c
https://stackoverflow.com/questions/2697892/what-is-return-type-of-new-in-c/2697929#2697929
https://stackoverflow.com/questions/5279042/placement-new-vs-explicit-constructor-call-in-c
https://stackoverflow.com/questions/38171964/move-construct-object-with-placement-new
https://stackoverflow.com/questions/519808/call-a-constructor-on-a-already-allocated-memory
https://isocpp.org/wiki/faq/dtors+&cd=1&hl=en&ct=clnk&gl=sg
https://docs.microsoft.com/en-us/cpp/cpp/new-operator-cpp?redirectedfrom=MSDN&view=vs-2019
https://thinkingeek.com/2017/11/19/simple-memory-pool/+&cd=1&hl=en&ct=clnk&gl=sg
https://www.boost.org/doc/libs/1_46_1/libs/pool/doc/index.html+&cd=2&hl=en&ct=clnk&gl=sg
/*==============================分割线===================================*/
AOP
http://vitiy.info/c11-functional-decomposition-easy-way-to-do-aop/+&cd=3&hl=zh-CN&ct=clnk&gl=sg
/*==============================分割线===================================*/
参考:
https://github.com/webcoyote/coho/blob/master/Base/List.h
数据和link的转换逻辑迷了好久,参考上面的仓里的测试用例才想明白,"embedded"Links
照着这个还原了一下WC里面的TSList实现如下:
Link
template<typename T>
class TSLink{
public:
TSLink(){
m_nextNode = (T*)((size_t)this + 1 - 0);
m_prevLink = this;
}
T* Next(){
T* ret = m_nextNode;
if ( ((size_t)ret & 1) || !ret )
ret = NULL;
return (T*)ret;
}
T* Prev(){
T* prevNode = m_prevLink->m_prevLink->m_nextNode;
if ( ((size_t)prevNode & 1) || !prevNode )
prevNode = NULL;
return prevNode;
}
TSLink<T>* NextLink(int offset){
T* next = m_nextNode;
if ( ((size_t)next & 1) || !next )
return (TSLink<T>*)((size_t)next & ~1);
if ( offset < 0 )
offset = (size_t) this - (size_t)m_prevLink->m_nextNode;
return (TSLink<T>*)((size_t)next + offset);
}
public:
TSLink<T>* m_prevLink;
T* m_nextNode;
};List(模板第二个参数我还没想明白,目前没影响，估计和offset获取赋值有关)
template<typename T,typename N>
class TSList{
public:
TSList(){
m_terminator.m_nextNode = NULL;
m_linkoffset = 0;
m_terminator.m_prevLink = (TSLink<T>*)&m_terminator.m_prevLink;
m_terminator.m_nextNode = (T*)((size_t)(&m_terminator.m_prevLink) | 1);
}
~TSList(){
UnlinkAll();
if ( m_terminator.m_prevLink ) {
m_terminator.m_prevLink->NextLink(-1)->m_prevLink = m_terminator.m_prevLink;
m_terminator.m_prevLink->m_nextNode = m_terminator.m_nextNode;
m_terminator.m_prevLink = NULL;
m_terminator.m_nextNode = NULL;
}
}
void UnlinkAll(){
while (1){
T* next = m_terminator.m_nextNode;
if ( ((size_t)next & 1) || !next )
break;
UnlinkNode(m_terminator.m_nextNode);
}
}
void UnlinkNode(T* whichNode) {
TSLink<T>* target;
if (whichNode)
target = (TSLink<T>*)whichNode;
else
target = &m_terminator;
if ( target->m_prevLink ){
target->NextLink(-1)->m_prevLink = target->m_prevLink;
target->m_prevLink->m_nextNode = target->m_nextNode;
target->m_prevLink = NULL;
target->m_nextNode = NULL;
}
}
T* NewNode(int option, int a3, int a4){
T *v5;
v5 = new T;
if (option)
LinkNode(v5, option, NULL);
return v5;
}
void LinkNode(TSLink<T>* a2, int option, TSLink<T>* a4){
TSLink<T>* target;
TSLink<T>* dest = a4;
if ( a2 )
target = a2;
else
target = &m_terminator;
if (target->m_prevLink) {
target->NextLink(-1)->m_prevLink = target->m_prevLink;
target->m_prevLink->m_nextNode = target->m_nextNode;
target->m_prevLink = NULL;
target->m_nextNode = NULL;
}
if ( !a4 )
dest = &m_terminator;
if ( option == 1 ) {
target->m_prevLink = dest;
target->m_nextNode = dest->m_nextNode;
dest->NextLink(m_linkoffset)->m_prevLink = target;
dest->m_nextNode = (T*)a2;
} else if ( option == 2 ) {
TSLink<T>* v6 = dest->m_prevLink;
target->m_prevLink = dest->m_prevLink;
target->m_nextNode = v6->m_nextNode;
v6->m_nextNode = (T*)a2;
dest->m_prevLink = target;
}
}
void LinkNode(T* a2, int option, TSLink<T>* a4) {
TSLink<T>* target;
if ( a2 )
target = (TSLink<T>*)(m_linkoffset + (size_t)a2);
else
target = &m_terminator;
if ( target->m_prevLink ){
target->NextLink(-1)->m_prevLink = target->m_prevLink;
target->m_prevLink->m_nextNode = target->m_nextNode;
target->m_prevLink = NULL;
target->m_nextNode = NULL;
}
TSLink<T> *dest;
if ( a4 )
dest = (TSLink<T>*)(m_linkoffset + (size_t)a4);
else
dest = &m_terminator;
if ( option == 1 ){
target->m_prevLink = dest;
target->m_nextNode = dest->m_nextNode;
dest->NextLink( m_linkoffset)->m_prevLink = target;
dest->m_nextNode = a2;
}else if ( option == 2 ){
TSLink<T> *v6 = dest->m_prevLink;
target->m_prevLink = dest->m_prevLink;
target->m_nextNode = v6->m_nextNode;
v6->m_nextNode = a2;
dest->m_prevLink = target;
}
}
T* DeleteNode(T* a2) {
T* v2;
v2 = Next(a2);
delete a2;
return v2;
}
T* Next(T* whichNode) {//sure
TSLink<T>* target;
T* result;
if (whichNode)
target = (TSLink<T>*)(m_linkoffset + (size_t)whichNode);
else
target = &m_terminator;
result = target->m_nextNode;
if ( (size_t)result & 1 || !result )
result = NULL;
return result;
}
T* Next(TSLink<T>* target) {//sure
T* result;
TSLink<T>* v2 = target;
if ( !target )
v2 = &m_terminator;
result = v2->m_nextNode;
if ( (size_t)result & 1 || !result )
result = NULL;
return result;
}
T* Next(TSList<T,N>* target) {//sure
T* result;
TSList<T,N>* v2 = target;
if ( !target )
v2 = this;
result = v2->m_terminator.m_nextNode;
if ( (size_t)result & 1 || !result )
result = NULL;
return result;
}
T* RawNext(T* whichNode) {
TSLink<T>* target;
if (whichNode)
target = (TSLink<T>*)(m_linkoffset + (size_t)whichNode);
else
target = &m_terminator;
return target->m_nextNode;
}
T* RawNext(TSLink<T>* whichNode) {
TSLink<T>* target;
target = whichNode;
if ( !whichNode )
target = &m_terminator;
return target->m_nextNode;
}
T* RawNext(TSList<T,N>* whichNode) {
TSList<T,N>* target;
target = whichNode;
if ( !whichNode )
target = this;
return target->m_terminator.m_nextNode;
}
T* Prev(T* whichNode) {
TSLink<T>* v2;
T* result;
if ( whichNode )
v2 = (TSLink<T>*)(m_linkoffset + whichNode);
else
v2 = &m_terminator;
result = v2->m_prevLink->m_nextNode;
if ( (size_t)result & 1 || !result )
result = NULL;
return result;
}
T* Prev(TSLink<T>* whichNode) {//sure
TSLink<T>* v2;
T* result;
v2 = whichNode;
if(!whichNode)
v2 = &m_terminator;
result = v2->m_prevLink->m_prevLink->m_nextNode;
if ( (size_t)result & 1 || !result )
result = NULL;
return result;
}
T* Head() {//sure
T* result;
result = m_terminator.m_nextNode;
if ( (size_t)result & 1 || !result )
result = NULL;
return result;
}
void Combine(TSList<T,N>* target, int option, TSLink<T>* mid) {
TSLink<T>* midLink = mid;
TSLink<T>* v5 = &target->m_terminator;
if ( &target->m_terminator != target->m_terminator.m_prevLink ){
if (!mid)
midLink = &m_terminator;
if ( option == 1 ) {
TSLink<T>* v9 = midLink;
T* v6 = midLink->m_nextNode;
midLink->NextLink(m_linkoffset)->m_prevLink = v5;
v9->m_nextNode = target->m_terminator.m_nextNode;
v5->NextLink(target->m_linkoffset)->m_prevLink = v9;
v5->m_prevLink->m_nextNode = v6;
}else if ( option == 2 ){
TSLink<T>* v7 = midLink->m_prevLink;
T* v8 = midLink->m_prevLink->m_nextNode;
midLink->m_prevLink->m_nextNode = target->m_terminator.m_nextNode;
midLink->m_prevLink = v5->m_prevLink;
v5->m_prevLink->NextLink(target->m_linkoffset)->m_prevLink = v7;
v5->m_prevLink->m_nextNode = v8;
}
target->m_terminator.m_prevLink = v5;
target->m_terminator.m_nextNode = (T*)((size_t)v5 | 1);
}
}
bool IsLinked(T* whichNode){
TSLink<T> *target;
if(whichNode)
target = (TSLink<T>*)(m_linkoffset + (size_t)whichNode);
else
target = &m_terminator;
return target->m_nextNode != NULL;
}
void Clear(){
T* target;
for (;;){//free(target)
target = m_terminator.m_nextNode;
if ( (size_t)target & 1 || !target )
break;
delete target;
}
}
int ChangeLinkOffset(int newOffset){
int result;
if ( m_linkoffset != newOffset ){
UnlinkAll();
m_linkoffset = newOffset;
m_terminator.m_prevLink = m_terminator.m_prevLink;
result = (size_t)m_terminator.m_prevLink | 1;
m_terminator.m_nextNode = (T*)result;
}
return result;
}
public:
int m_linkoffset;
TSLink<T> m_terminator;
};测试用例:
struct Data {
TSLink<Data> forward;
unsigned value;
};
int main(int argv,char* argc[]){
Data a,a2,a3,a4;
a.value = 1;
a2.value = 2;
a3.value = 3;
a4.value = 4;
TSList<Data,int> b,e;
std::cout << b.m_linkoffset << std::endl;
b.Clear();
std::cout << b.IsLinked(&a) << std::endl;
b.LinkNode(&a, 2, NULL);
b.LinkNode(&a2, 2, NULL);
b.LinkNode(&a3, 2, NULL);
std::cout << b.IsLinked(&a) << std::endl;
std::cout << b.m_linkoffset << std::endl;
std::cout << "================" << std::endl;
std::cout << (b.Head() ? b.Head()->value : 0) << std::endl;
std::cout << (b.Next(b.Head()) ? b.Next(b.Head())->value : 0) << std::endl;
std::cout << (b.Next(b.Next(b.Head())) ? b.Next(b.Next(b.Head()))->value : 0) << std::endl;
std::cout << "================" << std::endl;
e.LinkNode(&a4, 2, NULL);
b.Combine(&e,1,NULL);
std::cout << "================" << std::endl;
std::cout << (b.Head() ? b.Head()->value : 0) << std::endl;
std::cout << (b.Next(b.Head()) ? b.Next(b.Head())->value : 0) << std::endl;
std::cout << (b.Next(b.Next(b.Head())) ? b.Next(b.Next(b.Head()))->value : 0) << std::endl;
std::cout << (b.Next(b.Next(b.Next(b.Head()))) ? b.Next(b.Next(b.Next(b.Head())))->value : 0) << std::endl;
std::cout << "================" << std::endl;
Data* next = &a2;
if (!((size_t)next & 1) && next)
b.UnlinkNode(&a2);
std::cout << "================" << std::endl;
std::cout << (b.Head() ? b.Head()->value : 0) << std::endl;
std::cout << (b.Next(b.Head()) ? b.Next(b.Head())->value : 0) << std::endl;
std::cout << (b.Next(b.Next(b.Head())) ? b.Next(b.Next(b.Head()))->value : 0) << std::endl;
std::cout << "================" << std::endl;
getchar();
return 0;
}
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）