Segmentation fault

[dmartin at ne.arris-i.com (Derek Martin)]

On Sun, 6 Feb 2000, Mark Donnelly wrote:

> Seg faults: the wonderful, wonderful sign of memory leaks.  aaahhhh..
> 
> You're probably doing one of two things: first, you might be allocating
> memory and forgetting to free it again when you are finished (less
> likely), or using some bit of memory before you allocate it (more likely).

On that note, I've got a peice of code that permutes a string into all its
permutations.  I've been baffled by the fact that it segfaults on the call
to free() a block I've allocated to hold a permutation, if the string is
larger than 12 characters. If any of you ace hackers has an explanation
for this, I'd love to hear it.  

I first thought I was smashing the stack, until I ran the program and saw
that it goes through thousands of permutations before it finally
segfaults, and the depth of the stack isn't any deeper at that point than
at earlier points.  Then I ran the code through the debugger, and saw that
it was segfaulting in the free( temp ) call.  This makes NO sense to me at
all.

BTW, this code works great if the strlen < 12...

Here's the code:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "permute.h"

int
permutation( char *string, char *done )
{

  int i, j, len;
  char *temp; 
  char *done_so_far;
  char charcurrent[2];

  len = strlen( string );
  charcurrent[1] = '\0';

  if ( len == 1 ){
    printf( "%s%s\n", done, string );
    return 0;
  }

  else {

    /* store the string without the current char in temp */    
    temp = (char *)malloc( len * sizeof(char));
    done_so_far = (char *)malloc( strlen( done ) + 2);
   
    for ( i = 0; i < len; i++ ) {
      strcpy( done_so_far, done );
      strcpy( temp, string );
      temp = rest_of_string( temp, i );
      charcurrent[0] = string[i];
      strcat( done_so_far, charcurrent );

      /* do the recursive call with the placeholder */
      permutation( temp, done_so_far );
    }

    /* forgetting to do this causes a HUGE memory leak */
    /* as the size of the string(s) grows              */
    free(temp);
    free(done_so_far);
    
    return 0;
  }
  
}


char *
rest_of_string( char *string, int usedchar )
{
  
  string[usedchar] = '\0';
  strcat( string, (string + usedchar + 1) );
  return string;
  
}


heeellp meeee... <as I fall down an endless well of frustration>

-- 
"Quis custodiet ipsos custodes?"    "Who watches the watchmen?" 
-Juvenal, Satires, VI, 347 

Derek D. Martin      |  Senior UNIX Systems/Network Administrator
Arris Interactive    |  A Nortel Company
derekm at mediaone.net  |  dmartin at ne.arris-i.com
-------------------------------------------------

-
Subcription/unsubscription/info requests: send e-mail with
"subscribe", "unsubscribe", or "info" on the first line of the
message body to discuss-request at blu.org (Subject line is ignored).