Thread: Problem with malloc(), maybe extern??

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    7

    Problem with malloc(), maybe extern??

    Hello friends,

    I am working on a school assignment, and I seem to be having trouble with malloc. The assignment is to find the correct huffman encoding for a file given as input. To do this I have 2 C files, one called huffman.c, and the other called queue.c. Queue.c is supposed to serve only as a queue. This is my first time ever calling functions between classes, so maybe I have an error there. I am posting all of my code, but the part to pay attention to is the main method of huffman.c, and the function create_queue in queue.c. I am narrowed down the runtime error to the malloc line of create_queue.

    Here is the code:
    huffman.h:
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include "queue.h"
    
    #define true 1
    #define false 0
    #define BUFFER_LENGTH 1024
    
    typedef struct word {
      char* data;
      char* encoded;
      int weight;
    } word;
    
    typedef struct node {
      int weight;
      char data;
      
      struct node* left;
      struct node* right;
    } node;
    
    // Make sure the arguments are right. Return true if args are good.
    int check_args(int argc, char** argv);
    
    // Function used to read input. Stores the array in the address pointed to
    // by addr. Returns the number of words read by the function.
    int read_input(word** addr);
    
    // Returns the number of instances of the character c in the array of words.
    int* get_weights(word* word_list, int size);
    
    int compare(void* i1, void* i2);
    huffman.c:
    Code:
    #include "huffman.h"
    
    int main(int argc, char** argv) {
      int i;
      int size = 0;
      int* weights = NULL;
      word* word_list = NULL;
      queue* q = NULL;
    
      // Check arguments.
      if (!check_args(argc, argv)) {
        printf("Incorrect arguments.\n");
        exit(1);
      }
    
      // Read input.
      size = read_input(&word_list);
    
      // Get letter weights.
      weights = get_weights(word_list, size);
    
      q = create_queue(&compare);
      // node* temp;
    
      /*for (i = 0; i < 26; ++i) {
        fprintf(stderr, "%d\n", i);
        temp = (node*) malloc(sizeof(node));
        temp->weight = weights[i];
        temp->data = i + 97;
        temp->left = NULL;
        temp->right = NULL;
        }*/
    
      // Clean everything up.
    
      return 0;
    }
    
    int check_args(int argc, char** argv) {
      int ret = true;
    
      if (argc != 4)
        ret = false;
      else if (argv[1][0] != '-' || (argv[1][1] != 'd' && argv[1][1] != 'g'))
        ret = false;
      else if (atoi(argv[2]) <= 0)
        ret = false;
    
      return ret;
    }
    
    int read_input(word** addr) {
      int size = 0;
      int counter = 0;
      int weight = 0;
      int times_expanded = 0;
      char c;
      char* data;
    
      // Initialize array.
      (*addr) = (word*) malloc(sizeof(word) * BUFFER_LENGTH);
      times_expanded = 1;
    
      // Setup space for the first line.
      data = (char*) malloc(sizeof(char) * BUFFER_LENGTH);
    
      // Get the first char.
      c = getchar();
    
      // Keep reading chars until the end of file is reached.
      while (c != EOF) {
        // At a newline, start a new word if we were already in a word.
        // Otherwise, ignore it.
        if (c == '\n' && counter != 0) {
          data[counter] = '\0';
          (*addr)[size].data = data;
          (*addr)[size].encoded = NULL;
          (*addr)[size].weight = weight;
          
          counter = 0;
          weight = 0;
          data = (char*) malloc(sizeof(char) * BUFFER_LENGTH);
          ++size;
          
          // Allocate more space if needed.
          if (size % BUFFER_LENGTH == 0) {
    	(*addr) = (word*) realloc(*addr, sizeof(word) * 2 * times_expanded * BUFFER_LENGTH);
    	++times_expanded;
          }
        } else if (c != '\n') {
          data[counter] = c;
          weight += c - 96;
          ++counter;
    
          // Allocate more space as needed.
          if (counter % BUFFER_LENGTH == 0)
    	data = (char*) realloc(data, sizeof(char) * (counter + BUFFER_LENGTH));
        }
    
        c = getchar();
      }
    
      // This is to check that the last word was correctly stored.
      if (counter != 0) {
        data[counter] = '\0';
        (*addr)[size].data = data;
        (*addr)[size].encoded = NULL;
        (*addr)[size].weight = weight;
        ++size;
      }
    
      return size;
    }
    
    int* get_weights(word* word_list, int size) {
      int i;
      int j;
      int* weights = (int*) malloc(sizeof(int) * 26);
    
      for (i = 0; i < size; ++i)
        weights[i] = 0;
      
      for (i = 0; i < size; ++i) {
        j = 0;
        
        while (word_list[i].data[j] != '\0') {
          ++(weights[word_list[i].data[j] - 97]);
    
          ++j;
        }
      }
    
      return weights;
    }
    
    int compare(void* i1, void* i2) {
      int ret = 0;
      node* t1 = (node*) i1;
      node* t2 = (node*) i2;
    
      if (t1->weight < t2->weight)
        ret = -1;
      else if (t1->weight == t2->weight)
        ret = 0;
      else
        ret = 1;
    
      return ret;
    }
    queue.h:
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    
    #define true 1
    #define false 0
    
    typedef struct queue {
      // A comparison function. This function should return:
      //  0 if i1 = i2
      //  1 if i1 > i2
      // -1 if i1 < i2
      int (*compare)(void* i1, void* i2);
    
      struct q_entry* head;
    } queue;
    
    typedef struct q_entry {
      struct q_entry* next;
      void* value;
    } q_entry;
    
    extern queue* create_queue(int (*comparator)(void* i1, void* i2));
    
    extern void* extract_min(queue* q);
     
    extern void insert(queue* q, void* item);
    queue.c:
    Code:
    #include "queue.h"
    
    extern queue* create_queue(int (*comparator)(void* i1, void* i2)) {
      fprintf(stderr, "here\n");
    
      queue* q = (queue*) malloc(sizeof(queue));
      // q->compare = comparator;
      // q->head = NULL;
      
      return q;
    }
    
    extern void* extract_min(queue* q) {
      void* ret = NULL;
      
      if (q != NULL && q->head != NULL) {
        ret = q->head->value;
        q_entry* temp = q->head;
        
        q->head = q->head->next;
        free(temp);
      }
        
      return ret;
    }
     
    extern void insert(queue* q, void* item) {
      q_entry* node = NULL;
      q_entry* prev = NULL;
      q_entry* cur = NULL;
      int inserted = false;
    
      if (q != NULL && item != NULL) {
        node = q->head;
        cur = (q_entry*) malloc(sizeof(q_entry));
        cur->next = NULL;
        cur->value = item;
     
        if (node == NULL)
          q->head = cur; 
    
        while (!inserted && node != NULL) {
          if (q->compare(item, node->value) == -1) {
    	if (prev != NULL)
    	  prev->next = cur;
    	
    	cur->next = node;
    	inserted = true;
          }
    
          prev = node;
          node = node->next;
        }
    
        if (!inserted)
          prev->next = cur;
      }
    }
    Here is the error:
    *** glibc detected *** ./huffman: malloc(): memory corruption: 0x091d5d10 ***
    ======= Backtrace: =========
    /lib/libc.so.6(+0x6c501)[0xb71501]
    /lib/libc.so.6(+0x6f2fc)[0xb742fc]
    /lib/libc.so.6(__libc_malloc+0x63)[0xb75f33]
    ./huffman[0x804895a]
    ./huffman[0x80485bf]
    /lib/libc.so.6(__libc_start_main+0xe7)[0xb1bce7]
    ./huffman[0x80484a1]
    ======= Memory map: ========
    00127000-00141000 r-xp 00000000 08:01 154399 /lib/libgcc_s.so.1
    00141000-00142000 r--p 00019000 08:01 154399 /lib/libgcc_s.so.1
    00142000-00143000 rw-p 0001a000 08:01 154399 /lib/libgcc_s.so.1
    00498000-00499000 r-xp 00000000 00:00 0 [vdso]
    00b05000-00c5c000 r-xp 00000000 08:01 137223 /lib/libc-2.12.1.so
    00c5c000-00c5d000 ---p 00157000 08:01 137223 /lib/libc-2.12.1.so
    00c5d000-00c5f000 r--p 00157000 08:01 137223 /lib/libc-2.12.1.so
    00c5f000-00c60000 rw-p 00159000 08:01 137223 /lib/libc-2.12.1.so
    00c60000-00c63000 rw-p 00000000 00:00 0
    00ec2000-00ede000 r-xp 00000000 08:01 131744 /lib/ld-2.12.1.so
    00ede000-00edf000 r--p 0001b000 08:01 131744 /lib/ld-2.12.1.so
    00edf000-00ee0000 rw-p 0001c000 08:01 131744 /lib/ld-2.12.1.so
    08048000-08049000 r-xp 00000000 08:01 688 /home/max/Documents/cs333/c_gale_maxwell_program5/huffman
    08049000-0804a000 r--p 00000000 08:01 688 /home/max/Documents/cs333/c_gale_maxwell_program5/huffman
    0804a000-0804b000 rw-p 00001000 08:01 688 /home/max/Documents/cs333/c_gale_maxwell_program5/huffman
    08da3000-0bd4c000 rw-p 00000000 00:00 0 [heap]
    b7500000-b7521000 rw-p 00000000 00:00 0
    b7521000-b7600000 ---p 00000000 00:00 0
    b768d000-b77a8000 rw-p 00000000 00:00 0
    b77db000-b77dc000 rw-p 00000000 00:00 0
    b77ea000-b77ed000 rw-p 00000000 00:00 0
    bfddc000-bfdfd000 rw-p 00000000 00:00 0 [stack]
    Aborted
    I have test all other code other than the code relating to the queue, so I know all of that works. If I comment out the line in the create_queue function of queue.c that says:
    Code:
    queue* q = (queue*) malloc(sizeof(queue));
    then I do not get any errors. I am fairly certain it is that line that is throwing the error. Any help would be awesome^^

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So just for fun I ran this in gdb. You may find it interesting:
    Code:
    (gdb) set args -d 8 3
    (gdb) run
    Starting program: /Users/andrewf/helping/huffman -d 8 3
    Reading symbols for shared libraries +. done
    Now is the time for all good men to come to the aid of the party.
    Now is still the time for all good men to come to the aid of the party.
    ^D
    Program received signal EXC_BAD_ACCESS, Could not access memory.
    Reason: KERN_INVALID_ADDRESS at address: 0x00000001000fff7c
    0x0000000100000af9 in get_weights (word_list=0x100800000, size=2) at huffman.c:127
    127		    ++(weights[word_list[i].data[j] - 97]);
    (gdb) print i
    $1 = 0
    (gdb) print j
    $2 = 3
    (gdb) print word_list[i]
    $3 = {
      data = 0x100806000 "Now is the time for all good men to come to the aid of the party.", 
      encoded = 0x0, 
      weight = -458
    }
    (gdb) print word_list[i].data[j]
    $4 = 32 ' '
    (gdb) quit
    The program is running.  Exit anyway? (y or n) y
    I have no idea what the args are for, but those seem to work. Spaces would seem to be a problem.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    7
    The arguments are for something latter in the problem. Input format is:

    ./huffman -{d, g} <int> <filename> < <input file>

    Note that the none of the arguments matter, as long as they are there and correctly formatted. Make sure <int> is greater than 0. The only important thing is to make sure to redirect stdin to the inputfile.
    And the input file has to contain only lower case letters and new lines. The error you got is from the capital letter, I think. The program uses the ascii value of each character to index into an array, so capital letters will cause it to be out of bounds.
    Last edited by Dimes; 12-07-2010 at 10:16 PM.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If you don't want capital letters, then that's fine. But look at what happened again:
    Code:
     print word_list[i].data[j]
    $4 = 32 ' '
    If you don't break your words up at spaces (or tabs, or commas, or ....) then can you really call them "words"?

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    7
    The words aren't broken up at spaces because there aren't supposed to be any in the input file. There is code (not given) that strips all non-alphabetical characters (except new lines) from the input file and converts all upper case letters to lower case.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Then there aren't any errors if you do that. Hooray!

  7. #7
    Registered User
    Join Date
    Nov 2010
    Posts
    7
    You ran the program correctly?

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Dimes View Post
    You ran the program correctly?
    Yes.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    7
    Can I see your Makefile?

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Makefile! Ha ha ha.
    Code:
    gcc -Wall -Wextra -g -o huffman huffman.c queue.c

  11. #11
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    In read_input()

    Code:
      char c;
      while (c != EOF) {

    Code:
    int* get_weights(word* word_list, int size) {
      int i;
      int j;
      int* weights = (int*) malloc(sizeof(int) * 26);
    
      for (i = 0; i < size; ++i)               //  size > 26 ?
        weights[i] = 0;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. malloc access problem
    By parad0x13 in forum C++ Programming
    Replies: 4
    Last Post: 01-30-2009, 01:00 PM
  2. Problem in malloc
    By lolguy in forum C Programming
    Replies: 20
    Last Post: 01-06-2009, 07:33 PM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. Malloc problem
    By freeindy in forum C Programming
    Replies: 6
    Last Post: 05-02-2007, 12:13 PM
  5. Problem with malloc() and sorting words from text file
    By goron350 in forum C Programming
    Replies: 11
    Last Post: 11-30-2004, 10:01 AM