By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,987 Members | 1,552 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,987 IT Pros & Developers. It's quick & easy.

how do we read heterogenous linklist?

P: 3
While creating a heterogenous linklist we know that we use void pointer. But when it comes the time to read the information.
How do we exactly do that?( means
while reading how do we figure out to what datatype does the data belong)
Nov 3 '10 #1
Share this Question
Share on Google+
11 Replies


100+
P: 256
I'd say you embed some type identifier into your list node type. An int or enum would do, then you can see that id and know which type of thing is in that node.

Also, I'm assuming you're writing C code? If you have C++ available you shouldn't be writing lists.
Nov 3 '10 #2

Oralloy
Expert 100+
P: 983
Well, if you're writing in C++, then you can just use inheritence and virtual methods to safely control the elements of the list. Meaning that you should never have to explicitly test the type of an "element".

In C, you have to identify your elements somehow. As mac11 suggested, an effective way to do this is to build all of your elements as extensions of a common model, which has a "type" as its first attribute.

For example:
Expand|Select|Wrap|Line Numbers
  1. enum MyType
  2. {
  3.   TypeA,
  4.   TypeB,
  5. };
  6.  
  7. struct elementBase
  8. {
  9.   MyType theType;
  10. };
  11.  
  12. struct elementA
  13. {
  14.   struct elementBase;
  15.   ...more here...
  16. };
  17.  
  18. struct elementB
  19. {
  20.   struct elementBase;
  21.   ...more here...
  22. };
It's a model I've used successfully in the past. The elegant part is that it lets you address everything as a struct elementBase. The pain is that it requires that you be careful about type casting.

Good Luck!
Nov 3 '10 #3

Expert 100+
P: 2,396
Use a union for the various heterogenous types and you can avoid the type casts:
Expand|Select|Wrap|Line Numbers
  1. struct hetero {
  2.    struct hetero *next;
  3.    enum { TYPE1=1, TYPE2, ... } theType;
  4.    union {
  5.       struct { ... } struct1;
  6.       struct { ... } struct2;
  7.       ...
  8.       } body;
  9.    };
Nov 4 '10 #4

P: 3
Thanks Everyone,
I said exactly what Mac has said, but that fellow (who asked me this and was discussing) was saying something about object in structure, which i wasn't sure of neither he.

Can we use something like object in the structure.
if yes how? what would be code snap?
Nov 4 '10 #5

Oralloy
Expert 100+
P: 983
unconquerable,

I'm not sure I understand that. Can you give us an example of what you need?

Thanks.
Nov 4 '10 #6

100+
P: 256
C doesn't have objects, it has structs. Oralloy and donbock gave example pseudo-code above.
Nov 5 '10 #7

Oralloy
Expert 100+
P: 983
@mac11 - I've done object oriented code in C using the method outlined; the parts I didn't include were the idea of a constructor chain and use of strongly typed function pointers to provide effective virtual methods. If you build your system carefully, use accessor methods, and the like, then you can construct a very effective, typesafe object system in C.

@unconquorable - there are many flavours of object systems in the software world. Because C uses the "struct" as its basic object. The enum is not an object, for all that it looks like one. An "enum" is an abstracted memory mapping mechanism; one which radically simplifies writing types of program. What you don't get with C are directly implemented inheritence, methods, polymorphism, and overloading. C++ extends C to provide these "OO" capabilities. Neither C or C++ provides direct implementation of prototypical object behaviour.

By the way, structures are first class objects in C. For example, in this code I use no pointers, even though I send Complex number objects to the function add, and recieve a Complex object as the result of the computation:
Expand|Select|Wrap|Line Numbers
  1. /*
  2. **  demo.c
  3. **    demonstrate first class objects under C
  4. */
  5.  
  6. #include <stdio.h>
  7.  
  8. /*******************************/
  9.  
  10. struct Complex
  11. {
  12.   double real;
  13.   double imag;
  14. };
  15.  
  16. typedef struct Complex Complex;
  17.  
  18. /*******************************/
  19.  
  20. Complex add(Complex first, Complex second)
  21.  
  22. /*******************************/
  23.  
  24. int main(int argc, char **argv, char **envv)
  25. {
  26.   Complex this = { 1.0, 2.0 };
  27.   Complex that = { 5.0, 6.0 };
  28.  
  29.   Complex sum;
  30.  
  31.   sum = add(this, that);
  32.  
  33.   printf("sum = (%f, %f)\n", sum.real, sum.imag);
  34.  
  35.   return 0;
  36. }
  37.  
  38. /*******************************/
  39.  
  40. Complex add(Complex first, Complex second)
  41. {
  42.   Complex result = { 0.0, 0.0 };
  43.   result.real = first.real + second.real;
  44.   result.imag = first.imag + second.imag;
  45.   return result;
  46. }
  47.  
  48. /*******************************/
Cheers!
Nov 9 '10 #8

Expert 100+
P: 2,396
Expand|Select|Wrap|Line Numbers
  1. Complex add(Complex first, Complex second);
I'm veering off topic, but about 15 years ago I used a C compiler that burned me -- it implemented functions that return structs in a way that was nonreentrant. The consequence was intermittent errors that took me forever to find. Thus, my C functions never return composite types (structs or unions). (I can hold a grudge!)
Nov 9 '10 #9

Oralloy
Expert 100+
P: 983
@donbock,

Ouch! Getting burned by a compiler bug absolutely sucks.

I found an (in retrospect) amusing memory allocation bug in the HP/UX FORTRAN compiler about 20 years ago. I had developed a C++ based, IP networked, nulti-threading front-end to a large FORTRAN application suite that the company sold. I hadn't noticed, but "my" code was leaking memory, and would crash after a million or so transactions. Extensive analysis and instrumentation of my code demonstrated to me that I didn't have a memory leak in my C++ code. So, to find the bug, I ended up looking at a linker map of the program to find all users of malloc(). Well....it turns out that one of our FORTRAN modules was calling malloc(), but not free(). There wasn't a call to malloc() in the FORTRAN source, so I generated an assembly code listing of the compiled module to figure out where it was coming from. To make a long story short, the compiler was playing dynamic memory with FORTRAN modules which had entrypoints.

So yeah, I completely understand your grudge. And when it dies, make sure you stuff it and mount it over your mantelpiece.

Cheers!
Nov 9 '10 #10

Expert 100+
P: 2,396
No compiler bug. The [C89] C Standard does not offer any guarantees regarding reentrant code or thread-safety.
Nov 11 '10 #11

Oralloy
Expert 100+
P: 983
Ahhh, yes. You remind me of the various options that were available for PL/I functions - I know that recursive was one of them; and I don't recall about reentrant.

Back in the good 'ole days of 200 users on IBM 360s and 370s with fast (25MHz) CPUs.
Nov 11 '10 #12

Post your reply

Sign in to post your reply or Sign up for a free account.