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>
