StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POImposing type safety on existing C intrusive linked lists
primarykey
Id
20112704
data
AcceptedAnswerId
20124000
AnswerCount
1
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-11-21T04:45:01.210
FavoriteCount
0
LastActivityDate
2013-11-22T01:29:22.970
LastEditDate
2013-11-21T05:02:02.797
LastEditorUserId
2544218
OwnerUserId
2544218
ParentId
0
PostTypeId
1
Score
0
ViewCount
86
LastEditorDisplayName
text
Body
I have a fairly simple set of doubly linked list helpers centered around two basic structs: <pre><code>typedef struct DoubleLinkedListNode_struct { struct DoubleLinkedListNode_struct *m_prev; struct DoubleLinkedListNode_struct *m_next; } DoubleLinkedListNode; typedef struct DoubleLinkedList_struct { DoubleLinkedListNode m_anchor; } DoubleLinkedList; </code></pre> These primitive pieces are used to construct intrusive linked lists in a whole host of structures and (now) classes. I'm attempting to rework this set of structures and supporting functions with a whole ream of caveats and requirements. If you want the background read the part below the '------' break. My first attempt uses the old Node structures and provides a new type-safe List template: <pre><code>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); } }; </code></pre> And this template is used like this: <pre><code>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); } </code></pre> This all seems to work, and complains correctly, except this code: <pre><code> static const int Offset = ((unsigned int)(&(((Type *)0)->*MP))); </code></pre> which is intended to fail (at compile time) only if instance->*MP can't be resolved at compile time (i.e. it relies on the instance's virtual table, due to virtual inheritance). Is there some way I can fix this code, or some alternate way to prevent potential confusion with virtual inheritance? On the off chance you think I'm on the complete wrong path I've included the (overly long) background on what I'm doing and my requirements below). Otherwise just stop here. <hr> First, I'm going to stress that this is existing code written in C. It's used all over the place so I need a method which allows slow roll-out without having to rewrite every piece of code that uses the list structures at once. The typical use case usually goes something like this: <pre><code>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); } } </code></pre> The (uber evil and absolutely everywhere) macro GetObjectFromMember takes (TypeName,memberName,memberPointer) and returns a Typed pointer such that: <pre><code> TypeName *result = GetObjectFromMember(TypeName,memberName,memberPointer); ASSERT(&result->memberName == memberPointer); </code></pre> For the truly masochistic it looks like this: <pre><code> #define GetObjectFromMember(ObjectType,MemberName,MemberPointer) \ ((ObjectType *)(((char *)MemberPointer) - ((char *)(&(((ObjectType *)0)->MemberName))))) </code></pre> My goal is to find the least intrusive way to write some templates that can add type safety to the spots in this code most prone to error: <pre><code> DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList, &client->m_serviceNode ); </code></pre> Where someone might accidentally use the wrong node, like this: <pre><code> DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList, &client->m_wrongServiceNode ); </code></pre> which compiles cleanly and leads to a catastrophe during the callback phase where we do: <pre><code> MyClient *client = GetObjectFromMember( MyClient, m_serviceNode, iter ); client->v_doSomethingLater(client); </code></pre> Since the pointer derived by GetObjectFromMember will be wrong. The other major problem is that since we are now doing C++, GetObjectFromMember works only if TypeName does not reach memberName via virtual inheritance. I need whatever solution I come up with to fail at compile time if GetObjectFromMember isn't safe. So, the goals are: o-> Allow continued use of the existing DoubleLinkedListNode typename o-> Allow continued use of the existing DoubleLinkedList typename if possible (I suspect this isn't possible) o-> Allow continued use of the existing macros (DoubleLinkedListNode_pushBack and (many) others). o-> Compile time errors for virtual inheritance which breaks the GetObjectFromMember usage o-> Use case where this: <pre><code>DoubleLinkedList_pushBack( &client->m_serviceProvider.m_clientList, &client->m_serviceNode ); </code></pre>   -> can be freely replaced with this: <pre><code> client->m_serviceProvider.m_clientList.pushBack(client); </code></pre> o-> Use case where the Service_handleClients call is reworked to look something like: <pre><code>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; } } </code></pre> o-> No dynamic allocation of any kind. o-> Not significantly (order of magnitude) larger (memory) or slower (cpu) than existing implementation.
Tags
<c++>
Title
Imposing type safety on existing C intrusive linked lists
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USSpeed8ump
UserOwnerUserId
1. USSpeed8ump
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.