1

I have been trying to create a huffman tree in C++. I have a custom Huffman Node class and a Huffman tree class, whose header and source file contents are shown below:

This is my main() function:

#include <iostream>         // Includes the input and output stream header file.
#include <string>           // Includes the string library.
#include <exception>            // Includes the exceptions header file.
#include "HuffmanNode.h"        // Includes the Huffman node class and all its respective components.
#include "HuffmanTree.h"        // Includes the Huffman tree class and all its respective components.
#include <fstream>          // Includes the file stream header file.

using namespace FOOBAR;     // Declare the use of my custom made namespace.

int main(int argc, char* argv[]) {
    std::string input_file, output_file;

    try {
        std::cout << "" << std::endl;
        input_file = std::string(argv[1]);  output_file = std::string(argv[2]);
        HuffmanTree my_huffman_tree = HuffmanTree(/*fptr compare*/);    
        my_huffman_tree.generateMap(input_file);
        my_huffman_tree.createHuffmanNodes();   
        std::cout << "" << std::endl;
    }
    catch(std::exception e) {
        std::cout << "" << std::endl;
        std::cout << "Error: " << e.what() << std::endl; // Print out the exact nature of the error.
        std::cout << "" << std::endl;
        exit(0);    // Terminate program execution.
    }
    return 0;
}

This is my Huffman Node header file:

// Preprocessor directives that guard against redeclaration should image_manipulator.h be defined elsewhere in the program
#ifndef HUFFMANNODE_H 
#define HUFFMANNODE_H

// These are the included header files that are required for the execution of the program.
#include <memory>

// This is my custom namespace for the program.
namespace FOOBAR {
    class HuffmanNode {
        private:
            char character; int frequency;      // These are the constituents of each node i.e. consists of a character as well as a frequency.
            std::shared_ptr<HuffmanNode> left_node, right_node; // Left and right attributes for my left and right nodes.
        public:

            HuffmanNode(char the_char, int the_frequency);      // Declaration of default constructor.
            HuffmanNode(int the_frequency);             // Declaration of default constructor.
            HuffmanNode(const HuffmanNode& rhs);            // Copy constructor.
            HuffmanNode(const HuffmanNode&& rhs);           // Move constructior.
            HuffmanNode & operator=(const HuffmanNode& rhs);    // Copy assignment operator.
            HuffmanNode && operator=(const HuffmanNode&& rhs);  // Move assignment operator.
            char getCharacter() const;              // Retrieve a key in the map.
            int getFrequency() const;               // retrieve a value in the map.
            std::shared_ptr<HuffmanNode> getLeftNode();     // Fetch the left node.
            std::shared_ptr<HuffmanNode> getRightNode();        // Fetch the right node.
            ~HuffmanNode();                     // Destructor.

            // Declare other methods to be used here. 
    };
}

#endif

This is my Huffman Node source file:

#include "HuffmanNode.h"

namespace CHRTIN006 {

    // This is the implementation one of the Huffman Node constructor method.   
    HuffmanNode::HuffmanNode(char the_char, int the_frequency) {
        HuffmanNode::character = the_char;  HuffmanNode::frequency = the_frequency;
    }

    // This is the implementation one of the Huffman Node constructor method.   
    HuffmanNode::HuffmanNode(int the_frequency) {
        HuffmanNode::frequency = the_frequency;
    }

    // This is the implementation of the Huffman Node copy constructor.
    HuffmanNode::HuffmanNode(const HuffmanNode &rhs) {
        HuffmanNode::character = rhs.HuffmanNode::character;
        HuffmanNode::frequency = rhs.HuffmanNode::frequency;
    }

    // This is the implementation of the Huffman Node move constructor.
    HuffmanNode::HuffmanNode(const HuffmanNode &&rhs) {

    }

    // This is the implementation of the Huffman Node copy assignment operator.
    HuffmanNode& HuffmanNode::operator=(const HuffmanNode &rhs) {
        if(this == &rhs) {
            return *this;
        }

        HuffmanNode::character = rhs.HuffmanNode::character;
        HuffmanNode::frequency = rhs.HuffmanNode::frequency;
        return *this; 
    }

    // This is the implementation of the Huffman Node move assignment operator. 
    HuffmanNode && HuffmanNode::operator=(const HuffmanNode &&rhs) {

    }

    // This method will return the key of an entry in the map.
    char HuffmanNode::getCharacter() const{
        return HuffmanNode::character;
    }

    // This method will return the value of an entry in the map.
    int HuffmanNode::getFrequency() const{
        return HuffmanNode::frequency;
    }

    // Retrieve the left most node of that particular branch.
    std::shared_ptr<HuffmanNode> HuffmanNode::getLeftNode() {
        return HuffmanNode::left_node;
    }

    // Retrieve the right most node of that particular branch.
    std::shared_ptr<HuffmanNode> HuffmanNode::getRightNode() {
        return HuffmanNode::right_node;
    }

    // This is the implementation of the Huffman Node destructor.   
    HuffmanNode::~HuffmanNode() {

    }
}

This is my header file contents for my Huffman Tree class:

// Preprocessor directives that guard against redeclaration should HuffmanTree.h be defined elsewhere in the program.
#ifndef HUFFMANTREE_H 
#define HUFFMANTREE_H

// These are the included header files that are required for the execution of the program.
#include <queue>        // For building the huffman tree.
#include "HuffmanNode.h"    // Includes the Huffman Node header file.
#include <unordered_map>    // Header file for my map that is going to store the respective frequencies of each letter.
#include <memory>       // For making use of smart pointers.    
#include <vector>       // For making use of vectors within the program.
#include <functional>       // For including the comparison method in the constructor of the queue.

// This is my custom namespace for the program.
namespace FOOBAR {
    class HuffmanTree {     // This is where my Huffman tree class starts.

        public:     // Objects an variables declared under this specifier are treated as being public.
            // Going to be used to determine how to order entries in the queue.
            typedef bool (*fptr)(const HuffmanNode&, const HuffmanNode&);       
            bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b); /////////////////////////////

            HuffmanTree(/*fptr compare*/);          // Default constructor.
            HuffmanTree(const HuffmanTree& rhs);        // Copy constructor.
            HuffmanTree(const HuffmanTree&& rhs);       // Move constructior.
            HuffmanTree& operator=(const HuffmanTree& rhs); // Copy assignment operator.
            HuffmanTree&& operator=(const HuffmanTree&& rhs);   // Move assignment operator.
            ~HuffmanTree();                 // Destructor.

            // This method is going to count the number of occurrences of each letter.
            void generateMap(std::string file); 

            // Create Huffman nodes and populate them in the priority queue.
            void createHuffmanNodes();
            // Declare other methods to be used here.

        private:    // Objects an variables declared under this specifier are treated as being private. 
            std::shared_ptr<HuffmanNode> root_node; // The root node for the Huffman tree.
            std::unordered_map<char, int> my_map;   // Map containing the respective frequencies of each letter.
            std::unordered_map<char, int>::iterator my_iterator;    // Iterator for indexing every element in my map.
            // This is the queue that is going to have entries of my shared pointers.
            std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, fptr> my_queue;
    };      // This is where my Huffman tree class ends.
}           // End of namespace.

#endif



This is the source file for my Huffman Tree class:

#include "HuffmanTree.h"
#include <fstream>
#include <iostream>
#include <boost/lexical_cast.hpp>   // Includes the lexical cast functionlaity from the boost library.

namespace FOOBAR {

    // This is the implementation of the Huffman Tree default constructor method.   
    HuffmanTree::HuffmanTree(/*fptr compare*/) /*: my_queue(compare)*/  {
        root_node = nullptr;
    }

    // This is the implementation of the Huffman Tree copy constructor.
    HuffmanTree::HuffmanTree(const HuffmanTree& rhs) {
        root_node = rhs.root_node;
    }

    // This is the implementation of the Huffman Tree move constructor.
    HuffmanTree::HuffmanTree(const HuffmanTree&& rhs) {

    }

    // This is the implementation of the Huffman Tree copy assignment operator.
    HuffmanTree& HuffmanTree::operator=(const HuffmanTree& rhs) {
        if(this == &rhs) {
            return *this;
        }
        root_node = rhs.root_node;
        return *this;
    } 

    // This is the implementation of the Huffman Tree move assignment operator. 
    HuffmanTree&& HuffmanTree::operator=(const HuffmanTree&& rhs) {

    } 

    // This is the implementation of the compare method that is going to be used to determine how to order entries in the queue.
    bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b) { ////////////////////////////////////////
        if(node_a.getFrequency() > node_b.getFrequency()) {
            return true;
        }
        else  {
            return false;
        }
    }

    // This method is going to count the number of occurrences of each letter.
    void HuffmanTree::generateMap(std::string file) {
        std::ifstream input_stream(file);   std::string line = "";
        if(input_stream.fail()) {
            std::cerr << "Error: Could not open the file specified." << std::endl; // Print this error message.
        }

        else {
            while(std::getline(input_stream, line)) {
                for(int i = 0; i < line.length(); i++) {
                    char my_character = line.at(i);
                    my_iterator = HuffmanTree::my_map.find(my_character);
                    if(my_iterator == my_map.end()) {
                        HuffmanTree::my_map.insert(std::make_pair(my_character, 1));
                    }
                    else {
                        my_iterator -> second++;
                    }
                }                   
            }       
        }   
    }

    void HuffmanTree::createHuffmanNodes() {
        for(my_iterator = my_map.begin(); my_iterator != my_map.end(); ++my_iterator) {
            HuffmanNode some_huffman_node = HuffmanNode(boost::lexical_cast<char>(my_iterator -> first), boost::lexical_cast<int>(my_iterator -> second));      
            //my_queue.push(some_huffman_node); <---- Causes Segfault error
        }
    }

    // This is the implementation of the Huffman Tree destructor.   
    HuffmanTree::~HuffmanTree() {
        HuffmanTree::root_node = nullptr;
    }
}

Any input text can be used.

But as soon as I try to push a newly created huffman node, i get the following error:

Makefile:32: recipe for target 'run' failed make: * [run] Segmentation fault (core dumped)**

I have been stuck on this part alone for the past 3 days. Can somebody help me please? Thank you in advance.

7
  • 1
    You open the program in the debugger step through and find the source of the SEGFAULT. Commented Apr 4, 2015 at 9:03
  • I already tried doing that, but the thing is my main() is just calling methods set in this class. So as soon as it tries to call the createHuffmanNodes() method, it crashes. So indeed it is telling me that the segfault takes place at the moment I try to insert a Huffman Node in the queue. I still don't understand what I am doing wrong. Commented Apr 4, 2015 at 9:09
  • @TinasheChirongoma If you're going to paste that much code, you might as well complete it. In which case, HuffmanNode is missing. It's only in the comment above that you mention where it fails. Commented Apr 4, 2015 at 9:17
  • And about the only thing you have in the function that you say causes it to fail, creates a HuffmanNode instance. Which code, you haven't shown. In other words, your code fails somewhere you haven't shown. So, please add there relevant code, otherwise you can't be helped. Commented Apr 4, 2015 at 9:24
  • @swalog I have just added the rest of the files. Its just that one part where the segfault occurs. Commented Apr 4, 2015 at 9:34

2 Answers 2

3

You are using:

std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, fptr> my_queue;
                                                           ^^^

Where fptr is simply a typedef, from

typedef bool (*fptr)(const HuffmanNode&, const HuffmanNode&);

This is your root cause of the segfault.

Instead, and easier on the eyes, is using a comparison object:

struct CompareHuffmanNode {
    bool operator()(HuffmanNode& n1, HuffmanNode& n2)
    {
      return n1.getFrequency() > n2.getFrequency();
    }
};

And declaring your priority_queue as

std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, CompareHuffmanNode> my_queue;
Sign up to request clarification or add additional context in comments.

1 Comment

Yup yup, if you use a function pointer as the comparer type, you have to actually provide that function.
0

(Credit to swalog for isolating the failure)

In your code, part of this line is commented out:

HuffmanTree::HuffmanTree(/*fptr compare*/) /*: my_queue(compare)*/  {
                                            ^ HERE ^ HERE ^ HERE ^

By not providing a comparer, the priority_queue is creating a default instance of the template argument type, which for a function pointer is a null pointer. The queue does need to call the comparer when you add items, and calling a null pointer is your segfault.

It's not clear why you commented out that initializer-list, but you shouldn't have. It's a critical part of making the program run correctly.

You appear to have a member function which you intend to use as the comparer, but it isn't compatible with a plain function pointer. To make it compatible, you'll need to make it static:

bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b);

and then you can associate the queue with it during construction

HuffmanTree::HuffmanTree() : my_queue(&HuffmanTree::compare) {

If you make the template argument a comparer class like swalog showed, then a default instance will do the right thing. So that is a viable way to fix this as well.

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.