manipulating void* in array

[Stijn van Dongen]

A question about void*. I have a hash library where the hash create
function accepts functions
unsigned (*hash)(const void *a)
int (*cmp) (const void *a, const void *b)

The insert function accepts a void* key argument, and uses the
functions above to store this argument. It returns something (linked to
the key) that the caller can store a value in. The actual key argument
is always of the same pointer type (as seen in the caller, say foo*).

Now I would like to have a function, say hash_keys, which returns all
keys in the hash as a pointer to a malloced array of void*. However,
there is not really a type I can use. I see two possible solutions.
The first is to typedef a struct containing a void pointer:

typedef struct {
void* pp;
} genpp;

and have hash_keys return genpp* (the size could be written in an int*
argument
to hash_keys). This would make accessing the keys cumbersome.

Solution 2) is illegal C (I think), but it's tempting. hash_keys would
construct an array of void*-sized elements and copy its key pointers
there using char* arithmetic. It would return void* and the caller
would cast it to foo**. For one thing, this assumes sizeof(void*) is
sizeof(foo*) for all possible foo. For another, I see nothing in the
standard on void* that would support any of this. However, it feels as
if approach 2) is conceptually extremely similar to the first and I
suspect it would work on nearly all platforms/compilers.

The questions then are,

1. Did I miss another solution where hash_keys creates some array?
2. Is my assessment of 2) correct?
3. On what kind of platforms/compilers would 2) fail? Outside the scope
of this newsgroup, I know, but perhaps some kind soul can comment.

regards,
Stijn

 

[S.Tobias]

Your description is very vague, you'd better post some pseudo-code
to illustrate your problem (but please, as little as necessary).
I'll do my best.

A question about void*. I have a hash library where the hash create
function accepts functions
unsigned (*hash)(const void *a)
int (*cmp) (const void *a, const void *b)

The insert function accepts a void* key argument, and uses the
functions above to store this argument. It returns something (linked to
the key) that the caller can store a value in.

You mean the caller first inserts a key, and then fills in the rest
of the data? It doesn't sound like a good interface. Better compute
everything before inserting; insert function needn't return anything.

The actual key argument
is always of the same pointer type (as seen in the caller, say foo*).

If you operate on one data type (foo), then there's no advantage in
having void* pointers; use foo* in `hash' and `cmp' (I've noticed
they don't take size argument, therefore they must know the type,
or at least the size, of data they work on), and others. Use void* when
you need generic pointer, when the data you work on is unknown.

Now I would like to have a function, say hash_keys, which returns all
keys in the hash as a pointer to a malloced array of void*.

As above, you could return an array of `foo*'.

However,
there is not really a type I can use.
Why?

I see two possible solutions.
The first is to typedef a struct containing a void pointer:

typedef struct {
void* pp;
} genpp;

and have hash_keys return genpp* (the size could be written in an int*
argument
to hash_keys). This would make accessing the keys cumbersome.

There's no point in returning a struct having only one member. Return
the member.

Some propositions:

/* return array of void* (actually, pointer to its first element)
and it's size in `*size' */
void* hash_keys(size_t *size);

/* return array of void* in `keys' argument, and its size in
the return value; basically same as above, but the meaning
of arguement and return value is reversed */
size_t hash_keys(void* *keys);

/* return array of void*, N+1 elements, the last is null ptr */
void* hash_keys(void);

/* return array and its size as a pair in a struct */
struct { void* a; size_t s; } hash_keys(void);

Solution 2) is illegal C (I think), but it's tempting. hash_keys would
construct an array of void*-sized elements and copy its key pointers
there using char* arithmetic.

There's no reason for that, you should just assign one type to another,
an automatic conversion will be performed (no need for casting).

void *pv;
foo *pf;
pv = pf; //okay
pf = pv; //okay

It would return void* and the caller
would cast it to foo**.

I don't quite get what you think here, but I think you think wrong.

For one thing, this assumes sizeof(void*) is
sizeof(foo*) for all possible foo.

You can never assume that (unless `foo' is `char', which is probably
not what you have).

For another, I see nothing in the
standard on void* that would support any of this. However, it feels as
if approach 2) is conceptually extremely similar to the first and I
suspect it would work on nearly all platforms/compilers.

I don't see much difference between them. They differ in how
the values are stored in the array.

I don't quite understand what your problem is: is it how to return
an array to the caller, or how to store values in it? You need
to post some code to explain it.

The questions then are,

1. Did I miss another solution where hash_keys creates some array?
2. Is my assessment of 2) correct?

I think solution 2 had unnecessary flaws. You need to explain more
what your real problem is.

3. On what kind of platforms/compilers would 2) fail? Outside the scope
of this newsgroup, I know, but perhaps some kind soul can comment.

If the code is written in a portable manner, then it will fail only
on a broken implementation. If it isn't, It may fail on the same
platform of yours tomorrow, and always on your customers' machines
while you're not watching.

 

[Dave Thompson]

A question about void*. I have a hash library where the hash create
function accepts functions
unsigned (*hash)(const void *a)
int (*cmp) (const void *a, const void *b)

The insert function accepts a void* key argument, and uses the
functions above to store this argument. It returns something (linked to
the key) that the caller can store a value in. The actual key argument
is always of the same pointer type (as seen in the caller, say foo*).

Now I would like to have a function, say hash_keys, which returns all
keys in the hash as a pointer to a malloced array of void*. However,
there is not really a type I can use. I see two possible solutions.
The first is to typedef a struct containing a void pointer:

typedef struct {
void* pp;
} genpp;

and have hash_keys return genpp* (the size could be written in an int*
argument
to hash_keys). This would make accessing the keys cumbersome.

Solution 2) is illegal C (I think), but it's tempting. hash_keys would
construct an array of void*-sized elements and copy its key pointers
there using char* arithmetic. It would return void* and the caller
would cast it to foo**. For one thing, this assumes sizeof(void*) is
sizeof(foo*) for all possible foo. For another, I see nothing in the
standard on void* that would support any of this. However, it feels as
if approach 2) is conceptually extremely similar to the first and I
suspect it would work on nearly all platforms/compilers.

An array of void*, addressed as void**, and an array of struct
containing only void*, addressed as genpp*, are indeed similar. And in
fact are very likely (though not guaranteed) to be laid out the same.

But the individual element pointers, of type void* in either case, are
NOT guaranteed to be laid out the same as some other (data) pointer
type foo*. So treating either of these as (casting to) foo** and
trying to use it is not safe, and I know of systems, though only a
few, where it won't work. Note that even if different pointers are the
same size, their internal representations may be different, so
checking or veryifying size is not enough to be safe.

I'm not sure what you mean by "char* arithmetic" -- does the "hash"
(which sounds like it's actually a hash table) know about (remember?)
each thing stored in it, or is it packing (all or some of) them
(perhaps a buckets-worth) into a big array? I'm guessing the "hash"
knows only about void-pointers to things, and maybe their sizes, but
not their types? If so, the logical thing to do is to create and
return an array of void*, and the caller, who presumably knows the
type of what was (or should have been) stored, then converts that to a
foo* before using it, either by explicitly casting or implicitly by
assigning to its own (copy) pointer.

The questions then are,

1. Did I miss another solution where hash_keys creates some array?
2. Is my assessment of 2) correct?
3. On what kind of platforms/compilers would 2) fail? Outside the scope
of this newsgroup, I know, but perhaps some kind soul can comment.

- David.Thompson1 at worldnet.att.net

 

[Stijn van Dongen]

An array of void*, addressed as void**, and an array of struct
containing only void*, addressed as genpp*, are indeed similar. And in
fact are very likely (though not guaranteed) to be laid out the same.

I think the array of void* has to be adressed as void*; AFAIK there is
no type 'void**' in C (as you cannot dereference a void* pointer).

But the individual element pointers, of type void* in either case, are
NOT guaranteed to be laid out the same as some other (data) pointer
type foo*. So treating either of these as (casting to) foo** and
trying to use it is not safe, and I know of systems, though only a
few, where it won't work. Note that even if different pointers are the
same size, their internal representations may be different, so
checking or veryifying size is not enough to be safe.

ok, I suspected that much. Would still be interested to learn about
problematic systems, but it's illegal C and off-topic, so I won't
pursue it.

I'm not sure what you mean by "char* arithmetic" -- does the "hash"
(which sounds like it's actually a hash table) know about (remember?)
each thing stored in it, or is it packing (all or some of) them
(perhaps a buckets-worth) into a big array? I'm guessing the "hash"
knows only about void-pointers to things, and maybe their sizes, but
not their types?

The hash table (indeed) insert function gets a void*, and nothing else
- no size. It uses the cmp function given to it (when it was created)
to traverse the linked lists attached to a bucket array, and it uses
the hash function to compute the offset in that bucket array.

The thing that ties the key and value together is a struct looking like
this:

typedef struct {
void* key;
void* val;
} KV;

On my part, I'd prefer not to enter a discussion on the sanity of this
setup. The idea behind the whole setup (most of which is omitted here)
is that it provides a general setup for hash routines; the routines
provided by this particular hash library often serve as a layer below
another one that can implement the type of services and typechecking it
chooses to.

If so, the logical thing to do is to create and
return an array of void*, and the caller, who presumably knows the
type of what was (or should have been) stored, then converts that to a
foo* before using it, either by explicitly casting or implicitly by
assigning to its own (copy) pointer.

The reason why I don't want to do that is because it implies I'll have
a whole array of *copies* of my foo things. Given any one foo
(presumably some struct), I never want to duplicate it, and only pass
pointers to it around. Having copies around would cause endless trouble
with ownership issues. In the current setup returning foo* is also
impossible since the hash routines never (can) dereference their void*
key arguments. Which is a good thing. It could be achieved by passing
another callback to the hash table creation routine of course. But I
rather have a foo** array or a genpp* array as described above.

regards,
Stijn

 

[Netocrat]

The correct type is void** as Dave pointed out.

struct foo ** would be preferable but I understand that your function
needs to be generic.

But if I follow correctly, the key pointers are already void* type, so
you can use a direct assignment rather than byte-by-byte copying.

As Dave pointed out, this is not a portable cast.

You're right that that's not a portable assumption. But how does foo*
come into it? I thought your key pointer type was void*.

I think the array of void* has to be adressed as void*; AFAIK there is
no type 'void**' in C (as you cannot dereference a void* pointer).

A void ** type is valid. The result of dereferencing a void ** pointer
is a void * pointer, which is allowed.

Your second solution is workable.

To expand on Dave's suggestion, here is how to modify your approach:

a) return void**, not void*
b) copy the pointers directly rather than byte-by-byte. If a
conversion is required (afaict it isn't as the src and dest are both
void*) then rely on these properties of void* pointers (N869, 6.3.2.3):
"A pointer to void may be converted to or from a pointer to any
incomplete or object type. A pointer to any incomplete or object
type may be converted to a pointer to void and back again; the result
shall compare equal to the original pointer."
c) don't cast the return to foo** (as Dave said this is not portable);
instead cast an element at a time:

struct foo *my_foo_ptr = returned_void_ptr_array; /* cast not
req'd*/
struct foo my_foo_object = *my_foo_ptr;

or

struct foo my_foo_object = *(struct foo *)returned_void_ptr_array;
/* cast required */

The reason why I don't want to do that is because it implies I'll have a
whole array of *copies* of my foo things. Given any one foo (presumably
some struct), I never want to duplicate it, and only pass pointers to it
around. Having copies around would cause endless trouble with ownership
issues. In the current setup returning foo* is also impossible since the
hash routines never (can) dereference their void* key arguments. Which
is a good thing. It could be achieved by passing another callback to the
hash table creation routine of course. But I rather have a foo** array
or a genpp* array as described above.

The void ** approach doesn't require copies, but depending on usage it
may require typecasts.

If you can't accept the typecasting, then yes, a callback will be
necessary.
Something like (untested code):

1) declare your return array in hash_keys as
void *retarray = NULL; /* NOT void ** since this implies retarray[2] is
OK */
2) define your callback to take void **cbretarray, void *new_element,
int num_elements
3) pass &retarray as cbretarray
4) within the callback:

void *orgmem = *cbretarray; /* in case realloc fails */
*cbretarray = realloc(*cbretarray, (num_elements + 1) * sizeof(struct
foo *));
if (! (*cbretarray) )
; /* handle out of mem; original memory pointed to by orgmem */
else
((struct foo **)*cbretarray)[num_elements] = new_element;
/* applying cast to new_element is unnecessary */

Then declare void *hash_keys(..) and call it as
struct foo ** my_foo_array = hash_keys(..) /* no cast req'd */

You may choose to pass num_elements as a pointer and to increment its
dereferenced value within the callback only if realloc succeeds.

 

[Stijn van Dongen]

A void ** type is valid. The result of dereferencing a void ** pointer
is a void * pointer, which is allowed.

that was my misunderstanding. Don't know where it came from .. a quick
test program confirms both your and Daves remark on void**.
the rest is then indeed easy.

Your second solution is workable.

To expand on Dave's suggestion, here is how to modify your approach:

a) return void**, not void*
b) copy the pointers directly rather than byte-by-byte. If a
conversion is required (afaict it isn't as the src and dest are both
void*) then rely on these properties of void* pointers (N869, 6.3.2.3):
"A pointer to void may be converted to or from a pointer to any
incomplete or object type. A pointer to any incomplete or object
type may be converted to a pointer to void and back again; the result
shall compare equal to the original pointer."
c) don't cast the return to foo** (as Dave said this is not portable);
instead cast an element at a time:

struct foo *my_foo_ptr = returned_void_ptr_array; /* cast not
req'd*/
struct foo my_foo_object = *my_foo_ptr;

yep, that's what I want
thanks to you and Dave,
Stijn