🚀 go-pugleaf

yang@math.umass.edu (Huayong Yang) writes:

>I know void* means an arbitrary pointer. In an interview, I was asked to
>write a routine that swaps two pointers.

>I tried with this

>void Swap(void** p1, void** p2)

This is a routine to swap two "void *". It is _not_ a general pointer-
swapping routine.

>{
>  void* p = *p1;
>  *p1 = *p2;
>  *p2 = *p;

If you swap two integers, you don't dereference your "swap" variable.
You should _not_ do so when dealing with pointers.

   *p2 = p;

would be good enough in a routine that swaps two void pointers.

>}

>but it is not correct, because void* is not allowed as operand.

It is not allowed to dereference a void *, not is it necessary in
this example.

Kurt
--
| Kurt Watzka                             Phone : +49-89-2180-6254
| watzka@stat.uni-muenchen.de
| ua302aa@sunmail.lrz-muenchen.de

Kurt Watzka (watzka@stat.uni-muenchen.de) wrote:

: yang@math.umass.edu (Huayong Yang) writes:

: >void Swap(void** p1, void** p2)

: It is not allowed to dereference a void *, not is it necessary in
: this example.

I agree. But you forgot to give an answer to Huayong.
Please enlighten us with *your* solution to this problem.

The best I could directly think of is :

void swap(void ** x, void ** y)
{
	char * tmp;

	tmp = *( (char**)x );
	*( (char**)x ) = *( (char**)y );
	*( (char**)y ) = tmp;
}

You would call it for 
	SomeType * x, * y 
sth like
	swap((void**)&x,(void**)&y);
to avoid "incompatible pointer type"-warnings.

Best regards

	Claus

Claus Hirth <hirth@wand.franken.de> writes:
>Kurt Watzka (watzka@stat.uni-muenchen.de) wrote:
>: yang@math.umass.edu (Huayong Yang) writes:

>: >void Swap(void** p1, void** p2)

>: It is not allowed to dereference a void *, not is it necessary in
>: this example.

>I agree. But you forgot to give an answer to Huayong.
>Please enlighten us with *your* solution to this problem.

>The best I could directly think of is :

>void swap(void ** x, void ** y)
>{
>	char * tmp;

There is _no_ need to make this a char*. It can well be a void *, and
you don't need any casts.

>	tmp = *( (char**)x );

How about

    tmp = *x;

There is nothing wrong with dereferencing a pointer to pointer to void.

>	*( (char**)x ) = *( (char**)y );
>	*( (char**)y ) = tmp;

>From the same line of thought comes

   *x = *y;
   *y = tmp;

>}

>You would call it for 
>	SomeType * x, * y 

I would _not_ call it for anything but void pointers or char pointers,
because there is no generic pointer to pointer type in C, and the only
pointer type that must have the same representation as a void pointer
is a char pointer. 

>sth like
>	swap((void**)&x,(void**)&y);
>to avoid "incompatible pointer type"-warnings.

Avoiding warnings in this case means that you tell the compiler you know
what you are doing. If you know what you are doing, for example, if you
know that all pointer types will have the same representation on all
machines that your program will ever run on, go ahead. 

If this is not the case, you cannot write such a function using pointers
to pointers. You can still write a generic swap(), but it takes two
void pointers as it's arguments, and it has an additional "size" 
parameter. Such a generic swap function can fail, and it can be used 
to swap two pointers to SomeType:

   #include <string.h>

   int
   swap(void *a, void *b, size_t sz)
   {
      void *tmp;

      tmp = malloc(sz);
      if (tmp == NULL)
         return 0;
      memcpy(tmp, a, sz);
      memcpy(a, b, sz);
      memcpy(b, tmp, sz);
      return 1;
   }


   SomeType *a, b;

   if (!swap(&a, &b))
      /* die whining */
 

Kurt
--
| Kurt Watzka                             Phone : +49-89-2180-6254
| watzka@stat.uni-muenchen.de
| ua302aa@sunmail.lrz-muenchen.de

In article <4ja3qf$p9b@solutions.solon.com>
           hirth@wand.franken.de "Claus Hirth" writes:

 >Kurt Watzka (watzka@stat.uni-muenchen.de) wrote:
 >
 >: yang@math.umass.edu (Huayong Yang) writes:
 >
 >: >void Swap(void** p1, void** p2)
 >
 >: It is not allowed to dereference a void *, not is it necessary in
 >: this example.
 >
 >I agree. But you forgot to give an answer to Huayong.
 >Please enlighten us with *your* solution to this problem.

There isn't a simple generic solution to this problem.

 >The best I could directly think of is :
 >
 >void swap(void ** x, void ** y)
 >{
 >        char * tmp;
 >
 >        tmp = *( (char**)x );
 >        *( (char**)x ) = *( (char**)y );
 >        *( (char**)y ) = tmp;

You're treating the object being swapped as if it is a char *. If it
isn't a char * then this may not work - it results in undefined behaviour.

 >}
 >
 >You would call it for 
 >        SomeType * x, * y 
 >sth like
 >        swap((void**)&x,(void**)&y);
 >to avoid "incompatible pointer type"-warnings.

The warnings are there to indicate that you're doing something very wrong.
Simply shutting up the warnings is shooting yourself in the foot. Pointer
casting like this is rarely a sensible thing to do.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

In article <4jckqc$a5o@solutions.solon.com> watzka@stat.uni-muenchen.de
(Kurt Watzka) writes:

|> If this is not the case, you cannot write such a function using pointers
|> to pointers. You can still write a generic swap(), but it takes two
|> void pointers as it's arguments, and it has an additional "size" 
|> parameter. Such a generic swap function can fail, and it can be used 
|> to swap two pointers to SomeType:

|>    #include <string.h>

|>    int
|>    swap(void *a, void *b, size_t sz)
|>    {
|>       void *tmp;

|>       tmp = malloc(sz);
|>       if (tmp == NULL)
|>          return 0;
|>       memcpy(tmp, a, sz);
|>       memcpy(a, b, sz);
|>       memcpy(b, tmp, sz);

I think you forgot:

        free( tmp ) ;

Otherwise, you are guaranteed that the function will return 0 if you
call it often enough:-).

|>       return 1;
|>    }


|>    SomeType *a, b;

|>    if (!swap(&a, &b))
|>       /* die whining */

And you forgot your own extra parameter:-):

    if ( ! swap( &a , &b , sizeof( SomeType ) )
        ...

BTW, I've found that a small optimizing trick in functions like this can
sometimes work wonders for performance:

    int
    swap( void* a , void* b , size_t sz )
    {
        unsigned char   buffer[ EXPECTEDMAXSIZE ] ;
        void*           tmp = (sz <= sizeof( buffer ))
                                ? buffer
                                : malloc( sz ) ;
        if ( tmp == NULL )
            return 0 ;
        memcpy(tmp, a, sz);
        memcpy(a, b, sz);
        memcpy(b, tmp, sz);
        if ( tmp != buffer )
            free( tmp ) ;
        return 1 ;
    }
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
                            -- Beratung in industrieller Datenverarbeitung

J. Kanze (kanze@gabi-soft.fr) wrote:

: BTW, I've found that a small optimizing trick in functions like this can
: sometimes work wonders for performance:

:     int
:     swap( void* a , void* b , size_t sz )
:     {
:         unsigned char   buffer[ EXPECTEDMAXSIZE ] ;

An even smaller "trick" : use a static array instead.

Anyway.

What still nags at me about the portability issue : 
Is there a machine still in use (Kurt, please name it)
on which the representation of a 
	double * 
differs from the representation of a 
	char * 
?

Have a nice week-end

	Claus

In article <4jibl5$89u@solutions.solon.com>,
J. Kanze <kanze@gabi-soft.fr> wrote:
>In article <4jckqc$a5o@solutions.solon.com> watzka@stat.uni-muenchen.de
>(Kurt Watzka) writes:

[snip]

>|>    SomeType *a, b;
>
>|>    if (!swap(&a, &b))
>|>       /* die whining */
>
>And you forgot your own extra parameter:-):

And you forgot one ")" in:
>
>    if ( ! swap( &a , &b , sizeof( SomeType ) )
>        ...
Or perhaps you moved it up to your smiley  :)

And everyone's missed that interesting declaration for a and b
so far.  Reminds me of a recent thread  :)

>
>BTW, I've found that a small optimizing trick in functions like this can
>sometimes work wonders for performance:
>
>    int
>    swap( void* a , void* b , size_t sz )
>    {
>        unsigned char   buffer[ EXPECTEDMAXSIZE ] ;
>        void*           tmp = (sz <= sizeof( buffer ))
>                                ? buffer
>                                : malloc( sz ) ;

Or, if you don't need reentrant or resursive code, you can do:
	static void *tmp = NULL;
	static size_t tmp_sz = 0;

	if (sz > tmp_sz) {
	    .... use realloc here .... you get the idea ....

Details left to the reader (I'm feeling lazy tonight  :)

This avoids having to guess what EXPECTEDMAXSIZE might be,
but also suffers from never freeing that buffer.  OTOH, it might
end up avoiding zillions of calls to malloc if the guess was poor.
I've had a couple of thing like that bite when data formats
were changed, and I had code inherited from people long-gone.

The realloc can certainly do something like use sz+10000
to "grow" the tmp area in tunable chunks, depending on the application.

Cheers,
Stan.
--
Stan Ryckman  (stanr@tiac.net)

In article <4jmcnr$lr2@solutions.solon.com> stanr@tiac.net (Stan
Ryckman) writes:

|> In article <4jibl5$89u@solutions.solon.com>,

|> J. Kanze <kanze@gabi-soft.fr> wrote:

|> >BTW, I've found that a small optimizing trick in functions like this can
|> >sometimes work wonders for performance:
|> >
|> >    int
|> >    swap( void* a , void* b , size_t sz )
|> >    {
|> >        unsigned char   buffer[ EXPECTEDMAXSIZE ] ;
|> >        void*           tmp = (sz <= sizeof( buffer ))
|> >                                ? buffer
|> >                                : malloc( sz ) ;

|> Or, if you don't need reentrant or resursive code, you can do:
|> 	static void *tmp = NULL;
|> 	static size_t tmp_sz = 0;

|> 	if (sz > tmp_sz) {
|> 	    .... use realloc here .... you get the idea ....

I wish I'd have thought of this when I actually encountered the problem.
In the real case, the original author of the function had used multiple
returns, and I had a bit of a job finding all of the places where I had
to insert the `free'.  (The original code simply overwrote the rest of
the stack if sz were larger than EXPECTEDMAXSIZE.  Which sort of
explains why I was looking at it in the first place:-).)

|> Details left to the reader (I'm feeling lazy tonight  :)

|> This avoids having to guess what EXPECTEDMAXSIZE might be,
|> but also suffers from never freeing that buffer.  OTOH, it might
|> end up avoiding zillions of calls to malloc if the guess was poor.
|> I've had a couple of thing like that bite when data formats
|> were changed, and I had code inherited from people long-gone.

|> The realloc can certainly do something like use sz+10000
|> to "grow" the tmp area in tunable chunks, depending on the application.

Better yet: unless memory is really tight, have it double the size.
This will set a fairly reasonable upper bound on the number of reallocs
you will have to do.
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
                            -- Beratung in industrieller Datenverarbeitung

In article <4jmcnh$lqk@solutions.solon.com>, Claus Hirth <hirth@wand.franken.de> writes:
|> J. Kanze (kanze@gabi-soft.fr) wrote:
|> 
|> : BTW, I've found that a small optimizing trick in functions like this can
|> : sometimes work wonders for performance:
|> 
|> :     int
|> :     swap( void* a , void* b , size_t sz )
|> :     {
|> :         unsigned char   buffer[ EXPECTEDMAXSIZE ] ;
|> 
|> An even smaller "trick" : use a static array instead.

What improvement do you hope to gain with a static array?

Konrad Schwarz 

Claus Hirth wrote:
> What still nags at me about the portability issue :
> Is there a machine still in use (Kurt, please name it)
> on which the representation of a
>         double *
> differs from the representation of a
>         char *
> ?

Well, I'm not Kurt, but as I recall the Data General Eclipse
series of computers used 32-bit byte addresses for (char *)
and 31-bit word addresses for (double *).  Word addresses had
to be left-shifted by one to create the equivalent byte address,
and vice versa.  (If I recall correctly, DG used the top
bit of a word address to do some funky indirect addressing.)

Caveat: this was back in my Fortran days; I don't think I
ever worked with a C compiler on that machine, but I don't
see how it could have avoided using different representations
for character pointers and other pointers.

Perhaps I'm confused but when I read the question this is what I came
up with.  It compiles and worked as expected in a test case.

As far as the two pointers to be swapped are concerned, they are of
the same type correct?

I do not see the problem with:

void swap_ptr(void **p1, void **p2) {
  void *tmp = *p1;

  *p1 = *p2;
  *p2 = tmp;

  return;
}


Granted I did not do an extensive test but I did try ints, chars and floats
with no surprises. As in:

#include <stdio.h>
#include"swap_ptr.h"

int main(void) {
  char c1='A', c2='B', *pc1, *pc2;
  int  i1=1, i2=2, *pi1, *pi2;
  float f1=1.1, f2=2.2, *pf1, *pf2;

  pc1 = &c1;
  pc2 = &c2;
  pi1 = &i1;
  pi2 = &i2;
  pf1 = &f1;
  pf2 = &f2;

  printf("%c , %c\n", *pc1, *pc2);
  swap_ptr(pc1, pc2);
  printf("%c , %c\n", *pc1, *pc2);

  printf("%d, %d\n", *pi1, *pi2);
  swap_ptr(pi1, pi2);
  printf("%d, %d\n", *pi1, *pi2);

  printf("%f, %f\n", *pf1, *pf2);
  swap_ptr(pf1, pf2);
  printf("%f, %f\n", *pf1, *pf2);

  return(0);
}

The output looks like:

r980(davidm)$ main
A , B
B , A
1, 2
2, 1
1.100000, 2.200000
2.200000, 1.100000
r980(davidm)$ 

Could someone enlighten me as to why this thread is so long?


Thanks
Dave

On 27 Mar 1996 18:03:37 -0600, Lawrence Kirby <fred@genesis.demon.co.uk>
wrote:
 :  >: yang@math.umass.edu (Huayong Yang) writes:
 :  >
 :  >: >void Swap(void** p1, void** p2)
[...]
 : There isn't a simple generic solution to this problem.

I think it is an example of a ridiculous question.  What is wrong with this:

    Some_Type *a, *b;
       .
       .
    if (some_condition_has_occured_where_a_and_b_need_swapped)
      {
         Some_Type *tmp;
	 tmp = a; a = b; b = tmp;
      }
-- 
John E. Davis                   Center for Space Research/AXAF Science Center
617-258-8119                    MIT 37-662c, Cambridge, MA 02139
http://space.mit.edu/~davis

> > The realloc can certainly do something like use sz+10000
> > to "grow" the tmp area in tunable chunks, depending on the application.
> 
> Better yet: unless memory is really tight, have it double the size.
> This will set a fairly reasonable upper bound on the number of reallocs
> you will have to do.

Better yet: change "unless memory is really tight" to "if memory is
plentiful".  The doubling method can run out of memory when the amount
available is almost twice the amount that you need, not even considering
the possibility of fragmentation.
-- 
Mark Brader              "I always pass on good advice.  It's the only thing
msb@sq.com                 to do with it.  It is never any use to oneself."
SoftQuad Inc., Toronto       -- Lord Goring  (Oscar Wilde: An Ideal Husband)

My text in this article is in the public domain.

In article <4jmcnh$lqk@solutions.solon.com>
           hirth@wand.franken.de "Claus Hirth" writes:

 >J. Kanze (kanze@gabi-soft.fr) wrote:
 >
 >: BTW, I've found that a small optimizing trick in functions like this can
 >: sometimes work wonders for performance:
 >
 >:     int
 >:     swap( void* a , void* b , size_t sz )
 >:     {
 >:         unsigned char   buffer[ EXPECTEDMAXSIZE ] ;
 >
 >An even smaller "trick" : use a static array instead.

In what sense is that smaller?

 >Anyway.
 >
 >What still nags at me about the portability issue : 
 >Is there a machine still in use (Kurt, please name it)
 >on which the representation of a 
 >        double * 
 >differs from the representation of a 
 >        char * 
 >?

Section 5.17 of the FAQ suggests some candidates.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

In article <4jol6e$1rr@solutions.solon.com>,
J. Kanze <kanze@gabi-soft.fr> wrote:
>In article <4jmcnr$lr2@solutions.solon.com> stanr@tiac.net (Stan
>Ryckman) writes:

[snip]

>|> Or, if you don't need reentrant or resursive code, you can do:
>|> 	static void *tmp = NULL;
>|> 	static size_t tmp_sz = 0;
>
>|> 	if (sz > tmp_sz) {
>|> 	    .... use realloc here .... you get the idea ....
>
>I wish I'd have thought of this when I actually encountered the problem.
>In the real case, the original author of the function had used multiple
>returns, and I had a bit of a job finding all of the places where I had
>to insert the `free'.  (The original code simply overwrote the rest of
>the stack if sz were larger than EXPECTEDMAXSIZE.  Which sort of
>explains why I was looking at it in the first place:-).)

When I first "invented" this it was the same problem... something
on the stack (i.e., "auto") sized at EXPECTEDMAXSIZE, written
by a junior programmer because the data could *NEVER* be larger.
Of course, things changed, and the data became larger (but, to
make things more fun, only about once per day in a continuous
data stream), and I inherited the problem of fixing the mysterious
occasional crashes.

The old moral:  *never* trust your inputs.

[more snipped]

>Better yet: unless memory is really tight, have it double the size.
>This will set a fairly reasonable upper bound on the number of reallocs
>you will have to do.

Not necessarily better.  If you're at 40% of your machine's
physical memory, doubling could be a real performance killer.
With my suggestion (add some amount to the size and realloc)
you will rapidly reach the max if the sizes arrive "randomly".
Any strategy here would involve knowing something about your
target system, I think, but probably something like
11*(sz+C)/10 where C is much less than the physical memory
on your computer would be safer (even a few hundred realloc calls
rather than a dozen or so shouldn't matter, if the calls
occur with an "unlucky" distribution of sz values).

Cheers,
Stan.

ps - Your article was posted as a "sibling" article to mine
rather than a "child".  Your news posting software may be
doing something incorrect with references (specifically,
dropping one.)
--
Stan Ryckman  (stanr@tiac.net)

watzka@stat.uni-muenchen.de (Kurt Watzka):
> If this is not the case, you cannot write such a function using pointers
> to pointers. You can still write a generic swap(), but it takes two
> void pointers as it's arguments, and it has an additional "size" 

Actually, you can't, since you can't pass a pointer to a variable
that has been defined with "register"...  But if you don't pass a
pointer, you can't swap arrays.  Therefore, you can't write a generic
swap function or macro.  (The FAQ may say something about this.)

My Publib function library has a anything-but-register-variables
swap function, of course. :-)

-- 
Lars Wirzenius <liw@iki.fi> <wirzeniu@kruuna.helsinki.fi>
MIME and PGP mail welcome.  Key: finger @kruuna, or check keyservers.
Publib http://www.iki.fi/liw/publib/

In article <4jq1e4$a2g@solutions.solon.com>
           David_McReynolds@vos.stratus.com "David McReynolds" writes:

>Perhaps I'm confused but when I read the question this is what I came
>up with.  It compiles and worked as expected in a test case.
>
>As far as the two pointers to be swapped are concerned, they are of
>the same type correct?
>
>I do not see the problem with:
>
>void swap_ptr(void **p1, void **p2) {
>  void *tmp = *p1;
>
>  *p1 = *p2;
>  *p2 = tmp;
>
>  return;
>}

This swaps 2 void * pointers, it isn't guaranteed to swap any other type
of pointer (except possibly char *). There is no guarantee that any other
pointer has the same size or representation as void * (except char *).

>Granted I did not do an extensive test but I did try ints, chars and floats
>with no surprises. As in:

You're assuming that all non-function pointers at least have the same size if
not the same representation. That may well hold on your platform but isn't
true in general. As far as the C language is concerned your code invokes
undefined behaviour and is not portable.

>Could someone enlighten me as to why this thread is so long?

Well, a couple of the articles suggest systems where your assumption
doesn't hold.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

In article <4jr71q$h66@solutions.solon.com> stanr@tiac.net "Stan Ryckman" writes:

>>Better yet: unless memory is really tight, have it double the size.
>>This will set a fairly reasonable upper bound on the number of reallocs
>>you will have to do.
>
>Not necessarily better.  If you're at 40% of your machine's
>physical memory, doubling could be a real performance killer.
>With my suggestion (add some amount to the size and realloc)
>you will rapidly reach the max if the sizes arrive "randomly".
>Any strategy here would involve knowing something about your
>target system, I think, but probably something like
>11*(sz+C)/10 where C is much less than the physical memory
>on your computer would be safer (even a few hundred realloc calls
>rather than a dozen or so shouldn't matter, if the calls
>occur with an "unlucky" distribution of sz values).

My normal approach to this is to start with some reasonable non-zero value
and use:

   sz += sz / X;

where X is typically 2, 4 or 8 depending on the prevailing conditions (small
sop to efficiency).

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

msb@sq.com wrote:
: > > The realloc can certainly do something like use sz+10000
: > > to "grow" the tmp area in tunable chunks, depending on the application.
: > 
: > Better yet: unless memory is really tight, have it double the size.
: > This will set a fairly reasonable upper bound on the number of reallocs
: > you will have to do.

: Better yet: change "unless memory is really tight" to "if memory is
: plentiful".  The doubling method can run out of memory when the amount
: available is almost twice the amount that you need, not even considering
: the possibility of fragmentation.

Of course, if temporary realloc'ed buffers are a significant
percentage of a program's memory usage, it's design should be
rethought anyway ...

Under normal circumstances, O(log N) reallocs beats O(N) reallocs any
day (where N is the largest size buffer needed).

---------------------------------------------------------------------------
Tim Hollebeek         | Disclaimer :=> Everything above is a true statement,
Electron Psychologist |                for sufficiently false values of true.
Princeton University  | email: tim@wfn-shop.princeton.edu
----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)

davidm@ssi.stratus.com (David McReynolds) wrote:

 > Perhaps I'm confused but when I read the question this is what I came
 > up with.  It compiles and worked as expected in a test case.
 > 
 > As far as the two pointers to be swapped are concerned, they are of
 > the same type correct?
 > 
 > I do not see the problem with:
 > 
 > void swap_ptr(void **p1, void **p2) {
 >   void *tmp = *p1;
 > 
 >   *p1 = *p2;
 >   *p2 = tmp;
 > 
 >   return;
 > }
 > 
 > 
 > Granted I did not do an extensive test but I did try ints, chars and floats
 > with no surprises. As in:
 > 
 > #include <stdio.h>
 > #include"swap_ptr.h"
 > 
 > int main(void) {
 >   char c1='A', c2='B', *pc1, *pc2;
 >   int  i1=1, i2=2, *pi1, *pi2;
 >   float f1=1.1, f2=2.2, *pf1, *pf2;
 > 
 >   pc1 = &c1;
 >   pc2 = &c2;
 >   pi1 = &i1;
 >   pi2 = &i2;
 >   pf1 = &f1;
 >   pf2 = &f2;
 > 
 >   printf("%c , %c\n", *pc1, *pc2);
 >   swap_ptr(pc1, pc2);
 >   printf("%c , %c\n", *pc1, *pc2);
 > 
 >   printf("%d, %d\n", *pi1, *pi2);
 >   swap_ptr(pi1, pi2);
 >   printf("%d, %d\n", *pi1, *pi2);
 > 
 >   printf("%f, %f\n", *pf1, *pf2);
 >   swap_ptr(pf1, pf2);
 >   printf("%f, %f\n", *pf1, *pf2);
 > 
 >   return(0);
 > }
 > 
 > The output looks like:
 > 
 > r980(davidm)$ main
 > A , B
 > B , A
 > 1, 2
 > 2, 1
 > 1.100000, 2.200000
 > 2.200000, 1.100000
 > r980(davidm)$ 
 > 
 > Could someone enlighten me as to why this thread is so long?

Perhaps it's so long because people keep posting nonsense like you
just did.

If that program compiles, you need to get another compiler.  swap_ptr
is defined as taking void** arguments but your program is passing
char*, int*, and float* arguments.

Unless, of course, you are lying to the compiler in swap_ptr.h and
telling it that the function takes void* arguments.  In that case the
program results in undefined behavior.  In practice most compilers
will swap more memory than they should (for some types), possible
messing up other variables or less than they should, messing up the
variables being swapped.

Michael M Rubenstein

In article <4jq1o1$a8v@solutions.solon.com>, msb@sq.com writes:
|> > > The realloc can certainly do something like use sz+10000
|> > > to "grow" the tmp area in tunable chunks, depending on the application.

|> > Better yet: unless memory is really tight, have it double the size.

|> Better yet: change "unless memory is really tight" to "if memory is
|> plentiful".

alloca (), anybody?

Konrad Schwarz

In article <4jr71q$h66@solutions.solon.com>, stanr@tiac.net (Stan Ryckman) writes:

|> >Better yet: unless memory is really tight, have it double the size.

|> Not necessarily better.  If you're at 40% of your machine's
|> physical memory, doubling could be a real performance killer.

40% * 2 = 80% < 1, so 40% is kind of a bad choice for an example :)

|> With my suggestion (add some amount to the size and realloc)
|> you will rapidly reach the max if the sizes arrive "randomly".

I'd like to point out that the
worst case behavior with linear increases is O (n) mallocs and O (n**2) copies,
where n is the maximum size of blocks encountered;
with doubling, it is O (ld n) mallocs and O (n) copies.

|> Any strategy here would involve knowing something about your
|> target system, I think, [...]

Konrad Schwarz

In article <4jq1o1$a8v@solutions.solon.com> msb@sq.com writes:

|> > > The realloc can certainly do something like use sz+10000
|> > > to "grow" the tmp area in tunable chunks, depending on the application.
|> > 
|> > Better yet: unless memory is really tight, have it double the size.
|> > This will set a fairly reasonable upper bound on the number of reallocs
|> > you will have to do.

|> Better yet: change "unless memory is really tight" to "if memory is
|> plentiful".  The doubling method can run out of memory when the amount
|> available is almost twice the amount that you need, not even considering
|> the possibility of fragmentation.

I guess it depends on the definition of `really tight'.  Now that most
machines have virtual memory, I tend to only consider two situations:
`memory is really tight' (no virtual memory) or `memory is plentiful'
(virtual memory).

You're right, of course, in that it is one aspect to consider.  (I
suppose you could also add code that when doubling failed, you tried 1.5
times, then 1.25, then...:-)
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
                            -- Beratung in industrieller Datenverarbeitung

In article <4jttgp$3nh@solutions.solon.com>,
telnet user <tim@wagner.Princeton.EDU> wrote:
>msb@sq.com wrote:
[I wrote]
:: > > The realloc can certainly do something like use sz+10000
:: > > to "grow" the tmp area in tunable chunks, depending on the application.
:: > 
:: > Better yet: unless memory is really tight, have it double the size.
:: > This will set a fairly reasonable upper bound on the number of reallocs
:: > you will have to do.
:
:: Better yet: change "unless memory is really tight" to "if memory is
:: plentiful".  The doubling method can run out of memory when the amount
:: available is almost twice the amount that you need, not even considering
:: the possibility of fragmentation.

:Of course, if temporary realloc'ed buffers are a significant
:percentage of a program's memory usage, it's design should be
:rethought anyway ...

   (Q to moderator:  are mentions of misuse of the English language
   disallowed?  I'm getting tired of "it's" and "its" being used
   interchangeably.)

Not necessarily.  Besides, as proposed here, the buffer is not
temporary.  The first version used temporary malloc'd buffers whenever
sz exceeded some MAX_EXPECTED_SIZE.

:Under normal circumstances, O(log N) reallocs beats O(N) reallocs any
:day (where N is the largest size buffer needed).

Huh?  Neither adding a fixed number to sz, nor using 2*sz, has
anything to do with O(anything) here.  Both do a fairly trivial
number of realloc()'s and then reach the needed size, compared to the
original method, which would have required malloc() and free() on every
call to the function when MAX_EXPECTED_SIZE was poorly guessed.
As Mark pointed out, doubling leaves you with the potential of
using, say, 90% of the memory when you only need 46%.

I hereby modify my original suggestion, however, that realloc()
be used.  It's probably better (or equal) to free() and then malloc()
the new buffer, since at the time of the resizing, there is no need to
preserve its contents.  (I worked hard to get a sentence using both
"it's" and "its"!!  :)

:---------------------------------------------------------------------------
:Tim Hollebeek         | Disclaimer :=> Everything above is a true statement,
:Electron Psychologist |                for sufficiently false values of true.
:Princeton University  | email: tim@wfn-shop.princeton.edu
:----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)

Oh, you talk to electrons?  That explains it!  :)

Cheers,
Stan.
--
Stan Ryckman  (stanr@tiac.net)

Ok, time for my submission to this old thread.
My approach to a (generic) swap routine is that is must be reentrant
(no static buffers here!) and also should not dynamically allocate memory.
So we swap in place. Byte for byte (or char for char). It compiles cleanly
with gcc-2.7.2 (but gcc is not THE benchmark for STDC-compliant programs,
I know that).

---Programs follows---
#include <assert.h>
#include <stdio.h>
#include <stddef.h>

#define SWAP(a, b) memswap(&(a), &(b), sizeof(a))

static void
memswap(void *_a, void *_b, register size_t size)
{
	if (_a != _b)
	{
		register char *a = _a;
		register char *b = _b;
		/* Assert that objects don't overlap. */
		assert(a + size <= b || b + size <= a);
		for (; size != 0; size--, a++, b++)
		{
			register int c = *a;
			*a = *b;
			*b = c;
			/* This loop could be optimized, for instance by checking
			   for suitable alignment of a and b pointers and copying
			   larger units instead of bytes. */
		}
	}
}

int main()
{
	double x = 1.0, y = 2.0;
	printf("before swap: x = %f, y = %f\n", x, y);
	SWAP(x, y);
	printf("after swap:  x = %f, y = %f\n", x, y);
	return 0;
}
---Program ends---

Mufsi:tmp> gcc -g -Wall -ansi -pedantic swap.c -o swap
Mufsi:tmp> swap
before swap: x = 1.000000, y = 2.000000
after swap:  x = 2.000000, y = 1.000000
Mufsi:tmp>

	Ola Liljedahl
	olli@enea.se
	"OSE - Design on a higher level"

In article <4jmcnr$lr2@solutions.solon.com> stanr@tiac.net (Stan Ryckman) writes:
   >    int
   >    swap( void* a , void* b , size_t sz )
   >    {
   >        unsigned char   buffer[ EXPECTEDMAXSIZE ] ;
   >        void*           tmp = (sz <= sizeof( buffer ))
   >                                ? buffer
   >                                : malloc( sz ) ;

   Or, if you don't need reentrant or resursive code, you can do:
	   static void *tmp = NULL;
	   static size_t tmp_sz = 0;

	   if (sz > tmp_sz) {
	       .... use realloc here .... you get the idea ....

 Isn't this a bad thing to do though ?

 Because as I see it you only have to have one call to the function
with sz being large and then you have that mem eaten up forever even
if all your other calls will always be small. Also seeming that you
are using realloc anyway... wouldn't it be better to have the tmp
pointer as a static global and then you can have another function
which is called on shuting down, that will free your mem.

 ~J
--
/* James Antill **WWW**  http://cswww2.essex.ac.uk/users/loser/ */
#include <stdio.h>
main(int c, char **v){char *a="";if(c==2)while((c=getchar())!=EOF){if(!
*a)a=v[1];c^=*a++;putchar(c);}else printf(" %s <key>\n",v[0]);exit(0);}

In article <4jtteu$3lc@solutions.solon.com>,
Lawrence Kirby  <fred@genesis.demon.co.uk> wrote:
)In article <4jq1e4$a2g@solutions.solon.com>
)           David_McReynolds@vos.stratus.com "David McReynolds" writes:
)
)>Perhaps I'm confused but when I read the question this is what I came
)>up with.  It compiles and worked as expected in a test case.
)>
)>As far as the two pointers to be swapped are concerned, they are of
)>the same type correct?
)>
)>I do not see the problem with:
)>
)>void swap_ptr(void **p1, void **p2) {
)>  void *tmp = *p1;
)>
)>  *p1 = *p2;
)>  *p2 = tmp;
)>
)>  return;
)>}
)
)This swaps 2 void * pointers, it isn't guaranteed to swap any other type
)of pointer (except possibly char *). There is no guarantee that any other
)pointer has the same size or representation as void * (except char *).

This thread has some real silly stuff in it. Especially "is there a
machine still in use with different function/char/other pointers?"

The IBM PC when building using any 16 bit compiler using either Medium
or Compact Model has different size function and data pointers.

I think there are at least a FEW of those computers still out there.

Mike
-- 
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

I don't speak for DSC.         <- They make me say that.