topic_matcher.h

Go to the documentation of this file.

 
/*******************************************************************************
 * Copyright (c) 2022-2025 Frank Pagliughi <fpagliughi@mindspring.com>
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v2.0
 * and Eclipse Distribution License v1.0 which accompany this distribution.
 *
 * The Eclipse Public License is available at
 *    http://www.eclipse.org/legal/epl-v20.html
 * and the Eclipse Distribution License is available at
 *   http://www.eclipse.org/org/documents/edl-v10.php.
 *
 * Contributors:
 *    Frank Pagliughi - initial implementation and documentation
 *******************************************************************************/
 
#ifndef __mqtt_topic_matcher_h
#define __mqtt_topic_matcher_h
 
#include <forward_list>
#include <initializer_list>
#include <map>
#include <memory>
#include <string>
#include <vector>
 
#include "mqtt/topic.h"
#include "mqtt/types.h"
 
namespace mqtt {


template <typename T>
class topic_matcher
{
public:
    using key_type = string;
    using mapped_type = T;
    using value_type = std::pair<key_type, mapped_type>;
    using reference = value_type;
    using const_reference = const value_type&;
 
    using value_ptr = std::unique_ptr<value_type>;
    using mapped_ptr = std::unique_ptr<mapped_type>;
 
private:
    struct node
    {
        using ptr_t = std::unique_ptr<node>;
        using map_t = std::map<string, ptr_t>;

        value_ptr content;
        map_t children;

        static ptr_t create() { return std::make_unique<node>(); }
        bool empty() const { return !content && children.empty(); }

        void prune() {
            for (auto& child : children) {
                child.second->prune();
            }
 
            for (auto child = children.cbegin(); child != children.cend();) {
                if (child->second->empty()) {
                    child = children.erase(child);
                }
                else {
                    ++child;
                }
            }
        }
    };
    using node_ptr = typename node::ptr_t;
    using node_map = typename node::map_t;

    node_ptr root_;
 
public:
    class iterator
    {
        value_type* pval_;
        std::vector<node*> nodes_;
 
        void next() {
            // If there are no nodes left to search, we're done.
            if (nodes_.empty()) {
                pval_ = nullptr;
                return;
            }
 
            // Get the next node to search.
            auto snode = std::move(nodes_.back());
            nodes_.pop_back();
 
            // Push the children onto the stack for later
            for (auto const& child : snode->children) {
                nodes_.push_back(child.second.get());
            }
 
            // If there's a value in this node, use it;
            // otherwise keep looking.
            pval_ = snode->content.get();
            if (!pval_)
                this->next();
        }
 
        friend class topic_matcher;
 
        iterator(value_type* pval) : pval_{pval} {}
        iterator(node* root) : pval_{nullptr} {
            nodes_.push_back(root);
            next();
        }
 
    public:
        reference operator*() noexcept { return *pval_; }
        const_reference operator*() const noexcept { return *pval_; }
        value_type* operator->() noexcept { return pval_; }
        const value_type* operator->() const noexcept { return pval_; }
        iterator operator++(int) noexcept {
            auto tmp = *this;
            this->next();
            return tmp;
        }

        iterator& operator++() noexcept {
            this->next();
            return *this;
        }

        bool operator!=(const iterator& other) const noexcept { return pval_ != other.pval_; }
    };

    class const_iterator : public iterator
    {
        using base = iterator;
 
        friend class topic_matcher;
        const_iterator(iterator it) : base(it) {}
 
    public:
        const_reference operator*() const noexcept { return base::operator*(); }
        const value_type* operator->() const noexcept { return base::operator->(); }
    };

    class match_iterator
    {
        struct search_node
        {
            node* node_;
            std::forward_list<string> fields_;
            bool first_;
 
            search_node(node* nd, const std::forward_list<string>& sy, bool first = false)
                : node_{nd}, fields_{sy}, first_{first} {}
            search_node(node* nd, std::forward_list<string>&& sy, bool first = false)
                : node_{nd}, fields_{std::move(sy)}, first_{first} {}
        };

        value_type* pval_;
        std::vector<search_node> nodes_;

        void next() {
            pval_ = nullptr;
 
            // If there are no nodes left to search, we're done.
            if (nodes_.empty())
                return;
 
            // Get the next node to search.
            auto snode = std::move(nodes_.back());
            nodes_.pop_back();
 
            const auto map_end = snode.node_->children.end();
            typename node_map::iterator child;
 
            // If we're at the end of the topic fields, we either have a value,
            // or need to move on to the next node to search.
            if (snode.fields_.empty()) {
                pval_ = snode.node_->content.get();
                if (!pval_) {
                    // ...but a '#' matches the parent topic
                    if ((child = snode.node_->children.find("#")) != map_end) {
                        pval_ = child->second->content.get();
                        return;
                    }
                    this->next();
                }
                return;
            }
 
            // Get the next field of the topic to search
            auto field = std::move(snode.fields_.front());
            snode.fields_.pop_front();
 
            // Look for an exact match
            if ((child = snode.node_->children.find(field)) != map_end) {
                nodes_.push_back({child->second.get(), snode.fields_});
            }
 
            // Topics starting with '$' don't match wildcards in the first field
            // MQTT v5 Spec, Section 4.7.2:
            // https://docs.oasis-open.org/mqtt/mqtt/v5.0/os/mqtt-v5.0-os.html#_Toc3901246
 
            if (!snode.first_ || field.empty() || field[0] != '$') {
                // Look for a single-field wildcard match
                if ((child = snode.node_->children.find("+")) != map_end) {
                    nodes_.push_back({child->second.get(), snode.fields_});
                }
 
                // Look for a terminating match
                if ((child = snode.node_->children.find("#")) != map_end) {
                    // By definition, a '#' is a terminating leaf
                    pval_ = child->second->content.get();
                    return;
                }
            }
 
            this->next();
        }
 
        friend class topic_matcher;
 
        match_iterator() : pval_{nullptr} {}
        match_iterator(value_type* pval) : pval_{pval} {}
        match_iterator(node* root, const string& topic) : pval_{nullptr} {
            auto v = topic::split(topic);
            std::forward_list<string> fields{v.begin(), v.end()};
            nodes_.push_back(search_node{root, std::move(fields), true});
            next();
        }
 
    public:
        reference operator*() noexcept { return *pval_; }
        const_reference operator*() const noexcept { return *pval_; }
        value_type* operator->() noexcept { return pval_; }
        const value_type* operator->() const noexcept { return pval_; }
        match_iterator operator++(int) noexcept {
            auto tmp = *this;
            this->next();
            return tmp;
        }

        match_iterator& operator++() noexcept {
            this->next();
            return *this;
        }

        bool operator!=(const match_iterator& other) const noexcept {
            return pval_ != other.pval_;
        }
    };

    class const_match_iterator : public match_iterator
    {
        using base = match_iterator;
 
        friend class topic_matcher;
        const_match_iterator(match_iterator it) : base(it) {}
 
    public:
        const_reference operator*() const noexcept { return base::operator*(); }
        const value_type* operator->() const noexcept { return base::operator->(); }
    };

    topic_matcher() : root_(node::create()) {}
    topic_matcher(std::initializer_list<value_type> lst) : root_(node::create()) {
        for (const auto& v : lst) {
            insert(v);
        }
    }

    bool empty() const { return root_.empty(); }
    void insert(value_type&& val) {
        auto nd = root_.get();
        auto fields = topic::split(val.first);
 
        for (const auto& field : fields) {
            auto it = nd->children.find(field);
            if (it == nd->children.end()) {
                nd->children[field] = node::create();
                it = nd->children.find(field);
            }
            nd = it->second.get();
        }
        nd->content = std::make_unique<value_type>(std::move(val));
    }

    void insert(const value_type& val) {
        value_type v{val};
        this->insert(std::move(v));
    }

    mapped_ptr remove(const key_type& filter) {
        auto nd = root_.get();
        auto fields = topic::split(filter);
 
        for (auto& field : fields) {
            auto it = nd->children.find(field);
            if (it == nd->children.end())
                return mapped_ptr{};
 
            nd = it->second.get();
        }
        value_ptr valpair;
        nd->content.swap(valpair);
 
        return (valpair) ? std::make_unique<mapped_type>(valpair->second) : mapped_ptr{};
    }

    void prune() { root_->prune(); }
    iterator begin() { return iterator{root_.get()}; }
    iterator end() { return iterator{static_cast<value_type*>(nullptr)}; }
    const_iterator end() const noexcept {
        return const_iterator{static_cast<value_type*>(nullptr)};
    }

    const_iterator cbegin() const { return const_iterator{root_.get()}; }
    const_iterator cend() const noexcept { return end(); }
    iterator find(const key_type& filter) {
        auto nd = root_.get();
        auto fields = topic::split(filter);
 
        for (auto& field : fields) {
            auto it = nd->children.find(field);
            if (it == nd->children.end())
                return end();
            nd = it->second.get();
        }
        return iterator{nd->content.get()};
    }

    const_iterator find(const key_type& filter) const {
        return const_cast<topic_matcher*>(this)->find(filter);
    }

    match_iterator matches(const string& topic) { return match_iterator(root_.get(), topic); }
    const_match_iterator matches(const string& topic) const {
        return match_iterator(root_.get(), topic);
    }

    const_match_iterator matches_end() const noexcept { return match_iterator{}; }
    const_match_iterator matches_cend() const noexcept { return match_iterator{}; }
    bool has_match(const string& topic) { return matches(topic) != matches_cend(); }
};

}  // namespace mqtt
 
#endif  // __mqtt_topic_matcher_h