2
\$\begingroup\$

I trying to implement Huffman Codes on C. And, since my previous attempt failed, I decided to approach the issue more responsibly. So I'm asking for feedback on my implementation of the priority queue on C. First of all, the design of structures and interfaces is important to me! Also, how easy would it be to implement a Huffman tree using this structure? And of course, what about decomposition?

priority_queue.h

#ifndef PRIORITY_QUEUE
#define PRIORITY_QUEUE
#include <stdlib.h>
struct pq_node {
    unsigned long frequency;
    struct pq_node *parent;  //Pointers for Huffman tree
    struct pq_node *left;
    struct pq_node *right;
    char symbol;
};

struct priority_queue {
    struct pq_node *heap_on_array;
    size_t size;
    size_t capacity;
};

void init_queue(struct priority_queue **pq, size_t capacity);

void shift_up(struct priority_queue **pq, int i);  // i - index

void shift_down(struct priority_queue **pq, size_t i);  // i - index

struct pq_node extract_min(struct priority_queue **pq);

void insert(struct priority_queue **pq, char symbol);

void insert_element(struct priority_queue **pq, char symbol, unsigned long frequency);

void node_swap(struct pq_node *first, struct pq_node *second);

priority_queue.c

#include "priority_queue.h"
void init_queue(struct priority_queue **pq, size_t capacity)
{
    (*pq) = malloc(sizeof(struct priority_queue));
    (*pq)->heap_on_array = malloc(sizeof(struct pq_node) * capacity);
    (*pq)->capacity = capacity;
    (*pq)->size = 0;
};

void shift_up(struct priority_queue **pq, int i)
{
    while ((*pq)->heap_on_array[i].frequency < (*pq)->heap_on_array[(i-1)/2].frequency)
    {
        node_swap(&((*pq)->heap_on_array[i]), &((*pq)->heap_on_array[(i-1)/2]));
        i = (i - 1) / 2;
    }
}

void shift_down(struct priority_queue **pq, size_t i)
{
    while ((2 * i + 1) < (*pq)->size)
    {
        size_t left = 2 * i + 1;
        size_t right = 2 * i + 2;
        size_t j = left;
        if((right < (*pq)->size) && ((*pq)->heap_on_array[right].frequency < (*pq)->heap_on_array[left].frequency))
        {
            j = right;
        }
        if((*pq)->heap_on_array[i].frequency <= (*pq)->heap_on_array[j].frequency)
        {
            break;
        }
        node_swap(&((*pq)->heap_on_array[i]), &((*pq)->heap_on_array[j]));
        i = j;
    }
}

struct pq_node extract_min(struct priority_queue **pq)
{
    struct pq_node tmp = (*pq)->heap_on_array[0];
    (*pq)->heap_on_array[0] = (*pq)->heap_on_array[(*pq)->size - 1];
    (*pq)->size--;
    shift_down(pq, 0);
    return tmp;
}

void insert(struct priority_queue **pq, char symbol)
{
    for(size_t i = 0; i < (*pq)->size; ++i)
    {
        if((*pq)->heap_on_array[i].symbol == symbol)
        {
            (*pq)->heap_on_array[i].frequency++;
            shift_down(pq, i);
            return;
        }
    }
    
    if((*pq)->size == (*pq)->capacity)
    {
        (*pq)->heap_on_array = reallocarray((*pq)->heap_on_array, (*pq)->size * 2, sizeof(struct pq_node));
        (*pq)->capacity = (*pq)->capacity * 2;
    }
    (*pq)->size++;
    (*pq)->heap_on_array[(*pq)->size - 1].symbol = symbol;
    (*pq)->heap_on_array[(*pq)->size - 1].frequency = 1;
    shift_up(pq, (*pq)->size - 1);
}

void insert_element(struct priority_queue **pq, char symbol, unsigned long frequency)
{
    for(size_t i = 0; i < (*pq)->size; ++i)
    {
        if((*pq)->heap_on_array[i].symbol == symbol)
        {
            (*pq)->heap_on_array[i].frequency = frequency;
            shift_down(pq, i);
            return;
        }
    }

    if((*pq)->size == (*pq)->capacity)
    {
        (*pq)->heap_on_array = reallocarray((*pq)->heap_on_array, (*pq)->size * 2, sizeof(struct pq_node));
        (*pq)->capacity = (*pq)->capacity * 2;
    }
    (*pq)->size++;
    (*pq)->heap_on_array[(*pq)->size - 1].symbol = symbol;
    (*pq)->heap_on_array[(*pq)->size - 1].frequency = frequency;
    shift_up(pq, (*pq)->size - 1);
}

void node_swap(struct pq_node *first, struct pq_node *second)
{
    struct pq_node tmp = *first;
    *first = *second;
    *second = tmp;
}
```
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$
  • Avoid double pointers. They are absolutely unwarranted in all the functions (except init, but see below).

  • Prefer returning a value to a side effect. In the client code, which I presume is along the lines of

      struct priority_queue * pq;
      init_queue(&pq, capacity);
    

    I have to read the source of init_queue to see that there is a side effect of modifying the parameter I passed. Compare it to a clear assignment:

      struct priority_queue * pq;
      pq = init_queue(capacity);
    
  • Always test what malloc returns, and return NULL immediately if it fails. Ditto for reallocarray.

    Also, the blind

      (*pq)->heap_on_array = reallocarray((*pq)->heap_on_array, (*pq)->size * 2, sizeof(struct pq_node));
    

    leads to a memory leak in case of failure: the pointer to the original block is lost, and it cannot be freed. Typically one would

      temp = reallocarray(...);
      if (temp == NULL) {
          // handle_error, e.g. free(pq->heap_on_array);
          return;
      }
      pq->heap_on_array = temp;
    
  • No naked loops. Every loop implements an important algorithm, and deserves a name. In your case, the initial loop of insert_* is surely

      pq_node * find(priority_queue * pq, char symbol);
    
  • DRY. insert and insert_element are suspiciously similar. The only difference is in treating frequency. The common functionality shall be factored out into a function.

\$\endgroup\$
1
  • \$\begingroup\$ thanks for your answer, can you say more about the design of structures. Is them well-designed or not? Because structures is the main thing in all programms. \$\endgroup\$
    – Bogdasar
    Oct 9, 2020 at 20:20
2
\$\begingroup\$

in function:

void init_queue(struct priority_queue **pq, size_t capacity)

after the final closing brace '}' there is a semicolon ';'. This results in the compiler outputting:

untitled1.c:41:2: warning: ISO C does not allow extra ‘;’ outside of a function [-Wpedantic]

There are also some warnings about implicit conversions.

When compiling, always enable the warnings, then fix those warnings.

for gcc, at a minimum use:

-Wall -Wextra -Wconversion -pedantic -std=gnu11 

Note: other compilers use different options to produce the same results.

the file: priority_queue.h is missing the statement:

#endif

at the end of the file. So it does not compile!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.