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:
huffman.c: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);
queue.h: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.c: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);
Here is the error: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; } }
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:*** 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
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^^Code:queue* q = (queue*) malloc(sizeof(queue));