• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

PowerDNS / pdns / 18903493638

29 Oct 2025 09:39AM UTC coverage: 73.004%. Remained the same
18903493638

Pull #16388

github

web-flow
Merge 1bddbd8fe into 82ea647b4
Pull Request #16388: gh actions build-packages: fix pattern for the download-artifacts action and publication issues

38272 of 63120 branches covered (60.63%)

Branch coverage included in aggregate %.

127434 of 163861 relevant lines covered (77.77%)

6052684.91 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.11
/pdns/dnsname.hh
1
/*
2
 * This file is part of PowerDNS or dnsdist.
3
 * Copyright -- PowerDNS.COM B.V. and its contributors
4
 *
5
 * This program is free software; you can redistribute it and/or modify
6
 * it under the terms of version 2 of the GNU General Public License as
7
 * published by the Free Software Foundation.
8
 *
9
 * In addition, for the avoidance of any doubt, permission is granted to
10
 * link this program with OpenSSL and to (re)distribute the binaries
11
 * produced as the result of such linking.
12
 *
13
 * This program is distributed in the hope that it will be useful,
14
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
 * GNU General Public License for more details.
17
 *
18
 * You should have received a copy of the GNU General Public License
19
 * along with this program; if not, write to the Free Software
20
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21
 */
22
#pragma once
23
#include <array>
24
#include <cstring>
25
#include <optional>
26
#include <string>
27
#include <utility>
28
#include <vector>
29
#include <set>
30
#include <strings.h>
31
#include <stdexcept>
32
#include <sstream>
33
#include <iterator>
34
#include <unordered_set>
35
#include <string_view>
36

37
using namespace std::string_view_literals;
38

39
#include <boost/version.hpp>
40
#include <boost/container/string.hpp>
41

42
inline bool dns_isspace(char chr) __attribute__((const));
43
inline bool dns_isspace(char chr)
44
{
61,496,675✔
45
  return chr == ' ' || chr == '\t' || chr == '\r' || chr == '\n';
61,496,675✔
46
}
61,496,675✔
47

48
extern const unsigned char dns_toupper_table[256], dns_tolower_table[256];
49

50
inline unsigned char dns_toupper(unsigned char chr) __attribute__((pure));
51
inline unsigned char dns_toupper(unsigned char chr)
52
{
17,876,906✔
53
  return dns_toupper_table[chr];
17,876,906✔
54
}
17,876,906✔
55

56
inline unsigned char dns_tolower(unsigned char chr) __attribute__((pure));
57
inline unsigned char dns_tolower(unsigned char chr)
58
{
10,314,204,035✔
59
  return dns_tolower_table[chr];
10,314,204,035✔
60
}
10,314,204,035✔
61

62
#include "burtle.hh"
63
#include "views.hh"
64

65
/* Quest in life:
66
     accept escaped ascii presentations of DNS names and store them "natively"
67
     accept a DNS packet with an offset, and extract a DNS name from it
68
     build up DNSNames with prepend and append of 'raw' unescaped labels
69

70
   Be able to turn them into ASCII and "DNS name in a packet" again on request
71

72
   Provide some common operators for comparison, detection of being part of another domain
73

74
   NOTE: For now, everything MUST be . terminated, otherwise it is an error
75
*/
76

77
// DNSName: represents a case-insensitive string, allowing for non-printable
78
// characters. It is used for all kinds of name (of hosts, domains, keys,
79
// algorithm...) overall the PowerDNS codebase.
80
//
81
// The following type traits are provided:
82
// - EqualityComparable
83
// - LessThanComparable
84
// - Hash
85
#if defined(PDNS_AUTH)
86
class ZoneName;
87
#endif
88
class DNSName
89
{
90
public:
91
  static const size_t s_maxDNSNameLength = 255;
92

93
  DNSName() = default; //!< Constructs an *empty* DNSName, NOT the root!
78,456,590✔
94
  // Work around assertion in some boost versions that do not like self-assignment of boost::container::string
95
  DNSName& operator=(const DNSName& rhs)
96
  {
43,915,647✔
97
    if (this != &rhs) {
43,917,629✔
98
      d_storage = rhs.d_storage;
40,638,361✔
99
    }
40,638,361✔
100
    return *this;
43,915,647✔
101
  }
43,915,647✔
102
  DNSName& operator=(DNSName&& rhs) noexcept
103
  {
56,000,796✔
104
    if (this != &rhs) {
56,003,323✔
105
      d_storage = std::move(rhs.d_storage);
55,988,559✔
106
    }
55,988,559✔
107
    return *this;
56,000,796✔
108
  }
56,000,796✔
109
  DNSName(const DNSName& a) = default;
101,811,467✔
110
  DNSName(DNSName&& a) = default;
58,432,945✔
111

112
  explicit DNSName(std::string_view sw); //!< Constructs from a human formatted, escaped presentation
113
  DNSName(const char* p, size_t len, size_t offset, bool uncompress, uint16_t* qtype = nullptr, uint16_t* qclass = nullptr, unsigned int* consumed = nullptr, uint16_t minOffset = 0); //!< Construct from a DNS Packet, taking the first question if offset=12. If supplied, consumed is set to the number of bytes consumed from the packet, which will not be equal to the wire length of the resulting name in case of compression.
114

115
  bool isPartOf(const DNSName& rhs) const;   //!< Are we part of the rhs name? Note that name.isPartOf(name).
116
  inline bool operator==(const DNSName& rhs) const; //!< DNS-native comparison (case insensitive) - empty compares to empty
117
  bool operator!=(const DNSName& other) const { return !(*this == other); }
10,951,624✔
118
  // !< DNS-native (case insensitive) comparison against raw data in (uncompressed) wire format. The view has to start with the DNS name, but does not have to contain only a DNS name. Roughly, passing a view of a DNS packet starting just after the DNS header is OK, everything else is not because any names present later in the packet might be compressed.
119
  bool matchesUncompressedName(const std::string_view& wire_uncompressed) const;
120

121
  std::string toString(const std::string& separator=".", const bool trailing=true) const;              //!< Our human-friendly, escaped, representation
122
  void toString(std::string& output, const std::string& separator=".", const bool trailing=true) const;
123
  std::string toLogString() const; //!< like plain toString, but returns (empty) on empty names
124
  std::string toStringNoDot() const { return toString(".", false); }
777,648✔
125
  std::string toStringRootDot() const { if(isRoot()) return "."; else return toString(".", false); }
3,507,299✔
126
  std::string toDNSString() const;           //!< Our representation in DNS native format
127
  std::string toDNSStringLC() const;           //!< Our representation in DNS native format, lower cased
128
  void appendRawLabel(const std::string& str); //!< Append this unescaped label
129
  void appendRawLabel(const char* start, unsigned int length); //!< Append this unescaped label
130
  void prependRawLabel(const std::string& str); //!< Prepend this unescaped label
131
  std::vector<std::string> getRawLabels() const; //!< Individual raw unescaped labels
132
  std::string getRawLabel(unsigned int pos) const; //!< Get the specified raw unescaped label
133
  DNSName getLastLabel() const; //!< Get the DNSName of the last label
134
  bool chopOff();                               //!< Turn www.powerdns.com. into powerdns.com., returns false for .
135
  DNSName makeRelative(const DNSName& zone) const;
136
  DNSName makeLowerCase() const
137
  {
3,679,864✔
138
    DNSName ret(*this);
3,679,864✔
139
    ret.makeUsLowerCase();
3,679,864✔
140
    return ret;
3,679,864✔
141
  }
3,679,864✔
142
  void makeUsLowerCase()
143
  {
6,998,255✔
144
    for(auto & c : d_storage) {
171,717,750✔
145
      c=dns_tolower(c);
171,717,750✔
146
    }
171,717,750✔
147
  }
6,998,255✔
148
  void makeUsRelative(const DNSName& zone);
149
  DNSName getCommonLabels(const DNSName& other) const; //!< Return the list of common labels from the top, for example 'c.d' for 'a.b.c.d' and 'x.y.c.d'
150
  DNSName labelReverse() const;
151
  bool isWildcard() const;
152
  bool isHostname(bool allowUnderscore = false) const;
153
  unsigned int countLabels() const;
154
  size_t wirelength() const; //!< Number of total bytes in the name
155
  bool empty() const { return d_storage.empty(); }
215,141,064✔
156
  bool isRoot() const { return d_storage.size()==1 && d_storage[0]==0; }
49,613,228✔
157
  bool hasLabels() const { return !empty() && !isRoot(); }
1,648,105✔
158
  void clear() { d_storage.clear(); }
3,356,135✔
159
  void trimToLabels(unsigned int);
160
  size_t hash(size_t init=0) const
161
  {
32,375,137✔
162
    return burtleCI(d_storage, init);
32,375,137✔
163
  }
32,375,137✔
164
  DNSName& operator+=(const DNSName& rhs)
165
  {
13,744,873✔
166
    if(d_storage.size() + rhs.d_storage.size() > s_maxDNSNameLength + 1) // one extra byte for the second root label
13,744,873✔
167
      throwSafeRangeError("resulting name too long", rhs.d_storage.data(), rhs.d_storage.size());
467✔
168
    if(rhs.empty())
13,744,873✔
169
      return *this;
20✔
170

171
    if(d_storage.empty())
13,744,853!
172
      d_storage+=rhs.d_storage;
×
173
    else
13,744,853✔
174
      d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage);
13,744,853✔
175

176
    return *this;
13,744,853✔
177
  }
13,744,873✔
178

179
  bool operator<(const DNSName& rhs)  const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though.
180
  {
180,854,977✔
181
    struct DNSNameCompare
180,854,977✔
182
    {
180,854,977✔
183
      bool operator()(const unsigned char& lhs, const unsigned char& rhs) const
180,854,977✔
184
      {
4,349,846,111✔
185
        return dns_tolower(lhs) < dns_tolower(rhs);
4,349,846,111✔
186
      }
4,349,846,111✔
187
    };
180,854,977✔
188

189
    // note that this is case insensitive, including on the label lengths
190
    return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(),
180,854,977✔
191
             rhs.d_storage.rbegin(), rhs.d_storage.rend(), DNSNameCompare());
180,854,977✔
192
  }
180,854,977✔
193

194
  int slowCanonCompare_three_way(const DNSName& rhs) const;
195
  int canonCompare_three_way(const DNSName& rhs, bool pretty = false) const;
196
  inline bool canonCompare(const DNSName& rhs, bool pretty = false) const { return canonCompare_three_way(rhs, pretty) < 0; }
126,756,584✔
197

198
  typedef boost::container::string string_t;
199

200
  const string_t& getStorage() const {
48,951,485✔
201
    return d_storage;
48,951,485✔
202
  }
48,951,485✔
203

204
  [[nodiscard]] size_t sizeEstimate() const
205
  {
242✔
206
    return d_storage.size(); // knowingly overestimating small strings as most string
242✔
207
                             // implementations have internal capacity and we always include
208
                             // sizeof(*this)
209
  }
242✔
210

211
  bool has8bitBytes() const; /* returns true if at least one byte of the labels forming the name is not included in [A-Za-z0-9_*./@ \\:-] */
212

213
  class RawLabelsVisitor
214
  {
215
  public:
216
    /* Zero-copy, zero-allocation raw labels visitor.
217
       The general idea is that we walk the labels in the constructor,
218
       filling up our array of labels position and setting the initial
219
       value of d_position at the number of labels.
220
       We then can easily provide string_view into the first and last label.
221
       pop_back() moves d_position one label closer to the start, so we
222
       can also easily walk back the labels in reverse order.
223
       There is no copy because we use a reference into the DNSName storage,
224
       so it is absolutely forbidden to alter the DNSName for as long as we
225
       exist, and no allocation because we use a static array (there cannot
226
       be more than 128 labels in a DNSName).
227
    */
228
    RawLabelsVisitor(const string_t& storage);
229
    std::string_view front() const;
230
    std::string_view back() const;
231
    bool pop_back();
232
    bool empty() const;
233
  private:
234
    std::array<uint8_t, 128> d_labelPositions;
235
    const string_t& d_storage;
236
    size_t d_position{0};
237
  };
238
  RawLabelsVisitor getRawLabelsVisitor() const;
239

240
#if defined(PDNS_AUTH) // [
241
  // Sugar while ZoneName::operator DNSName are made explicit
242
  bool isPartOf(const ZoneName& rhs) const;
243
  DNSName makeRelative(const ZoneName& zone) const;
244
  void makeUsRelative(const ZoneName& zone);
245
#endif // ]
246

247
private:
248
  string_t d_storage;
249

250
  void packetParser(const char* qpos, size_t len, size_t offset, bool uncompress, uint16_t* qtype, uint16_t* qclass, unsigned int* consumed, int depth, uint16_t minOffset);
251
  size_t parsePacketUncompressed(const pdns::views::UnsignedCharView& view, size_t position, bool uncompress);
252
  static void appendEscapedLabel(std::string& appendTo, const char* orig, size_t len);
253
  static std::string unescapeLabel(const std::string& orig);
254
  static void throwSafeRangeError(const std::string& msg, const char* buf, size_t length);
255
};
256

257
size_t hash_value(DNSName const& d);
258

259
struct CanonDNSNameCompare
260
{
261
  bool operator()(const DNSName&a, const DNSName& b) const
262
  {
60,208,831✔
263
    return a.canonCompare(b);
60,208,831✔
264
  }
60,208,831✔
265
};
266

267
inline DNSName operator+(const DNSName& lhs, const DNSName& rhs)
268
{
9,151,978✔
269
  DNSName ret=lhs;
9,151,978✔
270
  ret += rhs;
9,151,978✔
271
  return ret;
9,151,978✔
272
}
9,151,978✔
273

274
extern const DNSName g_rootdnsname;          // .
275
extern const DNSName g_wildcarddnsname;      // *
276

277
extern const DNSName g_coodnsname;           // coo
278
extern const DNSName g_groupdnsname;         // group
279
extern const DNSName g_versiondnsname;       // version
280
extern const DNSName g_zonesdnsname;         // zones
281

282
extern const DNSName g_gsstsigdnsname;       // gss-tsig
283
extern const DNSName g_hmacmd5dnsname;       // hmac-md5
284
extern const DNSName g_hmacmd5dnsname_long;  // hmac-md5.sig-alg.reg.int
285
extern const DNSName g_hmacsha1dnsname;      // hmac-sha1
286
extern const DNSName g_hmacsha224dnsname;    // hmac-sha224
287
extern const DNSName g_hmacsha256dnsname;    // hmac-sha256
288
extern const DNSName g_hmacsha384dnsname;    // hmac-sha384
289
extern const DNSName g_hmacsha512dnsname;    // hmac-sha512
290

291
#if defined(PDNS_AUTH) // [
292
// ZoneName: this is equivalent to DNSName, but intended to only store zone
293
// names. In addition to the name, an optional variant is allowed. The
294
// variant is never part of a DNS packet; it can only be used by backends to
295
// perform specific extra processing.
296
// Variant names are limited to [a-z0-9_-].
297
// Conversions between DNSName and ZoneName are allowed, but must be explicit;
298
// conversions to DNSName lose the variant part.
299
class ZoneName
300
{
301
public:
302
  ZoneName() = default; //!< Constructs an *empty* ZoneName, NOT the root!
3,992,300✔
303
  // Work around assertion in some boost versions that do not like self-assignment of boost::container::string
304
  ZoneName& operator=(const ZoneName& rhs)
305
  {
1,088,054✔
306
    if (this != &rhs) {
1,088,054✔
307
      d_name = rhs.d_name;
1,087,986✔
308
      d_variant = rhs.d_variant;
1,087,986✔
309
    }
1,087,986✔
310
    return *this;
1,088,054✔
311
  }
1,088,054✔
312
  ZoneName& operator=(ZoneName&& rhs) noexcept
313
  {
1,134,402✔
314
    if (this != &rhs) {
1,134,402✔
315
      d_name = std::move(rhs.d_name);
1,134,396✔
316
      d_variant = std::move(rhs.d_variant);
1,134,396✔
317
    }
1,134,396✔
318
    return *this;
1,134,402✔
319
  }
1,134,402✔
320
  ZoneName(const ZoneName& a) = default;
1,929,120✔
321
  ZoneName(ZoneName&& a) = default;
2,087,829✔
322

323
  explicit ZoneName(std::string_view name);
324
  explicit ZoneName(std::string_view name, std::string_view variant) : d_name(name), d_variant(variant) {}
325
  explicit ZoneName(const DNSName& name, std::string_view variant = ""sv) : d_name(name), d_variant(variant) {}
1,686,943✔
326
  explicit ZoneName(std::string_view name, std::string_view::size_type sep);
327

328
  bool isPartOf(const ZoneName& rhs) const { return d_name.isPartOf(rhs.d_name); }
3✔
329
  bool isPartOf(const DNSName& rhs) const { return d_name.isPartOf(rhs); }
1,288✔
330
  bool operator==(const ZoneName& rhs) const { return d_name == rhs.d_name && d_variant == rhs.d_variant; }
1,147,805✔
331
  bool operator!=(const ZoneName& rhs) const { return !operator==(rhs); }
13,652✔
332

333
  std::string toString(const std::string& separator=".", const bool trailing=true) const;
334
  void toString(std::string& output, const std::string& separator=".", const bool trailing=true) const { output = toString(separator, trailing); }
335
  std::string toLogString() const;
336
  std::string toStringNoDot() const;
337
  std::string toStringRootDot() const;
338

339
  bool chopOff() { return d_name.chopOff(); }
935,037✔
340
  ZoneName makeLowerCase() const
341
  {
270,227✔
342
    ZoneName ret(*this);
270,227✔
343
    ret.d_name.makeUsLowerCase();
270,227✔
344
    return ret;
270,227✔
345
  }
270,227✔
346
  void makeUsLowerCase() { d_name.makeUsLowerCase(); }
551✔
347
  bool empty() const { return d_name.empty(); }
3,796,452✔
348
  void clear() { d_name.clear(); d_variant.clear(); }
18,960✔
349
  void trimToLabels(unsigned int trim) { d_name.trimToLabels(trim); }
910,318✔
350
  size_t hash(size_t init=0) const;
351

352
  bool operator<(const ZoneName& rhs)  const;
353

354
  int canonCompare_three_way(const ZoneName& rhs) const;
355
  inline bool canonCompare(const ZoneName& rhs) const { return canonCompare_three_way(rhs) < 0; }
46✔
356

357
  // Conversion from ZoneName to DNSName
358
  explicit operator const DNSName&() const { return d_name; }
23,152,894✔
359
  explicit operator DNSName&() { return d_name; }
4,771,417✔
360

361
  bool hasVariant() const { return !d_variant.empty(); }
104,307✔
362
  std::string getVariant() const { return d_variant; }
12,408✔
363
  void setVariant(std::string_view);
364

365
  // Search for a variant separator: mandatory (when variants are used) trailing
366
  // dot followed by another dot and the variant name, and return the length of
367
  // the zone name without its variant part, or npos if there is no variant
368
  // present.
369
  static std::string_view::size_type findVariantSeparator(std::string_view name);
370

371
private:
372
  DNSName d_name;
373
  std::string d_variant{};
374
};
375

376
size_t hash_value(ZoneName const& zone);
377

378
std::ostream & operator<<(std::ostream &ostr, const ZoneName& zone);
379
namespace std {
380
    template <>
381
    struct hash<ZoneName> {
382
        size_t operator () (const ZoneName& dn) const { return dn.hash(0); }
95,974✔
383
    };
384
}
385

386
struct CanonZoneNameCompare
387
{
388
  bool operator()(const ZoneName& a, const ZoneName& b) const
389
  {
46✔
390
    return a.canonCompare(b);
46✔
391
  }
46✔
392
};
393
#else // ] [
394
using ZoneName = DNSName;
395
using CanonZoneNameCompare = CanonDNSNameCompare;
396
#endif // ]
397

398
extern const ZoneName g_rootzonename;
399

400
template<typename T>
401
struct SuffixMatchTree
402
{
403
  SuffixMatchTree(std::string name = "", bool endNode_ = false) :
404
    d_name(std::move(name)), endNode(endNode_)
7,642✔
405
  {}
11,540✔
406

407
  SuffixMatchTree(const SuffixMatchTree& rhs): d_name(rhs.d_name), children(rhs.children), endNode(rhs.endNode)
3,688✔
408
  {
4,311✔
409
    if (endNode) {
4,311✔
410
      d_value = rhs.d_value;
1,494✔
411
    }
1,494✔
412
  }
4,311✔
413
  SuffixMatchTree & operator=(const SuffixMatchTree &rhs)
414
  {
627✔
415
    d_name = rhs.d_name;
627✔
416
    children = rhs.children;
627✔
417
    endNode = rhs.endNode;
627✔
418
    if (endNode) {
627!
419
      d_value = rhs.d_value;
420
    }
421
    return *this;
627✔
422
  }
627✔
423
  bool operator<(const SuffixMatchTree& rhs) const
424
  {
15,474✔
425
    return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0;
15,474✔
426
  }
15,474✔
427

428
  std::string d_name;
429
  mutable std::set<SuffixMatchTree, std::less<>> children;
430
  mutable bool endNode;
431
  mutable T d_value{};
432

433
  /* this structure is used to do a lookup without allocating and
434
     copying a string, using C++14's heterogeneous lookups in ordered
435
     containers */
436
  struct LightKey
437
  {
438
    std::string_view d_name;
439
    bool operator<(const SuffixMatchTree& smt) const
440
    {
124,045✔
441
      auto compareUpTo = std::min(this->d_name.size(), smt.d_name.size());
124,045✔
442
      auto ret = strncasecmp(this->d_name.data(), smt.d_name.data(), compareUpTo);
124,045✔
443
      if (ret != 0) {
124,045✔
444
        return ret < 0;
8,159✔
445
      }
8,159✔
446
      if (this->d_name.size() == smt.d_name.size()) {
115,886!
447
        return ret < 0;
115,722✔
448
      }
115,722✔
449
      return this->d_name.size() < smt.d_name.size();
164✔
450
    }
115,886✔
451
  };
452

453
  bool operator<(const LightKey& lk) const
454
  {
141,517✔
455
    auto compareUpTo = std::min(this->d_name.size(), lk.d_name.size());
141,517✔
456
    auto ret = strncasecmp(this->d_name.data(), lk.d_name.data(), compareUpTo);
141,517✔
457
    if (ret != 0) {
141,517✔
458
      return ret < 0;
25,139✔
459
    }
25,139✔
460
    if (this->d_name.size() == lk.d_name.size()) {
116,380!
461
      return ret < 0;
115,718✔
462
    }
115,718✔
463
    return this->d_name.size() < lk.d_name.size();
2,147,484,236✔
464
  }
116,378✔
465

466
  template<typename V>
467
  void visit(const V& v) const {
2,059✔
468
    for(const auto& c : children) {
2,059✔
469
      c.visit(v);
1,232✔
470
    }
1,232✔
471

472
    if (endNode) {
2,059✔
473
      v(*this);
1,125✔
474
    }
1,125✔
475
  }
2,059✔
476

477
  void add(const DNSName& name, T&& t)
478
  {
1,311✔
479
    auto labels = name.getRawLabels();
1,311✔
480
    add(labels, std::move(t));
1,311✔
481
  }
1,311✔
482

483
  void add(std::vector<std::string>& labels, T&& value) const
484
  {
4,947✔
485
    if (labels.empty()) { // this allows insertion of the root
4,947✔
486
      endNode = true;
13✔
487
      d_value = std::move(value);
13✔
488
    }
13✔
489
    else if(labels.size()==1) {
4,934✔
490
      auto res = children.emplace(*labels.begin(), true);
1,307✔
491
      if (!res.second) {
1,307✔
492
        // we might already have had the node as an
493
        // intermediary one, but it's now an end node
494
        if (!res.first->endNode) {
33!
495
          res.first->endNode = true;
33✔
496
        }
33✔
497
      }
33✔
498
      res.first->d_value = std::move(value);
1,307✔
499
    }
1,307✔
500
    else {
3,627✔
501
      auto res = children.emplace(*labels.rbegin(), false);
3,627✔
502
      labels.pop_back();
3,627✔
503
      res.first->add(labels, std::move(value));
3,627✔
504
    }
3,627✔
505
  }
4,947✔
506

507
  void remove(const DNSName &name, bool subtree=false) const
508
  {
1,203✔
509
    auto labels = name.getRawLabels();
1,203✔
510
    remove(labels, subtree);
1,203✔
511
  }
1,203✔
512

513
  /* Removes the node at `labels`, also make sure that no empty
514
   * children will be left behind in memory
515
   */
516
  void remove(std::vector<std::string>& labels, bool subtree = false) const
517
  {
2,796✔
518
    if (labels.empty()) { // this allows removal of the root
2,796✔
519
      endNode = false;
235✔
520
      if (subtree) {
235!
521
        children.clear();
229✔
522
      }
229✔
523
      return;
235✔
524
    }
235✔
525

526
    SuffixMatchTree smt(*labels.rbegin());
2,561✔
527
    auto child = children.find(smt);
2,561✔
528
    if (child == children.end()) {
2,561!
529
      // No subnode found, we're done
530
      return;
362✔
531
    }
362✔
532

533
    // We have found a child
534
    labels.pop_back();
2,199✔
535
    if (labels.empty()) {
2,199✔
536
      // The child is no longer an endnode
537
      child->endNode = false;
606✔
538

539
      if (subtree) {
606!
540
        child->children.clear();
10✔
541
      }
10✔
542

543
      // If the child has no further children, just remove it from the set.
544
      if (child->children.empty()) {
606!
545
        children.erase(child);
583✔
546
      }
583✔
547
      return;
606✔
548
    }
606✔
549

550
    // We are not at the end, let the child figure out what to do
551
    child->remove(labels);
1,593✔
552
  }
1,593✔
553

554
  T* lookup(const DNSName& name) const
555
  {
110,198✔
556
    auto bestNode = getBestNode(name);
110,198✔
557
    if (bestNode) {
110,198✔
558
      return &bestNode->d_value;
51,755✔
559
    }
51,755✔
560
    return nullptr;
58,443✔
561
  }
110,198✔
562

563
  std::optional<DNSName> getBestMatch(const DNSName& name) const
564
  {
15✔
565
    if (children.empty()) { // speed up empty set
15!
566
      return endNode ? std::optional<DNSName>(g_rootdnsname) : std::nullopt;
×
567
    }
×
568

569
    auto visitor = name.getRawLabelsVisitor();
15✔
570
    return getBestMatch(visitor);
15✔
571
  }
15✔
572

573
  // Returns all end-nodes, fully qualified (not as separate labels)
574
  std::vector<DNSName> getNodes() const {
16✔
575
    std::vector<DNSName> ret;
16✔
576
    if (endNode) {
16✔
577
      ret.push_back(DNSName(d_name));
6✔
578
    }
6✔
579
    for (const auto& child : children) {
16✔
580
      auto nodes = child.getNodes();
12✔
581
      ret.reserve(ret.size() + nodes.size());
12✔
582
      for (const auto &node: nodes) {
12✔
583
        ret.push_back(node + DNSName(d_name));
6✔
584
      }
6✔
585
    }
12✔
586
    return ret;
16✔
587
  }
16✔
588

589
private:
590
  const SuffixMatchTree* getBestNode(const DNSName& name)  const
591
  {
110,198✔
592
    if (children.empty()) { // speed up empty set
110,198✔
593
      if (endNode) {
50,405!
594
        return this;
10✔
595
      }
10✔
596
      return nullptr;
50,395✔
597
    }
50,405✔
598

599
    auto visitor = name.getRawLabelsVisitor();
59,793✔
600
    return getBestNode(visitor);
59,793✔
601
  }
110,198✔
602

603
  const SuffixMatchTree* getBestNode(DNSName::RawLabelsVisitor& visitor) const
604
  {
175,474✔
605
    if (visitor.empty()) { // optimization
175,474✔
606
      if (endNode) {
44,208✔
607
        return this;
44,116✔
608
      }
44,116✔
609
      return nullptr;
92✔
610
    }
44,208✔
611

612
    const LightKey lk{visitor.back()};
131,266✔
613
    auto child = children.find(lk);
131,266✔
614
    if (child == children.end()) {
131,266✔
615
      if (endNode) {
15,581✔
616
        return this;
7,624✔
617
      }
7,624✔
618
      return nullptr;
7,957✔
619
    }
15,581✔
620
    visitor.pop_back();
115,685✔
621
    auto result = child->getBestNode(visitor);
115,685✔
622
    if (result) {
115,685✔
623
      return result;
99,608✔
624
    }
99,608✔
625
    return endNode ? this : nullptr;
16,077!
626
  }
115,685✔
627

628
  std::optional<DNSName> getBestMatch(DNSName::RawLabelsVisitor& visitor) const
629
  {
51✔
630
    if (visitor.empty()) { // optimization
51✔
631
      if (endNode) {
3!
632
        return std::optional<DNSName>(d_name);
3✔
633
      }
3✔
634
      return std::nullopt;
×
635
    }
3✔
636

637
    const LightKey lk{visitor.back()};
48✔
638
    auto child = children.find(lk);
48✔
639
    if (child == children.end()) {
48✔
640
      if (endNode) {
12✔
641
        return std::optional<DNSName>(d_name);
6✔
642
      }
6✔
643
      return std::nullopt;
6✔
644
    }
12✔
645
    visitor.pop_back();
36✔
646
    auto result = child->getBestMatch(visitor);
36✔
647
    if (result) {
36✔
648
      if (!d_name.empty()) {
24✔
649
        result->appendRawLabel(d_name);
18✔
650
      }
18✔
651
      return result;
24✔
652
    }
24✔
653
    return endNode ? std::optional<DNSName>(d_name) : std::nullopt;
12!
654
  }
36✔
655
};
656

657
/* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode,
658
   anything part of that domain will return 'true' in check */
659
struct SuffixMatchNode
660
{
661
  public:
662
    SuffixMatchNode() = default;
2,804✔
663
    SuffixMatchTree<bool> d_tree;
664

665
    void add(const DNSName& dnsname)
666
    {
522✔
667
      d_tree.add(dnsname, true);
522✔
668
      d_nodes.insert(dnsname);
522✔
669
    }
522✔
670

671
    void add(const std::string& name)
672
    {
17✔
673
      add(DNSName(name));
17✔
674
    }
17✔
675

676
    void add(std::vector<std::string> labels)
677
    {
6✔
678
      d_tree.add(labels, true);
6✔
679
      DNSName tmp;
6✔
680
      while (!labels.empty()) {
12✔
681
        tmp.appendRawLabel(labels.back());
6✔
682
        labels.pop_back(); // This is safe because we have a copy of labels
6✔
683
      }
6✔
684
      d_nodes.insert(tmp);
6✔
685
    }
6✔
686

687
    void remove(const DNSName& name)
688
    {
6✔
689
      d_tree.remove(name);
6✔
690
      d_nodes.erase(name);
6✔
691
    }
6✔
692

693
    void remove(std::vector<std::string> labels)
694
    {
×
695
      d_tree.remove(labels);
×
696
      DNSName tmp;
×
697
      while (!labels.empty()) {
×
698
        tmp.appendRawLabel(labels.back());
×
699
        labels.pop_back(); // This is safe because we have a copy of labels
×
700
      }
×
701
      d_nodes.erase(tmp);
×
702
    }
×
703

704
    bool check(const DNSName& dnsname) const
705
    {
44,678✔
706
      return d_tree.lookup(dnsname) != nullptr;
44,678✔
707
    }
44,678✔
708

709
    std::optional<DNSName> getBestMatch(const DNSName& name) const
710
    {
15✔
711
      return d_tree.getBestMatch(name);
15✔
712
    }
15✔
713

714
    std::string toString() const
715
    {
537✔
716
      std::string ret;
537✔
717
      bool first = true;
537✔
718
      for (const auto& n : d_nodes) {
537✔
719
        if (!first) {
537!
720
          ret += ", ";
×
721
        }
×
722
        first = false;
537✔
723
        ret += n.toString();
537✔
724
      }
537✔
725
      return ret;
537✔
726
    }
537✔
727

728
  private:
729
    mutable std::set<DNSName> d_nodes; // Only used for string generation
730
};
731

732
std::ostream & operator<<(std::ostream &os, const DNSName& d);
733
namespace std {
734
    template <>
735
    struct hash<DNSName> {
736
        size_t operator () (const DNSName& dn) const { return dn.hash(0); }
9,579,382✔
737
    };
738
}
739

740
DNSName::string_t segmentDNSNameRaw(const char* input, size_t inputlen); // from ragel
741

742
bool DNSName::operator==(const DNSName& rhs) const
743
{
62,889,948✔
744
  if (rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size()) {
62,889,961✔
745
    return false;
34,824,017✔
746
  }
34,824,017✔
747

748
  const auto* us = d_storage.cbegin();
28,065,931✔
749
  const auto* p = rhs.d_storage.cbegin();
28,065,931✔
750
  for (; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) {
389,966,085✔
751
    if (dns_tolower(*p) != dns_tolower(*us)) {
365,923,544✔
752
      return false;
4,023,390✔
753
    }
4,023,390✔
754
  }
365,923,544✔
755
  return true;
24,042,541✔
756
}
28,065,931✔
757

758
struct DNSNameSet: public std::unordered_set<DNSName> {
759
    std::string toString() const {
×
760
        std::ostringstream oss;
×
761
        std::copy(begin(), end(), std::ostream_iterator<DNSName>(oss, "\n"));
×
762
        return oss.str();
×
763
    }
×
764
};
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc