Abstract class smart enough to know which variable to use for a specified struct

[tA-Kane]

I suppose this could go in Advanced Programming? But I feel it leans more towards general C++ knowledge.

I'm currently using an abstract, template<class T> class List, which allows me to add/remove structures (of type T) from a single doubly-linked list by adding two variables to the structure, T::Next and T::Previous. However, the downside to this is that it prevents the structure from being added to multiple linked lists. I cannot, for example, have one structure's instance (assume it has someone's name) in a list of employees and in a second list of clients. An employee could not be a client for the company s/he works for, and vice versa.

Would it be possible (and if so, how?) to tell the List class to use a different set of variable names (eg, tell it to use T->NextEmployee and T->NextClient)?

An obvious solution that I've thought of (but it's good to know other options, right?) would be to create another struct (maybe struct ListLinker), which contains the link pointers, and then simply have an array of that struct. Then, tell the List class which array index to use when adding/removing/etc. But there's also a catch to that: if the arrays are used extensively (which, in the future, they could), it could get to be a royal pain in the ass to keep track of which List "owns" which index, not to mention that it could waste a fair bit of memory if the array is statically allocated within T (since there are peaks of tens of thousands of instances of various T objects at runtime, it would really add up).

I suppose another solution could be to use some sort of database (such as SQL)... but I don't particularly like the overhead of that just for the ability to use multiple linked lists.

[Adron]

There are some macros to get a pointer to a struct from a pointer to a member. When you use those, you store a bunch of prev/next pointers inside a big struct, and make those pointers point to the actual prev/next pointers instead of pointing at the top of the struct. Then you use the macros to get from the prev/next pointer to the actual struct.

[tA-Kane]

Could you provide an example?

[Adron]

Ah, I was hoping someone else would. This is used a lot in the Windows DDK, so reading either the help file for that or checking some driver code that uses linked lists would show you how it is done.

The idea would be something like this:

Code Select Expand


struct LIST_NODE {
    LIST_NODE *next, *prev;
};

struct your_struct {
   LIST_NODE list1;
   LIST_NODE list2;
};

#define struct_from_member(ptr, str, mem) (str*)(((char*)ptr) - offsetof(str, mem))

LIST_NODE *list2ptr = get_struct_out_of_list2();
your_struct *structptr = struct_from_member(list2ptr, your_struct, list2);



[tA-Kane]

That looks quite good. Thanks.

I'm still open to any other ideas, if anyone has them though. 

[SecretShop]

You have 2 entities, a Client and an Employee and you want them to be in the same list?  Why not just make a person class and derive Client and Employee from it(making both of them classes instead of structs ofcourse) then just have a Person list?

[Joe[x86]]

I believe that the pointer to the struct is the pointer to the first object. Excuse my VB here, but I don't know how to do this in C(++).

Code Select Expand

Public Type ExampleStruct
    L1 As Long
    L2 As Long
    L3 As Long
    L4 As Long
End Type

Public Sub Main()
    Dim ExampleStructInstance as ExampleStruct
    Dim PtrStruct As Long, PtrL1 As Long, PtrL2 As Long, PtrL3 As Long, PtrL4 As Long
    PtrStruct = VarPtr(ExampleStructInstance)  '// VarPtr(Variant) is a built in function that returns a pointer
    PtrL1 = PtrStruct + 0
    PtrL2 = PtrStruct + 4
    PtrL3 = PtrStruct + 8
    PtrL4 = PtrStruct + 12
End Sub

[MyndFyre]

Stop doing "'//".  It's a waste of two characters.

Code Select Expand

struct ExampleStruct
{
    long L1;
    long L2;
    long L3;
    long L4;
};

int main(int argv, char **argc)
{
    ExampleStruct inst;
    long ptrStruct, ptrL1, ptrL2, ptrL3, ptrL4;
    ptrStruct = *(unsigned long *)inst;
    ptrL1 = ptrStruct;
    ptrL2 = ptrStruct + 4;
    ptrL3 = ptrStruct + 8;
    ptrL4 = ptrStruct + 12;
}

Did I mention "+ 0" is entirely useless?  Your code sucks, Joe.

Your code doesn't look right.  Let me think about this.

ptrStruct will have the value of L1 because you're dereferencing it as a long:

Code Select Expand

ptrStruct = * /* see the dereference operator there? */ (unsigned long*)inst;
Then ptrL1 will equal L1, ptrL2 will equal L1 + 4, ptrL3 will equal L1+8, and ptrL4 will equal L1+12.

You made the mistake of trying to mimic Joe's code.  This would be more accurate, I think:

Code Select Expand


int main(int argv, char **argc)
{
    ExampleStruct inst;
    long ptrStruct, ptrL1, ptrL2, ptrL3, ptrL4;
    ptrStruct = (long)inst; // don't forget that you don't want a signed/unsigned mismatch warning
    ptrL1 = ptrStruct;
    ptrL2 = ptrStruct + 4;
    ptrL3 = ptrStruct + 8;
    ptrL4 = ptrStruct + 12;
}
Then to write to the structure, you'd do this:

Code Select Expand


*((long*)ptrL2) = 12;

...if that doesn't make the compiler complain about an lvalue or something.

[FrOzeN]

Um, wouldn't it be easier to have one less variable?

Code Select Expand

int main(int argv, char **argc)
{
    ExampleStruct inst;
    long ptrL1, ptrL2, ptrL3, ptrL4;
    ptrL1 = (long)inst;
    ptrL2 = ptrL1 + 4;
    ptrL3 = ptrL2 + 4;
    ptrL4 = ptrL3 + 4;
}

[iago]

Um, wouldn't it be easier to have one less variable?

Code Select Expand

int main(int argv, char **argc)
{
    ExampleStruct inst;
    long ptrL1, ptrL2, ptrL3, ptrL4;
    ptrL1 = (long)inst;
    ptrL2 = ptrL1 + 4;
    ptrL3 = ptrL2 + 4;
    ptrL4 = ptrL3 + 4;
}

In general, when you're doing offsets like the way the code needs to be, you should start them all from the same base.  Sure, you're using less variables, but you're sacrificing a great deal of readability.  Readability is more important than code size, especially for something like this. 

I think the best way to do the offsets were the way Joe did it (with the +0, +4, +8, +12), because you can instantly see exactly what's going on. 

[tA-Kane]

You have 2 entities, a Client and an Employee and you want them to be in the same list? Why not just make a person class and derive Client and Employee from it(making both of them classes instead of structs ofcourse) then just have a Person list?

You're assuming that Client and Employees are separate objects, which is not the case. Just making both of them a subclass of Person would not inherintly solve the root problem: needing to be able to have a list of Clients and a list of Employees, and having a single object in both lists. What you're saying is to merge the Clients and Employees lists into a People list, which is not what I need.

Um, wouldn't it be easier to have one less variable?

Code Select Expand

int main(int argv, char **argc)
{
ExampleStruct inst;
long ptrL1, ptrL2, ptrL3, ptrL4;
ptrL1 = (long)inst;
ptrL2 = ptrL1 + 4;
ptrL3 = ptrL2 + 4;
ptrL4 = ptrL3 + 4;
}

The problem with all of those static offsets is that it's not quite portable, especially if pointers aren't 4-bytes long (such as on a 64-bit platform, which my employer has tossed around the idea of supporting). And also, if I'm not mistaken, the members of a class can be moved around by the compiler during compile-time.

[MyndFyre]

We were porting Joe's code through that entire situation.  There's pretty much no point to doing it this way when you just factor in that you have the ExampleStruct object and can just dereference a pointer to inst.