JudyTrie.hpp

Go to the documentation of this file.

#pragma once

#include <tudocomp/config.h>
#ifdef JUDY_H_AVAILABLE

#include <tudocomp/Algorithm.hpp>
#include <tudocomp/compressors/lz78/LZ78Trie.hpp>
#include <tudocomp/compressors/lz78/squeeze_node.hpp>
#include <Judy.h> // Judy Array

namespace tdc {
namespace lz78 {

class JudyTrie : public Algorithm, public LZ78Trie<> {

    Pvoid_t m_dict; // judy array
    size_t m_size;

    inline factorid_t& find(const squeeze_node_t& node) {
        void* pvalue;
        JLI(pvalue, m_dict, node); //lookup node in dict, store value in pvalue
        DCHECK_NE(pvalue, PJERR);
        return *reinterpret_cast<factorid_t*>(pvalue);
    }

public:
    inline static Meta meta() {
        Meta m("lz78trie", "judy", "Lempel-Ziv 78 Judy Array");
        return m;
    }
    inline JudyTrie(Env&& env, size_t n, const size_t& remaining_characters, factorid_t = 0)
        : Algorithm(std::move(env))
        , LZ78Trie(n,remaining_characters)
        , m_dict(static_cast<Pvoid_t>(nullptr))
        , m_size(0)
    {
    }

    inline node_t get_rootnode(uliteral_t c) const {
        DCHECK_LT(create_node(0,c), std::numeric_limits<factorid_t>::max());
        return node_t(create_node(0,c), false);
    }

    inline node_t add_rootnode(uliteral_t c) {
        DCHECK_EQ(find(create_node(0, c)), 0);
        find(create_node(0, c)) = size();
        ++m_size;
        return node_t(m_size-1, true);
    }

    inline void clear() {
        if(m_dict != nullptr) {
            int i;
            JLFA(i, m_dict);
        }
        m_size = 0;
    }

    inline node_t find_or_insert(const node_t& parent, uliteral_t c) {
        const squeeze_node_t node = create_node(parent.id(), c);

        factorid_t& id = find(node);

        if(id == 0) {
            const factorid_t newleaf_id = size()+1; 
            id = newleaf_id;
            ++m_size;
            return node_t(newleaf_id, true);
        }
        return node_t(id-1, false);
    }

    inline size_t size() const {
        return m_size;
    }
};

}} //ns

#endif// JUDY_H_AVAILABLE