Link list problem

[Shwetabh]

Hi,
This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. Please try to see what can be done about the
following problem.

/* I have been given two structures */
struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */

Thanks in advance.

[Walter Roberson]

In article <11************ **********@g43g 2000cwa.googleg roups.com>,
Shwetabh <sh**********@g mail.com> wrote:

This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. /* I have been given two structures */
struct node
{
struct node *next;
} *temp; struct data
{
int a;
float b;
char c;
struct node s;
}; /* Now the question is to access the values of a,b,c using temp */

Is it possible that struct node is defined slightly differently, as

struct node
{
struct data *next;
} *temp;
If not then it can't be done without some kind of cheating, as
clearly anything accesses by temp will be a pointer.

There is, of course, ready cheating, such as creating a context in
which temp is a pointer to a struct data instead of a struct node.
--
Oh, to be a Blobel!

[Jonathan Bartlett]

Shwetabh wrote:

Hi,
This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. Please try to see what can be done about the
following problem.

/* I have been given two structures */
struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */

So you are saying that "temp" is a pointer into data at member "s"?

There is no portable solution, as there is no way to determine the
amount of padding used for structure members. You could guess at it by
doing:

void *v = temp;
v -= sizeof(char) + sizeof(float) + sizeof(int);
struct data *d = v;

But that would only work if the structs had no padding to them, which is
an invalid assumption.

Perhaps another possibility is to do:

struct data d;
void *dp = &d;
void *s = &d.s;
int diff = s - dp;

void *v = tmp;
v -= diff;
struct data *answer = v;

Even then you probably have some pretty platform-specific problems.

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

[Richard Bos]

Jonathan Bartlett <jo*****@eskimo .com> wrote:

Shwetabh wrote:

struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */
So you are saying that "temp" is a pointer into data at member "s"?

No, he isn't saying that. He probably _meant_ that, since without some
hint of that ilk the puzzle is unsolvable, but he didn't say it.
There is no portable solution, as there is no way to determine the
amount of padding used for structure members.

Yes, there is, for a known, declared structure: offsetof.

(No, I'm not giving any more hints.)

Richard

[John Cochran]

In article <11************ **********@g43g 2000cwa.googleg roups.com>,
Shwetabh <sh**********@g mail.com> wrote:

Hi,
This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. Please try to see what can be done about the
following problem.

/* I have been given two structures */
struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */

Thanks in advance.

Ick.
The first thing I'd say is "I hope the code at this company doesn't do
silly things like this."
The second thing is that I'd use the macro "offsetof" along with some creative
casting and pointer arithmetic to transform a "struct node *" into
a "stuct data *". The rest is trivial.

But once again, I'd want an assurance that the above silliness isn't standard
practice at the company you're applying for a job at.

[pete]

Shwetabh wrote:

Hi,
This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. Please try to see what can be done about the
following problem.

/* I have been given two structures */
struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */

Thanks in advance.

/* BEGIN new.c */

#include <stdio.h>

int main(void)
{
struct node {
struct node *next;
} *temp;
struct data {
int a;
float b;
char c;
struct node s;
};

struct data ds;
ds.a = 12345;
ds.b = 3.14f;
ds.c = 'X';
temp = (struct node *)&ds;
printf("%d\n%f\ n%c\n",
((struct data *)temp) -> a,
((struct data *)temp) -> b,
((struct data *)temp) -> c
);
return 0;
}

/* END new.c */

N869
6.2.5 Types
[#27] All pointers to structure types
shall have the same representation and alignment
requirements as each other.

6.3.2.3 Pointers
[#7] A pointer to an object or incomplete type may be
converted to a pointer to a different object or incomplete
type. If the resulting pointer is not correctly aligned
for the pointed-to type, the behavior is undefined.
Otherwise, when converted back again, the result shall
compare equal to the original pointer.

--
pete

[Cong Wang]

Shwetabh wrote:

Hi,
This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. Please try to see what can be done about the
following problem.

/* I have been given two structures */
struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */

Thanks in advance.

Hmm,it is easy.ANSI C defines a macro 'offsetof' in stddef.h.

/*GCC 3.2.3*/
#ifndef __cplusplus
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#else /* C++ */
/* The reference cast is necessary to thwart an operator& that might
 be applicable to MEMBER's type.See DR 273 for details.*/
#define offsetof(TYPE, MEMBER) (reinterpret_ca st <size_t> \
(&reinter pret_cast <char &>(static_ca st <TYPE *> (0)->MEMBER)))
#endif /* C++ */

[Netocrat]

On Mon, 18 Jul 2005 14:00:00 +0000, John Cochran wrote:

In article <11************ **********@g43g 2000cwa.googleg roups.com>,
Shwetabh <sh**********@g mail.com> wrote:

Hi,
This is a question asked to me in an interview.
I haven't been able to figure out an answer for
it. Please try to see what can be done about the
following problem.

/* I have been given two structures */
struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

/* Now the question is to access the values of a,b,c using temp */

Thanks in advance.

Ick.
The first thing I'd say is "I hope the code at this company doesn't do
silly things like this."

Why not? This is the way linked lists are implemented in the Linux
kernel. It's a good approach - embed the node in the data rather than
the other way around and hence do away with the need for a data
pointer. And it's portable.

[Richard Bos]

"Netocrat" <ne******@dodo. com.au> wrote:

On Mon, 18 Jul 2005 14:00:00 +0000, John Cochran wrote:

In article <11************ **********@g43g 2000cwa.googleg roups.com>,
Shwetabh <sh**********@g mail.com> wrote:

struct node
{
struct node *next;
} *temp;

struct data
{
int a;
float b;
char c;
struct node s;
};

Ick.
The first thing I'd say is "I hope the code at this company doesn't do
silly things like this."

Why not? This is the way linked lists are implemented in the Linux
kernel. It's a good approach - embed the node in the data rather than
the other way around and hence do away with the need for a data
pointer. And it's portable.

Myeah - but it would be clearer to have the node first, rather than
last. That way, when you've traversed the list (or, for that matter,
tree, or whatever structure; this trick works with more than lists), you
can simply do dataptr=(struct data *)nodeptr, and avoid fiddling with
offsetof or worse. That cast must work correctly, since a struct must
have the same address as its first member.

Richard

[Netocrat]

On Tue, 19 Jul 2005 09:50:51 +0000, Richard Bos wrote:

"Netocrat" <ne******@dodo. com.au> wrote:

On Mon, 18 Jul 2005 14:00:00 +0000, John Cochran wrote:

> In article <11************ **********@g43g 2000cwa.googleg roups.com>,
> Shwetabh <sh**********@g mail.com> wrote:
>>struct node
>>{
>> struct node *next;
>>} *temp;
>>
>>struct data
>>{
>> int a;
>> float b;
>> char c;
>> struct node s;
>>};
>
> Ick.
> The first thing I'd say is "I hope the code at this company doesn't do
> silly things like this."

Why not? This is the way linked lists are implemented in the Linux
kernel. It's a good approach - embed the node in the data rather than
the other way around and hence do away with the need for a data
pointer. And it's portable.

Myeah - but it would be clearer to have the node first, rather than
last. That way, when you've traversed the list (or, for that matter,
tree, or whatever structure; this trick works with more than lists), you
can simply do dataptr=(struct data *)nodeptr, and avoid fiddling with
offsetof or worse. That cast must work correctly, since a struct must
have the same address as its first member.

Totally agree when the data can only be a member of one list. But often
(as is the case in the linux kernel), objects are members of multiple
lists.