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:

Quote:

---

*** 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^^

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.

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.

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"?

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.

Then there aren't any errors if you do that. Hooray!

You ran the program correctly?

Quote:

---

Originally Posted by Dimes

You ran the program correctly?

---

Yes.

Can I see your Makefile?

Makefile! Ha ha ha.

Code:

---

gcc -Wall -Wextra -g -o huffman huffman.c queue.c

---

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;

---