void *

[bandejapaisa]

I'm just experimenting with what i can and can't do with C and
pointer. I wanted to create a method that will swap 2 variables, no
matter what their type. I tried doing it like so:

void swap(void *source, void *dest) {
void *temp = source;

*source = *dest;
*dest = *temp;
}

...but i'm getting the error.

Invalid use of void type.

How can i achieve what i'm trying to do?

Thanks

 

[bandejapaisa]

Sorry, the error is "Invalid use of void expression"

 

[Seebs]

I'm just experimenting with what i can and can't do with C and
pointer. I wanted to create a method that will swap 2 variables, no
matter what their type.

Interesting thought!

I tried doing it like so:

void swap(void *source, void *dest) {
void *temp = source;

*source = *dest;
*dest = *temp;
}

..but i'm getting the error.

Invalid use of void type.

Right.

That's because "void" doesn't have a size. In general, when you convert
an address to (void *), you no longer have information about how large the
object pointed to was. As a result, there's no way for this to generate
code; it has no idea what to copy.

How can i achieve what i'm trying to do?

You can't completely solve this portably without providing extra data. The
problem is that there's no portable way to inquire as to the type of an
object in a macro or function or anything like that. Here's what I'd
probably do:

void swap_item(void *o1, void *o2, size_t len) {
/* assumes C99 or GNU C */
unsigned char buf[len];
memcpy(buf, o1, len);
memcpy(o1, o2, len);
memcpy(o2, buf, len);
}

#define swap(x, y) (swap_item((x),(y),sizeof((x))))

This doesn't sanity-check that x and y have compatible types, or even
compatible sizes.

-s

 

[Seebs]

void swap(void *vleft, void *vright, size_t len)
{
unsigned char *left = vleft;
unsigned char *right = vright;
unsigned char tmp;
while(len--)
{
tmp = *left;
*left++ = *right;
*right++ = tmp;
}
}

Oh, yes, listen to Richard, not me, he avoided depending on the VLA
feature. (Downside, for sufficiently large objects, mine might be
faster...)

-s

 

[Keith Thompson]

Oh, yes, listen to Richard, not me, he avoided depending on the VLA
feature. (Downside, for sufficiently large objects, mine might be
faster...)

A reasonable compromise, if you're concerned about both time and
space, would be to declare a fixed-size buffer and use memcpy() in a
loop.

 

[Seebs]

A reasonable compromise, if you're concerned about both time and
space, would be to declare a fixed-size buffer and use memcpy() in a
loop.

Yes.

Interestingly, this might end up being a good place to use Duff's Device.

-s

 

[bandejapaisa]

Its hard to know where to start.

Even forgetting the issues with types : have a careful look at your
*temp pointer. You dont actually store the temp value pointed at.

You are confused with pointers and the values they point to it seems.




you are storing the POINTER not the VALUE pointed to.

I did this because i was experimenting and it wouldn't compile when i
did

void *temp = *source;

Its the use of (void *) that i'm not quite getting. It worked fine
when i declared the types, i.e:

void swap(int *x, int *y) {
int *t = *x;
*x = *y;
*y = t;
}

 

[bandejapaisa]

It seems this problem is more complex than i thought. I was under the
assumption that i was missing something quite basic.

Thanks for your responses.

 

[Flash Gordon]

I would suggest going back to basics of pointers and step through with a
good debugger noting the pointer address values and the contents of the
memory they point to. It will become very clear, very quickly then.

Whilst stepping through in a debugger might be good sometimes, it is a
bit difficult when the code won't compile. RH and Peter have addressed
these issues, so I won't repeat them.

 

[Flash Gordon]

I would suggest going back to basics of pointers and step through with a
good debugger noting the pointer address values and the contents of the
memory they point to. It will become very clear, very quickly then.

Whilst stepping through in a debugger might be good sometimes, it is a
bit difficult when the code won't compile. RH and Peter have addressed
these issues, so I won't repeat them.

 

[Keith Thompson]

I did this because i was experimenting and it wouldn't compile when i
did

void *temp = *source;

Its the use of (void *) that i'm not quite getting. It worked fine
when i declared the types, i.e:

void swap(int *x, int *y) {
int *t = *x;
*x = *y;
*y = t;
}

When you write

*x = *y;

when x and y are of type int, the compiler knows that it needs to
generate code to copy sizeof(int) bytes.

When x and y are of type void*, how many bytes should be copied?
Assuming you have a specific number of bytes in mind, how is the
compiler to know what it is?

 

[Seebs]

I did this because i was experimenting and it wouldn't compile when i
did

void *temp = *source;

That's because you can't dereference source, because it's a
pointer-to-nothing. It's also the wrong thing.

What you'd want to do, if you could dereference source, would be
to write "void temp = *source;" -- but you can't, because there's no
such thing as a void object.

Its the use of (void *) that i'm not quite getting.

Imagine that it says "pointer to nothing". Although it's technically
incorrect, I just treat a "void *" as a pointer to a 0-byte object when
trying to figure out how it'll work.

void swap(int *x, int *y) {
int *t = *x;
*x = *y;
*y = t;
}

This is wrong, because you're storing the contents of x in a pointer to int.

It should be "int t = *x;"

Pointers summarized: Declaration reflects use. "int *t;" means "there is
an int, *t". So "*t" is an int, so "t" is a pointer-to-int. So you could
do:

int *p = x;
int t = *x;

because x is "int *", so "*x" is an int, but "x" is an "int *".

-s

 

[Thad Smith]

Its the use of (void *) that i'm not quite getting. It worked fine
when i declared the types, i.e:

void swap(int *x, int *y) {
int *t = *x;
*x = *y;
*y = t;
}

That is not guaranteed to work, since you are storing an int into an
int* variable, which could change the representation or not be large
enough. That should be
int t = *x;

An essential requirement of using a pointer is guarantee that when you
use (dereference) it, it is pointing to valid storage for the intended
type. A minimum requirement is that the pointer be assigned a value of
a suitable object, such as
int a;
int *p;
p = &a;

or by using a memory allocation routine
p = malloc(sizeof int);

If using the latter, verify that the memory allocation succeeded before
attempting to use the pointer:
#include <stdlib.h> /* outside your code */
...
if (p == NULL) {
/* code for error handling here, such as */
puts("Out of memory");
return EXIT_FAILURE;
}

 

[frank]

Yes.

Interestingly, this might end up being a good place to use Duff's
Device.

-s

send(to, from, count)
register short *to, *from;
register count;
{
register n=(count+7)/8;
switch(count%8){
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n>0);
}
}


How does the "interlacing" occur?

 

[arnuld]

#include <stddef.h>

/* the following function has woefully
inadequate error checking; the behaviour is undefined if you screw up
the call */

void swap(void *vleft, void *vright, size_t len) {
unsigned char *left = vleft;
unsigned char *right = vright;
unsigned char tmp;
while(len--)
{
tmp = *left;
*left++ = *right;
*right++ = tmp;
}
}

If arguments are /double*/ or types with values larger than /unsigned
char/ , we are going to get 2 implicit casts which will result only in
some random values assigned but this works correctly. Some sort of
pointer-magic ?



#include <stdio.h>
#include <stddef.h>
#include <limits.h>

/* the following function has woefully
inadequate error checking; the behaviour
is undefined if you screw up the call */

void swap(void *vleft, void *vright, size_t len);




int main(void)
{
double d1 = 23.999;
double d2 = 999.23;
long u1 = LONG_MAX;
long u2 = LONG_MIN;


printf("d1 = %f, d2 = %f\n", d1, d2);
printf("u1 = %ld, u2 = %ld\n\n", u1, u2);
swap(&d1, &d2, sizeof(d1));
swap(&u1, &u2, sizeof(u1));
printf("Values Swapped\n\n");
printf("d1 = %f, d2 = %f\n", d1, d2);
printf("u1 = %ld, u2 = %ld\n\n", u1, u2);


return 0;
}


void swap(void *vleft, void *vright, size_t len)
{
unsigned char *left = vleft;
unsigned char *right = vright;
unsigned char tmp;
while(len--)
{
tmp = *left;
*left++ = *right;
*right++ = tmp;
}
}
=========================== OUTPUT =====================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
[arnuld@dune programs]$ ./a.out
d1 = 23.999000, d2 = 999.230000
u1 = 2147483647, u2 = -2147483648

Values Swapped

d1 = 999.230000, d2 = 23.999000
u1 = -2147483648, u2 = 2147483647

[arnuld@dune programs]$

 

[user923005]

On Sun, 01 Nov 2009 19:40:03 +0000, Richard Heathfield wrote:
#include <stddef.h>

/* the following function has woefully
   inadequate error checking; the behaviour is undefined if you screw up
   the call */

void swap(void *vleft, void *vright, size_t len) {
  unsigned char *left = vleft;
  unsigned char *right = vright;
  unsigned char tmp;
  while(len--)
  {
    tmp = *left;
    *left++ = *right;
    *right++ = tmp;
  }
}

If arguments are /double*/ or types with values larger than /unsigned
char/ , we are going to get 2 implicit casts which will result only in
some random values assigned but this works correctly. Some sort of
pointer-magic ?

#include <stdio.h>
#include <stddef.h>
#include <limits.h>

/* the following function has woefully
   inadequate error checking; the behaviour
   is undefined if you screw up the call */

void swap(void *vleft, void *vright, size_t len);

int main(void)
{
  double d1 = 23.999;
  double d2 = 999.23;
  long u1 = LONG_MAX;
  long u2 = LONG_MIN;

  printf("d1 = %f, d2 = %f\n", d1, d2);
  printf("u1 = %ld, u2 = %ld\n\n", u1, u2);
  swap(&d1, &d2, sizeof(d1));
  swap(&u1, &u2, sizeof(u1));
  printf("Values Swapped\n\n");
  printf("d1 = %f, d2 = %f\n", d1, d2);
  printf("u1 = %ld, u2 = %ld\n\n", u1, u2);

  return 0;

}

void swap(void *vleft, void *vright, size_t len)
{
  unsigned char *left = vleft;
  unsigned char *right = vright;
  unsigned char tmp;
  while(len--)
  {
    tmp = *left;
    *left++ = *right;
    *right++ = tmp;
  }}

=========================== OUTPUT =====================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
[arnuld@dune programs]$ ./a.out
d1 = 23.999000, d2 = 999.230000
u1 = 2147483647, u2 = -2147483648

Values Swapped

d1 = 999.230000, d2 = 23.999000
u1 = -2147483648, u2 = 2147483647

[arnuld@dune programs]$

An especially clever swap routine is found in here (I left the entire
code body so you can see how it is used and even test it if you like):

/*
* Modifications from vanilla NetBSD source:
* Add do ... while() macro fix
* Remove __inline, _DIAGASSERTs, __P
*
* $PostgreSQL: pgsql/src/port/qsort.c,v 1.5 2004/10/05 00:12:49
neilc Exp $
*/

/* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */

/*-
* Copyright (c) 1992, 1993
* The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above
copyright
* notice, this list of conditions and the following disclaimer in
the
* documentation and/or other materials provided with the
distribution.
* 3. Neither the name of the University nor the names of its
contributors
* may be used to endorse or promote products derived from this
software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
OF
* SUCH DAMAGE.
*/

#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>

#define CROSSOVER_POINT (15)

static char *med3(char *, char *, char *, int (*) (const void *,
const void *));
static void swapfunc(char *, char *, size_t, int);

#undef min
#define min(a, b) ((a) < (b) ? (a) : (b))

/*
* Qsort routine from Bentley & McIlroy's "Engineering a Sort
Function".
*/
#define swapcode(TYPE, parmi, parmj, n) \
do { \
size_t i = (n) / sizeof (TYPE); \
TYPE *pi = (TYPE *)(void *)(parmi); \
TYPE *pj = (TYPE *)(void *)(parmj); \
do { \
TYPE t = *pi; \
*pi++ = *pj; \
*pj++ = t; \
} while (--i > 0); \
} while (0)

#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof
(long) || \
es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

static void swapfunc(char *a, char *b, size_t n, int swaptype)
{
if (swaptype <= 1)
swapcode(long, a, b, n);
else
swapcode(char, a, b, n);
}

#define swap(a, b) \
if (swaptype == 0) { \
long t = *(long *)(void *)(a); \
*(long *)(void *)(a) = *(long *)(void *)(b); \
*(long *)(void *)(b) = t; \
} else \
swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n),
swaptype)

static char *med3(char *a, char *b, char *c, int (*cmp) (const void
*, const void *))
{
return cmp(a, b) < 0 ?
(cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
}

static int sorted(void *arr, size_t count, size_t stride, int
(*cmp) (const void *, const void *))
{
size_t i;
char *p = arr;
char *thisp = p;
char *nextp = p + stride;
for (i = 0; i < count-1; i++)
{
if (cmp(thisp, nextp) > 0) {
return 0;
}
thisp = nextp;
nextp += stride;
}
return 1;
}

void qsb(void *a, size_t n, size_t es, int (*cmp) (const
void *, const void *))
{
char *pa,
*pb,
*pc,
*pd,
*pl,
*pm,
*pn;
int d,
r,
swaptype,
swap_cnt;

SWAPINIT(a, es);
loop:
swap_cnt = 0;
if (n < CROSSOVER_POINT) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; pl -
= es)
swap(pl, pl - es);
return;
}
if (sorted(a, n, es, cmp)) return;
pm = (char *) a + (n / 2) * es;
pl = (char *) a;
pn = (char *) a + (n - 1) * es;
if (n > 40) {
d = (n / 8) * es;
pl = med3(pl, pl + d, pl + 2 * d, cmp);
pm = med3(pm - d, pm, pm + d, cmp);
pn = med3(pn - 2 * d, pn - d, pn, cmp);
}
pm = med3(pl, pm, pn, cmp);
swap(a, pm);
pa = pb = (char *) a + es;

pc = pd = (char *) a + (n - 1) * es;
for (; {
while (pb <= pc && (r = cmp(pb, a)) <= 0) {
if (r == 0) {
swap_cnt = 1;
swap(pa, pb);
pa += es;
}
pb += es;
}
while (pb <= pc && (r = cmp(pc, a)) >= 0) {
if (r == 0) {
swap_cnt = 1;
swap(pc, pd);
pd -= es;
}
pc -= es;
}
if (pb > pc)
break;
swap(pb, pc);
swap_cnt = 1;
pb += es;
pc -= es;
}
if (swap_cnt == 0) { /* Switch to insertion sort */
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
pn = (char *) a + n * es;
r = min(pa - (char *) a, pb - pa);
vecswap(a, pb - r, r);
r = min(pd - pc, pn - pd - es);
vecswap(pb, pn - r, r);
if ((r = pb - pa) > es)
qsb(a, r / es, es, cmp);
if ((r = pd - pc) > es) {
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}
}

 

[Seebs]

If arguments are /double*/ or types with values larger than /unsigned
char/ , we are going to get 2 implicit casts which will result only in
some random values assigned but this works correctly. Some sort of
pointer-magic ?

No magic at all. When you convert a pointer to an object to a pointer to
unsigned char, you can iterate over its length copying individual bytes.
You can treat any object foo as an array of sizeof(foo) unsigned chars.

-s

 

[Nick Keighley]

 

[Seebs]

really?

I'd guess that's a typo, rather than an accurate description of an algorithm
that inexplicably flipped a bit.

-s

 

[arnuld]

No, a cast is an explicit conversion, so "implicit cast" is an oxymoron.

Wait a minute:

int i = 2.03;

that i will be assigned a value of 2. 2.03 was casted (converted ?)
implicitly to 2.

I hope this analogy (which, being an analogy, cannot be a perfect
parallel) will help you to understand. Here's a picture for you:

.....SNIP...

That was brilliant. I understood 100% of it. Many thanks