C array of pointers to structs realloc() error

Question

I'm trying to make a Huffman code to practice C coding and I keep geting the same error.

Let me explain the code. First it creates the struct below:

struct sNo {
    int valor;
    char letra;
    struct sNo *esq;
    struct sNo *dir;
};
typedef struct sNo sNo;

Then it creates an array of structs ('No'):

sNo *No;
No = calloc(qtd_no, sizeof(sNo));

It reads a string from the keyboard placing in this array the letter and the ammount of times it appears. Like the representation below with the word 'abracadabra':

No:    a/5 b/2 r/2 c/1 d/1  

Now, to make a Huffman tree, it's needed that I create another array ('pNo'), with pointers to the original array:

int qtd_pno = qtd_no;
sNo **pNo;
pNo = calloc(qtd_pno, sizeof(sNo*));
for (i = 0; i < qtd_pno; i++){
    pNo[i] = &No[i];    
}

The two arrays appear like that:

No:    a/5 b/2 r/2 c/1 d/1  
pNo:   a/5 b/2 r/2 c/1 d/1  

After that it can sort the array of pointers like below without changing the original one:

No:    a/5 b/2 r/2 c/1 d/1  
pNo:   c/1 d/1 r/2 b/2 a/5      

But when it tries to increase the size of the 'No' array...

qtd_no++;
No = realloc(No,(sizeof(sNo) * qtd_no));

... this is what happens with the arrays:

No:    a/5 b/2 r/2 c/1 d/1  /0
pNo:   c/1 d/1 r/2 b/2 /0

or something like that:

No:    a/5 b/2 r/2 c/1 d/1  /0
pNo:   c/1 d/1 r/2 b/2 �/1288268632 

Note that I'm not changing anything on the 'pNo' array, but somehow the value pointed is. I think it could be some specific characteristic of dynamic memory allocation, but I'm not sure.

EDIT
The complete code is below:

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


//Definicao do tipo struct No
struct sNo {
    int valor;
    char letra;
    struct sNo *esq;
    struct sNo *dir;
};
typedef struct sNo sNo;


//Funcoes
void SelectionSort(sNo *A[], int qtd_no);
void ImprimeArvore (sNo *a);


int main(){
    //Variaveis auxiliares
    int i, j;


    //Leitura de texto do teclado
    char texto[30];
    printf("Digite frase \n");
    setbuf(stdin, NULL);
    fgets(texto, 30, stdin);

    //Criacao dos nos
    int qtd_no = 0;
    sNo *No;

    for(i = 0; i < strlen(texto) && texto[i] != '\0'; i++){

        if(texto[i] >= 32){

            if(i == 0){

                qtd_no++;
                No = calloc(qtd_no, sizeof(sNo));
                if(No == NULL){
                    printf("Erro: memoria insuficiente\n");
                    exit(1);
                }

                No[i].letra = texto[i];
                No[i].valor = 1;
                No[i].esq = NULL;
                No[i].dir = NULL;
                printf("%d\t%c %c\t%d\n", i, texto[i], No[i].letra, No[i].valor);

            }else{

                for(j = 0; j <= qtd_no - 1; j++){

                    if(texto[i] == No[j].letra){
                        No[j].valor++;
                        printf("%d %d\t%c %c\t%d\n", i, j, texto[i], No[j].letra, No[j].valor);
                        break;

                    } 

                    else if(j == qtd_no - 1){

                        qtd_no++;
                        No = realloc(No,(sizeof(sNo) * qtd_no));
                        if(No == NULL){
                            printf("Erro: memoria insuficiente\n");
                            exit(1);
                        }

                        No[j+1].letra = texto[i];
                        No[j+1].valor = 1;
                        No[j+1].esq = NULL;
                        No[j+1].dir = NULL;
                        printf("%d %d\t%c %c\t%d\n", i, j, texto[i], No[j+1].letra, No[j+1].valor);
                        break;

                    }
                }
            }
        }
    }

    //Criacao de array com ponteiros para nos
    int qtd_pno = qtd_no;

    sNo **pNo;
    pNo = calloc(qtd_pno, sizeof(sNo*));
    if(pNo == NULL){
        printf("Erro: memoria insuficiente\n");
        exit(1);
    }

    for (i = 0; i < qtd_pno; i++){
        pNo[i] = &No[i];    
    }

    //Organizacao dos nos pelo valor
    SelectionSort(pNo, qtd_pno);

    //Criacao da arvore binaria
    while(qtd_pno > 1){

        qtd_no++;

        No = realloc(No,(sizeof(sNo) * qtd_no));
        if(No == NULL){
            printf("Erro: memoria insuficiente\n");
            exit(1);
        }

        No[qtd_no - 1].letra = '\0';
        No[qtd_no - 1].valor = (pNo[0]->valor) + (pNo[1]->valor);
        No[qtd_no - 1].esq = pNo[0];
        No[qtd_no - 1].dir = pNo[1];

        if(qtd_pno > 2){
            for(i = 0; i <= qtd_pno-2; i++){
                pNo[i] = pNo[i+2];
            }
        }

        qtd_pno--;
        pNo = realloc(pNo,(sizeof(sNo*) * qtd_pno));
        pNo[qtd_pno - 1] = &No[qtd_no - 1];

        if(qtd_pno > 1){
            SelectionSort(pNo, qtd_pno);
        }
    }

    sNo *raiz;
    raiz = pNo[0];
    free(pNo);

    printf("\n%s\n", texto);

    ImprimeArvore(raiz);
    printf("\n");

}

//Funcao de organizacao por valor
void SelectionSort(sNo *A[], int qtd_pno){

    sNo *temp;
    int i, j, Imin;

    for(i = 0; i < qtd_pno - 1; i++){
        Imin = i;
        for(j = i + 1; j < qtd_pno; j++){
            if((A[j]->valor) < (A[Imin]->valor)){
                Imin = j;
            }
        }

        temp = A[Imin];
        A[Imin] = A[i];
        A[i] = temp;
    }
}


void ImprimeArvore(sNo *a){

    if(a->letra) printf ("<%c/%d", (a->letra), (a->valor));
    else printf ("<_/%d", (a->valor));  

    if(a->esq != NULL) ImprimeArvore (a->esq);
    if(a->dir != NULL) ImprimeArvore (a->dir);

    printf (">");

}

Answer 1

The problem with your approach is that realloc does not make any guarantees about expanding your array in place.

to make a Huffman tree, it's needed that I create another array ('pNo'), with pointers to the original array

Since you have pointers to calloc-ed array inside other struct sNo objects, calling realloc on the block that has these structures may invalidate all external pointers to these structures. That is why your code runs into undefined behavior after a call to realloc.

One approach to fixing this problem is to store indexes instead of pointers. This works, as long as you keep a single dynamic array to which you add new items, but never remove items from it.