void ** v. void*
Robin Poot
typedef void* POSITION;
....
int main(void)
{
int size=5, i; int *iP;
Dbly list;
POSITION pos;
initDbly(&list);
for(i=0; i<size; i++){
iP=newInt();
*iP=i;
insertDbly(&list, iP);
}
/************************************************
in the following line, pos (void*) is passed to
a Dblynode **. No compiler error, and all works well;
However, you will notice that in the function dblyGetHead,
that the void* gets dereferenced (while it is a Dblynode**).
The compiler allows this with no error, but you obviously can't
dereference a void* ?????
Query:
1. Why does this work
2. Is the dereferecing of nPP ansi compliant?
3. Should I use void** and cast to Dblynode ** instead?
************************************************/
for(iP=dblyGetHead(&list, pos); /* <<<< void* being passed here to
dblynode ** */
iP!=NULL;
iP=dblyGetNext(pos)){ /* walk the list */
printf("int: %d\n", *iP);
}
return 0;
}
void *dblyGetHead(Dbly *dP, Dblynode **nPP)
/* abridged */
{
(*nPP)=dP->firstP;
return (*nPP)->dataP;
}
...
int *newInt(void)
/* abriged */
{
int *iP;
iP=malloc(sizeof *iP);
return iP;
}
Joe Wright
I doubt it works. POSITION pos is local to main() and uninitialized.
You'd have to pass &pos somewhere.
The called function would see void **p and could assign to pos with a
statement like *p = (void *)vp;
--
Joe Wright mailto:joeww...@earthlink.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Robin Poot
Joe Wright <joeww...@earthlink.net> wrote in message
news:3BF687...@earthlink.net...
> Robin Poot wrote:
> > A question concerning the use of void *.
> > typedef void* POSITION;
>
It does work.
> You'd have to pass &pos somewhere.
> The called function would see void **p and could assign to pos with a
> statement like *p = (void *)vp;
for example:
int **iPP;
void *vP;
vp=iPP; /* works; vP is now a general pointer to a iPP */
now you could send vP to a function expecting an iPP where you could a new
pointer value to (*iPP).
Passing & pos also works, but the compiler gives you a warning because only
void * 's are automatically cast to any other pointer type!
e.g., you would have to pass (int **)&pos to cast the void** explicitly.
My question is wheather the latter (or former for that matter) is ansi. I
did not think that void** was guranteed to be a general
_pointer-to-a-pointer_.
void * is guranteed as a general pointer. In my case, it holds a iPP.
Am I off base?
Regards
RP
Kevin Miller
>
> A question concerning the use of void *.
>
> typedef void* POSITION;
> ....
>
> int main(void)
> {
> int size=5, i; int *iP;
> Dbly list;
> POSITION pos;
>
> initDbly(&list);
>
> for(i=0; i<size; i++){
> iP=newInt();
> *iP=i;
> insertDbly(&list, iP);
> }
>
> /************************************************
> in the following line, pos (void*) is passed to
> a Dblynode **. No compiler error, and all works well;
> However, you will notice that in the function dblyGetHead,
> that the void* gets dereferenced (while it is a Dblynode**).
> The compiler allows this with no error, but you obviously can't
> dereference a void* ?????
But you /aren't/ dereferencing a (void *). You are dereferencing
a (Dblynode **). The mere fact that it was obtained from a
(void *) does not violate ANSI rules, /provided/ that it is
properly cast to a (Dblynode **) and has also been properly
initialized. It will be properly cast if a prototype for
"dblyGetHead" appears before it is called. /One/ way to give "pos"
a valid initialization would be something like this:
Dblynode aNode;
Dblynode * nodePtr;
nodePtr = & aNode;
pos = & nodePtr;
> Query:
> 1. Why does this work
There are two possibilities:
1. Because of some code you have omitted, that initializes "pos"
and also prototypes "dblyGetHead" before it is called in "main".
2. Sheer luck.
> 2. Is the dereferecing of nPP ansi compliant?
It depends. See comments above.
> 3. Should I use void** and cast to Dblynode ** instead?
No. Only use the type (void *) for generic pointers.
Or you could possibly just use non-generic pointers.
Generic pointers are usually used when a middle-level function
needs to pass data from a high-level function to a low-level
function, and due to its use in a variety of applications, cannot
know what the type of the data is. In such cases, the high-level
function will take the address of its data and cast it to
a (void *) and pass that to the middle-level function, which will
pass it on down to the low-level function, keeping it in the form
of a (void *). After the low-level function gets it, it then
casts it back to a pointer to the appropriate data type, and does
something with it. See, for example, the standard library
function "qsort", which acts like the middle-level function in
the above discussion, and passes generic pointers down to
a low-level comparison function. In your program, "pos" is
(or at least had better be) cast to a non-generic pointer before
it is passed to "dblyGetHead", so I am not sure what the reason
is for using a generic pointer. Of course, it is possible that
it is passed to some other function (not shown) /as/ a generic
pointer, so there may be a good reason for it.
Robin Poot
Kevin Miller <erase.1st.19.c...@earthlink.net> wrote in message
> Robin Poot wrote:
> > A question concerning the use of void *.
> > typedef void* POSITION;
>
> But you /aren't/ dereferencing a (void *). You are dereferencing
> a (Dblynode **). The mere fact that it was obtained from a
> (void *) does not violate ANSI rules, /provided/ that it is
> properly cast to a (Dblynode **) and has also been properly
> initialized. It will be properly cast if a prototype for
There are prototypes.
> "dblyGetHead" appears before it is called. /One/ way to give "pos"
> a valid initialization would be something like this:
pos inadvertantly gets initialized to NULL in my code. Would this work (as
any pointer can be initialized to NULL):
#define POSITION void*
POSITION pos=NULL; /* ?????? */
> No. Only use the type (void *) for generic pointers.
> Or you could possibly just use non-generic pointers.
> Generic pointers are usually used when a middle-level function
> needs to pass data from a high-level function to a low-level
> function, and due to its use in a variety of applications, cannot
> know what the type of the data is. In such cases, the high-level
> function will take the address of its data and cast it to
> a (void *) and pass that to the middle-level function, which will
> pass it on down to the low-level function, keeping it in the form
> of a (void *). After the low-level function gets it, it then
> casts it back to a pointer to the appropriate data type, and does
> something with it. See, for example, the standard library
> function "qsort", which acts like the middle-level function in
> the above discussion, and passes generic pointers down to
> a low-level comparison function. In your program, "pos" is
> (or at least had better be) cast to a non-generic pointer before
> it is passed to "dblyGetHead", so I am not sure what the reason
If I understand correctly, as long as my functions are prototyped,
c automatically casts back and forth between void * and other*,
which seems to be the case.
> is for using a generic pointer. Of course, it is possible that
> it is passed to some other function (not shown) /as/ a generic
> pointer, so there may be a good reason for it.
thanks for the explanation.
RP
Robin Poot
Is the use of void** to represent an array of
void pointers a valid ansi method.
The following code works and I use it in
practice, but I am concerned weather the void**
to represent an array of void pointers is
rigorous.
Comments???
/******************************************
function takes a doulby-linked-list
and transforms it into a properly proportioned
array of pointers.
- dataP is of type void*
- array is of type void pointers (i.e. void**)
- return type is void pointer (cast from
void** to void* by compiler on account of
return type.
******************************************/
void *dbly2Array(Dbly *listP, size_t *size)
{
Dblynode *currentP;
void **arrayPP;
size_t index;
/***** get size of array to fill *****/
*size=sizeDbly(listP);
/********************************
allocate memory for size# of objects
of void* size
*********************************/
arrayPP=malloc((*size) * sizeof *arrayPP);
if(arrayPP==NULL)
exit (EXIT_FAILURE);
/*********************************
walk through list assigining each void* data
element to a void* array element
*********************************/
currentP=listP->firstP;
for(index=0; index< (*size); index++){
arrayPP[index]=currentP->dataP;
currentP=currentP->nextP;
}
/********************************
cast from void** to void* is done by compiler
because the function is declared as void*
return type.
*********************************/
return arrayPP;
}
int main(void)
{
Dbly list;
int *iP;
int **ivP; /***** array of iP's *****/
size_t i, size;
/***** create linked list and fill with *int's *****/
initDbly(&list);
for(i=0; i<5, i++){
iP=newInt();
*iP = i;
insertDbly(&list, iP);
}
/*****************************
call to function returns a void* (internally a
void**) which is cast to iPP by compiler.
This works on all of my compilers.
*****************************/
ivP=dbly2Array(&list, &size);
/***** step through array int iPP's *****/
for(i=0; i<size, ,i++){
printf("int val: %d", *ivP[i]);
}
/***** free array *****/
free(ivP);
return 0;
}
This is a handy function as it allows you to sort a
list with the qsort function, among other things.
Regards,
Robin Poot
Kevin Miller
>
> thankyou
>
> Kevin Miller <erase.1st.19.c...@earthlink.net> wrote in message
> > Robin Poot wrote:
> > > A question concerning the use of void *.
> > > typedef void* POSITION;
> >
> > But you /aren't/ dereferencing a (void *). You are dereferencing
> > a (Dblynode **). The mere fact that it was obtained from a
> > (void *) does not violate ANSI rules, /provided/ that it is
> > properly cast to a (Dblynode **) and has also been properly
> > initialized. It will be properly cast if a prototype for
>
> There are prototypes.
>
> > "dblyGetHead" appears before it is called. /One/ way to give "pos"
> > a valid initialization would be something like this:
>
> pos inadvertantly gets initialized to NULL in my code. Would this work (as
> any pointer can be initialized to NULL):
>
> #define POSITION void*
>
> POSITION pos=NULL; /* ?????? */
It will work as long as your code in dblyGetHead tests nPP to see
if it is NULL, and if it is, assigns a valid pointer to actual
memory to it before dereferencing nPP. E.g.,
if (nPP == NULL) {
nPP = malloc (...);
}
(*nPP) = node_pointer;
or
node_pointer = (*nPP);
What you don't want is this:
void * vp = NULL;
(*(int *)vp) = 42;
Or this:
int * ip = NULL;
(*ip) = 42;
NULL is guaranteed not to be the address of any object
or function in your program, or any address that could
conceivably be returned by "malloc", so you would
presumably be taking the integer 42 and storing it
heaven-only-knows-where in your computer. I say
"presumably" because you are actually invoking undefined
behavior.
> If I understand correctly, as long as my functions are prototyped,
> c automatically casts back and forth between void * and other*,
> which seems to be the case.
Yes, that is correct.
Kevin Miller
CHANGE #1. Replace this with:
void **ivP;
> size_t i, size;
>
> /***** create linked list and fill with *int's *****/
> initDbly(&list);
> for(i=0; i<5, i++){
> iP=newInt();
> *iP = i;
> insertDbly(&list, iP);
> }
>
> /*****************************
> call to function returns a void* (internally a
> void**) which is cast to iPP by compiler.
>
> This works on all of my compilers.
> *****************************/
> ivP=dbly2Array(&list, &size);
>
> /***** step through array int iPP's *****/
> for(i=0; i<size, ,i++){
> printf("int val: %d", *ivP[i]);
CHANGE #2. Replace this with:
printf("int val: %d", *((int *)(ivP[i])));
You have to realize that casting a pointer to
void pointer (what you started with originally)
to a pointer to int pointer does not convert
the individual pointers in the array; it only
converts the pointer /to/ the array itself.
Also, there is no guarantee that a pointer to
void has the same size as a pointer to int.
So when you index into an array of void pointers
using code that thinks it has an array of int
pointers, it could miscalculate the offsets
from the beginning of the array and grab the
wrong part of that array.
Generally, when you cast from (thing *) to (void *), you
need to cast back to (thing *), and not (different *).
The code I have written above takes an array of
void pointers (the same thing you had in dbly2Array)
and grabs the i'th element (ivP[i]). After it has
grabbed it, it has an ordinary void pointer, and it
can be cast to a different type. (As stated above,
you can't cast the elements of an array by casting
the pointer to the beggining of the array.) So this
void pointer is then cast to an int pointer. Then
that int pointer is dereferenced, yielding an int.
Mostly [*], different types of pointers have the
same size, and mostly [*], pointer casts are null
operations, so this explains why your code works
for you. But it is not guaranteed to work on
every machine unless you make the two changes
I indicated above.
Due to precedence of the operators, the 2'nd line
that I added could actually be written like this:
printf("int val: %d", *(int *)ivP[i]);
But I wanted the order of operations to be absolutely
clear.
[*] - Mostly, as in "Earth: mostly harmless."
Robin Poot
Kevin Miller
> Robin Poot wrote:
> > One other question concerning void**
>
> > int **ivP; /***** array of iP's *****/
> CHANGE #1. Replace this with:
> void **ivP;
>
> > printf("int val: %d", *ivP[i]);
> CHANGE #2. Replace this with:
> printf("int val: %d", *((int *)(ivP[i])));
I understand, but its a little too ugly for me
to use with my API.
Would a suitable alternative be to include the
sizeof the array elements to the allocation function:
dbly2Array(Dbly *listP, size_t *sizeArray, size_t sizeElem)
{
...
void **vPP;
...
vPP=malloc(*sizeArray * sizeElem);
...
}
int main(void)
{
int **ivP;
...
ivP=dbly2Array(&list, &size, sizeof(int*));
/* now you could use *ivP[i] directly, no casting required ????? */
...
}
Regards,
RP
Kevin Miller
No. It's still an array of void pointers, even if it's in a block
of memory suitable for an array of int pointers.
If you think "printf("int val: %d", *(int *)ivP[i]);" is too ugly, why
don't you write a function like this:
int ** vpa2ipa (size_t num_elems, void ** vpa) {
size_t k;
int ** ipa;
ipa = malloc (num_elems * sizeof (*ipa));
if (ipa == NULL) {
fprintf (stderr, "No memory!\n"); /* Handle error here. */
exit (EXIT_FAILURE);
/* OR */
/* return NULL; */ /* Let parent function handle error. */
}
for (k = 0; k < num_elems; ++k) ipa [k] = vpa [k];
return ipa;
}
Then:
int ** ivP;
...
ivP = vpa2ipa(dbly2Array(&list, &size));
using your original "dbly2Array" function.
Robin Poot
Kevin Miller wrote
> ivP = vpa2ipa(dbly2Array(&list, &size));
With O(n) extra complexity, and two additional function calls (vpa2ipa +
free(ipa) ), I guess the casting looks not so ugly.
Regards,
RP
Chris Torek
so this may already have been addressed. I just want to put it in
a form that (I think) makes it tremendously obvious what is required.
In article <dvSJ7.1883$i61.2...@news20.bellglobal.com>,
Robin Poot <rp...@everestgeodetics.com> wrote:
>One other question concerning void**
>
>Is the use of void** to represent an array of
>void pointers a valid ansi method.
Yes. Be very careful, though, not to confuse "void *", "void **",
and other pointer flavors.
I think the best way to see the potential problems is to draw a
diagram of the memory layout on a machine like the PRIME (referred
to in the FAQ) or similar to the Data General Eclipse (which I
mention now and then as a "good bad example" :-) ).
Imagine that the machine you are using has 48-bit "char *" and
"void *" pointers, and that all other pointers are only 32 bits
wide. The 32-bit pointers point to "words" -- the 16-bit entities
that the hardware supports directly -- and the 48-bit pointers use
an extra, second word to store a single bit that tells whether you
are supposed to access the lower or upper byte of that word.
In that case, then, "void *" and "char *" are both 48 bits wide,
while "void **" and "int **" are both 32 bits.
Now suppose you call malloc() twice, and both times it succeeds,
using code like this to create a "two-dimensional" array of nrows
by ncols:
void **newarray(size_t nrows, size_t ncols, size_t datasize) {
void **rows;
char *tmp;
size_t i;
rows = malloc(n_rows * sizeof *rows);
tmp = malloc(n_rows * n_cols * data_size);
if (rows == NULL || tmp == NULL) {
free(rows); /* free both in case ... */
free(tmp); /* one of them succeeded */
return NULL; /* then signal failure */
}
for (i = 0; i < nrows; i++) {
rows[i] = tmp;
tmp += ncols * datasize;
}
return rows;
}
Suppose also that datasize happens to be 4 8-bit bytes, i.e., 32
bits, perhaps storing "int"s, and that nrows is 3 and ncols is 2.
What this builds, then, could be drawn like this:
32bitptr 48 bit ptr "2d array" of int
+------+ +-------------+ +-------+-------+
| rows | ----> | rows[0] | ---> | <val> | <val> |
+------+ +-------------+ +------- -------+
| rows[1] | ---> | <val> | <val> |
+-------------+ +------- -------+
| rows[2] | ---> | <val> | <val> |
+-------------+ +-------+-------+
I have deliberately exaggerated the scale slightly, but the key
here is to notice that each "void *" pointer in rows[i] is much
fatter than the overall "rows" pointer.
Any attempt to use rows[i] will "pull out" all 48 bits of pointer
value and use that to find the corresponding row. This will work
fine, because reach rows[i] really *is* a 48-bit-wide thing.
Suppose you were to now take the returned value from newarray(),
of type "void **", and convert it to type "int **", either by
a direct cast or by converting it in two steps, first to "void *",
then to "int **":
int **p = (int **)newarray(3, 2, sizeof(int)); /* WRONG */
if (p == NULL) ... handle error ...
This looks convenient -- but it does not work! This *expects*
a rather different picture that looks instead like this:
32bitptr 32bitptr "2d array" of int
+------+ +------+ +-------+-------+
| p | ----> | p[0] | ---> | <val> | <val> |
+------+ +------+ +------- -------+
| p[1] | ---> | <val> | <val> |
+------+ +------- -------+
| p[2] | ---> | <val> | <val> |
+------+ +-------+-------+
So, suppose the *actual* image in memory has those 48-bit pointers,
and we now try to use p[i]. This will follow a 32-bit pointer (now
called "p") and reach the correct block of memory -- but instead
of pulling out 48 bits at a time, it will pull out just 32. Those
will be mangled parts of the various rows[i]'s. p[0] will be the
first 32 bits of rows[0]; p[1] will be the last 16 of rows[0] plus
16 more out of rows[1]; and p[2] will be the last 32 of rows[1].
Clearly this is not going to work.
The caller, then, has to use, instead:
void **p = newarray(3, 2, sizeof(int));
if (p == NULL) ... handle error ...
Now each p[i] is the corresponding 48-bit-wide "void *" pointer that
was stored in each rows[i]. Unfortunately, this has type "void *",
not the desired "int *" type that lets you get at the two "int"s
in each column, so it must be converted to "int *":
int *tmp;
...
tmp = p[i]; /* assignment is OK because "void *" converts freely */
use(tmp[j]); /* access j'th column of row i */
tmp[j] = val; /* set j'th column value of row i */
Equivalently, you can write:
((int *)p[i])[j]
which uses the fact that a cast has the same effect as an assignment
to a temporary variable.
The key in all cases is that, because each p[i] was *written* as
a "void *", it must also be *read* as a "void *", not any other
kind of pointer.
You can remember this rule in a more general way, too. "Whatever
data type you put in, you have to pull out that same data type."
There are a few exceptions, but unless you are trying to dig into
the representations your compiler uses, you can simply avoid them
and have portable code.
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
El Cerrito, CA, USA Domain: to...@bsdi.com +1 510 234 3167
http://claw.eng.bsdi.com/torek/ (not always up) I report spam to abuse@.
the "nospam@" address in the header really works, too.
Robin Poot
With respect to differing pointer size.
I see the problem that if an array created as void* is cast to an array of
int* for use, that a size difference in pointers could cause accessing the
wrong element.
How then does qsort work. It asks for the size of each element as well as
the number of elements. Now qsort presumably gets the offset of different
elements in turn by using the element size * element number, and sends the
address of that element to the user supplied comparison function (received
as void*). That function must then cast the elelment to the user type*.
Is there not a way, then, to reverse that process. Could you create an
array of void* (or something else?) that that is sized to hold the ultimate
user type, and then fill the elements by calculating the offset and
assigning the pointer to that address? The user then casts the array to
type, say, int*. Would compiler then know how to access the individual
elements properly (with regards to starting address anyhow)?
Anyways, I can see the method might still fail on account of representation.
Regards,
RP
Kevin Miller
This is an excellent question.
Without doing some reading and some thinking, I can't give an answer
that I would have confidence in.
It's possible that casting from (void *) to (char *) will work, since
you would only need to be able to move bytes and take the address of
those bytes and convert those addresses to (void *) to pass to
the comparator. I'll have to think about this.
Of course, you should realize that it is not necessary that qsort be
written without special knowledge of the platform, since there are
different versions of the standard library provided for different
platforms. So the standard library need not be portable.
In fact, the standard library need not be written in C.
It should be obvious that at least one of the functions declared
in <stdio.h> is either not NOT written in C, or not written in
portable C, since there are no I/O operators in C, and you can't
reduce an I/O operation entirely to non-I/O operations unless
you are storing stuff at specific RAM addresses that are
memory-mapped to I/O hardware, and that would certainly not
be portable.
But I am not certain that qsort itself could not be
written in portable C. As I said earlier, I will have to think
about this. Unfortunately, I am far behind on a project at work
right now, and won't have time to address this until Thursday.
[Both Thursday (the 22'nd) and Friday (the 23'rd) are holidays
where I work.]
If anyone else knows the answer to this, I would be very
interested to hear it.
Richard Bos
> Robin Poot wrote:
> >
> > I see the problem that if an array created as void* is cast to an array of
> > int* for use, that a size difference in pointers could cause accessing the
> > wrong element.
Not just that, if the void * is somehow misaligned for ints, you could
get a trap - IIRC, in this case, you'd get a bus error, BICBWW.
> > How then does qsort work. It asks for the size of each element as well as
> > the number of elements. Now qsort presumably gets the offset of different
> > elements in turn by using the element size * element number, and sends the
> > address of that element to the user supplied comparison function (received
> > as void*). That function must then cast the elelment to the user type*.
Yes. Note, though, that for this to function the void * passed to
qsort() must have started life properly aligned for the base type to
begin with. That is, you _have_ an array of, say, doubles. This array,
or this *alloc()ed memory, is obviously correctly aligned for doubles.
Ok, so then a pointer to the first of these doubles is passed to
qsort(); in this call, it is automatically converted to a void *. Since
all object pointer types can be safely cast to void * without loss of
information - including loss of alignment - this void * is still safely
aligned for a double.
qsort() then manipulates this void *, by hand as it were, by adding
multiples of the desired size. It can do this only because
- it is allowed to assume that the pointer you passed to it was properly
aligned for an object of the size you also passed to it.
- it knows that adding integral multiples of the same size to a void *
is guaranteed by the standard to retain the correct alignment of that
void *; IOW, that void * function as if memory is flat and regular.
- it is allowed to assume that your comparison function knows about the
type it is about to compare, and that this type has the same alignment
as the base type of the original pointer.
Note that this only works _if_ the pointer, size, and function you pass
to qsort() do indeed belong together. The void * manipulation always
works; the subesquent interpretation of the manipulated void * only
works if it is done consistently.
> > Is there not a way, then, to reverse that process. Could you create an
> > array of void* (or something else?) that that is sized to hold the ultimate
> > user type, and then fill the elements by calculating the offset and
> > assigning the pointer to that address?
Yes, you can, provided the array starts out properly aligned. For
example, the memory you get from malloc() starts out not having a base
type at all (it is a void *); but it is also guaranteed to start out
aligned correctly for all types, so you can safely manipulate it by hand
as if it were, say, a double *, _as long as you do so consistently_.
> > The user then casts the array to
> > type, say, int*. Would compiler then know how to access the individual
> > elements properly (with regards to starting address anyhow)?
Well, not in this case. You posit "an array of void *", and then an "int
*". This boils down to interpreting void *s as ints; and as you
correctly say, you would have more problems than just alignment. Even if
the base pointer would be properly aligned for both a void * and an int,
if a void * and int are of different size, subsequent elements will be
misaligned.
And then there's the problem of trap representations, so that not all
valid void * bit patterns need represent valid ints, or vice versa, even
if they're the same size...
Note that there's one exception to all this: it is explicitly made
possible to access all objects as arrays of unsigned char. So if you
want to se how, e.g., a double is represented in memory, you only have
to access it through an unsigned char *, and print out all the bytes
separately...
Note, though, that this still doesn't need to tell you anything useful;
for example, under MS-DOS, two pointers to the same object could have
different representations, even if they were the same type. Such is the
joy of segmented architectures...
> But I am not certain that qsort itself could not be
> written in portable C.
It certainly can. It doesn't need to be, but especially in the case of
something as high-level as qsort(), I see no need why it shouldn't be.
Richard
Chris Torek
Robin Poot <rp...@everestgeodetics.com> writes:
>... How then does qsort work. It asks for the size of each element as
>well as the number of elements. Now qsort presumably gets the offset
>of different elements in turn by using the element size * element
>number, and sends the address of that element to the user supplied
>comparison function (received as void*). That function must then cast
>the elelment to the user type*.
Right, or close enough anyway. A cast is not required because
"const void *" converts freely to "const T *", for any data-type T.
Here is a (not very good and completely untested) qsort that uses
C99's variable-size array feature:
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
char *cbase = base;
size_t i, j;
char *ip, *jp;
char saveit[size];
/* cbase is the base of the array A, expressed in bytes/chars */
/* for each element beyond #0 (which is sorted in a list of 1) ... */
for (j = 1; j < nmemb; i++) {
/* ... point to the j'th element (to be added to list) */
jp = cbase + i * size;
/* ... and find first position where A[i] < A[j] */
for (i = 0; i < j; i++) {
ip = cbase + i * size;
if (compar(ip, jp) < 0)
break;
}
/*
* We now have the first i such that A[j] < A[i]. Slide
* A[i]..A[j-1] up one slot, then put A[j] in place.
* Note that if i==j there is nothing to do.
*/
if (i == j)
continue;
memcpy(saveit, jp, size); /* save original element */
memmove(ip, ip + size, (j - i) * size);
memcpy(ip, saveit, size);
}
}
Take a close look at the call to compar(), and the calls to memcpy()
and memmove(). Notice that they make no assumptions whatsoever
about the type of the objects being compared and moved! They only
need to know how many bytes (chars) those occupy, and that only to
find the objects, and save a copy of one (denoted A[i] above) while
shuffling the rest.
>Is there not a way, then, to reverse that process. Could you create an
>array of void* (or something else?) that that is sized to hold the ultimate
>user type, and then fill the elements by calculating the offset and
>assigning the pointer to that address? The user then casts the array to
>type, say, int*. Would compiler then know how to access the individual
>elements properly (with regards to starting address anyhow)?
Not directly. You could use a callback to "user code" (as it were)
to populate each object, so that that same user code can access
those objects in whatever way it likes later. For instance:
void *mkmat2(size_t nrows, size_t ncols, size_t psize,
size_t dsize, void (*setrowptr)(void *, const void *)) {
char *rowp, *datap;
size_t i;
rowp = malloc(nrows * psize);
datap = malloc(nrows * ncols * dsize);
... handle NULL from malloc as usual ...
/* now set all nrows row pointers, by asking caller to do it */
for (i = 0; i < nrows; i++)
setrowptr(rowp + i * psize, datap + i * cols * dsize);
return rowp;
}
To use this for "int **", you might write:
void setintstarptr(void *rpp0, const void *dp) {
int **rpp = rpp0;
*rpp = dp;
}
...
void somefn(size_t nrows, size_t ncols) {
int **ip;
...
ip = mkmat2(nrows, ncols, sizeof *ip, sizeof **ip, setintstarptr);
... check for error ...
... can now use ip[i][j] here ...
}
No doubt there should also be a corresponding freemat2() function.
This is also completely untested.
Micah Cowan
> Ok.
>
> With respect to differing pointer size.
>
> I see the problem that if an array created as void* is cast to an array of
> int* for use, that a size difference in pointers could cause accessing the
> wrong element.
No, it couldn't. Conversions between void* and int* is well-defined,
and must point to the same element, regardless of pointer size
differences.
Also, you're not really talking about arrays. since there's no such
thing as an "array created as void*"; and an array of int* would mean:
int *array[];
What you mean is something like:
int *buffer = malloc(SOME_SIZE * (sizeof *buffer));
Which allocates a buffer of SOME_SIZE ints, and converts the resulting
void-pointer to an int-pointer. No cast should be performed; this can
lead to errors, and is never useful in C.
> How then does qsort work. It asks for the size of each element as well as
> the number of elements. Now qsort presumably gets the offset of different
> elements in turn by using the element size * element number, and sends the
> address of that element to the user supplied comparison function (received
> as void*). That function must then cast the elelment to the user type*.
> Is there not a way, then, to reverse that process. Could you create an
> array of void* (or something else?) that that is sized to hold the ultimate
> user type, and then fill the elements by calculating the offset and
> assigning the pointer to that address? The user then casts the array to
> type, say, int*. Would compiler then know how to access the individual
> elements properly (with regards to starting address anyhow)?
Using the wrong terminology again: an "array of void*" is:
void *array[];
In any case, qsort() doesn't require casting at all. It would be a
very poor solution if it did.
As far as the rest of your paragraph goes, it's a little too confusing
for me to understand what you're asking. You can't cast arrays. You
don't *need* to cast void-pointers pointing at buffers.
Micah
Ben Pfaff
> "Robin Poot" <rp...@everestgeodetics.com> writes:
>
> > With respect to differing pointer size.
> >
> > I see the problem that if an array created as void* is cast to an array of
> > int* for use, that a size difference in pointers could cause accessing the
> > wrong element.
>
> No, it couldn't. Conversions between void* and int* is well-defined,
> and must point to the same element, regardless of pointer size
> differences.
I'm missing some context here. That may be true in this context,
but it's not true in general, because a void * may not be aligned
properly for an integer pointer. On the other hand, if you have
a valid int *, converting it to void * and back to int * will not
damage it.
--
"Your correction is 100% correct and 0% helpful. Well done!"
--Richard Heathfield
Micah Cowan
> Micah Cowan <mi...@localhost.localdomain> writes:
>
> > "Robin Poot" <rp...@everestgeodetics.com> writes:
> >
> > > With respect to differing pointer size.
> > >
> > > I see the problem that if an array created as void* is cast to an array of
> > > int* for use, that a size difference in pointers could cause accessing the
> > > wrong element.
> >
> > No, it couldn't. Conversions between void* and int* is well-defined,
> > and must point to the same element, regardless of pointer size
> > differences.
>
> I'm missing some context here. That may be true in this context,
> but it's not true in general, because a void * may not be aligned
> properly for an integer pointer. On the other hand, if you have
> a valid int *, converting it to void * and back to int * will not
> damage it.
Context wasn't really provided by the OP; however, by "array created
as void*", I assumed he meant "buffer allocated by malloc()", since
arrays and dynamic buffers are often confused. malloc(), naturally,
guarantees correct alignment; in other cases, all bets may be off.
Micah
--
"Everytime you declare main() as returning void - somewhere a little
baby cries. So please, do it for the children." -- Daniel Fox
Kevin Miller
>
> Ben Pfaff <b...@cs.stanford.edu> writes:
>
> > Micah Cowan <mi...@localhost.localdomain> writes:
> >
> > > "Robin Poot" <rp...@everestgeodetics.com> writes:
> > >
> > > > With respect to differing pointer size.
> > > >
> > > > I see the problem that if an array created as void* is cast to an array of
> > > > int* for use, that a size difference in pointers could cause accessing the
> > > > wrong element.
> > >
> > > No, it couldn't. Conversions between void* and int* is well-defined,
> > > and must point to the same element, regardless of pointer size
> > > differences.
> >
> > I'm missing some context here. That may be true in this context,
> > but it's not true in general, because a void * may not be aligned
> > properly for an integer pointer. On the other hand, if you have
> > a valid int *, converting it to void * and back to int * will not
> > damage it.
>
> Context wasn't really provided by the OP; however, by "array created
> as void*", I assumed he meant "buffer allocated by malloc()", since
> arrays and dynamic buffers are often confused. malloc(), naturally,
> guarantees correct alignment; in other cases, all bets may be off.
Context was provided further back in the thread, although his
question may not be clear from reading the last couple of posts.
By "array created as void*", the OP meant an object with type (void **).
Conceptually, he had the following:
int k;
int int_array [5] = { 42, 17, 36, 12, 88 };
void ** vpa;
int ** ipa;
void * vp;
vpa = malloc (5 * sizeof (* vpa));
for (k = 0; k < 5; ++k) vpa [k] = & (int_array [k]);
vp = vpa;
ipa = vp;
for (k = 0; k < 5; ++k) printf ("%d \n", *(ipa [k]));
There were function calls instead of simple assignments, and
the source of the data was a linked list rather than an
integer array, but the code above has the same pointer
conversions and indexing in it. One problem with the
code above is that converting the (void **) object to
an (int **) object does NOT convert the (void *) objects
it points to into (int *) objects.
And if sizeof (void *) = 4 while sizeof (int *) = 3, which is
perfectly legal, the byte offset used to access ipa [k] will
not be the same as the byte offset used to access vpa [k],
even though the bytes will not have been moved around by
the conversion of vpa to ipa.
Nevertheless, based on Richard Bos's and Chris Torek's posts,
I believe that there is a way for the OP to accomplish what
he wants, by passing an element size and converting his
pointer to an (unsigned char *) and moving bytes.
Micah Cowan
> > Context wasn't really provided by the OP; however, by "array created
> > as void*", I assumed he meant "buffer allocated by malloc()", since
> > arrays and dynamic buffers are often confused. malloc(), naturally,
> > guarantees correct alignment; in other cases, all bets may be off.
>
> Context was provided further back in the thread, although his
> question may not be clear from reading the last couple of posts.
Ah. Now that I've done "get thread" on this, I see. However, the OP
posted a response snipping all context, which confused me into
thinking it was a new thread (with little information).
Micah
--
"*I* don't think you understand your question."
-- Tom Plunket
pete
That looked like fun, so I wrote a couple of q sorts for C90
void Q_1(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
char *start;
char *end;
char *middle;
void *swap;
unsigned done;
swap = malloc(size);
if(!swap){
fputs("malloc failure in Q_1()", stderr);
exit(EXIT_FAILURE);
}
done = 0;
start = base;
end = start + ((nmemb - 1) * size);
do{
++done;
middle = start;
while(end > middle){
if(compar(middle, middle + size) > 0){
memcpy(swap, middle, size);
memcpy(middle, middle + size, size);
memcpy(middle + size, swap, size);
done = 0;
}
middle += size;
}
end -= size;
}while(!done);
free(swap);
}
void Q_2(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
char *start;
char *end;
char *middle;
void *swap;
unsigned done;
swap = malloc(size);
if(!swap){
fputs("malloc failure in Q_2()", stderr);
exit(EXIT_FAILURE);
}
done = 0;
start = base;
end = start + ((nmemb - 1) * size);
do{
++done;
middle = start;
while(end > middle){
if(compar(middle, middle + size) > 0){
memcpy(swap, middle, size);
memcpy(middle, middle + size, size);
memcpy(middle + size, swap, size);
done = 0;
}
middle += size;
}
if(done){
break;
}
++done;
middle = end -= size;
while(middle > start){
middle -= size;
if(compar(middle, middle + size) > 0){
memcpy(swap, middle, size);
memcpy(middle, middle + size, size);
memcpy(middle + size, swap, size);
done = 0;
}
}
start += size;
}while(!done);
free(swap);
}
--
pete
Chris Torek
>> Here is a (not very good and completely untested) qsort that uses
>> for (j = 1; j < nmemb; i++) {
In article <3BFC1A...@mindspring.com>
pete <pfi...@mindspring.com> writes:
>That looked like fun, so I wrote a couple of q sorts for C90 ...
You (and everyone else?) seems to have missed my obvious bug! :-)
Well, obvious now that I kept just the one line with the bug in it.
(The loop counts "j", so why is the last line "i++"? I would
blame it on a typo, but it was actually a "thinko".)
pete
>
> >Chris Torek wrote:
> >> Here is a (not very good and completely untested) qsort that uses
> >> C99's variable-size array feature ...
> >> for (j = 1; j < nmemb; i++) {
>
> In article <3BFC1A...@mindspring.com>
> pete <pfi...@mindspring.com> writes:
> >That looked like fun, so I wrote a couple of q sorts for C90 ...
>
> You (and everyone else?) seems to have missed my obvious bug! :-)
I don't have a C99 compiler.
I converted it to a C90 malloced form and then it crashed.
"My modified version of Chirs Torek's program just crashed"
"Whose fault is it?"
"Well, I just altered it, so it's my code now,
but as I'll paraphrase someone's sig file,
'code is harder to debug than to write,
so if you try as hard as you can to write it right,
then you can't debug it yourself'"
So, I gave up.
I had just very recently written a couple of bubble sort functions,
so I converted them to q sort functions and posted them.
--
pete
pete
> I had just very recently written a couple of bubble sort functions,
> so I converted them to q sort functions and posted them.
/* I rewrote this one */
void Q_4(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
char *first, *last, *middle, *next;
void *swap;
swap = malloc(size);
if(!swap){
fputs("malloc failure in Q_4()\n", stderr);
exit(EXIT_FAILURE);
}
next = base;
last = (nmemb - 1) * size + next;
while(last != next){
middle = first = next;
do{
if(compar(middle, middle + size) > 0){
memcpy(swap, middle, size);
memcpy(middle, middle + size, size);
memcpy(middle + size, swap, size);
next = middle;
}
middle += size;
}while(middle != last);
if(first == next){
break;
}
middle = last = next;
do{
if(compar(middle, middle - size) < 0){
memcpy(swap, middle, size);
memcpy(middle, middle - size, size);
memcpy(middle - size, swap, size);
next = middle;
}
middle -= size;
}while(middle != first);
}
free(swap);
}
--
pete
pete
> > I had just very recently written a couple of bubble sort functions,
> > so I converted them to q sort functions and posted them.
>
> /* I rewrote this one */
I rewrote the other one too.
OP was interested in what the guts of qsort look like.
Q_2 is the smallest simplest thing I could come up with, that
does the same thing as qsort, except that
it won't work right without stdlib.h and string.h, and
it's about a zillion times slower than qsort should be.
void Q_2(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
char *swap, *last, *next, *middle;
swap = malloc(size);
if(!swap){
fputs("malloc failure in Q_2\n", stderr);
exit(EXIT_FAILURE);
}
last = (nmemb - 1) * size + (char *)base;
while(last != base){
middle = next = base;
do{
if(compar(middle, middle + size) > 0){
memcpy(swap, middle, size);
memcpy(middle, middle + size, size);
memcpy(middle + size, swap, size);
next = middle;
}
middle += size;
}while(middle != last);
last = next;
}
free(swap);
}
--
pete