Rookie pointer problem: 2 dimensions, malloc

I will always be a pointer rookie, but any "real" C person will find this question to be kid stuff. As you can see underneath this very simple code, the input file is dropping a line (or character), though the code as written should exactly reproduce the input. Can anyone see the flaw in my code?

This is simple ANSI C. small model. I'm even using TC2.01 (may it never die). FWIW this is a massively stripped shell of a customizable sort. The game plan will be to take numerous argv column numbers and do a compound sort (vs. SORT.EXE only handling a single start column).

Code:

---

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

void main(void)
{
FILE                *fp;
char                **TwoDimenSortable, **prow, buff[10];
unsigned        u, ulines, umaxlen;


        if((fp=fopen("test.dat","r"))==NULL) {puts("fopen poop");exit(55);}
        /* count input file lines and max width too */
        for (ulines=0, umaxlen = 0; fgets(buff, sizeof buff,fp); ++ulines) {
                umaxlen=max(umaxlen, strlen(buff)); /* get max width while we're at it */
        }
        rewind(fp);
        /* malloc the mass 2 dimensional array */
        if (NULL==(TwoDimenSortable=(char **)malloc (ulines * umaxlen * sizeof (char)))) {
                printf("Jeez, couldn't malloc %u lines for %u cols.\n",ulines,umaxlen);
                exit(70);
        }
        /* malloc pointers to each line */
        if (NULL==(prow=malloc(ulines * sizeof(char *)))) {
                puts("malloc failure - cheez! (tiny one)\n");
                exit(44);
        }
        for (u=0; u<ulines; ++u) {
                prow[u] = (char *) TwoDimenSortable + (u * umaxlen);        /* qsortable pointer array */
                fgets(buff, sizeof buff, fp);
                if(buff[strlen(buff)-1]=='\n')buff[strlen(buff)-1]='\0'; /* stripEOL */
                strcpy((char *)TwoDimenSortable+u*umaxlen, buff);
        }
        fclose(fp);
        /* qsort(prow, ulines, umaxlen, strncmp); */
        for (u=0; u<ulines; ++u) {
                prow[umaxlen-1]='\0';
                puts(prow[u]);
        }
}
/*
The input file test.dat is 5 simple lines, each one byte and CRLF:
1
2
3
4
*/
/*
The output is bizarrely
1

3
4
*/

---

Seems to be this line

Code:

---

if (NULL==(TwoDimenSortable=(char **)malloc (ulines * umaxlen * sizeof (char)))) {

---

There is no space for the terminating '\0'.

Changing that line to ++umaxlen still retains the problem. But I did forget about fgets getting the terminator, so thanks - things are definitely bad news unless I fix that. (I must have been thinking fread :rolleyes: )

Doh, I'm using strcpy, not strncpy! DOH! DUH!!

Nonetheless the problem persists.

I'm being lazy, but it was easier to just rewrite your program than to try and debug the existing code. Forgive me. :o

Code:

---

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

int cmp ( const void *a, const void *b )
{
  return strcmp ( (const char *)a, (const char *)b );
}

int main ( void )
{
  FILE *fp = fopen ( "test.txt", "r" );
  char **lines, buf[BUFSIZ];
  int i, nlines = 0, ncols = 0;

  if ( fp == NULL ) {
    perror ( "fopen fail" );
    exit ( 55 );
  }

  while ( fgets ( buf, sizeof buf, fp ) != NULL ) {
    int len = strlen ( buf );

    ++nlines;
    if ( len > ncols )
      ncols = len;
  }

  rewind ( fp );

  lines = malloc ( nlines * sizeof *lines );
  if ( lines == NULL ) {
    perror ( "malloc fail" );
    exit ( 70 );
  }

  i = 0;

  while ( fgets ( buf, sizeof buf, fp ) != NULL ) {
    int len = strlen ( buf );

    lines[i] = malloc ( len + 1 );
    if ( lines[i] == NULL ) {
      while ( --i >= 0 )
        free ( lines[i] );
      free ( lines );

      perror ( "malloc fail" );
      exit ( 44 );
    }

    if ( buf[len - 1] == '\n' )
      buf[len - 1] = '\0';

    strcpy ( lines[i++], buf );
  }

  qsort ( lines, nlines, sizeof *lines, cmp );

  for ( i = 0; i < nlines; i++ ) {
    puts ( lines[i] );
    free ( lines[i] );
  }

  free ( lines );

  return 0;
}

---

Cheers!

Thanks Slacker, I'll look at your code. But mine should be really durn easy to catch with Turbo Debugger or something that shows the .ASM, or even (cough) Codeview - but I don't currently have access. So I'm still eager to hear the answer to this mystery. Moreover, did anyone NOT reproduce the error I showed?

As to your slant, you use multiple mallocs vs. the single contiguous one I used for data. (Then I set a pointer to every "implied" row within the contiguous area.) Is this approach doomed for feeding to qsort? I have nothing against your method, but I'd like to know if mine was kosher.

I noted some typos in the OP - "5 lines" at bottom s/b 4; strncmp s/b stricmp; and the first malloc umaxlen s/b ++umaxlen, as Zuk identified.

BTW I feel like I'm at the best place to ask - I walked to the kitchen after the first post and came back and saw 11 views. You get some serious traffic here. (And sysops, it's mondo fast - wtg)

with a few small modifications it runs fine

Code:

---

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

long max( long a, long b ) {
  return a > b ? a :b;
}

int cmp ( const void *a, const void *b )
{
  return strcmp ( (const char *)a, (const char *)b );
}

int main(void) {
        FILE                *fp;
        char                **TwoDimenSortable, **prow, buff[10];
        unsigned        u, ulines, umaxlen;

        if((fp=fopen("test.dat","r"))==NULL) {puts("fopen poop");exit(55);}
        /* count input file lines and max width too */
        for (ulines=0, umaxlen = 0; fgets(buff, sizeof buff,fp); ++ulines) {
            umaxlen=max(umaxlen, strlen(buff)); /* get max width while we're at it */
        }
        rewind(fp);
        umaxlen++;
        /* malloc the mass 2 dimensional array */
        if (NULL==(TwoDimenSortable=(char **)malloc (ulines * umaxlen * sizeof (char)))) {
                printf("Jeez, couldn't malloc %u lines for %u cols.\n",ulines,umaxlen);
                exit(70);
        }
        /* malloc pointers to each line */
        if (NULL==(prow=malloc(ulines * sizeof(char *)))) {
                puts("malloc failure - cheez! (tiny one)\n");
                exit(44);
        }
        for (u=0; u<ulines; ++u) {
                prow[u] = (char *) TwoDimenSortable + (u * umaxlen);        /* qsortable pointer array */
                fgets(buff, sizeof buff, fp);
                if(buff[strlen(buff)-1]=='\n')buff[strlen(buff)-1]='\0'; /* stripEOL */
                strcpy((char *)TwoDimenSortable+u*umaxlen, buff);
        }
        fclose(fp);
                qsort(*prow, ulines, umaxlen, cmp);
        for (u=0; u<ulines; ++u) {
                //prow[umaxlen-1]='\0';
                puts(prow[u]);
        }
}

---

>Is this approach doomed for feeding to qsort?
Not if you do it right. That approach uses one big array of the data, then another array of pointers into that array. You sort the pointers, so it's really irrelevant how the data is stored.

>So I'm still eager to hear the answer to this mystery.
It's simple, but obscure. TwoDimenSortable needs to be a pointer to char, not a pointer to pointer to char. The reason is that with your approach it's a data block, not an array of strings:

Code:

---

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

void main(void)
{
  FILE                *fp;
  char                *TwoDimenSortable, **prow, buff[10];
  unsigned        u, ulines, umaxlen;


  if((fp=fopen("test.dat","r"))==NULL) {puts("fopen poop");exit(55);}
  /* count input file lines and max width too */
  for (ulines=0, umaxlen = 0; fgets(buff, sizeof buff,fp); ++ulines) {
    umaxlen=max(umaxlen, strlen(buff)); /* get max width while we're at it */
  }
  rewind(fp);
  /* malloc the mass 2 dimensional array */
  if (NULL==(TwoDimenSortable=(char *)malloc (ulines * umaxlen * sizeof (char)))) {
    printf("Jeez, couldn't malloc %u lines for %u cols.\n",ulines,umaxlen);
    exit(70);
  }
  /* malloc pointers to each line */
  if (NULL==(prow=malloc(ulines * sizeof(char *)))) {
    puts("malloc failure - cheez! (tiny one)\n");
    exit(44);
  }
  for (u=0; u<ulines; ++u) {
    prow[u] = (char *) TwoDimenSortable + (u * umaxlen);        /* qsortable pointer array */
    fgets(buff, sizeof buff, fp);
    if(buff[strlen(buff)-1]=='\n')buff[strlen(buff)-1]='\0'; /* stripEOL */
    strcpy((char *)TwoDimenSortable+u*umaxlen, buff);
  }
  fclose(fp);
  /* qsort(prow, ulines, umaxlen, strncmp); */
  for (u=0; u<ulines; ++u) {
    prow[umaxlen-1]='\0';
    puts(prow[u]);
  }
}

---

All of the casting you do just confuses the issue, and the code is so tight that I'm not surprised it was a hard bug for you. ;) Just so you know, there are a bunch of ways you can improve your code and make it both correct and rock solid, but explaining them all would make for a long post. :(

Cheers!

The wrong declaration of TwoDimenSortable isn't the real problem because it was cast to the right type when used.
The real mistake was here. this is right

Code:

---

        qsort(*prow, ulines, umaxlen, cmp);
        for (u=0; u<ulines; ++u) {
                //prow[umaxlen-1]='\0';
                puts(prow[u]);
        }

---

All great observations. Way to go, all. You guys put some real time and thought and really walked the code. I'm grateful.

Zuk, you're absolutely right as to the //prow[umaxlen-1]='\0';
culprit. I kept looking in puzzlement, and since nobody mentioned it maybe no one sensed what the real story was:
prow[u][umaxlen-1]='\0';
DOOOOH! (And yaaaah, I know it's redundant - in fact, with the EOL strip, sort of "doubly redundant". Pretty lamo :mad: )

But true nastiness was thwarted by your astute catch with ++umaxlen. It's easy to see that [otherwise] umaxlen is 2 (strlen of '4','\n'). If I'm going to fgets to buff, I need room for 3 for "4\n" which buff has. But upon strcpy I really REALLY need 3 in the dest (the 2 dimensional).

Thanks, slacker - good comments. You're right that superfluous casts cloud the picture. Sometimes I keep them (superfluous ones) in, in order to keep the "pointering" straight as I visually follow the code flow.

As to char ** vs. * : it sounds like to me you're both right. char * seems to "smell better" as aesthetically truer, but I can see a case for ** too.

Quote:

---

Slacker: "there are a bunch of ways you can improve your code and make it both correct and rock solid, but explaining them all would make for a long post."

---

In consideration of the audience I stripped the original code to the bone and then some. Notably, numerous error checking and commenting were massacred. However I'm betting that you have some other good s**^H^H^H STUFF that is unrelated to the "massacre." I'm game.

Hey, where are forum posting tags shown? All I see is "html is off" on this page, and no link from it; nothing in options or thereabouts; but I do seem to have /code /quote, font, font size, font color.

:cool:

Quote:

---

Originally Posted by ZuK

Code:

---

int cmp ( const void *a, const void *b )
{
  return strcmp ( (const char *)a, (const char *)b );
}
[...]
  qsort(*prow, ulines, umaxlen, cmp);

---

---

Zuk, thanks again for not only the solution, but other useful, helpful direction and improvements.

I'm curious about doing the above, vs. just putting strcmp as a qsort arg. I've seen this a lot, and always wondered if it added a layer to the code. Perhaps you'd have to view the assembler (for whatever specific compiler) to remark definitively, but are there any hard rules or truisms about this technique with regard to performance?

And by the way - I'm not picking on you or suggesting that you write anything less than blisteringly fast code. I'm just an obsessive tweaker and saw this one opportunity, in isolation. :p

Talking about performance it's shurely a bit faster to pass strcmp directly to qsort. But I don't like the compiler complain about incompatible pointer types.
To pass strcmp to qsort works with strings and ascending sortorder only so I usuallay have to have some other sortfunctions anyways. I just got used to do it this way.
BTW the function cmp() was stolen from Slacker's post.
Kurt

Oh yeah, forgot about the compiler warning. That sometimes trumps speed :p