12 #ifndef __NET_RADIXTREE_H__
13 #define __NET_RADIXTREE_H__
50 return std::toupper(lhs->myPrefix[0]) ==
51 std::toupper(rhs->myPrefix[0]);
57 Node() : myPrefix(), myValue(), myChildren(), myAllowsPartial(false) {}
63 myAllowsPartial(allows_partial)
68 bool allows_partial =
false)
72 myAllowsPartial(allows_partial)
80 return *myValue.get();
92 bool allow_partial =
false)
96 auto it = findPartialPrefixChild(key);
97 if (it == myChildren.end())
101 auto child = UTmakeIntrusive<Node>(key,
data, allow_partial);
102 myChildren.insert(child);
109 const exint prefix_length = getPrefixLength(
110 key, child->myPrefix);
113 if (key.
length() == child->myPrefix.length() &&
114 key.
length() == prefix_length)
116 if (child->hasValue())
119 child->myValue = UTmakeUnique<Type>(
data);
120 child->myAllowsPartial = allow_partial;
125 else if (prefix_length == child->myPrefix.length())
128 child->insert(suffix, data, allow_partial);
133 else if (prefix_length == key.
length())
138 auto new_child = UTmakeIntrusive<Node>(
139 key,
data, allow_partial);
142 myChildren.erase(child);
144 child->myPrefix = suffix;
146 new_child->myChildren.insert(child);
149 myChildren.insert(new_child);
159 child->myPrefix.begin(), prefix_length);
167 auto parent = UTmakeIntrusive<Node>(item_prefix);
170 myChildren.insert(parent);
173 child->myPrefix = item_suffix;
175 parent->myChildren.insert(child);
179 auto new_child = UTmakeIntrusive<Node>(
180 suffix,
data, allow_partial);
181 parent->myChildren.insert(new_child);
191 auto it = findPartialPrefixChild(prefix);
192 if (it == myChildren.end() || !prefix.
startsWith((*it)->myPrefix))
202 ?
static_cast<const char *
>(myPrefix) :
"<empty>");
210 for (
auto &&child : myChildren)
211 child->debug(wbuf, indent + 1);
221 for (
auto k_it = key.
begin(), np_it = node_prefix.
begin();
222 k_it != key.
end() && np_it != node_prefix.
end();
223 ++
length, ++k_it, ++np_it)
237 return myChildren.end();
239 char item = prefix[0];
240 for (
auto it = myChildren.begin(); it != myChildren.end(); it++)
242 if ((*it)->myPrefix[0] == item)
245 return myChildren.end();
252 bool myAllowsPartial;
258 bool allow_partial =
false)
261 myRoot = UTmakeIntrusive<Node>();
262 myRoot->insert(name, data, allow_partial);
268 if (myRoot ==
nullptr)
271 if (myRoot->prefix() == prefix)
275 NodeT last_partial =
nullptr;
279 while (offset < wbuf.
length() && child !=
nullptr)
283 child = child->findChild(view);
287 offset += child->prefix().
length();
290 if (child->allowsPartial())
291 last_partial = child;
296 else if (last_partial !=
nullptr)
313 if (node ==
nullptr || !node->hasValue())
323 return node !=
nullptr && node->hasValue();
332 myRoot->debug(wbuf, 0);
344 #endif // __NET_RADIXTREE_H__
SYS_NO_DISCARD_RESULT bool startsWith(const char *prefix, bool case_sensitive=true, exint len=-1) const
Returns true if our string starts with the specified prefix.
SYS_FORCE_INLINE const_iterator begin() const
SYS_FORCE_INLINE exint length() const
SYS_NO_DISCARD_RESULT bool contains(const UT_StringHolder &prefix) const
Check if the tree contains the provided string.
SYS_FORCE_INLINE bool allowsPartial() const
A simple radix tree implementation.
UT_UniquePtr< Type > ValueT
SYS_FORCE_INLINE const UT_StringHolder & prefix() const
void insert(const UT_StringHolder &name, const T &data, bool allow_partial=false)
Insert a node.
SYS_FORCE_INLINE bool isLeaf() const
void debug(UT_WorkBuffer &wbuf, unsigned indent=0) const
GLuint const GLchar * name
A reference counter base class for use with UT_IntrusivePtr.
NodeT find(const UT_StringHolder &prefix) const
Find the node based on the provided prefix.
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Node(const UT_StringHolder &prefix, const T &data, bool allows_partial=false)
SYS_FORCE_INLINE const_iterator end() const
A utility class to do read-only operations on a subset of an existing string.
size_t appendFormat(const char *fmt, const Args &...args)
bool operator()(const NodeT &lhs, const NodeT &rhs) const
SYS_NO_DISCARD_RESULT SYS_FORCE_INLINE exint length() const
Returns the length of the string in bytes.
hboost::optional< T > UT_Optional
SYS_FORCE_INLINE const char * end() const
SYS_FORCE_INLINE const char * begin() const
Iterator compatibility.
#define SYS_NO_DISCARD_RESULT
std::enable_if< !std::is_array< T >::value, UT_UniquePtr< T >>::type UTmakeUnique(REST &&...args)
SYS_FORCE_INLINE bool hasValue() const
SYS_FORCE_INLINE UT_Optional< Type & > value() const
GLuint GLsizei GLsizei * length
UT_Set< NodeT, hboost::hash< NodeT >, NodeCompare > ChildrenT
UT_IntrusivePtr< Node > NodeT
NodeT findChild(const UT_StringView prefix)
SYS_FORCE_INLINE void append(char character)
void clear()
Clear out the tree.
SYS_FORCE_INLINE void clear()
void debug(UT_WorkBuffer &wbuf) const
Write out the tree into the work buffer. This is pretty printed.
SYS_NO_DISCARD_RESULT NodeT match(const UT_StringHolder &prefix) const
Node(const UT_StringHolder &prefix, bool allows_partial=false)
void insert(const UT_StringHolder &key, const T &data, bool allow_partial=false)