Loading...
Searching...
No Matches
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
mqtt::topic_matcher::const_iterator
Definition topic_matcher.h:258
mqtt::topic_matcher::const_iterator::operator->
const value_type * operator->() const noexcept
Definition topic_matcher.h:274
mqtt::topic_matcher::const_iterator::operator*
const_reference operator*() const noexcept
Definition topic_matcher.h:269
mqtt::topic_matcher::const_iterator::topic_matcher
friend class topic_matcher
Definition topic_matcher.h:261
mqtt::topic_matcher::const_match_iterator
Definition topic_matcher.h:435
mqtt::topic_matcher::const_match_iterator::operator->
const value_type * operator->() const noexcept
Definition topic_matcher.h:451
mqtt::topic_matcher::const_match_iterator::operator*
const_reference operator*() const noexcept
Definition topic_matcher.h:446
mqtt::topic_matcher::const_match_iterator::topic_matcher
friend class topic_matcher
Definition topic_matcher.h:438
mqtt::topic_matcher::iterator
Definition topic_matcher.h:171
mqtt::topic_matcher::iterator::operator->
const value_type * operator->() const noexcept
Definition topic_matcher.h:228
mqtt::topic_matcher::iterator::operator++
iterator operator++(int) noexcept
Definition topic_matcher.h:233
mqtt::topic_matcher::iterator::operator*
reference operator*() noexcept
Definition topic_matcher.h:213
mqtt::topic_matcher::iterator::operator*
const_reference operator*() const noexcept
Definition topic_matcher.h:218
mqtt::topic_matcher::iterator::operator++
iterator & operator++() noexcept
Definition topic_matcher.h:242
mqtt::topic_matcher::iterator::operator!=
bool operator!=(const iterator &other) const noexcept
Definition topic_matcher.h:253
mqtt::topic_matcher::iterator::topic_matcher
friend class topic_matcher
Definition topic_matcher.h:200
mqtt::topic_matcher::iterator::operator->
value_type * operator->() noexcept
Definition topic_matcher.h:223
mqtt::topic_matcher::match_iterator
Definition topic_matcher.h:282
mqtt::topic_matcher::match_iterator::operator*
reference operator*() noexcept
Definition topic_matcher.h:386
mqtt::topic_matcher::match_iterator::operator++
match_iterator & operator++() noexcept
Definition topic_matcher.h:415
mqtt::topic_matcher::match_iterator::operator*
const_reference operator*() const noexcept
Definition topic_matcher.h:391
mqtt::topic_matcher::match_iterator::operator!=
bool operator!=(const match_iterator &other) const noexcept
Definition topic_matcher.h:426
mqtt::topic_matcher::match_iterator::operator->
value_type * operator->() noexcept
Definition topic_matcher.h:396
mqtt::topic_matcher::match_iterator::operator++
match_iterator operator++(int) noexcept
Definition topic_matcher.h:406
mqtt::topic_matcher::match_iterator::operator->
const value_type * operator->() const noexcept
Definition topic_matcher.h:401
mqtt::topic_matcher::match_iterator::topic_matcher
friend class topic_matcher
Definition topic_matcher.h:370
mqtt::topic_matcher::reference
value_type reference
Definition topic_matcher.h:121
mqtt::topic_matcher::value_ptr
std::unique_ptr< value_type > value_ptr
Definition topic_matcher.h:124
mqtt::topic_matcher::matches
const_match_iterator matches(const string &topic) const
Definition topic_matcher.h:602
mqtt::topic_matcher::empty
bool empty() const
Definition topic_matcher.h:482
mqtt::topic_matcher::insert
void insert(const value_type &val)
Definition topic_matcher.h:506
mqtt::topic_matcher::cend
const_iterator cend() const noexcept
Definition topic_matcher.h:564
mqtt::topic_matcher::key_type
string key_type
Definition topic_matcher.h:118
mqtt::topic_matcher::insert
void insert(value_type &&val)
Definition topic_matcher.h:487
mqtt::topic_matcher::remove
mapped_ptr remove(const key_type &filter)
Definition topic_matcher.h:518
mqtt::topic_matcher::value_type
std::pair< key_type, mapped_type > value_type
Definition topic_matcher.h:120
mqtt::topic_matcher::end
iterator end()
Definition topic_matcher.h:547
mqtt::topic_matcher::end
const_iterator end() const noexcept
Definition topic_matcher.h:552
mqtt::topic_matcher::matches_end
const_match_iterator matches_end() const noexcept
Definition topic_matcher.h:613
mqtt::topic_matcher::mapped_type
T mapped_type
Definition topic_matcher.h:119
mqtt::topic_matcher::begin
iterator begin()
Definition topic_matcher.h:542
mqtt::topic_matcher::matches
match_iterator matches(const string &topic)
Definition topic_matcher.h:596
mqtt::topic_matcher::find
const_iterator find(const key_type &filter) const
Definition topic_matcher.h:588
mqtt::topic_matcher::cbegin
const_iterator cbegin() const
Definition topic_matcher.h:559
mqtt::topic_matcher::find
iterator find(const key_type &filter)
Definition topic_matcher.h:570
mqtt::topic_matcher::topic_matcher
topic_matcher(std::initializer_list< value_type > lst)
Definition topic_matcher.h:472
mqtt::topic_matcher::prune
void prune()
Definition topic_matcher.h:537
mqtt::topic_matcher::has_match
bool has_match(const string &topic)
Definition topic_matcher.h:629
mqtt::topic_matcher::matches_cend
const_match_iterator matches_cend() const noexcept
Definition topic_matcher.h:622
mqtt::topic_matcher::const_reference
const value_type & const_reference
Definition topic_matcher.h:122
mqtt::topic_matcher::mapped_ptr
std::unique_ptr< mapped_type > mapped_ptr
Definition topic_matcher.h:125
mqtt::topic_matcher::topic_matcher
topic_matcher()
Definition topic_matcher.h:457
mqtt::topic
Definition topic.h:54
mqtt::topic::split
static std::vector< std::string > split(const std::string &topic)
mqtt
Definition async_client.h:60
mqtt::string
std::string string
Definition types.h:43
topic.h
types.h