c++ - 对现有的 C 侵入式链表施加类型安全

Question

我有一组相当简单的双向链表助手，以两个基本结构为中心:

typedef struct DoubleLinkedListNode_struct {
   struct DoubleLinkedListNode_struct *m_prev;
   struct DoubleLinkedListNode_struct *m_next;
} DoubleLinkedListNode;

typedef struct DoubleLinkedList_struct {
   DoubleLinkedListNode m_anchor;
} DoubleLinkedList;

这些原始片段用于在大量结构和(现在)类中构造侵入式链表。我正试图通过大量的警告和要求来重新设计这组结构和支持功能。如果您想要背景，请阅读“------”分隔符下方的部分。

我的第一次尝试使用旧的 Node 结构并提供了一个新的类型安全的 List 模板:

template<typename Type, DoubleLinkedListNode Type::*MP>
struct NewDoubleLinkedList
{
   DoubleLinkedListNode m_anchor;
   //static const int Offset = ((unsigned int)(&(((Type *)0)->*MP))); ///<- broken

   void pushBack(Type *inst) { DoubleLinkedList_pushBack(this,&(inst->*MP)); }
   Type *begin() { return GetObjectFromMember(Type,*MP,m_anchor.m_next); }
   Type *end() { return GetObjectFromMember(Type,*MP,&m_anchor); }
   Type *getNext(Type *from) { return GetObjectFromMember(Type,*MP,from->*MP.m_next); }
};

这个模板是这样使用的:

struct MyClient {
   DoubleLinkedListNode m_serviceNode;
};

void testNewList()
{
   NewDoubleLinkedList<MyClient,&MyClient::m_serviceNode> newList;
   MyClient testClient;

   newList.pushBack(&testClient);

   MyClient *client = newList.begin();
   while(client != newList.end()) {
      ASSERT(client == &testClient);
      client = newList.getNext(client);
   }

   DoubleLinkedListNode_remove(&testClient.m_serviceNode);
}

这一切似乎都有效，并且正确地提示，除了这段代码:

   static const int Offset = ((unsigned int)(&(((Type *)0)->*MP))); 

仅当 instance->*MP 在编译时无法解析(即由于虚拟继承，它依赖于实例的虚拟表)时才会失败(在编译时)。

有什么方法可以修复这段代码，或者有什么替代方法可以防止与虚拟继承的潜在混淆吗？

如果您认为我完全走错了路，我已经在下面包含了(过长的)我正在做的事情的背景和我的要求)。否则就 停在这里。

---

首先，我要强调这是用 C 语言编写的现有代码。它被广泛使用，因此我需要一种允许缓慢推出的方法，而不必重写使用列表结构的每一段代码一次。

典型的用例通常是这样的:

struct MyService {
   ...  //other backend service data
   DoubleLinkedList m_clientList;
}

struct MyClient {
   ...  //other client service data
   MyService *m_serviceProvider;
   DoubleLinkedListNode m_serviceNode;
   DoubleLinkedListNode m_wrongServiceNode;
   void (*v_doSomethingLater)( MyClient *);  //"virtual" function
}

void Client_requestService( MyClient *client )
{
   ...  //prep work for service request
   DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList,
                              &client->m_serviceNode );
}

void Service_handleClients( MyService *service )
{
    DoubleLinkedListNode *iter = DoubleLinkedList_begin(&service->m_clientList);
    DoubleLinkedListNode *end = DoubleLinkedList_end(&service->m_clientList);
    while(iter != end) {
       MyClient *client = GetObjectFromMember( MyClient, m_serviceNode, iter );
       iter = DoubleLinkedListNode_getNext(iter);
       client->v_doSomethingLater(client);
    }
}

( super 邪恶，绝对无处不在)宏 GetObjectFromMember 接受(TypeName，memberName，memberPointer)并返回一个 Typed 指针，这样:

   TypeName *result = GetObjectFromMember(TypeName,memberName,memberPointer);
   ASSERT(&result->memberName == memberPointer);

对于真正的受虐狂来说，它看起来像这样:

  #define GetObjectFromMember(ObjectType,MemberName,MemberPointer) \
              ((ObjectType *)(((char *)MemberPointer) - ((char *)(&(((ObjectType *)0)->MemberName)))))

我的目标是找到侵入性最小的方法来编写一些模板，这些模板可以为这段代码中最容易出错的地方添加类型安全:

   DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList,
                              &client->m_serviceNode );

有人可能不小心使用了错误的节点，就像这样:

   DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList,
                              &client->m_wrongServiceNode );

编译干净并在回调阶段导致灾难:

   MyClient *client = GetObjectFromMember( MyClient, m_serviceNode, iter );
   client->v_doSomethingLater(client);

因为GetObjectFromMember派生的指针是错误的。

另一个主要问题是，由于我们现在使用的是 C++，GetObjectFromMember 仅在 TypeName 未通过虚拟继承到达 memberName 时才起作用。如果 GetObjectFromMember 不安全，我需要想出的任何解决方案在编译时失败。

因此，目标是:

o-> 允许继续使用现有的 DoubleLinkedListNode 类型名
o-> 如果可能，允许继续使用现有的 DoubleLinkedList 类型名称(我怀疑这是不可能的)
o-> 允许继续使用现有宏(DoubleLinkedListNode_pushBack 和(许多)其他宏)。
o-> 虚拟继承的编译时错误会破坏 GetObjectFromMember 的使用
o-> 使用案例:

DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList,
                           &client->m_serviceNode );

-> 可以自由替换为:

   client->m_serviceProvider.m_clientList.pushBack(client);

o-> 将 Service_handleClients 调用重新设计为如下所示的用例:

void Service_handleClients( MyFabulousService *service )
{
    MyClient *client = service->m_clientList.begin();
    while(client != service->m_clientList.end()) {
       MyClient *nextClient = service->m_clientList.getNext(client);
       client->v_doSomethingLater(client);
       client = nextClient;
    }
}

o-> 没有任何类型的动态分配。
o-> 与现有实现相比，(内存)或速度(cpu)没有显着(数量级)。

Answer 1

事实 1:表达式 &Type::member 的类型为 MemberType ClassType::*，其中 ClassType 是 所在的类member 已声明，不一定是 Type。

事实 2:仅当基类不是虚拟基类(也不是有歧义的根据)。在我看来，这正是您每次使用 GetObjectFromMember 时想要检查的内容。

那么怎么样:

// Precondition: mptr points at the specified member of a ClassType object.
// Precondition: member must not be in a virtual base class of ClassType.
//
// The second precondition is not an issue if the template arguments are
// deduced from an &AnyClass::member expression, since ClassType will
// deduce as the member's actual enclosing class.
template<typename ClassType, typename MemberType>
ClassType* ObjectContainingMember(MemberType ClassType::*member,
                                  MemberType *mptr)
{
    ClassType* dummy = 0;
    std::size_t member_offset =
        reinterpret_cast<char*>(&(dummy->*member)) -
        reinterpret_cast<char*>(dummy);
    char* obj_addr =
        reinterpret_cast<char*>(mptr) - member_offset;
    return reinterpret_cast<ClassType*>(obj_addr);
}

// Precondition: MemberPointer points at the specified member of
// an ObjectType object.  Returns a pointer to that ObjectType.
#define GetObjectFromMember(ObjectType,MemberName,MemberPointer)  \
    static_cast<ObjectType*>(ObjectContainingMember(              \
        &ObjectType::MemberName, MemberPointer))

因为事实 1，模板参数 ClassType 将被推断为声明成员的类。