I am trying to write a program that is going to use the Huffman algorithm to create a dictionary to compress a text file. I am having some problems regarding realloc. My program works just fine, but valgrind reports a lot of errors regarding realloc. I tried writing my own and using the function but nothing works. Any ideas?
If you want to check the output you have to do it like "-o 1 -f read.txt -v"
read.txt could be a any text file that has words that are in ASCII table
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getopt.h>
const int expand_size = 4;
int length = 4;
typedef struct {
char w[2]; //word
int v; //value
int d; //direction
char b; //binary
} node_t;
int maxi(node_t * huff, int n) {
int maxi = huff[0].v;
for (int i = 0; i < n; i++)
if (huff[i].v > maxi) {
maxi = huff[i].v;
}
return maxi;
}
int mini(node_t * huff, int n) {
int mini = maxi(huff, n);
int w = 0;
for (int i = 0; i < n; i++)
if (huff[i].v <= mini && huff[i].v >= 0) {
w = i;
mini = huff[i].v;
}
return w;
}
node_t * realoc(node_t * huff) {
node_t * temp = realloc(huff, (length + expand_size) * sizeof(node_t));
return temp;
}
int huffman(node_t * huff, int n) {
int j = 1;
int i = 1;
int index1;
int index2;
int value1;
int value2;
while (i != n) {
index1 = mini(huff, n);
value1 = huff[index1].v;
huff[index1].v = -1;
index2 = mini(huff, n);
value2 = huff[index2].v;
huff[index2].v = -1;
huff[index1].d = n;
huff[index2].d = n;
huff[index1].b = '1';
huff[index2].b = '0';
if (n == length) {
node_t * temp;
temp = realoc(huff);
huff = temp;
for (int h = length; h < length + expand_size; h++) {
huff[h].v = 0;
}
length += expand_size;
}
huff[n].v = value1 + value2;
huff[n].w[0] = j + '0';
j++;
i = i + 2;
n++;
}
return n;
}
int main(int argc, char ** argv) {
int n;
///reading from a file///
FILE * read;
char word[2];
char c;
///getopt parimeters///
int opt;
char * file = NULL;
char steps = 0;
char compression_level = 0;
///getopt///
while ((opt = getopt(argc, argv, "o:f:v")) != -1) {
switch (opt) {
case 'f':
file = optarg;
break;
case 'v':
steps = 1;
break;
case 'o':
compression_level = atof(optarg);
break;
case '?':
printf("Złe parametry wywołania");
return 1;
break;
}
}
read = fopen(file, "r");
node_t * huff = malloc(sizeof(node_t) * (length));
int counter = 0; ///how many nodes are in the table (nodes from the file not the ones that we create with huffman algorithm)
for (int i = 0; i < length; i++)
huff[i].v = 0;
if (read == NULL) {
printf("file can't be opened \n");
return 1;
}
if (compression_level == 1) {
while ((c = fgetc(read)) != EOF) {
for (int i = 0; i < length; i++) {
if (huff[i].v == 0) {
huff[i].w[0] = c;
huff[i].v++;
counter++;
break;
}
if (huff[i].w[0] == c) {
huff[i].v++;
break;
}
if (i == length - 1) {
node_t * temp;
temp = realoc(huff);
huff = temp;
for (int j = length; j < length + expand_size; j++) {
huff[j].v = 0;
//huff[j].w[0] = ' ';
}
length += expand_size;
}
}
}
}
n = huffman(huff, counter);
///printing the table///
int l;
for (int i = 0; i < counter; i++) {
l = i;
if (compression_level == 1)
printf("%c: ", huff[i].w[0]);
if (compression_level == 2)
printf("%c%c: ", huff[i].w[0], huff[i].w[1]);
while (l != n - 1) {
printf("%c", huff[l].b);
l = huff[l].d;
}
printf("\n");
}
if (steps == 1) {
for (int i = 0; i < counter; i++) {
if (huff[i].w[0] == 10)
printf("'%d' 'LINE FEED' occured %d razy\n", huff[i].w[0], huff[i].v);
//else printf("'%d' '%s' wystapilo %d razy\n", huff[i].w, huff[i].w, huff[i].v);
}
printf("array length %d\n", length);
printf("how many nodes %d\n", n);
printf("how many primary nodes %d\n", counter);
//printf("v = %d, o = %d\n", steps, compression_level);
}
free(huff);
fclose(read);
return 0;
}
In your function int huffman(node_t *huff, int n) you try to realloc() the huff pointer but in C we pass variables by value so you only receive a copy of the pointer. This means caller retains the original pointer and the realloc() memory is lost when you return from the function. You need to pass in a **huff:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getopt.h>
const int expand_size = 4;
int length = 4;
typedef struct {
char w[2]; //word
int v; //value
int d; //direction
char b; //binary
} node_t;
int maxi(node_t *huff, int n) {
int maxi = huff[0].v;
for(int i=0;i<n;i++)
if(huff[i].v>maxi)
maxi=huff[i].v;
return maxi;
}
int mini(node_t *huff, int n) {
int mini = maxi(huff, n);
int w=0;
for(int i=0;i<n;i++)
if(huff[i].v<=mini && huff[i].v >=0){
w=i;
mini=huff[i].v;
}
return w;
}
int huffman(node_t **huff, int n){
int j=1;
int i=1;
while (i!=n){
int index1=mini(*huff, n);
int value1=(*huff)[index1].v;
(*huff)[index1].v=-1;
int index2=mini(*huff, n);
int value2=(*huff)[index2].v;
(*huff)[index2].v=-1;
(*huff)[index1].d = n;
(*huff)[index2].d = n;
(*huff)[index1].b = '1';
(*huff)[index2].b = '0';
if ( n == length ){
node_t *temp = realloc(*huff, (length + expand_size) * sizeof *temp);
if(!temp) {
printf("realloc failed\n");
exit(1);
}
*huff=temp;
for ( int h = length; h < length + expand_size; h++){
(*huff)[h].v = 0;
}
length += expand_size;
}
(*huff)[n].v=value1 + value2;
(*huff)[n].w[0]=j+'0';
j++;
i=i+2;
n++;
}
return n;
}
int main( int argc, char** argv) {
int opt;
char *file = NULL;
char steps = 0;
char compression_level = 0;
while ((opt = getopt (argc, argv, "o:f:v")) != -1) {
switch (opt) {
case 'f':
file = optarg;
break;
case 'v':
steps = 1;
break;
case 'o':
compression_level = atof ( optarg );
break;
case '?':
printf("Złe parametry wywołania");
return 1;
break;
}
}
if(!file) {
printf("file is required\n");
return EXIT_FAILURE;
}
FILE *read = fopen(file, "r");
node_t *huff = malloc(length * sizeof *huff);
int counter = 0;
for (int i=0; i<length; i++)
huff[i].v = 0;
if (read == NULL) {
printf ("file can't be opened \n");
return 1;
}
if(compression_level == 1){
int c;
while ((c = fgetc(read)) != EOF ){
for (int i=0; i<length; i++){
if (!huff[i].v){
huff[i].w[0] = c;
huff[i].v++;
counter++;
break;
}
if (huff[i].w[0]== c){
huff[i].v++;
break;
}
if (i == length - 1){
node_t *temp = realloc(huff, (length + expand_size) * sizeof *temp);
if(!temp) {
printf("relloc failed\n");
exit(EXIT_FAILURE);
}
huff=temp;
for (int j = length; j < length + expand_size; j++)
huff[j].v = 0;
length += expand_size;
}
}
}
}
int n = huffman(&huff, counter);
for(int i=0; i<counter; i++){
int l=i;
if(compression_level == 1)
printf("%c: ", huff[i].w[0]);
if(compression_level == 2)
printf("%c%c: ", huff[i].w[0], huff[i].w[1]);
while (l!=n-1){
printf("%c", huff[l].b);
l = huff[l].d;
}
printf("\n");
}
if (steps == 1) {
for (int i=0; i<counter; i++){
if( huff[i].w[0] == 10)
printf("'%d' 'LINE FEED' occured %d razy\n", huff[i].w[0], huff[i].v);
}
printf("array length %d\n", length);
printf("how many nodes %d\n", n);
printf("how many primary nodes %d\n", counter);
}
free(huff);
fclose(read);
return 0;
}
I also reduced scope of variables, checked return value of realloc(), checked that file is set. Here is the valgrind summary after the change:
==2612036== HEAP SUMMARY:
==2612036== in use at exit: 0 bytes in 0 blocks
==2612036== total heap usage: 41 allocs, 41 frees, 53,016 bytes allocated
==2612036==
==2612036== All heap blocks were freed -- no leaks are possible