HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NET_RadixTree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: NET_RadixTree.h
7  *
8  * COMMENTS:
9  *
10  */
11 
12 #ifndef __NET_RADIXTREE_H__
13 #define __NET_RADIXTREE_H__
14 
15 #include "NET_API.h"
16 
17 #include <UT/UT_Assert.h>
18 #include <UT/UT_Debug.h>
19 #include <UT/UT_Optional.h>
20 #include <UT/UT_Set.h>
21 #include <UT/UT_SharedPtr.h>
22 #include <UT/UT_StringHolder.h>
23 #include <UT/UT_UniquePtr.h>
24 #include <UT/UT_WorkBuffer.h>
25 #include <UT/UT_IntrusivePtr.h>
26 
27 #include <SYS/SYS_Compiler.h>
28 
29 #include <cctype>
30 
31 /// A simple radix tree implementation
32 template <typename T>
34 {
35 public:
36  class Node;
37 
39 
40  class Node : public UT_IntrusiveRefCounter<Node>
41  {
42  public:
43  using Type = T;
45 
46  struct NodeCompare
47  {
48  bool operator()(const NodeT &lhs, const NodeT &rhs) const
49  {
50  return std::toupper(lhs->myPrefix[0]) ==
51  std::toupper(rhs->myPrefix[0]);
52  }
53  };
54 
56 
57  Node() : myPrefix(), myValue(), myChildren(), myAllowsPartial(false) {}
58 
59  Node(const UT_StringHolder &prefix, bool allows_partial = false)
60  : myPrefix(prefix),
61  myValue(),
62  myChildren(),
63  myAllowsPartial(allows_partial)
64  {
65  }
67  const T &data,
68  bool allows_partial = false)
69  : myPrefix(prefix),
70  myValue(UTmakeUnique<T>(data)),
71  myChildren(),
72  myAllowsPartial(allows_partial)
73  {
74  }
75 
77  {
78  if (!myValue)
79  return hboost::none;
80  return *myValue.get();
81  }
82  SYS_FORCE_INLINE bool hasValue() const { return myValue != nullptr; }
84  {
85  return myPrefix;
86  }
87  SYS_FORCE_INLINE bool isLeaf() const { return myChildren.size() == 0; }
88  SYS_FORCE_INLINE bool allowsPartial() const { return myAllowsPartial; }
89 
90  void insert(const UT_StringHolder &key,
91  const T &data,
92  bool allow_partial = false)
93  {
94  UT_ASSERT(key.length() > 0);
95 
96  auto it = findPartialPrefixChild(key);
97  if (it == myChildren.end())
98  {
99  // No child partially matched the prefix so we will create
100  // one
101  auto child = UTmakeIntrusive<Node>(key, data, allow_partial);
102  myChildren.insert(child);
103  }
104  else
105  {
106  auto child = *it;
107  UT_ASSERT(child);
108 
109  const exint prefix_length = getPrefixLength(
110  key, child->myPrefix);
111 
112  // Check if this is a duplicate key
113  if (key.length() == child->myPrefix.length() &&
114  key.length() == prefix_length)
115  {
116  if (child->hasValue())
117  return;
118 
119  child->myValue = UTmakeUnique<Type>(data);
120  child->myAllowsPartial = allow_partial;
121  return;
122  }
123  // The childs key is the prefix of the insert item
124  // abc -> abc - d [ after inserting "abcd" ]
125  else if (prefix_length == child->myPrefix.length())
126  {
127  UT_StringHolder suffix(key.begin() + prefix_length);
128  child->insert(suffix, data, allow_partial);
129  return;
130  }
131  // The insert item is the prefix of the childs prefix
132  // abc -> ab - c [after inserting "abc"]
133  else if (prefix_length == key.length())
134  {
135  UT_StringHolder suffix(child->myPrefix.begin() +
136  prefix_length);
137 
138  auto new_child = UTmakeIntrusive<Node>(
139  key, data, allow_partial);
140 
141  // Remove the current child
142  myChildren.erase(child);
143  // Update the child prefix
144  child->myPrefix = suffix;
145  // Add old child to the new child
146  new_child->myChildren.insert(child);
147 
148  // Attach the new child to the current children
149  myChildren.insert(new_child);
150  }
151  // Inserting item and childs key have the same common prefix
152  else
153  {
154  // We need to split the current child and the suffix
155  // into
156  // two children whos parent is the prefix of the two
157  // children
158  UT_StringHolder item_prefix(
159  child->myPrefix.begin(), prefix_length);
160  UT_StringHolder item_suffix(child->myPrefix.begin() +
161  prefix_length);
162 
163  // remove the existing child as this will be move to the
164  // parent of the two children.
165  UT_VERIFY(myChildren.erase(child) == 1);
166 
167  auto parent = UTmakeIntrusive<Node>(item_prefix);
168  // Add the prefix of the old child and the new key into
169  // this children set.
170  myChildren.insert(parent);
171 
172  // update the new prefix
173  child->myPrefix = item_suffix;
174  // Add the suffix of the old key into the new branch
175  parent->myChildren.insert(child);
176 
177  // Add the suffix of the key into the new split branch
178  UT_StringHolder suffix(key.begin() + prefix_length);
179  auto new_child = UTmakeIntrusive<Node>(
180  suffix, data, allow_partial);
181  parent->myChildren.insert(new_child);
182  }
183  }
184  }
185 
186  // Find a child based on the prefix
188  {
189  UT_ASSERT(prefix.length() > 0);
190 
191  auto it = findPartialPrefixChild(prefix);
192  if (it == myChildren.end() || !prefix.startsWith((*it)->myPrefix))
193  return nullptr;
194 
195  return *it;
196  }
197 
198  void debug(UT_WorkBuffer &wbuf, unsigned indent = 0)
199  {
200  wbuf.append(indent, ' ');
201  wbuf.append(myPrefix.length() > 0
202  ? static_cast<const char *>(myPrefix) : "<empty>");
203  wbuf.append(' ');
204  if (hasValue())
205  wbuf.appendFormat("{}", *myValue);
206  else
207  wbuf.append("<None>");
208  wbuf.append('\n');
209 
210  for (auto &&child : myChildren)
211  child->debug(wbuf, indent + 1);
212  }
213 
214  private:
215  // Find the max length that both key and node prefix share
216  exint getPrefixLength(const UT_StringHolder &key,
217  const UT_StringHolder &node_prefix)
218  {
219  exint length = 0;
220 
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)
224  {
225  if (*k_it != *np_it)
226  break;
227  }
228 
229  return length;
230  }
231 
232  // Find a child that is a partial match to the prefix.
233  typename ChildrenT::iterator findPartialPrefixChild(
234  const UT_StringHolder &prefix)
235  {
236  if (prefix.length() <= 0)
237  return myChildren.end();
238 
239  char item = prefix[0];
240  for (auto it = myChildren.begin(); it != myChildren.end(); it++)
241  {
242  if ((*it)->myPrefix[0] == item)
243  return it;
244  }
245  return myChildren.end();
246  }
247 
248  UT_StringHolder myPrefix;
249  ValueT myValue;
250  ChildrenT myChildren;
251  // If the node allows for partial matches
252  bool myAllowsPartial;
253  };
254 
255  /// Insert a node
257  const T &data,
258  bool allow_partial = false)
259  {
260  if (!myRoot)
261  myRoot = UTmakeIntrusive<Node>();
262  myRoot->insert(name, data, allow_partial);
263  }
264 
265  /// Find the node based on the provided prefix.
266  NodeT find(const UT_StringHolder &prefix) const
267  {
268  if (myRoot == nullptr)
269  return nullptr;
270 
271  if (myRoot->prefix() == prefix)
272  return myRoot;
273 
274  auto child = myRoot;
275  NodeT last_partial = nullptr;
276  UT_WorkBuffer wbuf(prefix);
277 
278  exint offset = 0;
279  while (offset < wbuf.length() && child != nullptr)
280  {
281  UT_ASSERT(wbuf.begin() + offset <= wbuf.end());
282  UT_StringView view(wbuf.begin() + offset, wbuf.end());
283  child = child->findChild(view);
284 
285  if (child)
286  {
287  offset += child->prefix().length();
288  // If this child allows for partial matches then update the
289  // last partial node we found.
290  if (child->allowsPartial())
291  last_partial = child;
292  }
293  // If we didnt find a child that matches check if our traversal came
294  // across a node that allows for partial matches. If we found one
295  // then return this node instead of reporting nothing found.
296  else if (last_partial != nullptr)
297  return last_partial;
298  }
299 
300  return child;
301  }
302 
303  /// Find the node that fully matches the prefix or partially matches based
304  /// on the tree node being setup for it. Basically this method only returns
305  /// a viable node if it "fully" matches the prefix. Use find() if you want
306  /// find any node that will either partially match or fully match the
307  /// prefix.
309  {
310  NodeT node = find(prefix);
311  // Check that the node we found actually has a value (is an actuall
312  // value in our tree).
313  if (node == nullptr || !node->hasValue())
314  return nullptr;
315  return node;
316  }
317 
318  /// Check if the tree contains the provided string
320  {
321  NodeT node = find(prefix);
322 
323  return node != nullptr && node->hasValue();
324  }
325 
326  /// Write out the tree into the work buffer. This is pretty printed.
327  void debug(UT_WorkBuffer &wbuf)
328  {
329  wbuf.clear();
330 
331  if (myRoot)
332  myRoot->debug(wbuf, 0);
333  else
334  wbuf = "<empty>";
335  }
336 
337  /// Clear out the tree
338  void clear() { myRoot.reset(); }
339 
340 private:
341  NodeT myRoot;
342 };
343 
344 #endif // __NET_RADIXTREE_H__
345 
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
Definition: NET_RadixTree.h:88
A simple radix tree implementation.
Definition: NET_RadixTree.h:33
UT_UniquePtr< Type > ValueT
Definition: NET_RadixTree.h:44
SYS_FORCE_INLINE const UT_StringHolder & prefix() const
Definition: NET_RadixTree.h:83
void debug(UT_WorkBuffer &wbuf)
Write out the tree into the work buffer. This is pretty printed.
void insert(const UT_StringHolder &name, const T &data, bool allow_partial=false)
Insert a node.
int64 exint
Definition: SYS_Types.h:125
SYS_FORCE_INLINE bool isLeaf() const
Definition: NET_RadixTree.h:87
GLuint const GLchar * name
Definition: glcorearb.h:785
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.
Definition: UT_UniquePtr.h:33
Node(const UT_StringHolder &prefix, const T &data, bool allows_partial=false)
Definition: NET_RadixTree.h:66
SYS_FORCE_INLINE const_iterator end() const
A utility class to do read-only operations on a subset of an existing string.
Definition: UT_StringView.h:40
size_t appendFormat(const char *fmt, const Args &...args)
bool operator()(const NodeT &lhs, const NodeT &rhs) const
Definition: NET_RadixTree.h:48
SYS_NO_DISCARD_RESULT SYS_FORCE_INLINE exint length() const
Returns the length of the string in bytes.
hboost::optional< T > UT_Optional
Definition: UT_Optional.h:16
exint length() const
SYS_FORCE_INLINE const char * end() const
SYS_FORCE_INLINE const char * begin() const
Iterator compatibility.
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
#define SYS_NO_DISCARD_RESULT
Definition: SYS_Compiler.h:93
std::enable_if< !std::is_array< T >::value, UT_UniquePtr< T >>::type UTmakeUnique(REST &&...args)
Definition: UT_UniquePtr.h:46
SYS_FORCE_INLINE bool hasValue() const
Definition: NET_RadixTree.h:82
SYS_FORCE_INLINE UT_Optional< Type & > value() const
Definition: NET_RadixTree.h:76
GLboolean * data
Definition: glcorearb.h:130
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:794
UT_Set< NodeT, hboost::hash< NodeT >, NodeCompare > ChildrenT
Definition: NET_RadixTree.h:55
#define UT_VERIFY(expr)
Definition: UT_Assert.h:217
UT_IntrusivePtr< Node > NodeT
Definition: NET_RadixTree.h:38
NodeT findChild(const UT_StringView prefix)
SYS_FORCE_INLINE void append(char character)
void debug(UT_WorkBuffer &wbuf, unsigned indent=0)
void clear()
Clear out the tree.
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:171
SYS_FORCE_INLINE void clear()
GLintptr offset
Definition: glcorearb.h:664
SYS_NO_DISCARD_RESULT NodeT match(const UT_StringHolder &prefix) const
Node(const UT_StringHolder &prefix, bool allows_partial=false)
Definition: NET_RadixTree.h:59
void insert(const UT_StringHolder &key, const T &data, bool allow_partial=false)
Definition: NET_RadixTree.h:90