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

alignment question about pointer conversion

P: n/a
I want to implement a common list that can cantain any type of data,
so I declare the list as (briefly)

---------------------------------------
struct list
{
int data_size;
int node_num;
char nodes[]; //will be list_node1,list_node2...
};
struct list_node
{
int pre;
int next;
char data[]; //will contain any struct
};

-------------------------------------
The whole list buffer is large enough by malloc. The list will
manage datas like a list. All data has same type. But the type can be
any one.

When using, I memcpy different struct to list_node.data, and get
data by (strcut xxx *) list_node.data.

It seems that the list.nodes and list_node.data will both have
the problem of alignment.

How do I resolve the problem?

Dec 6 '06 #1
Share this Question
Share on Google+
10 Replies


P: n/a
"haomiao" <mi******@ustc.eduwrote:
# I want to implement a common list that can cantain any type of data,
# so I declare the list as (briefly)
#
# ---------------------------------------
# struct list
# {
# int data_size;
# int node_num;
# char nodes[]; //will be list_node1,list_node2...
# };
#
#
# struct list_node
# {
# int pre;
# int next;
# char data[]; //will contain any struct
# };
#
# -------------------------------------
# The whole list buffer is large enough by malloc. The list will
# manage datas like a list. All data has same type. But the type can be
# any one.
#
# When using, I memcpy different struct to list_node.data, and get
# data by (strcut xxx *) list_node.data.
#
# It seems that the list.nodes and list_node.data will both have
# the problem of alignment.

If you memcpy in and out, you can avoid alignment issues.

T value; struct list_node *p;
p = list_node_allocator(sizeof p+sizeof value);

memcpy(p->data,&value,sizeof value);

memcpy(&value,p->data,sizeof value);

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Who's leading this mob?
Dec 6 '06 #2

P: n/a
haomiao <mi******@ustc.eduwrote:
I want to implement a common list that can cantain any type of data,
so I declare the list as (briefly)
---------------------------------------
struct list
{
int data_size;
int node_num;
char nodes[]; //will be list_node1,list_node2...
Is this going to be an array of pointers to nodes or just a memory
area for were all nodes are going to be stored?

And do you understand that this can only done with C99? C89 didn't
support "flexible array members".
};
struct list_node
{
int pre;
int next;
Typically, linked lists are implemented using pointers to the
previous and next element of the list...
char data[]; //will contain any struct
};
-------------------------------------
The whole list buffer is large enough by malloc. The list will
manage datas like a list. All data has same type. But the type can be
any one.
It would help if you would show a bit of the code you're using to
do all this...
When using, I memcpy different struct to list_node.data, and get
data by (strcut xxx *) list_node.data.
It seems that the list.nodes and list_node.data will both have
the problem of alignment.
Yes, definitely. For the list structure, if you have an array of
pointers to nodes, you could avoid the problem by using a flexible
array of struct list_node pointers instead of just a char array.
That should make sure that there are no alignment problems.
How do I resolve the problem?
Either by using memcpy() to copy the data out of the structure to
some correctly aligned memory or by using the method you can also
use with C89, i.e. using a void pointer instead of the flexible
array and allocating memory which you then set that pointer to.

Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de
Dec 6 '06 #3

P: n/a
Jens Thoms Toerring wrote:
haomiao <mi******@ustc.eduwrote:
I want to implement a common list that can cantain any type of data,
so I declare the list as (briefly)
---------------------------------------
struct list
{
int data_size;
int node_num;
char nodes[]; //will be list_node1,list_node2...

Is this going to be an array of pointers to nodes or just a memory
area for were all nodes are going to be stored?
A memory area for were all nodes are going to be stored.
>
And do you understand that this can only done with C99? C89 didn't
support "flexible array members".
Yes, I am using C99.

>
};
struct list_node
{
int pre;
int next;

Typically, linked lists are implemented using pointers to the
previous and next element of the list...
I forgot, the list will be in the share memory, so pre and next
be the relative address of element. Here they are the subscript
of the list.nodes.

>
char data[]; //will contain any struct
};
-------------------------------------
The whole list buffer is large enough by malloc. The list will
manage datas like a list. All data has same type. But the type can be
any one.

It would help if you would show a bit of the code you're using to
do all this...
for example, if a struct as
struct s1{...};
then the list memory is like this, suppose list is like v0->v1->v2...

---------------------
data_size // sizeof(struct s1)
node_num // assume be 10
--------------------- node0
pre=-1 // -1 means no pre
next=2 // node2
struct s1 v0 // by using memcpy(node0->data,&v0,sizeof(struct
s1)
--------------------- node1
pre=2 // node2
next=3 // node3
struct s1 v2
--------------------- node2
pre=0 // node0
next=1 // node1
struct s1 v1
---------------------
...

when using, for example, to get nth element
--list.c----------------------------------
char * get_nth_data(struct list * list,int n){
char * addr;
struct list_node *node;
int node_size = sizeod(struct list_node)+list->data_size;
int node_index = 0;
for (int i=0;i<n;i++){
addr = list->nodes + node_index * node_size;
node = (struct list_node *)addr; // have alignment problem
node_index = node->next;
}
return node->data;
}
--using.c----------------------------------
struct s1 *v = (struct s1 *)get_nth_data(list,n); // have alignment
problem
.....
-------------------------------------------

I want this list frame can be used for any struct like s1 list,s2
list,s3 list.

But now it seems have some alignment problem.
>
When using, I memcpy different struct to list_node.data, and get
data by (strcut xxx *) list_node.data.
It seems that the list.nodes and list_node.data will both have
the problem of alignment.

Yes, definitely. For the list structure, if you have an array of
pointers to nodes, you could avoid the problem by using a flexible
array of struct list_node pointers instead of just a char array.
That should make sure that there are no alignment problems.
How do I resolve the problem?

Either by using memcpy() to copy the data out of the structure to
some correctly aligned memory or by using the method you can also
use with C89, i.e. using a void pointer instead of the flexible
array and allocating memory which you then set that pointer to.
For the efficiency,I want to directly use pointer than the memcpy.

And in my environment, I get a large shm before hand.
In this shm, there are many list like s1 list, s2 list ...,in each
subarea.

So, how can I modify my data structure to satisfy the alignment
requiement?

>
Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de
Dec 6 '06 #4

P: n/a
haomiao <mi******@ustc.eduwrote:
Jens Thoms Toerring wrote:
haomiao <mi******@ustc.eduwrote:
I want to implement a common list that can cantain any type of data,
so I declare the list as (briefly)
---------------------------------------
struct list
{
int data_size;
int node_num;
char nodes[]; //will be list_node1,list_node2...
Is this going to be an array of pointers to nodes or just a memory
area for were all nodes are going to be stored?
A memory area for were all nodes are going to be stored.
And do you understand that this can only done with C99? C89 didn't
support "flexible array members".
Yes, I am using C99.
};
struct list_node
{
int pre;
int next;
Typically, linked lists are implemented using pointers to the
previous and next element of the list...
I forgot, the list will be in the share memory, so pre and next
be the relative address of element. Here they are the subscript
of the list.nodes.
I see.
char data[]; //will contain any struct
};
-------------------------------------
The whole list buffer is large enough by malloc. The list will
manage datas like a list. All data has same type. But the type can be
any one.
It would help if you would show a bit of the code you're using to
do all this...
for example, if a struct as
struct s1{...};
then the list memory is like this, suppose list is like v0->v1->v2...
---------------------
data_size // sizeof(struct s1)
node_num // assume be 10
--------------------- node0
pre=-1 // -1 means no pre
next=2 // node2
struct s1 v0 // by using memcpy(node0->data,&v0,sizeof(struct
s1)
--------------------- node1
pre=2 // node2
next=3 // node3
struct s1 v2
--------------------- node2
pre=0 // node0
next=1 // node1
struct s1 v1
---------------------
...
when using, for example, to get nth element
--list.c----------------------------------
char * get_nth_data(struct list * list,int n){
char * addr;
struct list_node *node;
int node_size = sizeod(struct list_node)+list->data_size;
int node_index = 0;
for (int i=0;i<n;i++){
addr = list->nodes + node_index * node_size;
node = (struct list_node *)addr; // have alignment problem
node_index = node->next;
}
return node->data;
}
--using.c----------------------------------
struct s1 *v = (struct s1 *)get_nth_data(list,n); // have alignment
problem
....
-------------------------------------------
I want this list frame can be used for any struct like s1 list,s2
list,s3 list.
But now it seems have some alignment problem.
When using, I memcpy different struct to list_node.data, and get
data by (strcut xxx *) list_node.data.
It seems that the list.nodes and list_node.data will both have
the problem of alignment.
Yes, definitely. For the list structure, if you have an array of
pointers to nodes, you could avoid the problem by using a flexible
array of struct list_node pointers instead of just a char array.
That should make sure that there are no alignment problems.
How do I resolve the problem?
Either by using memcpy() to copy the data out of the structure to
some correctly aligned memory or by using the method you can also
use with C89, i.e. using a void pointer instead of the flexible
array and allocating memory which you then set that pointer to.
For the efficiency,I want to directly use pointer than the memcpy.
And in my environment, I get a large shm before hand.
In this shm, there are many list like s1 list, s2 list ...,in each
subarea.
So, how can I modify my data structure to satisfy the alignment
requiement?
I don't think there's any portable way you can achieve all your
objectives. Already having the structures packed as tightly as
possible would make it impossible to get the alignment right under
all circumstances. But, worse. there's no standard way to determine
the alignment requirements at run-time I would be aware of. So you
would either have to memcpy() to properly aligned memory (did you
check if this copying is really a serious bottleneck?) or to use
some non-standard way to determine the alignment requirements at
run-time (e.g. gcc has the __alignof__ keyword for this) and then
make sure the addresses for all the structures you store are aligned
accordingly (can be tricky;-). Sorry, but I don't think there are
any other alternatives.
Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de
Dec 6 '06 #5

P: n/a
thanks for your advices!

Dec 7 '06 #6

P: n/a
Jens Thoms Toerring:
>But, worse. there's no standard way to determine
the alignment requirements at run-time I would be aware of.
#include <stddef.h/* offsetof() */
#define align_of(T) \
offsetof(struct { char provoke_padding; T data; }, data)

align_of(T) yields the alignment of type T or at least an upper
bound for it.

--
Bitte in die Adressierung auch meinen |Please put my full name also into
Vor- u. Nachnamen stellen z.B. |the recipient like
Friedhelm Waitzmann <xxx@example>, (Friedhelm Waitzmann) xxx@example,
"Waitzmann, Friedhelm" <xxx@example>
Dec 18 '06 #7

P: n/a
Friedhelm Usenet Waitzmann <us******************@spamgourmet.comwrote:
Jens Thoms Toerring:
But, worse. there's no standard way to determine
the alignment requirements at run-time I would be aware of.

#include <stddef.h/* offsetof() */
#define align_of(T) \
offsetof(struct { char provoke_padding; T data; }, data)

align_of(T) yields the alignment of type T or at least an upper
bound for it.
Better to read the whole thread...

The point was to do this where T is itself a struct with a C99 flexible
array member. For such structs (and AFAICT only for such structs), this
trick doesn't work.

Richard
Dec 18 '06 #8

P: n/a
haomiao:
I want to implement a common list that can cantain any type of data,
so I declare the list as (briefly)
>---------------------------------------
struct list
{
int data_size;
int node_num;
char nodes[]; //will be list_node1,list_node2...
};
>struct list_node
{
int pre;
int next;
char data[]; //will contain any struct
};
>-------------------------------------
The whole list buffer is large enough by malloc. The list will
manage datas like a list. All data has same type. But the type can be
any one.
When using, I memcpy different struct to list_node.data, and get
data by (strcut xxx *) list_node.data.
It seems that the list.nodes and list_node.data will both have
the problem of alignment.
How do I resolve the problem?
I think, one must fiddle around not only with the size of the
data items that one wants to store in the list, but also with the
alignment contraint of the data items. The alignment of the data
items affects their offset in the list nodes and alignment and
size of the list nodes. The alignment of the list nodes affects
the offset of the first list node in the list.

(Untested)

#include <stddef.h/* offsetof */

#define alignof(T) \
offsetof(struct { char provoke_padding; T data; }, data);
/* Unfortunately, alignof(T) does not work, when T is a struct
* with a flexible array member.
*/

struct list
{
size_t data_offset;
/* offsetof real data in a real list_node; it is always >=
* offsetof(struct list_node, data), and it is a multiple
* of the alignment of the real data.
*/
size_t list_node_offset;
/* offsetof first real list_node in struct list; it is
* always >= offsetof(struct list, nodes), and it is a
* multiple of the alignment of a real list_node.
*/
size_t list_node_size;
/* sizeof the real list_nodes in struct list; it is the
* offset of the char following the last char of the real
* data rounded up to a multiple of the alignment of a real
* list_node.
*/
size_t node_num;
unsigned char nodes[];
/* I suggest unsigned char, so that all bit patterns here
* are valid values i.e. no trap representations.
*/
};

struct list_connector
{
int pre;
int next;
};

/* struct list_node
* {
* struct list_connector lc;
* unsigned char data[];
* };
*
* struct list_node is not used in the program. It merely shows,
* that the data is stored in the characters following the
* list connector.
*/
};

static size_t round_up(size_t what, size_t unit)
{
size_t remainder = what % unit;

return what + (remainder != 0? unit - remainder: 0);
}

static size_t smallest_common_multiple(size_t a, size_t b)
{
size_t gcd; /* greatest common divisor */

if (a b)
{
size_t t; t = a; a = b; b = t;
}
/* a <= b */
{
size_t u = a, v = b;
/* u <= v; */
while ( u != 0)
{
v %= u;
{
size_t t = u; u = v; v = t;
}
}
gcd = v;
}
return a / gcd * b;
}

/* list_init_for_real_data() initializes .data_offset,
* .list_node_offset, and .list_node_size. size_of_data and
* alignof_data provide the size and the alignment of the type of
* the real data that will be stored in the list.
*
* sizeof_data must be a multiple of alignof_data.
*/
void list_init_for_real_data(struct list *lp,
size_t sizeof_data, size_t alignof_data)
{
/* As the real data in list nodes must be aligned to multiples of
* alignof_data, round the offset of .data ( == sizeof(struct
* list_connector)) up to the next multiple of alignof_data.
*/
lp->data_offset =
round_up(sizeof (struct list_connector), alignof_data);
/* The alignment for a real list_node must be so that each of
* its members (.lc and the real data) can be accessed
* with no problems. Therefore
* smallest_common_multiple(alignof (struct list_connector),
* alignof_real_data)) is considered suitable for aligning a
* real list_node.
*/
{
size_t alignof_real_list_node =
smallest_common_multiple(alignof(struct list_connector),
alignof_data);

lp->list_node_offset =
round_up(offsetof(struct list, nodes),
alignof_real_list_node);

lp->list_node_size =
round_up(lp->data_offset + sizeof_data,
alignof_real_list_node);
}
}

/* list_offsetof_node(lp, size_t n) returns the offsetof the real
* list_node #n (counted from 0)
*/
size_t list_offsetof_node(struct list const *lp, size_t n)
{
return (lp->list_node_offset + n * lp->list_node_size);
}

/* list_access_node(lp, size_t n) returns a pointer to the real
* list_node #n (counted from 0)
*/
struct list_connector *list_access_node(struct list const *lp, size_t n)
{
return
(struct list_connector *)
((char *)lp + list_offsetof_node(lp, n));
}

/* list_node_access_data(lp, lnp) returns a
* pointer to the real data in the real list node *lnp. (lp is
* needed to provide the offsetof the real data in *lnp.)
*/
void *list_node_access_data(struct list const *lp,
struct list_connector const *lnp)
{
return (void *)((char *)lnp + lp->data_offset);
}

How to use it: Example: A List of 100 Doubles.

struct list *lp;

* Create and initialize list storage:
{
/* Create a list template that is used only once for
* list_offsetof_node() to calculate the size of the
* storage to be malloc()ed.
*/
struct list template;
list_init_for_real_data(&template, sizeof (double),
alignof(double));
lp = malloc(list_offsetof_node(&template, 100));
}
list_init_for_real_data(lp, sizeof (double),
alignof(double));

* Store 1.5 in node #42:
{
struct list_connector *lnp = list_access_node(lp, 42);
*(double *)list_node_access_data(lp,lnp) = 1.5;
}

--
Bitte in die Adressierung auch meinen |Please put my full name also into
Vor- u. Nachnamen stellen z.B. |the recipient like
Friedhelm Waitzmann <xxx@example>, (Friedhelm Waitzmann) xxx@example,
"Waitzmann, Friedhelm" <xxx@example>
Dec 22 '06 #9

P: n/a
Thanks, this example should reslove my problem in practice.

And I have another question.
#define alignof(T) \
offsetof(struct { char provoke_padding; T data; }, data);
/* Unfortunately, alignof(T) does not work, when T is a struct
* with a flexible array member.
*/
My question is :
Is this macro portable(even not think about flexible array)?
>From the C99 stardard, it seems that the macro returns just the offset
of 'data' from the beginning of the struct.

So, only if the alignment of the struct is multiple of the aligment of
T, the macro returns the correct allignment of T. But from the
standard, this 'if ' can not be derived.

Or, as Jens's advice, using non-standard way like __alignof__ .

Dec 23 '06 #10

P: n/a
haomiao wrote:
Thanks, this example should reslove my problem in practice.

And I have another question.
#define alignof(T) \
offsetof(struct { char provoke_padding; T data; }, data);
/* Unfortunately, alignof(T) does not work, when T is a struct
* with a flexible array member.
*/

My question is :
Is this macro portable(even not think about flexible array)?
From the C99 stardard, it seems that the macro returns just the offset
of 'data' from the beginning of the struct.
Correct.
So, only if the alignment of the struct is multiple of the aligment of
T, the macro returns the correct allignment of T. But from the
standard, this 'if ' can not be derived.
The alignment of a struct must be a common multiple of the alignment of
its members. Otherwise, you could not have an array of that struct
(because either a member of the first, or a member of the second
element would be misaligned). The provided alignof macro is guaranteed
to evaluate to either the alignment of T, or a multiple of it. In
practice, you won't get a multiple of it, and even if you do, it's safe
(though not optimal) to treat that as the alignment.
Or, as Jens's advice, using non-standard way like __alignof__ .
Dec 23 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.