PahoMqttCpp
MQTT C++ Client for POSIX and Windows
Loading...
Searching...
No Matches
topic_matcher.h
Go to the documentation of this file.
1
7
8/*******************************************************************************
9 * Copyright (c) 2022-2025 Frank Pagliughi <fpagliughi@mindspring.com>
10 *
11 * All rights reserved. This program and the accompanying materials
12 * are made available under the terms of the Eclipse Public License v2.0
13 * and Eclipse Distribution License v1.0 which accompany this distribution.
14 *
15 * The Eclipse Public License is available at
16 * http://www.eclipse.org/legal/epl-v20.html
17 * and the Eclipse Distribution License is available at
18 * http://www.eclipse.org/org/documents/edl-v10.php.
19 *
20 * Contributors:
21 * Frank Pagliughi - initial implementation and documentation
22 *******************************************************************************/
23
24#ifndef __mqtt_topic_matcher_h
25#define __mqtt_topic_matcher_h
26
27#include <forward_list>
28#include <initializer_list>
29#include <map>
30#include <memory>
31#include <string>
32#include <vector>
33
34#include "mqtt/topic.h"
35#include "mqtt/types.h"
36
37namespace mqtt {
38
40
107template <typename T>
109{
110public:
112 using mapped_type = T;
113 using value_type = std::pair<key_type, mapped_type>;
116
117 using value_ptr = std::unique_ptr<value_type>;
118 using mapped_ptr = std::unique_ptr<mapped_type>;
119
120private:
124 struct node
125 {
126 using ptr_t = std::unique_ptr<node>;
127 using map_t = std::map<string, ptr_t>;
128
130 value_ptr content;
132 map_t children;
133
135 static ptr_t create() { return std::make_unique<node>(); }
137 bool empty() const { return !content && children.empty(); }
138
140 void prune() {
141 for (auto& child : children) {
142 child.second->prune();
143 }
144
145 for (auto child = children.cbegin(); child != children.cend();) {
146 if (child->second->empty()) {
147 child = children.erase(child);
148 }
149 else {
150 ++child;
151 }
152 }
153 }
154 };
155 using node_ptr = typename node::ptr_t;
156 using node_map = typename node::map_t;
157
159 node_ptr root_;
160
161public:
163 class iterator
164 {
166 value_type* pval_;
168 std::vector<node*> nodes_;
169
170 void next() {
171 // If there are no nodes left to search, we're done.
172 if (nodes_.empty()) {
173 pval_ = nullptr;
174 return;
175 }
176
177 // Get the next node to search.
178 auto snode = std::move(nodes_.back());
179 nodes_.pop_back();
180
181 // Push the children onto the stack for later
182 for (auto const& child : snode->children) {
183 nodes_.push_back(child.second.get());
184 }
185
186 // If there's a value in this node, use it;
187 // otherwise keep looking.
188 pval_ = snode->content.get();
189 if (!pval_)
190 this->next();
191 }
192
193 friend class topic_matcher;
194
195 iterator(value_type* pval) : pval_{pval} {}
196 iterator(node* root) : pval_{nullptr} {
197 nodes_.push_back(root);
198 next();
199 }
200
201 public:
206 reference operator*() noexcept { return *pval_; }
211 const_reference operator*() const noexcept { return *pval_; }
216 value_type* operator->() noexcept { return pval_; }
221 const value_type* operator->() const noexcept { return pval_; }
226 iterator operator++(int) noexcept {
227 auto tmp = *this;
228 this->next();
229 return tmp;
230 }
231
235 iterator& operator++() noexcept {
236 this->next();
237 return *this;
238 }
239
246 bool operator!=(const iterator& other) const noexcept { return pval_ != other.pval_; }
247 };
248
250 class const_iterator : public iterator
251 {
252 using base = iterator;
253
254 friend class topic_matcher;
255 const_iterator(iterator it) : base(it) {}
256
257 public:
262 const_reference operator*() const noexcept { return base::operator*(); }
267 const value_type* operator->() const noexcept { return base::operator->(); }
268 };
269
274 class match_iterator
275 {
277 struct search_node
278 {
280 node* node_;
282 std::forward_list<string> fields_;
284 bool first_;
285
286 search_node(node* nd, const std::forward_list<string>& sy, bool first = false)
287 : node_{nd}, fields_{sy}, first_{first} {}
288 search_node(node* nd, std::forward_list<string>&& sy, bool first = false)
289 : node_{nd}, fields_{std::move(sy)}, first_{first} {}
290 };
291
293 value_type* pval_;
295 std::vector<search_node> nodes_;
296
304 void next() {
305 pval_ = nullptr;
306
307 // If there are no nodes left to search, we're done.
308 if (nodes_.empty())
309 return;
310
311 // Get the next node to search.
312 auto snode = std::move(nodes_.back());
313 nodes_.pop_back();
314
315 // If we're at the end of the topic fields, we either have a value,
316 // or need to move on to the next node to search.
317 if (snode.fields_.empty()) {
318 pval_ = snode.node_->content.get();
319 if (!pval_)
320 this->next();
321 return;
322 }
323
324 // Get the next field of the topic to search
325 auto field = std::move(snode.fields_.front());
326 snode.fields_.pop_front();
327
328 typename node_map::iterator child;
329 const auto map_end = snode.node_->children.end();
330
331 // Look for an exact match
332 if ((child = snode.node_->children.find(field)) != map_end) {
333 nodes_.push_back({child->second.get(), snode.fields_});
334 }
335
336 // Topics starting with '$' don't match wildcards in the first field
337 // MQTT v5 Spec, Section 4.7.2:
338 // https://docs.oasis-open.org/mqtt/mqtt/v5.0/os/mqtt-v5.0-os.html#_Toc3901246
339
340 if (!snode.first_ || field.empty() || field[0] != '$') {
341 // Look for a single-field wildcard match
342 if ((child = snode.node_->children.find("+")) != map_end) {
343 nodes_.push_back({child->second.get(), snode.fields_});
344 }
345
346 // Look for a terminating match
347 if ((child = snode.node_->children.find("#")) != map_end) {
348 // By definition, a '#' is a terminating leaf
349 pval_ = child->second->content.get();
350 return;
351 }
352 }
353
354 this->next();
355 }
356
357 friend class topic_matcher;
358
359 match_iterator() : pval_{nullptr} {}
360 match_iterator(value_type* pval) : pval_{pval} {}
361 match_iterator(node* root, const string& topic) : pval_{nullptr} {
362 auto v = topic::split(topic);
363 std::forward_list<string> fields{v.begin(), v.end()};
364 nodes_.push_back(search_node{root, std::move(fields), true});
365 next();
366 }
367
368 public:
373 reference operator*() noexcept { return *pval_; }
378 const_reference operator*() const noexcept { return *pval_; }
383 value_type* operator->() noexcept { return pval_; }
388 const value_type* operator->() const noexcept { return pval_; }
393 match_iterator operator++(int) noexcept {
394 auto tmp = *this;
395 this->next();
396 return tmp;
397 }
398
402 match_iterator& operator++() noexcept {
403 this->next();
404 return *this;
405 }
406
413 bool operator!=(const match_iterator& other) const noexcept {
414 return pval_ != other.pval_;
415 }
416 };
417
421 class const_match_iterator : public match_iterator
422 {
423 using base = match_iterator;
424
425 friend class topic_matcher;
426 const_match_iterator(match_iterator it) : base(it) {}
427
428 public:
433 const_reference operator*() const noexcept { return base::operator*(); }
438 const value_type* operator->() const noexcept { return base::operator->(); }
439 };
440
444 topic_matcher() : root_(node::create()) {}
459 topic_matcher(std::initializer_list<value_type> lst) : root_(node::create()) {
460 for (const auto& v : lst) {
461 insert(v);
462 }
463 }
464
469 bool empty() const { return root_.empty(); }
474 void insert(value_type&& val) {
475 auto nd = root_.get();
476 auto fields = topic::split(val.first);
477
478 for (const auto& field : fields) {
479 auto it = nd->children.find(field);
480 if (it == nd->children.end()) {
481 nd->children[field] = node::create();
482 it = nd->children.find(field);
483 }
484 nd = it->second.get();
485 }
486 nd->content = std::make_unique<value_type>(std::move(val));
487 }
488
493 void insert(const value_type& val) {
494 value_type v{val};
495 this->insert(std::move(v));
496 }
497
505 mapped_ptr remove(const key_type& filter) {
506 auto nd = root_.get();
507 auto fields = topic::split(filter);
508
509 for (auto& field : fields) {
510 auto it = nd->children.find(field);
511 if (it == nd->children.end())
512 return mapped_ptr{};
513
514 nd = it->second.get();
515 }
516 value_ptr valpair;
517 nd->content.swap(valpair);
518
519 return (valpair) ? std::make_unique<mapped_type>(valpair->second) : mapped_ptr{};
520 }
521
524 void prune() { root_->prune(); }
529 iterator begin() { return iterator{root_.get()}; }
534 iterator end() { return iterator{static_cast<value_type*>(nullptr)}; }
539 const_iterator end() const noexcept {
540 return const_iterator{static_cast<value_type*>(nullptr)};
541 }
542
546 const_iterator cbegin() const { return const_iterator{root_.get()}; }
551 const_iterator cend() const noexcept { return end(); }
557 iterator find(const key_type& filter) {
558 auto nd = root_.get();
559 auto fields = topic::split(filter);
560
561 for (auto& field : fields) {
562 auto it = nd->children.find(field);
563 if (it == nd->children.end())
564 return end();
565 nd = it->second.get();
566 }
567 return iterator{nd->content.get()};
568 }
569
575 const_iterator find(const key_type& filter) const {
576 return const_cast<topic_matcher*>(this)->find(filter);
577 }
578
583 match_iterator matches(const string& topic) { return match_iterator(root_.get(), topic); }
589 const_match_iterator matches(const string& topic) const {
590 return match_iterator(root_.get(), topic);
591 }
592
600 const_match_iterator matches_end() const noexcept { return match_iterator{}; }
609 const_match_iterator matches_cend() const noexcept { return match_iterator{}; }
616 bool has_match(const string& topic) { return matches(topic) != matches_cend(); }
617};
618
620} // namespace mqtt
621
622#endif // __mqtt_topic_matcher_h
Definition topic_matcher.h:251
const value_type * operator->() const noexcept
Definition topic_matcher.h:267
const_reference operator*() const noexcept
Definition topic_matcher.h:262
friend class topic_matcher
Definition topic_matcher.h:254
Definition topic_matcher.h:422
const value_type * operator->() const noexcept
Definition topic_matcher.h:438
const_reference operator*() const noexcept
Definition topic_matcher.h:433
friend class topic_matcher
Definition topic_matcher.h:425
Definition topic_matcher.h:164
const value_type * operator->() const noexcept
Definition topic_matcher.h:221
iterator operator++(int) noexcept
Definition topic_matcher.h:226
reference operator*() noexcept
Definition topic_matcher.h:206
const_reference operator*() const noexcept
Definition topic_matcher.h:211
iterator & operator++() noexcept
Definition topic_matcher.h:235
bool operator!=(const iterator &other) const noexcept
Definition topic_matcher.h:246
friend class topic_matcher
Definition topic_matcher.h:193
value_type * operator->() noexcept
Definition topic_matcher.h:216
Definition topic_matcher.h:275
reference operator*() noexcept
Definition topic_matcher.h:373
match_iterator & operator++() noexcept
Definition topic_matcher.h:402
const_reference operator*() const noexcept
Definition topic_matcher.h:378
bool operator!=(const match_iterator &other) const noexcept
Definition topic_matcher.h:413
value_type * operator->() noexcept
Definition topic_matcher.h:383
match_iterator operator++(int) noexcept
Definition topic_matcher.h:393
const value_type * operator->() const noexcept
Definition topic_matcher.h:388
friend class topic_matcher
Definition topic_matcher.h:357
value_type reference
Definition topic_matcher.h:114
std::unique_ptr< value_type > value_ptr
Definition topic_matcher.h:117
const_match_iterator matches(const string &topic) const
Definition topic_matcher.h:589
bool empty() const
Definition topic_matcher.h:469
void insert(const value_type &val)
Definition topic_matcher.h:493
const_iterator cend() const noexcept
Definition topic_matcher.h:551
string key_type
Definition topic_matcher.h:111
void insert(value_type &&val)
Definition topic_matcher.h:474
mapped_ptr remove(const key_type &filter)
Definition topic_matcher.h:505
std::pair< key_type, mapped_type > value_type
Definition topic_matcher.h:113
iterator end()
Definition topic_matcher.h:534
const_iterator end() const noexcept
Definition topic_matcher.h:539
const_match_iterator matches_end() const noexcept
Definition topic_matcher.h:600
T mapped_type
Definition topic_matcher.h:112
iterator begin()
Definition topic_matcher.h:529
match_iterator matches(const string &topic)
Definition topic_matcher.h:583
const_iterator find(const key_type &filter) const
Definition topic_matcher.h:575
const_iterator cbegin() const
Definition topic_matcher.h:546
iterator find(const key_type &filter)
Definition topic_matcher.h:557
topic_matcher(std::initializer_list< value_type > lst)
Definition topic_matcher.h:459
void prune()
Definition topic_matcher.h:524
bool has_match(const string &topic)
Definition topic_matcher.h:616
const_match_iterator matches_cend() const noexcept
Definition topic_matcher.h:609
const value_type & const_reference
Definition topic_matcher.h:115
std::unique_ptr< mapped_type > mapped_ptr
Definition topic_matcher.h:118
topic_matcher()
Definition topic_matcher.h:444
Definition topic.h:45
static std::vector< std::string > split(const std::string &topic)
Definition async_client.h:60
std::string string
Definition types.h:43