Malloc could not allocate memory

Question

I am getting this strange problem with my code. Malloc is returning a null pointer here.. I have 3 GB memmory on my ram and it could not allocate a few bytes. Why is it happening?? Someone please help..

Here is my code

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

struct htree{
   unsigned char ch;
   unsigned long int freq;
   struct htree *left, *right, *parent;
   };

struct code_list{
   unsigned char ch;
   char *code;
   };



typedef struct htree node;
typedef struct code_list * dict;

dict codes;

int readfile(char *filename, long int *char_count)
{
 int types = 0;
 FILE *fp = fopen(filename,"rb");
 unsigned char byteread;
 fread(&byteread,1,1,fp);
 int count=0;
 while(!feof(fp))
 {

                 if (char_count[byteread] == 0)
                 {
                 types++;
                 }
                 char_count[byteread]++;
                 fread(&byteread,1,1,fp);

 }
 fclose(fp);
 return types-1;
}
node * genhuffnode()
{
 node *t = (node *)malloc(sizeof(struct htree));
 t -> ch = '\0';
 t -> freq = 0;
 t -> left = NULL;
 t -> right = NULL;
 t -> parent = NULL;
 return t;
}

node * genhufftree(long int *char_count, int max_index)
{
 node **stack;
 node *temp;
 stack = (node **) calloc(max_index,sizeof(node *));
 int i,j=0;
 for(i=0;i<256;i++)
 {
                   if(char_count[i]>0)
                   {
                   stack[j] = (node *)malloc(sizeof(node));
                   stack[j] -> ch = i;
                   stack[j] -> freq = char_count[i];
                   stack[j] -> left = NULL;
                   stack[j] -> right = NULL;
                   stack[j] -> parent = NULL;
                   j++;
                   }
 }

 for(i=0;i<=max_index;i++)
 for(j=i+1;j<=max_index;j++)
 if(stack[j] -> freq > stack[i] -> freq)
 {
                 temp = stack[j];
                 stack[j] = stack[i];
                 stack[i] = temp;
 }
 while(i>0)
 {
           temp = genhuffnode();
           temp -> freq = stack[i] -> freq + stack[i-1] -> freq;
           temp -> left = stack[i-1];
           temp -> right = stack[i];
           stack[i-1] -> parent = temp;
           stack[i] -> parent = temp;

           for(j=i-2;j>0;j--)
           {
                              if(temp->freq > stack[j-1]->freq)
                              stack[j+1] = stack[j];
                              else break;
           }
           stack[j] = temp;
           i--;
 }
 return stack[0];
}

void generatedict(node *root, char *s)
{
 if(root == NULL)
 return;
 char *new_code;

 static int index = 0;

 int len = strlen(s)+1;

 if(root->left == NULL && root->right == NULL)
 {

               codes[index].ch = root->ch;
               codes[index].code = (char *) malloc(len*sizeof(char));
               strcpy(codes[index].code,s);
               index++;
 }
 else
 {

               new_code = (char *)(malloc(len+1));/// this malloc is causing prob
               if(new_code == NULL)
               {
               printf("Coudnt allocate memory\n");
               getchar();
               exit(1);
               }
               else 
               {
               strcpy(new_code,s);
               new_code[len] = '\0';
               new_code[len-1] = '0';
               generatedict(root->left,new_code);
               new_code[len-1] = '1';
               generatedict(root->right,new_code);
               }
 }

 free(root);
 return;
}

void writedict(int total_entries)
{
 FILE *fp = fopen("dictionary","wb");
 fwrite(codes,sizeof(struct code_list) * total_entries, sizeof(struct code_list) *         total_entries, fp);
 fclose(fp);
}                  

main()
{

  long int char_count[256];
  int max_index;
  max_index = readfile("2.jpg",char_count);
  node *root_node;
  root_node = genhufftree(char_count, max_index);
  codes = (struct code_list *)calloc(256,sizeof(struct code_list));         
  generatedict(root_node,"");
  writedict(max_index+1);

  getchar();
}

Note : please keep any file named "2.jpg" in the same folder as the  executable

Answer 1

My guess is that your program corrupts malloc pool in one of those earlier places where you call malloc (there are many malloc calls!). You are not checking the return value for most of the malloc calls.

I would suggest to check return value of malloc at all places to see which one fails first. Also, check for memory leaks in your code using valgrind (Linux) or purify (windows).

Answer 2

If you don't think your program is exhausting memory, then most likely malloc() just thinks you've exhausted memory. This could happen if you free unallocated pointers, free the same pointer more than once, overwrite a buffer, etc. Debug your program carefully, looking for these problems, and/or use valgrind to find them automatically.