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)
90 bool allow_partial =
false)
94 auto it = findPartialPrefixChild(key);
95 if (it == myChildren.end())
99 auto child = UTmakeIntrusive<Node>(key,
data, allow_partial);
100 myChildren.insert(child);
107 const exint prefix_length = getPrefixLength(
108 key, child->myPrefix);
111 if (key.
length() == child->myPrefix.length() &&
112 key.
length() == prefix_length)
114 if (child->hasValue())
117 child->myValue = UTmakeUnique<Type>(
data);
118 child->myAllowsPartial = allow_partial;
123 else if (prefix_length == child->myPrefix.length())
126 child->insert(suffix, data, allow_partial);
131 else if (prefix_length == key.
length())
136 auto new_child = UTmakeIntrusive<Node>(
137 key,
data, allow_partial);
140 myChildren.erase(child);
142 child->myPrefix = suffix;
144 new_child->myChildren.insert(child);
147 myChildren.insert(new_child);
157 child->myPrefix.begin(), prefix_length);
165 auto parent = UTmakeIntrusive<Node>(item_prefix);
168 myChildren.insert(parent);
171 child->myPrefix = item_suffix;
173 parent->myChildren.insert(child);
177 auto new_child = UTmakeIntrusive<Node>(
178 suffix,
data, allow_partial);
179 parent->myChildren.insert(new_child);
189 auto it = findPartialPrefixChild(prefix);
190 if (it == myChildren.end() || !prefix.
startsWith((*it)->myPrefix))
200 ?
static_cast<const char *
>(myPrefix) :
"<empty>");
208 for (
auto &&child : myChildren)
209 child->debug(wbuf, indent + 1);
219 for (
auto k_it = key.
begin(), np_it = node_prefix.
begin();
220 k_it != key.
end() && np_it != node_prefix.
end();
221 ++
length, ++k_it, ++np_it)
235 return myChildren.end();
237 char item = prefix[0];
238 for (
auto it = myChildren.begin(); it != myChildren.end(); it++)
240 if ((*it)->myPrefix[0] == item)
243 return myChildren.end();
250 bool myAllowsPartial;
256 bool allow_partial =
false)
259 myRoot = UTmakeIntrusive<Node>();
260 myRoot->insert(name, data, allow_partial);
266 if (myRoot ==
nullptr)
269 if (myRoot->prefix() == prefix)
273 NodeT last_partial =
nullptr;
277 while (offset < wbuf.
length() && child !=
nullptr)
281 child = child->findChild(
view);
285 offset += child->prefix().length();
288 if (child->allowsPartial())
289 last_partial = child;
294 else if (last_partial !=
nullptr)
311 if (node ==
nullptr || !node->hasValue())
321 return node !=
nullptr && node->hasValue();
330 myRoot->debug(wbuf, 0);
342 #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
GLuint GLsizei GLsizei * length
void debug(UT_WorkBuffer &wbuf, unsigned indent=0) const
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.
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)
GLuint const GLchar * name
SYS_FORCE_INLINE bool hasValue() const
SYS_FORCE_INLINE Type * value() const
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)