Mastering Algorithms With C - Kyle Loudon [165]
}
if (pqueue_extract(&pqueue, (void **)&right) != 0) {
pqueue_destroy(&pqueue);
free(merge);
return -1;
}
/**************************************************************************
* *
* Allocate storage for the data in the root node of the merged tree. *
* *
**************************************************************************/
if ((data = (HuffNode *)malloc(sizeof(HuffNode))) == NULL) {
pqueue_destroy(&pqueue);
free(merge);
return -1;
}
memset(data, 0, sizeof(HuffNode));
/**************************************************************************
* *
* Sum the frequencies in the root nodes of the trees being merged. *
* *
**************************************************************************/
data->freq = ((HuffNode *)bitree_data(bitree_root(left)))->freq +
((HuffNode *)bitree_data(bitree_root(right)))->freq;
/**************************************************************************
* *
* Merge the two trees. *
* *
**************************************************************************/
if (bitree_merge(merge, left, right, data) != 0) {
pqueue_destroy(&pqueue);
free(merge);
return -1;
}
/**************************************************************************
* *
* Insert the merged tree into the priority queue and free the others. *
* *
**************************************************************************/
if (pqueue_insert(&pqueue, merge) != 0) {
pqueue_destroy(&pqueue);
bitree_destroy(merge);
free(merge);
return -1;
}
free(left);
free(right);
}
/*****************************************************************************
* *
* The last tree in the priority queue is the Huffman tree. *
* *
*****************************************************************************/
if (pqueue_extract(&pqueue, (void **)tree) != 0) {
pqueue_destroy(&pqueue);
return -1;
}
else {
pqueue_destroy(&pqueue);
}
return 0;
}
/*****************************************************************************
* *
* ------------------------------ build_table ----------------------------- *
* *
*****************************************************************************/
static void build_table(BiTreeNode *node, unsigned short code, unsigned char
size, HuffCode *table) {
if (!bitree_is_eob(node)) {
if (!bitree_is_eob(bitree_left(node))) {
/***********************************************************************
* *
* Move to the left and append 0 to the current code. *
* *
***********************************************************************/
build_table(bitree_left(node), code << 1, size + 1, table);
}
if (!bitree_is_eob(bitree_right(node))) {
/***********************************************************************
* *
* Move to the right and append 1 to the current code. *
* *
***********************************************************************/
build_table(bitree_right(node), (code << 1) | 0x0001, size + 1, table);
}
if (bitree_is_eob(bitree_left(node))&&bitree_is_eob(bitree_right(node))) {
/***********************************************************************
* *
* Ensure that the current code is in big-endian format. *
* *
***********************************************************************/
code = htons(code);
/***********************************************************************
* *
* Assign the current code to the symbol in the leaf node. *
* *
***********************************************************************/
table[((HuffNode *)bitree_data(node))->symbol].used = 1;
table[((HuffNode *)bitree_data(node))->symbol].code = code;
table[((HuffNode *)bitree_data(node))->symbol].size = size;
}
}
return;
}
/*****************************************************************************
* *
* --------------------------- huffman_compress --------------------------- *
* *
*****************************************************************************/
int huffman_compress(const unsigned char *original, unsigned