ALib C++ Library
Library Version: 2511 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
stringtree.inl
Go to the documentation of this file.
1//==================================================================================================
2/// \file
3/// This header-file is part of module \alib_containers of the \aliblong.
4///
5/// \emoji :copyright: 2013-2025 A-Worx GmbH, Germany.
6/// Published under \ref mainpage_license "Boost Software License".
7//==================================================================================================
8ALIB_EXPORT namespace alib { namespace containers {
9
10#if ALIB_DEBUG
11 /// Statistic variable increased by \alib{containers;StringTreeNamesDynamic} with every creation
12 /// of a node. With process creation the variable is \c 0. A user may reset the variable to
13 /// inspect percentages of name overflows during certain operations. The variable is not thread
14 /// safe and used by any instance of class \b StringTree which uses node handler
15 /// \b StringTreeNamesDynamic.
16 /// @see Sibling variable \alib{containers;DBG_STATS_STRINGTREE_NAME_OVERFLOWS}
17 ALIB_DLL extern uinteger DBG_STATS_STRINGTREE_NAMES;
18
19 /// Statistic variable increased by \alib{containers;StringTreeNamesDynamic} with every creation
20 /// of a node whose name exceeds the internal string buffer size.
21 /// With process creation the variable is \c 0. A user may reset the variable to
22 /// inspect percentages of name overflows during certain operations. The variable is not thread
23 /// safe and used by any instance of class \b StringTree which uses node handler
24 /// \b StringTreeNamesDynamic.
25 /// @see Sibling variable \alib{containers;DBG_STATS_STRINGTREE_NAME_OVERFLOWS}
26 ALIB_DLL extern uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS;
27#endif
28
29/// This struct is the default type for template parameter
30/// \ref alib_ns_containers_stringtree_referencedoc "TNodeHandler" of class
31/// \alib{containers;StringTree}.
32///
33/// Besides defining the character type as given with template parameter \p{TChar}, the node name
34/// string-type is exposed with #NameStringType. The string-type depends on the template parameter
35/// \p{TLocalCapacity}:
36/// - If this is \c 0, the type evaluates to a simple string with no internal storage.
37/// - If this is greater than zero, the type evaluates to a \alib{strings;TLocalString;LocalString}
38/// of given capacity.
39///
40/// This design allows allocating a fixed-size string buffer with each node, and only if a
41/// node's name exceeds this capacity, a dynamic allocation for storing the node name is performed.
42/// As a consequence, some overhead of wasted memory will occur, as this capacity is
43/// allocated with every node, regardless of its name's length.
44/// To investigate into the percentage of overflows to evaluate a reasonable value for template
45/// parameter \p{TLocalCapacity}, simple global debug counters
46/// \alib{containers;DBG_STATS_STRINGTREE_NAMES} and \alib{containers;DBG_STATS_STRINGTREE_NAME_OVERFLOWS}
47/// can be used.
48///
49/// Method #InitializeNode is invoked after the insertion of a new element (aka "node")
50/// into the container and #FreeNode is invoked before the destruction of a node.
51/// When #InitializeNode is invoked, the custom object of template type \p{T} (of the \b StringTree)
52/// is already default constructed and the key of the node in union
53/// (field \alib{containers;detail::StringTreeBase::NodeKey::name}) is set to what was provided
54/// as a child name or path string. (In the latter case, it is set to a substring of the
55/// given path.). If template parameter \p{TLocalCapacity} is greater than 0, the
56/// method copies the key to field \e storage of the union (which is still accessible with the
57/// base string-type of union-field \e key).
58/// If \c 0 is given, the node name is replaced by a copy of the string which is dynamically
59/// allocated.
60///
61/// ## Custom Implementations ##
62/// A custom implementation has to provide all four entities that this type provides in a
63/// compatible fashion.
64///
65/// The main purpose of the node handler types is to ensure that the name strings of inserted
66/// nodes are duly allocated, copied, and freed as needed:
67/// When a new element is (or a whole path of new elements are) created, then the initial name
68/// of the nodes are taken from the string passed to the corresponding interface method of class
69/// \b StringTree (and inner types). The challenge is that this string's life-cycle might
70/// be only short term. Therefore, right after the creation of an element, the method
71/// #InitializeNode is invoked, allowing to create a safe copy of the name.<br>
72/// To free any allocated space, the method #FreeNode is invoked.
73///
74/// Besides this, custom implementations may tweak the given node on their own discretion.
75/// Especially a custom implementation may create and recycle other portions of the stored
76/// objects to establish \ref alib_contmono_intro_strictweak "weak monotonic allocation rules".
77/// A sample of such more complex behavior is found with \alib type \alib{files;FTree}.
78///
79/// \see
80/// Two other built-in implementations of this type to be used with \b StringTree instantiations
81/// are provided with this \alibmod:
82/// - \alib{containers;StringTreeNamesStatic}.
83/// - \alib{containers;StringTreeNamesAlloc}.
84/// \see
85/// Further information can be found in chapter
86/// \ref alib_ns_containers_stringtree_alloc_names "4. Node and Node Name String Allocation"
87/// of the reference documentation of class \b StringTree.
88///
89/// @tparam TChar The character type of the key strings. This type is used with any
90/// interface method of \alib{containers;StringTree} that accepts a node name
91/// or path string.<br>
92/// Defaults to type \alib{characters;character}.
93/// @tparam TLocalCapacity The capacity of the \alib{strings;TLocalString;LocalString} to place in
94/// the <b>StringTree</b>'s node. If \c 0 is given, a normal
95/// \alib{strings;TString;String} is used for the name, and the buffer is
96/// copied to an dynamically allocated array.<br>
97/// Defaults to \c 32.
98template<typename TChar= character, integer TLocalCapacity= 32>
99struct StringTreeNamesDynamic
100{
101 /// The character type that the \b StringTree uses for child name and path strings.
102 using CharacterType = TChar;
103
104 /// The string-type of a node's name.
105 using NameStringType = std::conditional_t<( TLocalCapacity > 0),
106 strings::TLocalString<TChar, TLocalCapacity>,
107 strings::TString <TChar> >;
108
109
110 /// This implementation copies the node's name to a dynamically allocated piece of heap memory.
111 /// \see
112 /// See the class description for further information.
113 /// @param node The node that was just created. Allows access to the key and
114 /// custom value data. While the parent and sibling nodes are likewise accessible,
115 /// it is strictly forbidden to modify those.
116 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
117 /// this method. Any member may be accessed, including
118 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
119 /// allocator that the tree uses for the allocation of nodes.
120 /// @tparam TTree The type of the templated instantiation of struct
121 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
122 /// (Deduced by the compiler.)
123 template<typename TTree>
124 static
125 void InitializeNode( typename TTree::Node& node, TTree& tree ) {
126 (void) tree;
127
128 // if not a local string buffer, then dynamically allocate and copy.
129 if constexpr (TLocalCapacity <= 0) {
130 CharacterType* buffer= new CharacterType[size_t(node.name.key.Length())];
131 node.name.key.CopyTo( buffer );
132 node.name.key= strings::TString<CharacterType>( buffer, node.name.key.Length() );
133 } else {
134 // create a local string which may allocate heap if name is too long
135 strings::TString<TChar> key= node.name.key; // get current pointer
136 new (&node.name.storage) NameStringType(); // placement-new to re-establish local string
137 node.name.storage.DbgDisableBufferReplacementWarning(); // Disable warnings
138 ALIB_DBG( const TChar* internalBuffer= node.name.storage.Buffer(); ) // get internal local buffer
139 node.name.storage.Append(key); // copy key to buf
140 ALIB_DBG( ++DBG_STATS_STRINGTREE_NAMES;
141 if( internalBuffer != node.name.storage.Buffer() ) // ++statistics if local buffer was too small
142 ++DBG_STATS_STRINGTREE_NAME_OVERFLOWS; )
143 } }
144
145 /// This implementation frees the dynamically allocated memory of the node's name.
146 /// \see
147 /// See the class description for further information.
148 /// @param node The node that is to be removed. Allows access to the key and
149 /// custom value data. While the parent and sibling nodes are likewise accessible,
150 /// it is strictly forbidden to modify those.
151 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
152 /// this method. Any member may be accessed, including
153 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
154 /// allocator that the tree uses for the allocation of nodes.
155 /// @tparam TTree The type of the templated instantiation of struct
156 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
157 /// (Deduced by the compiler.)
158 template<typename TTree>
159 static
160 void FreeNode( typename TTree::Node& node, TTree& tree ) {
161 (void) tree;
162 if constexpr (TLocalCapacity <= 0)
163 delete[] node.name.key.Buffer();
164 else
165 node.name.storage.~TLocalString();
166 }
167
168}; // StringTreeNamesDynamic
169
170/// Built-in implementation usable as template parameter
171/// \ref alib_ns_containers_stringtree_referencedoc "TNodeHandler" of class
172/// \alib{containers;StringTree}.
173///
174/// This type does not allocate memory and does not copy the key string of a node. Therefore, this
175/// type is very efficient to use in situations where exclusively "static" strings for child names
176/// and paths are passed to the interface methods of class \b StringTree (and inner types) which
177/// lead to the creation of new child nodes.<br>
178/// The term "static" here means that the strings given are either static character data of a
179/// compilation unit or by any other means their allocated memory and the contained data survive
180/// the life-cycle of the corresponding \b StringTree.
181///
182/// \see
183/// Two other built-in implementations of this type to be used with \b StringTree instantiations
184/// are provided with this \alibmod:
185/// - \alib{containers;StringTreeNamesDynamic}.
186/// - \alib{containers;StringTreeNamesAlloc}.
187/// \see
188/// Further information can be found in chapter
189/// \ref alib_ns_containers_stringtree_alloc_names "4. Node and Node Name String Allocation"
190/// of the reference documentation of class \b StringTree.
191///
192/// @tparam TChar The character type of the key strings. This type is used with any
193/// interface method of \alib{containers;StringTree} that accepts a node name or path
194/// string.
195template<typename TChar= character>
196struct StringTreeNamesStatic
197{
198 /// The character type that the \b StringTree uses for child name and path strings.
199 using CharacterType = TChar;
200
201 /// The string-type of a node's name.
202 using NameStringType = strings::TString<TChar>;
203
204 /// This implementation is empty.
205 ///
206 /// \see
207 /// See description of this class and the "default implementation"
208 /// \alib{containers;StringTreeNamesDynamic}.
209 ///
210 /// @param node The node that was just created. Allows access to the key and
211 /// custom value data. While the parent and sibling nodes are likewise accessible,
212 /// it is strictly forbidden to modify those.
213 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
214 /// this method. Any member may be accessed, including
215 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
216 /// allocator that the tree uses for the allocation of nodes.
217 /// @tparam TTree The type of the templated instantiation of struct
218 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
219 /// (Deduced by the compiler.)
220 template<typename TTree>
221 static
222 void InitializeNode( typename TTree::Node& node, TTree& tree ) { (void) node; (void) tree; }
223
224 /// This implementation is empty.
225 ///
226 /// \see
227 /// See description of this class and the "default implementation"
228 /// \alib{containers;StringTreeNamesDynamic}.
229 ///
230 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
231 /// this method. Any member may be accessed, including
232 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
233 /// allocator that the tree uses for the allocation of nodes.
234 /// @param node The node that is to be removed. Allows access to the key and
235 /// custom value data. While the parent and sibling nodes are likewise accessible,
236 /// it is strictly forbidden to modify those.
237 /// @tparam TTree The type of the templated instantiation of struct
238 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
239 /// (Deduced by the compiler.)
240 template<typename TTree>
241 static
242 void FreeNode( TTree::Node& node, TTree& tree ) { (void) node; (void) tree; }
243}; // StringTreeNamesStatic
244
245/// Built-in implementation usable as template parameter
246/// \ref alib_ns_containers_stringtree_referencedoc "TNodeHandler" of class
247/// \alib{containers;StringTree}.
248///
249/// This type copies the node's name into memory acquired with the monotonic allocator that the
250/// \b StringTree uses.<br>
251///
252/// \attention
253/// The use of this type is dangerous in respect to memory exhaustion. While class
254/// \b StringTree uses monotonic allocation in a
255/// \ref alib_ns_containers_stringtree_hashing "very safe way", with the use of this
256/// type, repeated removals and insertions of tree nodes, increase the memory usage.<br>
257/// Consequently, the use of this type is restricted to cases that imply a limited
258/// number of insertions.
259///
260/// \see
261/// Two other built-in implementations of this type to be used with \b StringTree instantiations
262/// are provided with this \alibmod:
263/// - \alib{containers;StringTreeNamesStatic}.
264/// - \alib{containers;StringTreeNamesDynamic}.
265/// \see
266/// Further information can be found in chapter
267/// \ref alib_ns_containers_stringtree_alloc_names "4. Node and Node Name String Allocation"
268/// of the reference documentation of class \b StringTree.
269///
270/// @tparam TChar The character type of the key strings. This type is used with any
271/// interface method of \alib{containers;StringTree} that accepts a node name or path
272/// string.
273template<typename TChar= character>
274struct StringTreeNamesAlloc
275{
276 /// The character type that the \b StringTree uses for child name and path strings.
277 using CharacterType= TChar;
278
279 /// The string-type of a node's name.
280 using NameStringType = strings::TString<TChar>;
281
282 /// This implementation copies the node's name to a piece of memory allocated in the
283 /// allocator found in field \alib{containers::detail::StringTreeBase;nodeTable}
284 /// of the given \p{tree}.
285 ///
286 /// \see
287 /// See description of this class and the "default implementation"
288 /// \alib{containers;StringTreeNamesDynamic}.
289 ///
290 /// @param node The node that was just created. Allows access to the key and
291 /// custom value data. While the parent and sibling nodes are likewise accessible,
292 /// it is strictly forbidden to modify those.
293 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
294 /// this method. Any member may be accessed, including
295 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
296 /// allocator that the tree uses for the allocation of nodes.
297 /// @tparam TTree The type of the templated instantiation of struct
298 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
299 /// (Deduced by the compiler.)
300 template<typename TTree>
301 static
302 void InitializeNode( typename TTree::Node& node, TTree& tree )
303 { node.name.storage.Allocate( tree.nodeTable.GetAllocator(), node.name.key ); }
304
305 /// This implementation does nothing.
306 ///
307 /// \see
308 /// See description of this class and the "default implementation"
309 /// \alib{containers;StringTreeNamesDynamic}.
310 ///
311 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
312 /// this method. Any member may be accessed, including
313 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
314 /// allocator that the tree uses for the allocation of nodes.
315 /// @param node The node that is to be removed. Allows access to the key and
316 /// custom value data. While the parent and sibling nodes are likewise accessible,
317 /// it is strictly forbidden to modify those.
318 /// @tparam TTree The type of the templated instantiation of struct
319 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
320 /// (Deduced by the compiler.)
321 template<typename TTree>
322 static
323 void FreeNode( typename TTree::baseNode& node, TTree& tree ) { (void) node; (void) tree; }
324};
325
326//==================================================================================================
327/// # 1. Introduction # {#alib_ns_containers_stringtree_overview}
328/// This container type implements a directed, non-circular graph (tree) with named nodes.
329///
330/// The internal node type \alib{containers;detail::StringTreeBase::Node} stores:
331/// 1. A name string, which has to be unique in respect to the names of sibling nodes. (Just like
332/// no two files in a folder may have the same name.)
333/// 2. Five pointers to related nodes:
334/// - the parent node
335/// - the previous and next sibling nodes,
336/// - the first and last child nodes,
337/// 3. A data field holding the node's custom value of template type \p{T}.
338///
339/// The way from the root node to a descendent node, usually is called "path". The class incorporates
340/// functionality to work with string representations of such paths where names of child nodes are
341/// concatenated and separated by a special separation character.
342///
343/// The search and creation of tree nodes by using aforementioned path strings, is very similar to
344/// what is well known from addressing files and folders in file systems.
345/// This class does not differentiate between 'folders' and 'files', hence between 'nodes' and
346/// 'leafs'. Every node has the same data of type \p{T} attached and may or may not have child nodes.
347/// If such differentiation - or other semantics - is wanted, this may well be modeled by custom
348/// attributes provided in template type \p{T}.
349///
350/// \I{#############################################################################################}
351/// # 2. Helper Types # {#alib_ns_containers_stringtree_inner}
352/// Two important helper types exist.
353/// All operations on tree nodes like insertion, deletion, search, and attribute access is performed
354/// using objects of the public inner type \alib{containers;StringTree::TCursor}. This is a
355/// lightweight, iterator-like "handle" containing a pointer to the originating tree object and to
356/// a represented node. The type provides various methods to travers the tree. It is templated over
357/// a boolean value which determines if a const or mutable \b StringTree is given. Shortcuts for
358/// these types are \alib{containers;StringTree::Cursor} and
359/// \alib{containers;StringTree::ConstCursor}.
360///
361/// Besides this, class \alib{containers;StringTreeIterator} allows recursive iterations with
362/// built-in or custom sort orders. Note that this class is available with inclusion of
363/// \implude{Containers.StringTreeIterator}.
364///
365/// Both types are explained in the following paragraphs.
366///
367/// \I{#############################################################################################}
368/// ## 2.1 Inner Class Cursor ## {#alib_ns_containers_stringtree_cursor}
369///
370/// The main interface into class \b %StringTree is given by public, inner type
371/// \alib{containers;StringTree::Cursor}. Method #Root returns an object of that type that
372/// initially refers to the root node of the tree.
373/// With this, child names and composite "paths" can be used to move the pointer along existing nodes
374/// of the tree or to create new child nodes or even a whole path of such child nodes at once.
375///
376/// Class \b %Cursor is very lightweight as it contains just two pointers, one to the
377/// \b %StringTree it originates from and one to the tree node currently represented.
378/// Hence, objects of this type can be copied, assigned, and passed around very efficiently.<br>
379/// The currently represented node's templated custom data can be accessed with method
380/// #TCursor::Value.
381///
382/// The methods to traverse over the nodes of the tree are:
383/// - #TCursor::GoToRoot
384/// - #TCursor::GoToParent
385/// - #TCursor::GoTo
386/// - #TCursor::GoToNextSibling
387/// - #TCursor::GoToPreviousSibling
388/// - #TCursor::GoToChild
389/// - #TCursor::GoToFirstChild
390/// - #TCursor::GoToLastChild
391///
392/// With these methods, class \b StringTree::Cursor constitutes a sort of iterator idiom
393/// idiom. For example, to traverse all entries in the root folder, the following schematic would
394/// be used:
395///
396/// myCursor= myTree.GetRoot()
397/// myCursor.GotoFirstChild()
398/// While( myCursor.IsValid() )
399/// DoSomething( myCursor.Value() )
400/// myCursor.GotoNextSibling
401///
402/// For some of these methods an alternative version exists, which returns a corresponding copy
403/// of the cursor, while leaving the original object unchanged. These methods share
404/// the same name excluding the prefix <b>GoTo</b>.
405///
406/// For the creation of new child nodes or a complete path of such, methods
407/// - #TCursor::GoToCreateChildIfNotExistent and ,
408/// - #TCursor::GoToCreatedPathIfNotExistent
409/// are provided.
410///
411/// Next, four methods that perform node deletion exist:
412/// - #TCursor::DeleteChild (two overloaded versions),
413/// - #TCursor::DeleteChildren and
414/// - #TCursor::Delete
415///
416/// The already mentioned methods:
417/// - #TCursor::GoToParent,
418/// - #TCursor::GoToFirstChild,
419/// - #TCursor::GoToLastChild,
420/// - #TCursor::GoToNextSibling and
421/// - #TCursor::GoToPreviousSibling
422///
423/// of class \b Cursor can be used to iterate from a node upward to the root node or through the
424/// list of children of a node. Each method may \e invalidate the object in the case that no
425/// corresponding parent or sibling node exists.
426/// Invalid cursor objects can be (or rather have to be!) detected using method
427/// #TCursor::IsValid.
428/// Most of the class's methods must not be invoked on an invalidated object. Doing so is undefined
429/// behavior and \ref alib_mod_assert "raises an ALib error" in debug-builds.
430/// Invalid \b %Cursor objects can reset to a valid state using methods
431/// - #TCursor::GoToRoot and
432/// - #TCursor::GoTo
433///
434/// if absolute path addressing is used.
435///
436/// Instances that have been default-constructed may only be set to a valid state by (copy-)
437/// assigning a valid instance.
438///
439/// \I{#############################################################################################}
440/// ## 2.2. Class StringTreeIterator ## {#alib_ns_containers_stringtree_iterator}
441/// Class \alib{containers;StringTreeIterator} provides a configurable and controlled
442/// way of iterating a branch of a tree. Some features of the class are:
443/// - Iterators can be initialized to start from any node of the tree
444/// Iteration ends when all (recursive) child nodes of the start node have been visited.
445/// - The iteration follows a "depth first search" approach: Before visiting a sibling node,
446/// all children of a node are visited. However, it is not differentiated whether a sibling
447/// has child nodes or not. In case all siblings with children are to be processed first,
448/// a custom sorter has to be created which prefers those nodes that have children.
449/// - The recursion depth can be limited, including to depth \c 0, which iterates only the
450/// direct child nodes of the start node.
451/// - Before entering a new depth-level during iteration, different sort orders can be set.
452/// The choices are:
453/// - No sorting (iterates in order of node insertion).
454/// - Built-in sorting by node (path) name, ascending/descending, case-sensitive or ignoring case
455/// - user-defined by path name, the number of children, or any other attribute of the node,
456/// of course including a node's custom data values.
457///
458/// Class \b StringTreeIterator is of rather heavy weight, and sorted iteration needs to allocate
459/// memory for sorting the child nodes for each depth level of a potential recursion.
460/// Therefore, it is recommended to reuse instances of the class with later, similar iterations.
461/// In addition, this explains why this class does not follow the concept of
462/// <c>std::iterator_traits</c>, which is designed to be used with lightweight iterator types.
463///
464/// \I{#############################################################################################}
465/// # 3. Node Allocation And Hashing # {#alib_ns_containers_stringtree_hashing}
466/// While each node maintains a doubly linked list of child nodes for iteration, this class stores
467/// each inserted element in a \alib{containers;HashTable} using the parent node and the
468/// element's name as a unique key.
469/// This is done to be able to search for a child with a given name in constant time.
470/// This container does not perform any other memory allocations than those that this
471/// \b HashTable does.
472///
473/// With that, the implementation of this container type is able to leave all allocation and
474/// <em>"recycling"</em> of node elements to this hash table, which is found in base class's field
475/// \alib{containers;detail::StringTreeBase::nodeTable}. As explained in the documentation of
476/// \alib{containers;HashTable}, its allocation mechanism can be made safe in respect to
477/// memory exhaustion. This is true even if a \alib{MonoAllocator} is used and a virtually
478/// unlimited number of insertions and removals of elements is performed.
479/// Such safeness depends on template parameter \p{TRecycling} which is just passed to the
480/// internal hash table's definition of nodes.
481/// \see
482/// For more information on this topic see also chapter \ref alib_contmono_intro_recycling
483/// of this \alibmod_nl Programmer's Manual.
484///
485/// \I{#############################################################################################}
486/// # 4. Node and Node Name String Allocation # {#alib_ns_containers_stringtree_alloc_names}
487///
488/// The C++ version of this class allows user-defined allocation (and copying) of the node's name
489/// character strings. For this, a template parameter \p{TNodeHandler} is defined,
490/// which defaults to built-in struct \alib{containers;StringTreeNamesDynamic}.
491/// This default "node handler" defines the name type of nodes to \alib{strings;TLocalString;LocalString}
492/// with a default capacity of \c 32 characters.
493/// This way, this local string performs dynamic allocation automatically when a node is
494/// constructed.<br>
495/// In the case that many "long" node names are expected, it might be efficient to set the capacity
496/// to \c 0. In this case, type \b StringTreeNamesDynamic defines the string-type to a normal
497/// \b String and uses C++ keywords <c>new</c> and <c>delete[]</c> to allocate
498/// and free character buffers for the name string.
499///
500/// A second built-in and ready-to-use "node handler" type is given with
501/// \alib{containers;StringTreeNamesStatic}. This uses an unbuffered \b String and has empty
502/// implementations of its static methods. This way no copies of the original string buffers that
503/// are passed to the to interface methods of class \b Cursor that create children are made.
504/// This is useful (and very efficient!) if \b all child name and creation path strings provided
505/// of class \b %Cursor are permanently valid, or, in other words, their life-cycle spans over
506/// the life-cycle of the nodes in a tree. Then, the names do not need to be copied to dedicated
507/// allocated memory.
508///
509/// Finally, string trees that during their lifetime just grow and where no nodes (or only a limited
510/// number of nodes) are removed until the whole tree is disposed may be instantiated using
511/// the third built-in type \alib{containers;StringTreeNamesAlloc}.
512/// With that, the concept of \ref alib_contmono_intro "monotonic allocation" that this container
513/// type might use can be extended to the node name strings.
514/// Type \b StringTreeNamesAlloc grabs the allocator from the tree provided with method
515/// \alib{containers::StringTreeNamesAlloc;InitializeNode} and just clones the given
516/// string into this.
517///
518/// \I{#############################################################################################}
519/// # 5. Equipping the Root Node with Values # {#alib_ns_containers_stringtree_rootnodevalues}
520/// It depends on the field of application, whether the root node should dispose over an instance
521/// of custom type \p{T} or not.
522/// For example, a tree of depth \c 1, which could be implemented using type
523/// <c>std::vector<T></c>, no stored type \p{T} can be attached to the vector object itself, only
524/// to its "children".<br>
525/// Nevertheless, in many use cases, the root node naturally contains the same data as any other
526/// node in the tree. Therefore, if this class would not support root node data, using
527/// code would, for example, have to check a \alib{containers::StringTree;TCursor;Cursor} for pointing
528/// to the root node and in this case get the custom data from somewhere else.<br>
529/// On the other hand, if this class would "insist" in the provision of root node values, then already
530/// with construction of the tree, arguments for the construction of the associated \p{T} object
531/// would have to be provided - even if the root node value was never used.
532/// The provision of initial "dummy" root data, is sometimes not even (easily) possible, and would
533/// sometimes add the need to adjust the custom stored type \p{T} to fit into this class.
534/// (In fact, with former versions of \alib, root-node initialization data was mandatory to provide
535/// already with the construction of the tree.)
536///
537/// Therefore, this class makes the use of root node values optional. After construction of a
538/// \b StringTree, methods \alib{containers::StringTree;ConstructRootValue} and
539/// methods \alib{containers::StringTree;DestructRootValue} may be used to initialize and
540/// destruct the optional root nodes' data.
541///
542/// To prevent memory leaks, in debug-compilations, the following \alib_assertions and warnings are
543/// raised:
544/// - \alib{containers::StringTree;TCursor::Value;Cursor::Value} will raise an assertion if
545/// called on the root node without having set a value.
546/// - \alib{containers::StringTree;ConstructRootValue} will raise a warning if called twice
547/// without a prior call to \alib{containers::StringTree;DestructRootValue}.
548/// - \alib{containers::StringTree;DestructRootValue} will raise a warning if called without
549/// a prior call to \alib{containers::StringTree;ConstructRootValue}.
550/// - The destructor of this class will raise a warning if a root value was set but not deleted.
551///
552/// \I{#############################################################################################}
553/// # Reference Documentation # {#alib_ns_containers_stringtree_referencedoc}
554///
555/// @tparam TAllocator The \alib{lang;Allocator;allocator type} to use.
556/// @tparam T The custom type of elements stored in this container.
557/// @tparam TNodeHandler
558/// A template type that needs to provide an interface as documented with
559/// \alib{containers;StringTreeNamesDynamic}, which is also the default type
560/// if not specified. For details see
561/// \ref alib_ns_containers_stringtree_alloc_names "corresponding section" of this
562/// class's documentation.
563/// The type is published as \alib{containers;StringTree::HandlerType}.
564/// @tparam TRecycling Denotes the type of recycling that is to be performed.
565/// Possible values are
566/// \alib{containers;Recycling;None},
567/// \alib{containers;Recycling;Private} (the default), or
568/// \alib{containers;Recycling;Shared}.
569//==================================================================================================
570template<typename TAllocator,
571 typename T,
572 typename TNodeHandler= StringTreeNamesDynamic<character>,
573 Recycling TRecycling = Recycling::Private>
574class StringTree : protected detail::StringTreeBase<TAllocator,T,TNodeHandler,TRecycling>
575{
576 #if !DOXYGEN
577 protected:
578 friend class Cursor;
579 friend class ConstCursor;
580 friend TNodeHandler;
581
582 using basetree = detail::StringTreeBase<TAllocator,T,TNodeHandler,TRecycling>;
583 using baseNodeKey = typename basetree::NodeKey;
584 using baseNodeBase = typename basetree::NodeBase;
585 using baseNode = typename basetree::Node;
586 using baseCursor = typename basetree::CursorBase;
587 using baseConstCursor = typename basetree::ConstCursorBase;
588 #endif
589
590 public:
591 /// Type definition publishing template parameter \p{TAllocator}.
592 using AllocatorType = TAllocator;
593
594 /// The character type of node names and paths strings. This is defined using character type
595 /// definition \alib{containers::StringTreeNamesDynamic;CharacterType} of template
596 /// type \p{TNodeHandler}.
597 using CharacterType = typename TNodeHandler::CharacterType;
598
599 /// The string-type of node names and paths. This is defined using character type definition
600 /// \alib{containers::StringTreeNamesDynamic;CharacterType} of template type
601 /// \p{TNodeHandler}.
602 using NameType = strings::TString<CharacterType>;
603
604 /// The substring-type of paths. This is defined using character type definition
605 /// \alib{containers::StringTreeNamesDynamic;CharacterType} of template type
606 /// \p{TNodeHandler}.
607 using SubstringType = typename strings::TSubstring<CharacterType>;
608
609 /// Type definition publishing template parameter \p{TNodeHandler}.
610 using HandlerType = TNodeHandler;
611
612 /// This type definition may be used to define an externally managed shared recycler,
613 /// which can be passed to the alternative constructor of this class when template
614 /// parameter \p{TRecycling} equals \alib{containers;Recycling;Shared}.
615 /// \see
616 /// Chapter \ref alib_contmono_containers_recycling_shared of the Programmer's Manual
617 /// for this \alibmod.
618 using SharedRecyclerType= typename basetree::SharedRecyclerType;
619
620
621 /// A handle type used with methods #TCursor::Export and #ImportCursor.
622 struct CursorHandle
623 {
624 uinteger value; ///< The encapsulated value.
625
626 /// Comparison operator.
627 /// @param other The cursor handle to compare this handle to.
628 /// @return \c true if both handles refer to the same cursor or if both handles are
629 /// invalid. \c false otherwise.
630 bool operator==(const CursorHandle& other) const noexcept { return value==other.value; }
631
632 /// Checks if this is a valid handle.
633 /// @return \c true if this handle is not nulled.
634 bool IsValid() const noexcept { return value != 0; }
635 };
636
637 /// A handle type used with methods #TCursor::Export and #ImportCursor.
638 struct ConstCursorHandle
639 {
640 uinteger value; ///< The encapsulated value.
641
642 /// Defaulted default constructor.
643 ConstCursorHandle() =default;
644
645 /// Constructor accepting a raw value.
646 /// @param pValue The value that this handle is supposed to use.
647 ConstCursorHandle(uinteger pValue) : value{pValue} {}
648
649 /// Constructor accepting a mutable handle.
650 /// @param mutableHandle The mutable handle that is to be converted to a constant one.
651 ConstCursorHandle( const CursorHandle& mutableHandle) : value{mutableHandle.value} {}
652
653 /// Comparison operator.
654 /// @param other The cursor handle to compare this handle to.
655 /// @return \c true if both handles refer to the same cursor or if both handles are
656 /// invalid. \c false otherwise.
657 bool operator==(const ConstCursorHandle& other) const noexcept
658 { return value==other.value; }
659
660 /// Comparison operator.
661 /// @param other The cursor handle to compare this handle to.
662 /// @return \c true if both handles refer to the same cursor or if both handles are
663 /// invalid. \c false otherwise.
664 bool operator==(const CursorHandle& other) const noexcept { return value==other.value; }
665
666 /// Checks if this is a valid handle.
667 /// @return \c true if this handle is not nulled.
668 bool IsValid() const noexcept { return value != 0; }
669 };
670
671 /// This public, inner class provides the main interface into outer class \b StringTree.
672 /// The class should be considered being similar to a simple pointer or to a lightweight
673 /// iterator type, which refers to a tree and a current node.<br>
674 /// The class's interface allows the access to a node's name and value and to insert and
675 /// remove child nodes.
676 ///
677 /// Instances of this class can be received with method #Root and then from methods of this
678 /// type itself.
679 ///
680 /// The default constructor creates an invalid object, which has to be initialized by
681 /// assigning a valid object before its first use.
682 ///
683 /// \see
684 /// For more information on how this class is used, see paragraph
685 /// \ref alib_ns_containers_stringtree_cursor "2.1 Inner Class Cursor"
686 /// of the description of class \b %StringTree.
687 ///
688 /// @tparam TConst If true, internal fields representing the StringTree and the current Node
689 /// become \c const and methods which are not declared \c const become
690 /// unavailable.
691 ///
692 /// ## Friends ##
693 /// class \alib{containers;StringTree}
694 template<bool TConst>
695 class TCursor : protected basetree::template TCursorBase<TConst>
696 {
697 #if !DOXYGEN
698 friend class StringTree;
699 #endif
700
701 #if !DOXYGEN
702 #if ALIB_DEBUG_CRITICAL_SECTIONS
703 #define DCS ALIB_DCS_WITH(cmCursor::tree->nodeTable.dcs)
704 #define DCSSHRD ALIB_DCS_SHARED_WITH(cmCursor::tree->nodeTable.dcs)
705 #else
706 #define DCS
707 #define DCSSHRD
708 #endif
709 #endif
710
711 protected:
712 /// Constant or mutable version of the base tree type, depending on template parameter
713 /// \p{TConst}
714 using cmTree = std::conditional_t<!TConst, basetree, const basetree>;
715
716 /// Constant or mutable version of the base node type, depending on template parameter
717 /// \p{TConst}
718 using cmNode = std::conditional_t<!TConst, baseNode, const baseNode>;
719
720 /// Constant or mutable version of the base cursor type, depending on template parameter
721 /// \p{TConst}
722 using cmCursor = std::conditional_t<!TConst, baseCursor, baseConstCursor>;
723
724 //############################## Protected methods (class Cursor) ############################
725 /// Internal constructor
726 /// @param pNode The node to refer to.
727 /// @param pTree The \b %StringTree we work on.
728 TCursor(cmNode *pNode, cmTree *pTree) noexcept
729 : basetree::template TCursorBase<TConst>(pNode, pTree) {}
730
731 /// Checks if this cursor is associated with a tree.
732 /// Empty and optimized out with release-builds.
733 void dbgCheckTree() const {
734 ALIB_ASSERT_ERROR(cmCursor::tree != nullptr, "STRINGTREE",
735 "Invalid StringTree::Cursor: No binding with a StringTree. "
736 "(Probably default-constructed.)")
737 }
738
739 /// Checks if this cursor is associated with a tree and a valid node of the tree.
740 /// Empty and optimized out with release-builds.
741 void dbgCheckTreeAndNode() const {
742 dbgCheckTree();
743 ALIB_ASSERT_ERROR( cmCursor::node != nullptr, "STRINGTREE",
744 "Invalid StringTree::Cursor not representing a node of the assigned tree." )
745 }
746
747 //########################### Constructor, comparison operators, etc #########################
748 public:
749 /// Constant or mutable version of the outer string tree type, depending on template
750 /// parameter \p{TConst}
751 using TStringTree = std::conditional_t<!TConst, StringTree, const StringTree>;
752
753
754 /// Public constructor. Creates an invalid cursor.
755 /// The only way to make a default-constructed instance valid is by
756 /// (copy-) assigning another instance.
757 TCursor() noexcept =default;
758
759 /// Copy constructor.
760 /// @param src The cursor to copy.
761 TCursor( const TCursor& src) noexcept
762 : TCursor{ src.node, src.tree } {}
763
764 /// Move constructor.
765 /// @param src The cursor to move.
766 TCursor( TCursor&& src) noexcept
767 : TCursor{ src.node, src.tree } {}
768
769 /// Trivial default copy assign operator.
770 /// @return A reference to \c this.
771 TCursor &operator=(const TCursor &) noexcept =default;
772
773 /// Trivial default move assign operator.
774 /// @return A reference to \c this.
775 TCursor &operator=(TCursor &&) noexcept =default;
776
777 /// Trivial default destructor.
778 ~TCursor() noexcept =default;
779
780 /// Conversion operator from <em>TCursor<TConst></em> to <em>TCursor<!TConst></em>.
781 /// For const to mutable, this will fail as intended.
782 /// @return A constant iterator, if this is a mutable. Otherwise compilation will
783 /// duly fail.
784 operator TCursor<!TConst>() { return TCursor<!TConst>(cmCursor::node, cmCursor::tree); }
785
786 /// Comparison operator.
787 /// @param other The object to compare ourselves to.
788 /// @return \c true if this and given cursor are equal, \c false
789 /// otherwise.
790 bool operator==(const TCursor &other) const {
791 return cmCursor::node == other.node
792 && cmCursor::tree == other.tree;
793 }
794
795 /// Comparison operator.
796 /// @param other The object to compare ourselves to.
797 /// @return \c false if this and given cursor are equal, \c true
798 /// otherwise.
799 bool operator!=(const TCursor &other) const { return !((*this) == other); }
800
801 /// This method exports the address of the node in the \b StringTree.
802 /// The second pointer needed to comprise a cursor determines the tree a node belongs to.
803 /// Sometimes, it is necessary to store and restore a cursor, where the corresponding
804 /// tree is known. With this method, in combination with method StringTree::ImportCursor,
805 /// such storage with <c>sizeof(void*)</c>(instead of twice that size).
806 ///
807 /// \attention In fact this method and the corresponding constructor perform pointer
808 /// operations and keyword <c>reinterpret_cast</c>. Use with care.
809 /// @return A value usable to reconstruct this cursor with the method
810 /// #StringTree::ImportCursor.
811 CursorHandle Export() { return CursorHandle{uinteger(cmCursor::node)}; }
812
813 /// Overloaded \c const version that returns a \c const handle, usable likewise only
814 /// to re-construct a \c const cursor instance.
815 ///
816 /// @return A value usable to reconstruct this cursor with method
817 /// #StringTree::ImportCursor.
818 ConstCursorHandle Export() const { return ConstCursorHandle {uinteger(cmCursor::node)}; }
819
820 /// Determines if this is a valid object. Cursors may become invalid with
821 /// transition methods like #GoToParent, #GoToFirstChild, or GoToNextSibling.
822 /// An invalid object may be turned into a valid one by either
823 /// - assigning a valid object (copy assignment), or
824 /// - invoking method #GoToRoot, or
825 /// - invoking method #GoTo using absolute path addressing.
826 ///
827 /// Note that the latter is not applicable to a default-constructed objects
828 /// (which are also invalid) as with such no \b %StringTree is assigned.
829 ///
830 /// @return \c true if this is a valid cursor.
831 /// If invalid, \c false is returned and this object must not be used.
832 bool IsValid() const { return cmCursor::node != nullptr; }
833
834 /// Returns the opposite of #IsValid.
835 ///
836 /// @return \c true if this is an invalid cursor that must not be used,
837 /// \c false otherwise.
838 bool IsInvalid() const { return !IsValid(); }
839
840 //######################### Tree navigation inplace, returning status ########################
841 /// Returns a cursor to the root node of the tree.
842 /// @return A cursor representing the root node of the tree this pointer
843 /// represents.
844 TCursor Root() const {
845 dbgCheckTree();
846 return TCursor(cmCursor::tree, &cmCursor::tree->root.root);
847 }
848
849 /// Moves this cursor to the root node of the tree.
850 /// @return A reference to this object
851 TCursor& GoToRoot() {
852 dbgCheckTree();
853 cmCursor::node = &cmCursor::tree->root.root;
854 return *this;
855 }
856
857 /// Creates a cursor value representing the parent node of the
858 /// node represented by this object.
859 ///
860 /// If this object represents the root node of the tree, the returned cursor
861 /// is invalid.
862 ///
863 /// @return A cursor pointing to the parent node of the node represented
864 /// by this cursor.
865 TCursor Parent() const {
866 dbgCheckTreeAndNode();
867 return TCursor(static_cast<cmNode*>(cmCursor::node->parent), cmCursor::tree);
868 }
869
870 /// Moves this cursor to the parent of the current node.
871 /// If this is the root node, this object becomes invalid.
872 ///
873 /// @return *this to allow concatenated calls
874 TCursor& GoToParent() {DCSSHRD
875 dbgCheckTreeAndNode();
876 cmCursor::node = static_cast<cmNode*>(cmCursor::node->parent);
877 return (*this);
878 }
879
880 /// Returns a cursor value that represents the next sibling of the node
881 /// represented this cursor.
882 /// If the node has no next sibling, an invalid cursor is returned.
883 ///
884 /// @return A cursor object representing the next sibling of the node
885 /// represented by this object.
886 TCursor NextSibling() const {DCSSHRD
887 return TCursor( HasNextSibling() ? static_cast<cmNode*>(cmCursor::node->next())
888 : nullptr,
889 cmCursor::tree );
890 }
891
892 /// Moves this cursor to the next sibling of the represented node.
893 /// If the node has no next sibling, this cursor becomes invalid.
894 /// The latter is always true if this is the root node of the tree.
895 ///
896 /// @return \c true if this cursor was moved,
897 /// \c false if the represented node has no next sibling.
898 bool GoToNextSibling() {DCSSHRD
899 // go to node next and check for hook?
900 if (HasNextSibling()) {
901 cmCursor::node = static_cast<cmNode*>(cmCursor::node->next());
902 return true;
903 }
904 cmCursor::node = nullptr;
905 return false;
906 }
907
908 /// Returns a cursor value that represents the previous sibling of the node
909 /// represented this cursor.
910 /// If the node has no previous sibling, an invalid cursor is returned.
911 ///
912 /// @return A cursor object representing the previous sibling of the node
913 /// represented by this object.
914 TCursor PreviousSibling() const {DCSSHRD
915 return TCursor( HasPreviousSibling() ? static_cast<cmNode*>(cmCursor::node->prev())
916 : nullptr,
917 cmCursor::tree );
918 }
919
920 /// Moves this cursor to the previous sibling of the represented node.
921 /// If the node has no previous sibling, this cursor becomes invalid.
922 /// The latter is always true if this is the root node of the tree.
923 ///
924 /// @return \c true if this cursor was moved,
925 /// \c false if the represented node has no previous sibling.
926 bool GoToPreviousSibling() {DCSSHRD
927 if( HasPreviousSibling() ) {
928 cmCursor::node= static_cast<cmNode*>(cmCursor::node->prev());
929 return true;
930 }
931 cmCursor::node= nullptr;
932 return false;
933 }
934
935 /// Returns a cursor object that represents the first child of the node
936 /// represented.
937 /// If the represented node has no children, an invalid cursor is returned.
938 ///
939 /// @return A cursor representing the first child of the node this cursor points to.
940 TCursor FirstChild() const {DCSSHRD
941 return TCursor( HasChildren() ? static_cast<cmNode*>(cmCursor::node->children.first())
942 : nullptr,
943 cmCursor::tree );
944 }
945
946 /// Moves this cursor to the first child of its represented node.
947 /// If the represented node has no children, this cursor becomes invalid.
948 ///
949 /// @return \c true if the cursor was moved, \c false if the represented node
950 /// has no children.
951 bool GoToFirstChild() {DCSSHRD
952 if( HasChildren() ) {
953 cmCursor::node= static_cast<cmNode*>(cmCursor::node->children.first());
954 return true;
955 }
956 cmCursor::node= nullptr;
957 return false;
958 }
959
960 /// Returns a cursor value that represents the last child of the node
961 /// represented.
962 /// If the represented node has no children, an invalid cursor is returned.
963 ///
964 /// @return A cursor representing the last child of the node represented
965 /// by this cursor.
966 TCursor LastChild() const {DCSSHRD
967 return TCursor( HasChildren() ? static_cast<cmNode*>(cmCursor::node->children.last())
968 : nullptr,
969 cmCursor::tree );
970 }
971
972 /// Moves this cursor to the last child of its represented node.
973 /// If the represented node has no children, this cursor becomes invalid.
974 ///
975 /// @return \c true if the cursor was moved, \c false if the represented node
976 /// has no children.
977 bool GoToLastChild() {DCSSHRD
978 if( HasChildren() ) {
979 cmCursor::node= static_cast<cmNode*>(cmCursor::node->children.last());
980 return true;
981 }
982 cmCursor::node= nullptr;
983 return false;
984 }
985
986 /// Searches a child with the given name and returns a cursor to it.
987 /// If no child with this name exists, the returned cursor is invalid
988 ///
989 /// The given \p{name} is not considered a path and is not checked for being <c>"."</c>
990 /// or <c>".."</c> or if it contains a separator character.
991 /// Children with such name cannot exist and hence can't be found. However, in
992 /// debug-builds, a \ref alib_mod_assert "warning is raised".
993 ///
994 /// @param name The name of the child to search.
995 /// @return A cursor representing the last child of the node represented
996 /// by this cursor.
997 TCursor Child( const NameType& name ) const {DCSSHRD
998 dbgCheckTreeAndNode();
999 ALIB_DBG( cmCursor::tree->checkChildName( name ); ) // gives warning
1000 return TCursor( static_cast<cmNode*>(cmCursor::node->findChild(cmCursor::tree, name)),
1001 cmCursor::tree );
1002 }
1003
1004 /// Searches a child with the given name and moves this cursor to it.
1005 /// If no child with this name exists, the cursor does not change and
1006 /// \c false is returned.
1007 ///
1008 /// The given \p{name} is not considered a path and is not checked for being <c>"."</c>
1009 /// or <c>".."</c> or if it contains a separator character.
1010 /// Children with such a name cannot exist and hence can't be found. However, in
1011 /// debug-builds, a \ref alib_mod_assert "warning is raised".
1012 ///
1013 /// @param name The name of the child to search.
1014 /// @return \c true if the child existed and this object changed, \c false
1015 /// otherwise.
1016 bool GoToChild( const NameType& name ) {DCSSHRD
1017 dbgCheckTreeAndNode();
1018 ALIB_DBG( cmCursor::tree->checkChildName( name ); )
1019
1020 cmNode* child= static_cast<cmNode*>(cmCursor::node->findChild( cmCursor::tree, name ));
1021 if(child) {
1022 cmCursor::node= child;
1023 return true;
1024 }
1025 return false;
1026 }
1027
1028 /// Moves this cursor to the child with given \p{name}.
1029 /// If no child with this name exists, one will be created.
1030 ///
1031 /// If the given \p{childName} is invalid (equals to <c>"."</c> or
1032 /// <c>".."</c> or contains the separation character), then still \c true is returned,
1033 /// but this cursor becomes invalid.
1034 /// In addition, with debug-builds, a \ref alib_mod_assert "warning is raised".
1035 ///
1036 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1037 /// @param name The name of the desired child.
1038 /// @param args Variadic parameters to be forwarded to the constructor of custom type
1039 /// \p{T} in the case a child is created.
1040 /// @return A pair of a cursor pointing to the child and a boolean that equals
1041 /// \c false if the child was found, and \c true if a child was created.
1042 /// If the given name was invalid, the returned cursor will be invalid
1043 /// while the boolean still indicates "not found" (aka \c true).
1044 template<typename... TArgs>
1045 std::pair<TCursor, bool> CreateChildIfNotExistent( const NameType& name,
1046 TArgs&&... args ) {DCS
1047 dbgCheckTreeAndNode();
1048 if( !cmCursor::tree->checkChildName( name ) )
1049 return std::make_pair( TCursor(cmCursor::tree, nullptr), true );
1050
1051 auto result= cmCursor::node->findOrCreateChild( cmCursor::tree, name,
1052 std::forward<TArgs>(args)... );
1053
1054 return std::make_pair( TCursor( cmCursor::tree, result.first ), result.second );
1055 }
1056
1057 /// Moves this cursor to the child with given \p{name}.
1058 /// If no child with this name exists, one will be created.
1059 ///
1060 /// If the given \p{childName} is invalid (equals to <c>"."</c> or
1061 /// <c>".."</c> or contains the separation character), then still \c true is returned,
1062 /// but this cursor becomes invalid.
1063 /// In addition, with debug-builds, a \ref alib_mod_assert "warning is raised".
1064 ///
1065 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1066 /// @param name The name of the desired child.
1067 /// @param args Variadic parameters to be forwarded to the constructor of custom type
1068 /// \p{T} in the case a child is created.
1069 /// @return \c false if the child was found, and \c true if one was created or the given
1070 /// child name was invalid.
1071 template<typename... TArgs>
1072 bool GoToCreateChildIfNotExistent(const NameType& name, TArgs&&... args) {DCS
1073 dbgCheckTreeAndNode();
1074 if( !cmCursor::tree->checkChildName( name ) ) {
1075 cmCursor::node= nullptr;
1076 return true;
1077 }
1078
1079 auto result= cmCursor::node->findOrCreateChild( cmCursor::tree, name,
1080 std::forward<TArgs>(args)... );
1081
1082 cmCursor::node= static_cast<cmNode*>(result.first);
1083 return result.second;
1084 }
1085
1086 /// Follows the given \p{path} from the currently represented node to the target
1087 /// node and returns a new cursor instance..
1088 ///
1089 /// The method supports absolute and relative path addressing: If \p{path} begins
1090 /// with a separation character, then the transition starts with the root node of the
1091 /// \b %StringTree. Furthermore, child name <c>"."</c> is ignored and just skipped
1092 /// while a name of <c>".."</c> addresses the parent node during the transition.
1093 /// Repeated separation characters are ignored.<br>
1094 /// If, while processing the path string, the root node is found an the next
1095 /// path element is "..", this element is ignored and processing continues.
1096 /// As a sample, assuming that nodes \e /a and \e /b exist, the paths:
1097 ///
1098 /// /a/../b
1099 /// and
1100 ///
1101 /// /a/../../b
1102 /// both evaluate to
1103 ///
1104 /// /b
1105 ///
1106 /// Relative paths must not be used on \ref TCursor::IsValid "invalid" cursors. Doing so
1107 /// is undefined behavior and \ref alib_mod_assert "raises an ALib error" in
1108 /// debug-compilations.
1109 ///
1110 /// If a child along the path does not exist, the traversal is ended and the remaining
1111 /// portion of the path is returned.
1112 ///
1113 /// \note
1114 /// If parameter \p{path} is a temporary object, the resulting \b Substring must
1115 /// not be used, as it refers to the given string's buffer. In any case, its
1116 /// length can still be compared to \c 0 to evaluate success of the traversal.
1117 ///
1118 /// @param path The path to follow, starting with the node this pointer represents.
1119 ///
1120 /// @return A pair of a cursor pointing to last child not of the existing portion
1121 /// of the given \p{path}, and a substring that contains the non-existing
1122 /// portion of a path, or is empty if the complete path existed.
1123 std::pair<TCursor, SubstringType> operator()( const NameType& path ) const {DCSSHRD
1124 dbgCheckTreeAndNode();
1125 SubstringType remainingPath(path);
1126 cmNode* grandChild= cmCursor::followPath( remainingPath );
1127 return std::make_pair( TCursor(grandChild, cmCursor::tree), remainingPath );
1128 }
1129
1130 /// Same as the
1131 /// \doxlinkproblem{classalib_1_1containers_1_1StringTree_1_1TCursor.html;a55db5acb390a2d38dd8e30c123cb6e4b;operator()(const NameType&)},
1132 /// but moves this cursor instead of returning a new one.
1133 ///
1134 /// @param path The path to move this cursor along.
1135 /// @return The unconsumed portion of the path.
1136 /// An empty \b Substring if the path existed.
1137 SubstringType GoTo( const NameType& path ) {DCSSHRD
1138 dbgCheckTreeAndNode();
1139 SubstringType remainingPath(path);
1140 cmCursor::node= cmCursor::followPath( remainingPath );
1141 return remainingPath;
1142 }
1143
1144 /// Follows the given path and creates non-existing children along the way.
1145 ///
1146 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected the same as
1147 /// documented with the
1148 /// \doxlinkproblem{classalib_1_1containers_1_1StringTree_1_1TCursor.html;a55db5acb390a2d38dd8e30c123cb6e4b;operator()(const NameType&)}.
1149 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
1150 /// remain untouched.
1151 ///
1152 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1153 /// @param path The path to move along.
1154 /// @param args Variadic parameters to be forwarded to the constructor of each node
1155 /// that is created.
1156 /// @return A <c>std::pair</c> containing a resulting \b Cursor and the number of nodes
1157 /// created.
1158 template<typename... TArgs>
1159 std::pair<TCursor, integer> CreatePathIfNotExistent( const NameType& path,
1160 TArgs&&... args ) {DCS
1161 dbgCheckTree();
1162 ALIB_ASSERT_ERROR( IsValid() || path.CharAtStart() == cmCursor::tree->separator,
1163 "STRINGTREE", "Invalid StringTree::Cursor given with relative path addressing." )
1164
1165 auto result= cmCursor::followPathCreate( path, std::forward<TArgs>(args)... );
1166
1167 return std::make_pair( TCursor(static_cast<cmNode*>(result.first), cmCursor::tree),
1168 result.second );
1169 }
1170
1171 /// Follows the given path and creates non-existing children along the way.
1172 ///
1173 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected same as in
1174 /// \doxlinkproblem{classalib_1_1containers_1_1StringTree_1_1TCursor.html;a55db5acb390a2d38dd8e30c123cb6e4b;operator()(const NameType&)}.
1175 ///
1176 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
1177 /// remain untouched.
1178 ///
1179 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1180 /// @param path The path to move along.
1181 /// @param args Variadic parameters to be forwarded to the constructor of each node
1182 /// that is created.
1183 /// @return The number of nodes created.
1184 template<typename... TArgs>
1185 integer GoToCreatedPathIfNotExistent( const NameType& path,
1186 TArgs&&... args ) {DCS
1187 dbgCheckTree();
1188 ALIB_ASSERT_ERROR( IsValid() || path.CharAtStart() == cmCursor::tree->separator,
1189 "STRINGTREE", "Invalid StringTree::Cursor given with relative path addressing." )
1190
1191 auto result= cmCursor::followPathCreate( path, std::forward<TArgs>(args)... );
1192 cmCursor::node= static_cast<cmNode*>(result.first);
1193 return result.second;
1194 }
1195
1196 //###################################### Cursor Interface ####################################
1197 /// Returns the name of the represented node.
1198 /// Note that the concatenated names of recursive child nodes, separated by
1199 /// \p{TSeparator} constitute a \e path.
1200 ///
1201 /// @return A constant reference to the name of the represented node.
1202 const NameType& Name() const { dbgCheckTreeAndNode(); return cmCursor::node->name.key; }
1203
1204 /// Returns the tree that this cursor belongs to.
1205 /// @tparam TParent Optional template parameter, which casts the internal tree type
1206 /// to a derived type. This is for convenience, as otherwise the
1207 /// cast hast to be done by the caller which does not look too nice.
1208 /// @return The tree that this object refers to.
1209 template<typename TParent= StringTree>
1210 requires std::derived_from<TParent, StringTree>
1211 TParent& Tree() const { dbgCheckTree(); return *static_cast<TParent*>(cmCursor::tree); }
1212
1213 /// Retrieves a reference to the templated value of type \p{T} stored in the represented
1214 /// node.
1215 /// \note This method is only available if the template parameter \p{TConst} of this
1216 /// type is \c false.
1217 /// @see Operators #operator->() and #operator*().
1218 /// @tparam TRequires Defaulted template parameter. Must not be specified.
1219 /// @return The current node's value.
1220 template<bool TRequires= !TConst>
1221 requires TRequires
1222 T& Value() {
1223 dbgCheckTree();
1224 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1225 "Root node has no value. Either this operation is unwanted or root node's value\n"
1226 "has to be explicitly set using ConstructRootValue(...)" )
1227 return static_cast<baseNode*>(cmCursor::node)->data;
1228 }
1229
1230 /// Retrieves a constant reference to the templated value of type \p{T} stored in
1231 /// the represented node.
1232 /// @see Operators #operator->() and #operator*().
1233 /// @return The current node's value.
1234 const T& Value() const {
1235 dbgCheckTree();
1236 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1237 "Root node has no value. Either this operation is unwanted or root node's value\n"
1238 "has to be explicitly set using ConstructRootValue(...)" )
1239 return static_cast<const baseNode*>(cmCursor::node)->data;
1240 }
1241
1242 /// Retrieves a pointer to the templated value of type \p{T} stored
1243 /// in the represented node.
1244 /// \note This method is only available if the template parameter \p{TConst} of this
1245 /// type is \c false.
1246 /// @tparam TRequires Defaulted template parameter. Must not be specified.
1247 /// @return The current node's value.
1248 template<bool TRequires= !TConst>
1249 requires TRequires
1250 T* operator->() {
1251 dbgCheckTree();
1252 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1253 "Root node has no value. Either this operation is unwanted or root node's value\n"
1254 "has to be explicitly set using ConstructRootValue(...)" )
1255 return &static_cast<baseNode*>(cmCursor::node)->data;
1256 }
1257
1258 /// Retrieves a constant pointer to the templated value of type \p{T} stored in
1259 /// the represented node.
1260 /// @return The current node's value.
1261 const T* operator->() const {
1262 dbgCheckTree();
1263 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1264 "Root node has no value. Either this operation is unwanted or root node's value\n"
1265 "has to be explicitly set using ConstructRootValue(...)" )
1266 return &static_cast<const baseNode*>(cmCursor::node)->data;
1267 }
1268
1269 /// Retrieves a reference to the templated value of type \p{T} stored
1270 /// in the represented node.
1271 /// \note This method is only available if the template parameter \p{TConst} of this
1272 /// type is \c false.
1273 /// @tparam TRequires Defaulted template parameter. Must not be specified.
1274 /// @return The current node's value.
1275 template<bool TRequires= !TConst>
1276 requires TRequires
1277 T& operator*() {
1278 dbgCheckTree();
1279 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1280 "Root node has no value. Either this operation is unwanted or root node's value\n"
1281 "has to be explicitly set using ConstructRootValue(...)" )
1282 return static_cast<baseNode*>(cmCursor::node)->data;
1283 }
1284
1285 /// Retrieves a reference to the templated value of type \p{T} stored
1286 /// in the represented node.
1287 /// \note This operator is only available if template parameter \p{TConst} is false.
1288 /// @return The current node's value.
1289 const T& operator*() const {
1290 dbgCheckTree();
1291 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1292 "Root node has no value. Either this operation is unwanted or root node's value\n"
1293 "has to be explicitly set using ConstructRootValue(...)" )
1294 return static_cast<const baseNode*>(cmCursor::node)->data;
1295 }
1296
1297 /// Returns \c true if this cursor represents the root node of the
1298 /// \b %StringTree, \c false otherwise.
1299 /// @return \c true if this object represents the root node, \c false otherwise.
1300 bool IsRoot() const { dbgCheckTreeAndNode(); return cmCursor::node->isRoot(); }
1301
1302 /// Determines the depth of the node represented by this object. This is done by
1303 /// counting the iterations needed to reach the root node of the tree.
1304 /// @return The distance from this node to the root node.
1305 int Depth() const
1306 {DCSSHRD
1307 dbgCheckTreeAndNode();
1308 return cmCursor::node->depth();
1309 }
1310
1311 /// Determines the distance between the node represented by this cursor to the
1312 /// node represented by given \p{other}. The distace is defined as follows:
1313 ///
1314 /// - \b 0 if other represents the same node.
1315 /// - \b 1 if other represents the parent of this node.
1316 /// - \b 2 if other represents the grand-parent of this node.
1317 /// - \b 3 ...
1318 /// - \b N if other represents the root node.
1319 ///
1320 /// @param other The node to test.
1321 /// @return The distance from this node to the root node. \c -1 is returned in case
1322 /// \p{other} is not found in the path to this node.
1323 int Distance( const TCursor<true>& other ) const {DCSSHRD
1324 dbgCheckTreeAndNode();
1325 ALIB_ASSERT_ERROR( other.node, "STRINGTREE", "Invalid node given." )
1326 ALIB_ASSERT_ERROR( cmCursor::tree == other.tree, "STRINGTREE",
1327 "Given node belongs to a different StringTree." )
1328 return cmCursor::node->distance( other.node );
1329 }
1330
1331 /// Returns \c true if the represented node has at least one direct child.
1332 /// @return \c true if the current node has children, \c false otherwise.
1333 bool HasChildren() const
1334 {DCSSHRD
1335 dbgCheckTreeAndNode();
1336 return cmCursor::node->qtyChildren != 0;
1337 }
1338
1339 /// Returns the number of direct children of the represented node.<br>
1340 /// Note that this method runs in constant time.
1341 /// @return The number of direct children of the represented node.
1342 uinteger CountChildren() const
1343 {DCSSHRD
1344 dbgCheckTreeAndNode();
1345 return cmCursor::node->qtyChildren;
1346 }
1347
1348 /// Evaluates if the node represented by this object has a next sibling in its
1349 /// parent's list of children.
1350 /// @return \c true if a next sibling to this object's represented node exists,
1351 /// \c false otherwise.
1352 bool HasNextSibling() const {DCSSHRD
1353 dbgCheckTreeAndNode();
1354 return !IsRoot()
1355 && !cmCursor::node->parent->children.isLast( cmCursor::node );
1356 }
1357
1358 /// Evaluates if the node represented by this object has a previous sibling in its
1359 /// parent's list of children.
1360 /// @return \c true if a previous sibling to this object's represented node exists,
1361 /// \c false otherwise.
1362 bool HasPreviousSibling() const {DCSSHRD
1363 dbgCheckTreeAndNode();
1364 return !IsRoot()
1365 && !cmCursor::node->parent->children.isFirst( cmCursor::node );
1366 }
1367
1368 /// Writes the absolute path to the represented node (including the represented node's
1369 /// name) to the given \b %AString.<br>
1370 /// If this node represents the root node, then nothing is written but a single
1371 /// separation character.
1372 ///
1373 /// While the implementation of this method is as efficient as possible (to avoid
1374 /// insertions at the beginning of the target string while moving to the destination/root
1375 /// node, internally a local node-stack is created first, which then is traversed
1376 /// top-down), still in many situations, it is recommended to search for other ways to
1377 /// keep track of the current path of a node and modify and re-use such path.
1378 /// For this, class \alib{containers;StringTreeIterator}, optionally allows maintaining
1379 /// a string representing the current path with every iteration.
1380 ///
1381 /// \see
1382 /// Overloaded version <b>AssemblePath(AString&,TCursor<TConst>&,lang::CurrentData)</b>,
1383 /// which allows the creation a relative path from a parent node to this node.
1384 ///
1385 /// @param targetString The string buffer to append the path to.
1386 /// @param targetData Denotes whether \p{target} should be cleared before
1387 /// appending the path. Defaults to \b CurrentData::Clear.
1388 /// @return The given \b AString to allow concatenated operations.
1389 strings::TAString<typename cmTree::CharacterType, lang::HeapAllocator>&
1390 AssemblePath( strings::TAString<typename cmTree::CharacterType>& targetString,
1391 lang::CurrentData targetData=
1392 lang::CurrentData::Clear ) const
1393 {DCSSHRD
1394 if( targetData == lang::CurrentData::Clear )
1395 targetString.Reset();
1396
1397 return cmCursor::node->assemblePath( targetString, cmCursor::node, nullptr,
1398 cmCursor::tree->separator );
1399 }
1400
1401 /// Same as #AssemblePath but accepts a parent node to stop at, instead of the root node.
1402 /// The path created is a relative path from the \p{parent} to the represented node,
1403 /// hence it does \b not include the parent' name and also does \b not start with the
1404 /// separation character. The latter is true even if the given \p{targetParent} represents
1405 /// the root node. In this case the path is a relative path from the root node \c '/'
1406 /// to the child.
1407 ///
1408 /// If the given \p{parent} is not found within the list of parent nodes, then
1409 /// an absolute path from the tree's root to the represented node is returned.
1410 ///
1411 ///
1412 /// @param targetString The string buffer to append the path to.
1413 /// @param parent Denotes the parent node to start a relative path from.
1414 /// @param targetData Denotes whether \p{target} should be cleared before
1415 /// appending the path. Defaults to \b CurrentData::Clear.
1416 /// @return The given \b AString to allow concatenated operations.
1417 strings::TAString<typename cmTree::CharacterType, lang::HeapAllocator>&
1418 AssemblePath( strings::TAString<typename cmTree::CharacterType,
1419 lang::HeapAllocator >& targetString,
1420 const TCursor<true>& parent,
1421 lang::CurrentData targetData
1422 = lang::CurrentData::Clear ) const
1423 {DCSSHRD
1424 dbgCheckTreeAndNode();
1425 if( targetData == lang::CurrentData::Clear )
1426 targetString.Reset();
1427 return cmCursor::node->assemblePath( targetString, cmCursor::node, parent.node,
1428 cmCursor::tree->separator );
1429 }
1430
1431 //################################### Cursor child creation ##################################
1432 /// Creates and returns a child node. If a node already exists, nothing is done and
1433 /// \c nullptr is returned as this is considered an error.
1434 ///
1435 /// If the child name is illegal (equal to <c>"."</c> or <c>".."</c> or contains a
1436 /// separation character), an \alib_warning is raised and an invalid cursor
1437 /// is returned.
1438 ///
1439 /// Template parameter \p{TCheck} may be used to suppress the search for an
1440 /// existing child with the same name, as well as the check for correctness of the
1441 /// given child name.
1442 /// This tremendously improves the execution performance of this method.
1443 ///
1444 /// \attention Setting template parameter \p{TCheck} to \alib{NC} and inserting
1445 /// child nodes with the same name, sets a \b %StringTree to an
1446 /// undefined state.
1447 ///
1448 /// @tparam TCheck If \alib{NC}, no check for an existing child with the same name
1449 /// is performed.
1450 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1451 /// @param childName The name of the child
1452 /// @param args Variadic parameters to be forwarded to the constructor of custom
1453 /// type \p{T} of the child created.
1454 ///
1455 /// @return A new cursor object representing the created child node.
1456 /// If the given \p{childName} was invalid or the child existed already,
1457 /// the returned object is invalid.
1458 template<typename TCheck =CHK, typename... TArgs>
1459 TCursor CreateChild( const NameType& childName, TArgs&&... args ) const {DCS
1460 dbgCheckTreeAndNode();
1461 if constexpr ( TCheck::value ) {
1462 // check name
1463 if( !baseCursor::tree->checkChildName( childName ) ) {
1464 ALIB_WARNING( "STRINGTREE", "Illegal child name \"{}\"", childName )
1465 return Cursor( nullptr, baseCursor::tree );
1466 }
1467
1468 // check existence
1469 if( baseCursor::node->qtyChildren > 0
1470 && baseCursor::tree->nodeTable.Contains( baseNodeKey( baseCursor::node, childName) ))
1471 return Cursor( nullptr, baseCursor::tree );
1472 }
1473
1474 baseNode* child= &baseCursor::tree->nodeTable.EmplaceUnique( baseCursor::node, childName,
1475 std::forward<TArgs>(args)... )
1476 .Value();
1477 TNodeHandler::InitializeNode( *child, *baseCursor::tree );
1478
1479 baseCursor::node->children.pushEnd( child );
1480 ++baseCursor::node->qtyChildren;
1481 return TCursor( child, baseCursor::tree );
1482 }
1483
1484 //###################################### Cursor deletion #####################################
1485 /// Searches and deletes the child named \p{childName} from the node that this object
1486 /// refers to. This object itself is not changed.
1487 ///
1488 /// \see
1489 /// Overloaded version of this method that accepts a cursor referring to
1490 /// the child in question.
1491 ///
1492 ///
1493 /// @param childName The name of the desired child.
1494 /// @return \c true if the child existed and was deleted, \c false otherwise.
1495 bool DeleteChild( const NameType& childName ) const {DCS
1496 dbgCheckTreeAndNode();
1497 if( baseCursor::node->qtyChildren == 0 )
1498 return false;
1499
1500 auto handle= baseCursor::tree->nodeTable.Extract( baseNodeKey( baseCursor::node, childName) );
1501 if( handle.IsEmpty() )
1502 return false;
1503 handle.Value().deleteChildren( baseCursor::tree );
1504 TNodeHandler::FreeNode( handle.Value(), *baseCursor::tree );
1505 handle.Value().remove();
1506
1507 --baseCursor::node->qtyChildren;
1508 return true;
1509 }
1510
1511 /// Deletes the child represented by the given cursor \p{child} from the node that this
1512 /// cursor refers to. After the invocation, the given \p{child} cursor refers to its
1513 /// next sibling. If no such sibling exists, \p{child} becomes invalid.
1514 /// This cursor itself is not changed.
1515 ///
1516 /// \note
1517 /// This method is useful to implement forward iterations through children of a parent
1518 /// node with the aim to delete certain child nodes. No corresponding version of this
1519 /// method exists that moves the given \p{child} pointer to its previous sibling.
1520 /// For reverse iterations, a copy of the \p{child} argument has to be passed.
1521 /// However, any overhead caused by such temporary object creation will be optimized
1522 /// out by common C++ compilers.
1523 ///
1524 /// @param child Deletes the child represented by the given node.
1525 /// @return The total number of nodes deleted.
1526 uinteger DeleteChild( TCursor& child ) const {DCS
1527 dbgCheckTreeAndNode();
1528 cmNode* nodeToDelete= child.node;
1529 child.GoToNextSibling();
1530 return baseCursor::node->deleteChild( baseCursor::tree, nodeToDelete );
1531 }
1532
1533 /// Deletes the children of the node that this cursor refers to.
1534 /// This object itself is not changed.
1535 ///
1536 /// @return The number of children that were deleted.
1537 uinteger DeleteChildren() const
1538 {DCS
1539 dbgCheckTreeAndNode();
1540 return baseCursor::node->deleteChildren( baseCursor::tree );
1541 }
1542
1543 /// Deletes the branch that this cursor refers to from the tree.
1544 /// If this cursor does not represent the root node, then after the operation,
1545 /// it refers to the parent of the current node.<br>
1546 /// If the represented node is the root node, only the children are deleted and this
1547 /// object remains representing the root node. Note that in this case any explicitly
1548 /// set custom value of the root node is \b not deleted. For this, exclusively methods
1549 /// #ConstructRootValue and #DestructRootValue are to be used.
1550 ///
1551 /// \note
1552 /// When working with class \alib{containers::StringTreeIterator}, this method
1553 /// invalidates an iterator instance if it is invoked on a returned cursor.
1554 /// To avoid this, the provided special method
1555 /// \alib{containers;StringTreeIterator::DeleteNode} is to be used.
1556 ///
1557 /// @return
1558 /// The total number of nodes deleted. Can be zero, in case this object represents
1559 /// the root node and this node has no children.
1560 uinteger Delete() {DCS
1561 dbgCheckTreeAndNode();
1562 if( baseCursor::node->isRoot() )
1563 return baseCursor::node->deleteChildren( baseCursor::tree );
1564
1565 cmNode * child= baseCursor::node;
1566 baseCursor::node= static_cast<cmNode*>(baseCursor::node->parent);
1567 return baseCursor::node->deleteChild( baseCursor::tree, child );
1568 }
1569 }; // inner class TCursor
1570
1571 /// The mutable version of type \b TCursor<TConst>.
1572 using Cursor = TCursor<false>;
1573
1574 /// The constant version of type \b TCursor<TConst>.
1575 using ConstCursor = TCursor<true>;
1576
1577 protected:
1578 /// Protected methods that allows derived types to create cursor instances from
1579 /// nodes received directly from the hashtable.
1580 /// @param node The base node.
1581 /// @return A valid cursor.
1582 Cursor createCursor(baseNode& node) { return Cursor(&node, this); }
1583
1584 //################################################################################################
1585 // StringTree Main
1586 //################################################################################################
1587 public:
1588 #if !DOXYGEN
1589 #if ALIB_DEBUG_CRITICAL_SECTIONS
1590 #undef DCS
1591 #undef DCSSHRD
1592 #define DCS ALIB_DCS_WITH(basetree::nodeTable.dcs)
1593 #define DCSSHRD ALIB_DCS_SHARED_WITH(basetree::nodeTable.dcs)
1594 #endif
1595 #endif
1596
1597 /// Constructor.
1598 /// @param allocator The allocator instance to use.
1599 /// @param pathSeparator The separation character used with path strings.
1600 StringTree( AllocatorType& allocator, CharacterType pathSeparator )
1601 : basetree( allocator, pathSeparator ) {
1602 #if ALIB_DEBUG_CRITICAL_SECTIONS
1603 basetree::nodeTable.dcs.DCSName= "StringTree";
1604 #endif
1605 }
1606
1607 /// Constructor taking a shared recycler.
1608 /// @param pRecycler The shared recycler.
1609 /// @param pathSeparator The separation character used with path strings.
1610 template<typename TSharedRecycler= SharedRecyclerType>
1611 requires(!std::same_as<TSharedRecycler, void>)
1612 StringTree( CharacterType pathSeparator, TSharedRecycler& pRecycler )
1613 : basetree( pRecycler, pathSeparator ) {
1614 #if ALIB_DEBUG_CRITICAL_SECTIONS
1615 basetree::nodeTable.dcs.DCSName= "StringTree";
1616 #endif
1617 }
1618
1619 /// Destructor.
1620 /// Raises a warning if \alib{containers::StringTree;ConstructRootValue;a root value was} but
1621 /// not deleted accordingly.
1622 ~StringTree() {
1623 for( auto& node : basetree::nodeTable )
1624 TNodeHandler::FreeNode( *static_cast<baseNode*>(&node), *this );
1625
1626 ALIB_ASSERT_WARNING( basetree::dbgRootDataSet == 0, "STRINGTREE",
1627 "Possible memory leak! The root node's value object was set but not deleted before\n"
1628 "destruction of this StringTree. To suppress this warning call DestructRootValue()\n"
1629 "before destruction. In case this is not necessary (because the stored type does not\n"
1630 "leak if not destructed), emplace it in macro ALIB_DBG() to remove the call in\n"
1631 "release-builds." )
1632 }
1633
1634 /// Shortcut to
1635 /// \alib{containers;HashTable::GetAllocator;NodeTable().GetAllocator()}.
1636 /// @return The allocator that was provided in the constructor and stored in the internal
1637 /// #NodeTable.
1638 AllocatorType& GetAllocator() noexcept { return basetree::nodeTable.GetAllocator(); }
1639
1640 #if ALIB_DEBUG_CRITICAL_SECTIONS
1641 /// Returns the critical sections debug instance to allow taking ownership from external
1642 /// code and increase the chance to detect the violation of critical sections.
1643 /// For example, this method is used by class \alib{containers;StringTreeIterator}.
1644 /// This method is available only if the compiler symbol \ref ALIB_DEBUG_CRITICAL_SECTIONS
1645 /// is given.
1646 /// @return The internal DCS.
1647 lang::DbgCriticalSections& DbgGetDCS() const { return basetree::nodeTable.dcs; }
1648 #endif
1649
1650 /// Returns the path separator character that this string tree works with.
1651 /// @return The path separator character.
1652 constexpr CharacterType Separator() const noexcept { return basetree::separator; }
1653
1654 #if ALIB_DEBUG_CRITICAL_SECTIONS
1655 /// Sets the critical section name of this string tree. Empty and optimized out if compiler
1656 /// symbol \ref ALIB_DEBUG_CRITICAL_SECTIONS is not set.
1657 /// @param name The name to use with debug-assertions.
1658 void DbgSetDCSName(const char* name) const { basetree::nodeTable.dcs.DCSName= name; }
1659 #else
1660 constexpr void DbgSetDCSName(const char*) const {}
1661 #endif
1662
1663 /// Depending on the use case, it might be appropriate to attach a value of template type \p{T}
1664 /// to the root node of the tree. If so, this can be done with this method. If not done, in
1665 /// debug compilations, the method #TCursor::Value will
1666 /// raise an \alib_assertion if called on the root node.
1667 ///
1668 /// Custom data that is explicitly attached to the root node with this method has to be
1669 /// deleted explicitly by calling #DestructRootValue before deletion of the tree.
1670 ///
1671 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1672 /// @param args Variadic parameters to be forwarded to the constructor of custom
1673 /// type \p{T} of the child created.
1674 template<typename... TArgs>
1675 void ConstructRootValue( TArgs&&... args ) {
1676 #if ALIB_DEBUG
1677 ALIB_ASSERT_WARNING( basetree::dbgRootDataSet != 1, "STRINGTREE",
1678 "Root node value is set without prior deletion. Possible memory leak (depending on\n "
1679 "allocation of template type T). This warning is only printed on the first overwrite.")
1680 ++basetree::dbgRootDataSet;
1681 #endif
1682
1683 new (&basetree::root.root.data) T( std::forward<TArgs>(args)... );
1684 }
1685
1686 /// Calls the destructor of the custom data object of type \p{T}, which may explicitly set using
1687 /// #ConstructRootValue.\n
1688 /// If not done, in debug-compilations, an \alib_warning is raised in the destructor
1689 /// of this tree.
1690 void DestructRootValue() {
1691 #if ALIB_DEBUG
1692 ALIB_ASSERT_ERROR( basetree::dbgRootDataSet != 0, "STRINGTREE",
1693 "Deletion of root node data without prior setting (or double deletion)." )
1694 --basetree::dbgRootDataSet;
1695 #endif
1696 basetree::root.root.data.~T();
1697 }
1698
1699 /// Removes all elements from this container. The use of this method is more efficient than
1700 /// deleting the children of the root node.
1701 ///
1702 /// Invokes \alib{containers;HashTable::Clear} on field
1703 /// \alib{containers::detail::StringTreeBase;nodeTable}. As documented with that method, the
1704 /// allocated nodes will be preserved for "recycling" with future insertions.
1705 ///
1706 /// The custom data of the root node is preserved.
1707 void Clear() {DCS
1708 // clear the nodes in the table, then the table itself
1709 for( auto& node : basetree::nodeTable )
1710 TNodeHandler::FreeNode( *static_cast<baseNode*>(&node), *this );
1711 basetree::nodeTable.Clear();
1712
1713 // re-initialize root node
1714 basetree::root.root.children.reset();
1715 basetree::root.root.qtyChildren= 0;
1716 }
1717
1718 /// Clears all nodes and values. The use of this method is more efficient than deleting the
1719 /// children of the root node.<br>
1720 /// In addition, depending on template type \p{TNodeHandler}, it may also declare allocated
1721 /// memory for future reuse.<br>
1722 /// The latter is true for type \alib{containers;StringTreeNamesAlloc}.
1723 ///
1724 /// Invokes \alib{containers;HashTable::Reset} on field
1725 /// \alib{containers::detail::StringTreeBase;nodeTable}.
1726 /// As documented with that method, in the case of \alib{containers;Recycling;private recycling},
1727 /// all previously allocated recyclable instances of the internal element type are disposed.
1728 ///
1729 /// \note The value of the root-node, set with #ConstructRootValue is not deleted.
1730 void Reset() {
1731 {DCS
1732 for( auto& node : basetree::nodeTable )
1733 TNodeHandler::FreeNode( *static_cast<baseNode*>(&node), *this );
1734 }
1735
1736 basetree::nodeTable.Reset();
1737 basetree::root.root.children.reset();
1738 basetree::root.root.qtyChildren= 0;
1739 }
1740
1741 /// Counts the number of currently allocated but unused (not contained) element nodes
1742 /// that will be recycled with upcoming insertions.
1743 ///
1744 /// \note
1745 /// This method is provided for completeness and unit-testing. It should not be of
1746 /// relevance for common usage.
1747 /// Furthermore, this method is not available (aka does not compile) with instantiations
1748 /// that specify template parameter \p{TRecycling} as
1749 /// \alib{containers;Recycling;None}.
1750 ///
1751 /// @return The number of removed and not yet recycled elements.
1752 integer RecyclablesCount() const { return basetree::nodeTable.RecyclablesCount(); }
1753
1754 /// Returns the overall number of elements contained in this tree.
1755 ///
1756 /// \note
1757 /// This method performs in constant time.
1758 ///
1759 /// @return The number elements contained in this tree.
1760 integer Size() const { return basetree::nodeTable.Size(); }
1761
1762 /// Tests for emptiness.
1763 ///
1764 /// @return \c true if this tree is empty, \c false otherwise.
1765 bool IsEmpty() const { return basetree::nodeTable.Size() == 0; }
1766
1767 /// Invokes \alib{containers;HashTable::ReserveRecyclables} on the internal hashtable.
1768 ///
1769 /// @see Chapter \ref alib_contmono_containers_recycling_reserving of the Programmer's
1770 /// Manual.
1771 ///
1772 /// @param qty The expected resulting number (or increase) of elements to be stored in
1773 /// this container.
1774 /// @param reference Denotes whether \p{qty} is meant as an absolute size or an
1775 /// increase.
1776 void ReserveRecyclables( integer qty, lang::ValueReference reference )
1777 { basetree::nodeTable.ReserveRecyclables( qty, reference ); }
1778
1779 /// Returns the internal \alib{containers;HashTable} used for storing the tree nodes.
1780 /// This may be used to manipulate load factors, for direct iteration over all nodes, etc.<br>
1781 /// \note The returned object should be used with caution to keep the tree and its data
1782 /// consistent.
1783 /// @return The internal node table.
1784 auto& NodeTable() { return basetree::nodeTable; }
1785
1786 /// Returns the internal \alib{containers;HashTable} used for storing the tree nodes.
1787 /// This may be used to manipulate load factors, for direct iteration over all nodes, etc.<br>
1788 /// \note The returned object should be used with caution to keep the tree and its data
1789 /// consistent.
1790 /// @return The internal node table.
1791 const auto& NodeTable() const { return basetree::nodeTable; }
1792
1793 /// Creates a cursor instance representing the root node.
1794 /// @return A cursor pointing to the root node of this \b %StringTree.
1795 Cursor Root() { return Cursor( &basetree::root.root, this ); }
1796
1797 /// Creates a \c const cursor instance representing the root node.
1798 /// @return A read-only pointer, pointing to the root node of this \b %StringTree.
1799 const ConstCursor Root() const { return ConstCursor( &basetree::root.root, this ); }
1800
1801 /// Imports a cursor previously exported with #TCursor::Export.
1802 /// @param handle The handle value.
1803 /// @return The imported cursor value.
1804 Cursor ImportCursor( CursorHandle handle )
1805 { return Cursor( reinterpret_cast<typename basetree::Node*>(handle.value), this ); }
1806
1807 /// Imports a cursor previously exported with #TCursor::Export.
1808 /// @param handle The handle value.
1809 /// @return The imported \c const cursor value.
1810 ConstCursor ImportCursor( ConstCursorHandle handle) const
1811 { return ConstCursor( reinterpret_cast<typename basetree::Node*>(handle.value), this ); }
1812
1813 #if !DOXYGEN
1814 #if ALIB_DEBUG_CRITICAL_SECTIONS
1815 #undef DCS
1816 #undef DCSSHRD
1817 #endif
1818 #endif
1819
1820}; // StringTree
1821
1822} // namespace alib::[containers]
1823
1824/// Type alias in namespace \b alib.
1825template<typename TChar, integer TLocalCapacity= 32>
1826using StringTreeNamesDynamic = containers::StringTreeNamesDynamic<TChar, TLocalCapacity>;
1827
1828/// Type alias in namespace \b alib.
1829template<typename TChar>
1830using StringTreeNamesStatic = containers::StringTreeNamesStatic<TChar>;
1831
1832/// Type alias in namespace \b alib.
1833template<typename TChar>
1834using StringTreeNamesAlloc = containers::StringTreeNamesAlloc<TChar>;
1835
1836/// Type alias in namespace \b alib.
1837template<typename TAllocator,
1838 typename T,
1839 typename TNodeHandler = StringTreeNamesDynamic<character>,
1840 Recycling TRecycling = Recycling::Private >
1841using StringTree = containers::StringTree<TAllocator, T, TNodeHandler, TRecycling>;
1842
1843
1844} // namespace [alib]
alib::containers::StringTree::TCursor::GoTo
SubstringType GoTo(const NameType &path)
Definition stringtree.inl:1137
alib::containers::StringTree::TCursor::Distance
int Distance(const TCursor< true > &other) const
Definition stringtree.inl:1323
alib::containers::StringTree::TCursor::TCursor
TCursor(cmNode *pNode, cmTree *pTree) noexcept
Definition stringtree.inl:728
alib::containers::StringTree::TCursor::operator!=
bool operator!=(const TCursor &other) const
Definition stringtree.inl:799
alib::containers::StringTree::TCursor::GoToCreatedPathIfNotExistent
integer GoToCreatedPathIfNotExistent(const NameType &path, TArgs &&... args)
Definition stringtree.inl:1185
alib::containers::StringTree::TCursor::operator()
std::pair< TCursor, SubstringType > operator()(const NameType &path) const
Definition stringtree.inl:1123
alib::containers::StringTree::TCursor::operator=
TCursor & operator=(const TCursor &) noexcept=default
alib::containers::StringTree::TCursor::CreateChild
TCursor CreateChild(const NameType &childName, TArgs &&... args) const
Definition stringtree.inl:1459
alib::containers::StringTree::TCursor::TStringTree
std::conditional_t<!TConst, StringTree, const StringTree > TStringTree
Definition stringtree.inl:751
alib::containers::StringTree::TCursor::DeleteChild
uinteger DeleteChild(TCursor &child) const
Definition stringtree.inl:1526
alib::containers::StringTree::TCursor::cmTree
std::conditional_t<!TConst, basetree, const basetree > cmTree
Definition stringtree.inl:714
alib::containers::StringTree::TCursor::Export
ConstCursorHandle Export() const
Definition stringtree.inl:818
alib::containers::StringTree::TCursor::cmNode
std::conditional_t<!TConst, baseNode, const baseNode > cmNode
Definition stringtree.inl:718
alib::containers::StringTree::TCursor::AssemblePath
strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > & AssemblePath(strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > &targetString, const TCursor< true > &parent, lang::CurrentData targetData=lang::CurrentData::Clear) const
Definition stringtree.inl:1418
alib::containers::StringTree::TCursor::Child
TCursor Child(const NameType &name) const
Definition stringtree.inl:997
alib::containers::StringTree::TCursor::GoToCreateChildIfNotExistent
bool GoToCreateChildIfNotExistent(const NameType &name, TArgs &&... args)
Definition stringtree.inl:1072
alib::containers::StringTree::TCursor::GoToChild
bool GoToChild(const NameType &name)
Definition stringtree.inl:1016
alib::containers::StringTree::TCursor::CreatePathIfNotExistent
std::pair< TCursor, integer > CreatePathIfNotExistent(const NameType &path, TArgs &&... args)
Definition stringtree.inl:1159
alib::containers::StringTree::TCursor::cmCursor
std::conditional_t<!TConst, baseCursor, baseConstCursor > cmCursor
Definition stringtree.inl:722
alib::containers::StringTree::TCursor::operator==
bool operator==(const TCursor &other) const
Definition stringtree.inl:790
alib::containers::StringTree::TCursor::CreateChildIfNotExistent
std::pair< TCursor, bool > CreateChildIfNotExistent(const NameType &name, TArgs &&... args)
Definition stringtree.inl:1045
alib::containers::StringTree::TCursor::operator=
TCursor & operator=(TCursor &&) noexcept=default
alib::containers::StringTree::TCursor::DeleteChild
bool DeleteChild(const NameType &childName) const
Definition stringtree.inl:1495
alib::containers::StringTree::TCursor::AssemblePath
strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > & AssemblePath(strings::TAString< typename cmTree::CharacterType > &targetString, lang::CurrentData targetData=lang::CurrentData::Clear) const
Definition stringtree.inl:1390
alib::containers::StringTree::ReserveRecyclables
void ReserveRecyclables(integer qty, lang::ValueReference reference)
Definition stringtree.inl:1776
alib::containers::StringTree::DbgGetDCS
lang::DbgCriticalSections & DbgGetDCS() const
Definition stringtree.inl:1647
alib::containers::StringTree::Separator
constexpr CharacterType Separator() const noexcept
Definition stringtree.inl:1652
alib::containers::StringTree::NodeTable
const auto & NodeTable() const
Definition stringtree.inl:1791
alib::containers::StringTree::ConstCursor
TCursor< true > ConstCursor
The constant version of type TCursor<TConst>.
Definition stringtree.inl:1575
alib::containers::StringTree< MonoAllocator, T, StringTreeNamesAlloc< character > >::CharacterType
typename StringTreeNamesAlloc< character >::CharacterType CharacterType
Definition stringtree.inl:597
alib::containers::StringTree::ImportCursor
Cursor ImportCursor(CursorHandle handle)
Definition stringtree.inl:1804
alib::containers::StringTree::Root
const ConstCursor Root() const
Definition stringtree.inl:1799
alib::containers::StringTree::createCursor
Cursor createCursor(baseNode &node)
Definition stringtree.inl:1582
alib::containers::StringTree::StringTree
StringTree(CharacterType pathSeparator, TSharedRecycler &pRecycler)
Definition stringtree.inl:1612
alib::containers::StringTree::DbgSetDCSName
void DbgSetDCSName(const char *name) const
Definition stringtree.inl:1658
alib::containers::StringTree::GetAllocator
AllocatorType & GetAllocator() noexcept
Definition stringtree.inl:1638
alib::containers::StringTree::Cursor
TCursor< false > Cursor
The mutable version of type TCursor<TConst>.
Definition stringtree.inl:1572
alib::containers::StringTree::StringTree
StringTree(AllocatorType &allocator, CharacterType pathSeparator)
Definition stringtree.inl:1600
alib::containers::StringTree::ConstructRootValue
void ConstructRootValue(TArgs &&... args)
Definition stringtree.inl:1675
alib::containers::StringTree::ImportCursor
ConstCursor ImportCursor(ConstCursorHandle handle) const
Definition stringtree.inl:1810
alib::strings::TString::CharAtStart
TChar CharAtStart() const
Definition string.inl:433
ALIB_DLL
#define ALIB_DLL
Definition alib.inl:503
ALIB_WARNING
#define ALIB_WARNING(domain,...)
Definition alib.inl:1063
ALIB_ASSERT_WARNING
#define ALIB_ASSERT_WARNING(cond, domain,...)
Definition alib.inl:1067
ALIB_EXPORT
#define ALIB_EXPORT
Definition alib.inl:497
ALIB_DBG
#define ALIB_DBG(...)
Definition alib.inl:853
ALIB_ASSERT_ERROR
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1066
alib::containers::DBG_STATS_STRINGTREE_NAMES
uinteger DBG_STATS_STRINGTREE_NAMES
Definition stringtreebase.cpp:30
alib::containers::DBG_STATS_STRINGTREE_NAME_OVERFLOWS
uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS
Definition stringtreebase.cpp:31
alib::lang::CurrentData::Clear
@ Clear
Chooses to clear existing data.
Definition commonenumdefs.inl:82
alib::lang::ValueReference
ValueReference
Denotes if a value is interpreted as an absolute or relative number.
Definition commonenumdefs.inl:208
alib::integer
lang::integer integer
Type alias in namespace alib.
Definition integers.inl:149
alib::StringTreeNamesStatic
containers::StringTreeNamesStatic< TChar > StringTreeNamesStatic
Type alias in namespace alib.
Definition stringtree.inl:1830
alib::Recycling
containers::Recycling Recycling
Type alias in namespace alib.
Definition recycling.inl:35
alib::StringTree
containers::StringTree< TAllocator, T, TNodeHandler, TRecycling > StringTree
Type alias in namespace alib.
Definition stringtree.inl:1841
alib::StringTreeNamesAlloc
containers::StringTreeNamesAlloc< TChar > StringTreeNamesAlloc
Type alias in namespace alib.
Definition stringtree.inl:1834
alib::uinteger
lang::uinteger uinteger
Type alias in namespace alib.
Definition integers.inl:152
alib::StringTreeNamesDynamic
containers::StringTreeNamesDynamic< TChar, TLocalCapacity > StringTreeNamesDynamic
Type alias in namespace alib.
Definition stringtree.inl:1826
alib::CHK
See sibling type NC.
Definition chk_nc.inl:33
alib::containers::StringTreeNamesAlloc::NameStringType
strings::TString< TChar > NameStringType
The string-type of a node's name.
Definition stringtree.inl:280
alib::containers::StringTreeNamesAlloc::FreeNode
static void FreeNode(typename TTree::baseNode &node, TTree &tree)
Definition stringtree.inl:323
alib::containers::StringTreeNamesAlloc::InitializeNode
static void InitializeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:302
alib::containers::StringTreeNamesAlloc::CharacterType
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
Definition stringtree.inl:277
alib::containers::StringTreeNamesDynamic::CharacterType
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
Definition stringtree.inl:102
alib::containers::StringTreeNamesDynamic::NameStringType
std::conditional_t<(TLocalCapacity > 0), strings::TLocalString< TChar, TLocalCapacity >, strings::TString< TChar > > NameStringType
The string-type of a node's name.
Definition stringtree.inl:105
alib::containers::StringTreeNamesDynamic::InitializeNode
static void InitializeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:125
alib::containers::StringTreeNamesDynamic::FreeNode
static void FreeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:160
alib::containers::StringTreeNamesStatic::FreeNode
static void FreeNode(TTree::Node &node, TTree &tree)
Definition stringtree.inl:242
alib::containers::StringTreeNamesStatic::CharacterType
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
Definition stringtree.inl:199
alib::containers::StringTreeNamesStatic::InitializeNode
static void InitializeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:222
alib::containers::StringTreeNamesStatic::NameStringType
strings::TString< TChar > NameStringType
The string-type of a node's name.
Definition stringtree.inl:202
alib::containers::StringTree::ConstCursorHandle
A handle type used with methods TCursor::Export and ImportCursor.
Definition stringtree.inl:639
alib::containers::StringTree::ConstCursorHandle::operator==
bool operator==(const CursorHandle &other) const noexcept
Definition stringtree.inl:664
alib::containers::StringTree::ConstCursorHandle::ConstCursorHandle
ConstCursorHandle(const CursorHandle &mutableHandle)
Definition stringtree.inl:651
alib::containers::StringTree::ConstCursorHandle::ConstCursorHandle
ConstCursorHandle()=default
Defaulted default constructor.
alib::containers::StringTree::ConstCursorHandle::value
uinteger value
The encapsulated value.
Definition stringtree.inl:640
alib::containers::StringTree::ConstCursorHandle::operator==
bool operator==(const ConstCursorHandle &other) const noexcept
Definition stringtree.inl:657
alib::containers::StringTree::CursorHandle
A handle type used with methods TCursor::Export and ImportCursor.
Definition stringtree.inl:623
alib::containers::StringTree::CursorHandle::value
uinteger value
The encapsulated value.
Definition stringtree.inl:624
alib::containers::StringTree::CursorHandle::operator==
bool operator==(const CursorHandle &other) const noexcept
Definition stringtree.inl:630
alib::containers::detail::StringTreeBase::nodeTable
HashTable< TAllocator, typename NodeKey::ValueDescriptor, typename NodeKey::Hash, typename NodeKey::EqualTo, lang::Caching::Enabled, TRecycling > nodeTable
Definition stringtreebase.inl:437
alib::containers::detail::StringTreeBase::checkChildName
bool checkChildName(const NameType &name) const
Definition stringtreebase.inl:674
alib::lang::AllocatorMember::GetAllocator
TAllocator & GetAllocator() const noexcept
Definition allocation.inl:671