ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
stringtreebase.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//==================================================================================================
9
10/// Base struct of \alib{containers;StringTree} providing internals.
11/// \note
12/// The separation of the internals of class \b StringTree to this type in namespace \b detail
13/// has no benefit on compilation speed or other positive "technical" effect, nor is it a matter
14/// of software design.<br>
15/// A user of derived class \alib{containers;HashTable} finds all interface methods and types
16/// in one place, which is not cluttered by the documentation of the internals found here.
17/// Otherwise, the separation is exclusively supporting source code organization.
18///
19/// @see For a description of the template parameters and a general introduction to the topic,
20/// se the reference documentation of the derived derived main class
21/// \alib{containers;StringTree}.
22template<typename TAllocator, typename T, typename TNodeHandler, Recycling TRecycling>
24{
25 // #############################################################################################
26 // Inner types
27 // #############################################################################################
28 struct NodeBase; // forward declaration
29 struct Node; // forward declaration
30
31 /// Alias shortcut for a bidirectional list of \b Node elements.
33
34 /// The character type of node names and paths strings. This is defined using character type
35 /// definition \alib{containers::StringTreeNamesDynamic;CharacterType} of template type
36 /// \p{TNodeHandler}.
37 using CharacterType = typename TNodeHandler::CharacterType;
38
39 /// The string-type of node names and paths if provided externally for comparison.
41
42 /// The string-type of node names and paths. This is defined by
43 /// \alib{containers::StringTreeNamesDynamic;NameStringType} of template type \p{TNodeHandler}.
44 using NameStorageType = typename TNodeHandler::NameStringType;
45
46 /// The substring-type of paths. This is defined using character type definition
47 /// \alib{containers::StringTreeNamesDynamic;CharacterType} of template type \p{TNodeHandler}.
49
50 /// The unique key to any element stored in this container.
51 /// By being a (second) base type for of type \alib{containers::detail::StringTreeBase;Node}, any
52 /// node includes this key.
53 struct NodeKey
54 {
55 /// The parent node. A value of \c nullptr indicates that this is the root node of
56 /// the tree, which is always existing.
58
59 /// A union of base string and the derived (or same) final storage type. Only the node
60 /// handler will finalize the name into the second field.
62 {
63 /// Constructor taking a key string. @param n The name of the node.
64 explicit NodeNameUnion(const NameType& n) : key(n) {}
65
66 /// Copy constructor. @param n The union to copy.
67 explicit NodeNameUnion(const NodeNameUnion& n) : key(n.key) {}
68
69 /// Destructor.
71
72 NameType key; ///< The name to compare when just keys are used.
73 NameStorageType storage; ///< The name when stored in the hashtable
74 };
75
76 /// A string object containing the pointer to this node's name.
77 /// Node names constitute path strings and, together with the pointer to their parent, form
78 /// the key of the hash set found with field \alib{containers::detail::StringTreeBase;nodeTable}.
79 /// <br>
80 /// Node names must not contain the separator character and must not equal to <c>"."</c> or
81 /// <c>".."</c>.
82 ///
83 /// The name of the root node is nulled.
85
86 /// Constructor
87 /// @param pParent Parent node to search a child for.
88 /// @param pName Child name to search
89 NodeKey( NodeBase* pParent, const NameType& pName )
90 : parent(pParent)
91 , name( pName )
92 {}
93
94 /// Hash functor for nodes hashed in field #nodeTable.
95 struct Hash
96 {
97 /// Calculates a hash code for \b NodeKey objects.
98 /// @param key The key to hash.
99 /// @return The hash code.
100 std::size_t operator()(const NodeKey& key) const
101 {
102 return key.name.key.Hashcode()
103 + reinterpret_cast<std::size_t>(key.parent) * 29;
104 }
105 };
106
107 /// Equality functor for nodes in field #nodeTable.
108 struct EqualTo
109 {
110 /// Invokes \alib{strings;TString::Equals;String::Equals} on \p{lhs}, passing \p{rhs}
111 /// and returns the result.
112 /// @param lhs The first string object.
113 /// @param rhs The second string object.
114 /// @return The result of the string comparison.
115 bool operator()(const NodeKey& lhs,
116 const NodeKey& rhs ) const
117 {
118 return lhs.parent == rhs.parent
119 && lhs.name.key. template Equals<NC>( rhs.name.key );
120 }
121 };
122
123 /// ValueDescriptor for hash table #nodeTable.
125 {
126 /// Casts given \p{src} down to its base class
127 /// \alib{containers::detail::StringTreeBase;NodeKey}.
128 /// @param src The node to receive the key-portion for.
129 /// @return The key-portion of the node.
130 NodeKey& Key( NodeBase& src ) const { return static_cast<NodeKey&>( src ); }
131 };
132 };
133
134 /// This is the base class of the internal node type \alib{containers::detail::StringTreeBase;Node}.
135 /// This type implements functionality needed. Derived type \b Node then only adds the custom
136 /// value \p T.
137 ///
138 /// Objects of this type cannot be received directly and all interface is available
139 /// via public type \alib{containers;StringTree::Cursor} only, which holds a pointer to
140 /// an object of this class.
142 public NodeKey
143 {
144 /// The number of children currently stored in this node.
146
147 /// The hook to the doubly linked list of children.
149
150 /// Constructor.
151 /// @param pKey The key portion of the node.
152 NodeBase(const NodeKey& pKey)
153 : NodeKey ( pKey )
154 , qtyChildren(0)
155 {}
156
157 /// Constructor. Custom data is default-initialized.
158 /// @param pParent Parent node to search a child for.
159 /// @param pName Child name to search
160 NodeBase( NodeBase* pParent, const NameType& pName)
161 : NodeKey ( pParent, pName )
162 , qtyChildren(0)
163 {}
164
165 /// Returns \c true if this is the root node, \c false otherwise.
166 /// @return \c true if this is the root node, \c false otherwise.
167 bool isRoot() const
168 {
169 return NodeKey::parent == nullptr;
170 }
171
172 /// Searches a child with a given name.
173 /// The name is not checked for <c>.</c>, <c>..</c> or if separation characters.
174 ///
175 /// @param tree The tree this node belongs to.
176 /// @param childName The name of the child to search.
177 /// @return The child or \c nullptr if not found.
178 NodeBase* findChild( StringTreeBase* tree, const NameType& childName )
179 {
180 if( qtyChildren == 0 )
181 return nullptr;
182
183 // With a small number of children, the search is faster if we iterate, because
184 // a) no hash value has to be calculated and
185 // b) the string compare is fast, at least if string have different length or are
186 // different at the beginning.
187 // A good value is probably five children. With bigger numbers, it soon becomes better
188 // to calculate the hash value. While in the bucket also children of other nodes
189 // are found, each entry of the hashtable is first compared against the full hash code.
190 if( qtyChildren <= 5 )
191 {
192 NodeBase* childIt= children.first();
193 while( childIt != &children.hook )
194 {
195 if( childIt->name.key. template Equals<NC>( childName ) )
196 return childIt;
197 childIt= childIt->next();
198 }
199
200 return nullptr;
201 }
202
203 // search in hash table
204 auto childIt= tree->nodeTable.Find( NodeKey( this, childName ) );
205 return childIt != tree->nodeTable.end() ? &childIt.Value()
206 : nullptr;
207 }
208
209 /// Iterates over the parent nodes to the root node and returns this node's depth.
210 /// @return The depth of this node.
211 int depth() const
212 {
213 int result= -1;
214 const NodeBase* p= this;
215 while( p != nullptr )
216 {
217 ++result;
218 p= p->parent;
219 }
220 return result;
221 }
222
223 /// Iterates over the parent nodes and searches given \p{other} in the path.
224 /// @param other The node to calculate the distance to.
225 /// @return The distance of \p{other} to this node.
226 /// \c 0 if the nodes are the same.
227 /// \c -1 if \p{other} was not found.
228 int distance( const NodeBase* other ) const
229 {
230 int result= 0;
231 const NodeBase* p= this;
232 while( p != nullptr )
233 {
234 if( p == other )
235 return result;
236 ++result;
237 p= p->parent;
238 }
239 return -1;
240 }
241
242 /// Searches a child with a given name, if not found, one is created.
243 /// The name is not checked for <c>.</c>, <c>..</c> or if separation characters.
244 ///
245 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
246 /// @param tree The tree this node belongs to.
247 /// @param childName The name of the child to search.
248 /// @param args Variadic parameters to be forwarded to the constructor of custom type
249 /// \p{T} in the case a child is created.
250 /// @return A pair containing an iterator referencing either the element found or the new
251 /// element added.
252 /// The bool component is \c true if the insertion took place and \c false nothing
253 /// was changed.
254 template<typename... TArgs>
255 std::pair<NodeBase*,bool> findOrCreateChild( StringTreeBase* tree,
256 const NameType& childName,
257 TArgs&&... args )
258 {
259 auto childCreation= tree->nodeTable.EmplaceIfNotExistent( NodeKey(this, childName),
260 std::forward<TArgs>(args)...);
261 NodeBase* child= &childCreation.first.Value();
262
263 if( childCreation.second )
264 {
265 TNodeHandler::InitializeNode( *tree, *static_cast<Node*>(child ) );
266 children.pushEnd( child );
267 ++qtyChildren;
268 }
269
270 return std::make_pair( child, childCreation.second );
271 }
272
273 /// Deletes a given child node.
274 /// \note
275 /// If the given node is not a child of this node, the behavior is undefined.
276 /// With debug-builds, in this case an \alib assertion is raised.
277 ///
278 /// @param tree The tree this node belongs to.
279 /// @param child A pointer to a child of this node that is to be deleted.
280 /// @return The total number of nodes deleted.
282 {
284 "STRINGTREE", "This node has no children to remove")
285 ALIB_ASSERT_ERROR( child->parent == this,
286 "STRINGTREE", "The given node is not a child of this node.")
287
288 --qtyChildren;
289 child->remove(); // remove from linked list
290 auto count= child->deleteChildren( tree );
291 auto handle= tree->nodeTable.Extract( *child );
292 ALIB_ASSERT( !handle.IsEmpty(), "STRINGTREE" )
293 TNodeHandler::FreeNode( *tree, handle.Value() );
294
295 return count + 1;
296 }
297
298 /// Deletes all child nodes.
299 /// @param tree The tree this node belongs to.
300 /// @return The number of children that were deleted.
302 {
303 if( children.isEmpty() )
304 return 0;
305
307
308 auto* child= children.first();
309 while( child != &children.hook )
310 {
311 count+= child->deleteChildren( tree ); // recursion
312 auto handle= tree->nodeTable.Extract( *child ); ALIB_ASSERT( !handle.IsEmpty(), "STRINGTREE")
313 TNodeHandler::FreeNode( *tree, handle.Value() );
314 child= child->next();
315 --qtyChildren;
316 }
317
318 ALIB_ASSERT(qtyChildren == 0, "STRINGTREE")
319 children.reset();
320 return count;
321 }
322
323 /// Implementation of
324 /// \alib{containers;StringTree<T,TNodeHandler,TRecycling>;TCursor::AssemblePath}.
325 ///
326 /// @param target The target to append the path to.
327 /// @param childNode The (current) child node.
328 /// @param maxParent The last parent node to travel up to. The root node is designated
329 /// by \c nullptr.
330 /// @param separatorChar The separator character as defined with the template parameter of
331 /// class \alib{containers;StringTree}.
332 /// @return The given \b AString to allow concatenated operations on it.
335 lang::HeapAllocator>& target,
336 const NodeBase* childNode,
337 const NodeBase* maxParent,
338 CharacterType separatorChar ) const
339 {
340 static constexpr int STACK_SIZE= 32;
341 const NodeBase* nStack[STACK_SIZE];
342
343 // build stack
344 int sp =1;
345 nStack[0] = childNode;
346 while( childNode->parent != maxParent )
347 {
348 childNode= childNode->parent;
349 if( childNode == nullptr)
350 break;
351
352 // local stack full? -> let a recursive call do the rest
353 if(sp == STACK_SIZE)
354 {
355 assemblePath( target, childNode, maxParent, separatorChar );
356 break;
357 }
358 nStack[sp++]= childNode;
359 }
360
361 // unroll stack now from top to bottom
362 while( --sp >= 0)
363 {
364 if( nStack[sp]->parent != nullptr )
365 {
366 if( target.CharAtEnd() != separatorChar
367 && nStack[sp]->parent != maxParent )
368 target << separatorChar;
369
370 target << nStack[sp]->name.key;
371 }
372 else
373 target << separatorChar;
374 }
375
376 return target;
377 }
378 }; // inner class NodeBase
379
380 /// This is the "final" internal node type, just adds a field of template type \p{T}
381 /// to its base class.
382 ///
383 /// Objects of this type cannot be received directly, and all interfaces are available
384 /// via public type \alib{containers;StringTree::Cursor} only, which holds a pointer to
385 /// an object of this class.
386 struct Node : public NodeBase
387 {
388 /// The templated custom data object stored with each node.
390
391 /// Deleted copy constructor.
392 Node( const Node& ) = delete;
393
394 /// Deleted move constructor.
395 Node( Node&& ) = delete;
396
397 /// Constructor. Custom data is default-initialized.
398 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
399 /// @param pKey The key portion of the node.
400 /// @param args Variadic parameters. Forwarded to the constructor of custom type \p{T}.
401 template<typename... TArgs>
402 Node( const NodeKey& pKey, TArgs&&... args )
403 : NodeBase( pKey )
404 , data ( std::forward<TArgs>(args)... )
405 {}
406
407 /// Constructor. Custom data is default-initialized.
408 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
409 /// @param pParent Parent node to search a child for.
410 /// @param pName Child name to search
411 /// @param args Variadic parameters. Forwarded to the constructor of custom type \p{T}.
412 template<typename... TArgs>
413 Node( NodeBase* pParent, const NameType& pName, TArgs&&... args )
414 : NodeBase( pParent, pName )
415 , data ( std::forward<TArgs>(args)... )
416 {}
417
418 }; // inner class Node
419
420 // #############################################################################################
421 // StringTreeBase: members
422 // #############################################################################################
423 /// This is a union of either a node with a custom object or without. This tricks us into the
424 /// position to embed the memory for a custom type which may optionally be assigned to the root
425 /// node, without constructing it.
426 /// Construction will only be done with explicit use of method
427 /// \alib{containers;StringTree::ConstructRootValue}.
429 {
430 NodeBase rootBase; ///< Base version of the root node, which becomes initialized.
431 Node root; ///< Full version of the root node, without initialization of member T.
432
433 /// Explicitly implement otherwise implicitly deleted constructor
434 RootNodeSpacer() : rootBase( nullptr, nullptr) {}
435
436 /// Destructor
438 };
439
440 /// The root node.
441 RootNodeSpacer root;
442
443 #if ALIB_DEBUG
444 /// Flag available only in debug-compilations to detect access to root node's value
445 /// without prior use of method \alib{containers::StringTree;ConstructRootValue}. Also, the
446 /// destructor issues a warning, in case the root node's value was not deleted with
447 /// \alib{containers::StringTree;DestructRootValue}.
449 #endif
450
451
452 /// The separator character to use with path strings.
453 /// This is set once with construction.
455
456 /// Hash set which contains all children of all nodes.
457 /// This is used to find children of nodes by their parent/name combination.
458 HashTable< TAllocator,
459 typename NodeKey::ValueDescriptor,
460 typename NodeKey::Hash,
461 typename NodeKey::EqualTo,
463 TRecycling > nodeTable;
464
465 /// This type definition may be used to define an externally managed shared recycler,
466 /// which can be passed to the alternative constructor of this class when template
467 /// parameter \p{TRecycling} equals \alib{containers;Recycling;Shared}.
468 /// \see
469 /// Chapter \ref alib_contmono_containers_recycling_shared of the Programmer's Manual
470 /// for this \alibmod.
472
473
474 // #############################################################################################
475 // class TCursorBase
476 // #############################################################################################
477 /// Base class for \alib{containers;StringTree::Cursor}
478 /// @tparam TConst If true, internal fields representing the StringTree and the current Node
479 /// become \c const and the method #followPathCreate becomes unavailable.
480 template<bool TConst>
482 {
483 /// Constant or mutable version of the base tree type, depending on template parameter \p{TConst}
484 using cmTree = std::conditional_t<!TConst, StringTreeBase, const StringTreeBase>;
485
486 /// Constant or mutable version of type \b NodeBase, depending on template parameter \p{TConst}
487 using cmNodeBase = std::conditional_t<!TConst, NodeBase, const NodeBase>;
488
489 /// Constant or mutable version of type \b Node, depending on template parameter \p{TConst}
490 using cmNode = std::conditional_t<!TConst, Node, const Node>;
491
492
493 /// The \b %StringTree this object refers to.
495
496 /// The currently represented node of the #tree.
498
499 /// Constructor initializing both fields #tree and #node.
500 /// @param pTree The \b %StringTree we work on.
501 /// @param pNode The node to refer to.
502 TCursorBase( cmTree* pTree, cmNode* pNode) noexcept
503 : tree( pTree )
504 , node( pNode )
505 {}
506
507 /// Default constructor. Creates an invalid (uninitialized) object.
508 TCursorBase() noexcept
509 : tree( nullptr )
510 , node( nullptr )
511 {}
512
513 /// Trivial default copy constructor.
514 TCursorBase( const TCursorBase& ) noexcept = default;
515
516 /// Trivial default move constructor.
517 TCursorBase( TCursorBase&& ) noexcept = default;
518
519 /// Trivial default copy assign operator.
520 /// @return A reference to \c this.
521 TCursorBase& operator=( const TCursorBase& ) noexcept = default;
522
523 /// Trivial default move assign operator.
524 /// @return A reference to \c this.
525 TCursorBase& operator=( TCursorBase&& ) noexcept = default;
526
527 /// Trivial default destructor.
528 ~TCursorBase() noexcept = default;
529
530
531 /// Finds a child node along the \p{path} given, but does not create new nodes.
532 /// Incomplete results may occur if a child along the path was not found.
533 /// In this case, parameter \p{path} contains the remaining path, excluding a leading
534 /// separator.
535 ///
536 /// A leading slash (aka \p{TSeparator}) allows absolute path addressing, which means
537 /// the root of \p{node} is searched if a leading separator is found.
538 ///
539 /// Besides normal child names, this method accepts
540 /// - multiple separator characters (ignored)
541 /// - child name "." (ignored)
542 /// - child name ".." for parent node
543 ///
544 /// @param[in,out] path Creation path. Provided as reference and consumed as far
545 /// as the path exits.
546 /// @return The node found
548 {
549 cmNodeBase* actNode= node;
550
551 // check for "root addressing"
552 if( path.CharAtStart() == tree->separator )
553 {
554 path.ConsumeChars( 1 );
555 while( actNode->parent != nullptr )
556 actNode= actNode->parent;
557 }
558
559 // loop over node names in path
560 for(;;)
561 {
562 // multiple separators are ignored
563 while(path.ConsumeChar( tree->separator ) )
564 ;
565
566 if( path.IsEmpty() )
567 return static_cast<cmNode*>(actNode);
568
569
570 NameType name=path.template Substring<NC>(0, path.IndexOfOrLength(tree->separator));
571
572
573 if( name.Length() == 2 && name[0] == '.' && name[1] == '.' )
574 {
575 // we move up only if possible. If not, the ".." is just ignored (consumed)
576 // (This behavior was just more helpful in the use cases so far)
577 if( actNode->parent != nullptr )
578 actNode= actNode->parent;
579 }
580
581 else if( name.Length() != 1 || name[0] != '.' )
582 {
583 cmNodeBase* child= actNode->findChild( tree, name );
584 if( child == nullptr )
585 return static_cast<cmNode*>(actNode);
586
587 actNode= child;
588 }
589
590 path.ConsumeChars( name.Length() );
591 }
592 }
593
594 /// Follows the given path and creates non-existing children along the way.
595 ///
596 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected same
597 /// as in #followPath.
598 ///
599 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
600 /// remain untouched.
601 ///
602 /// \note This method is only available if the template parameter \p{TConst} of this
603 /// type is \c false.
604 /// @tparam TRequires Defaulted template parameter. Must not be specified.
605 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
606 /// @param path The path to move along.
607 /// @param args Variadic parameters to be forwarded to the constructor of each node
608 /// that is created.
609 /// @return A <c>std::pair</c> containing a resulting \b Node* and the number of nodes
610 /// created.
611 template<typename... TArgs, bool TRequires= !TConst >
612 requires TRequires
613 std::pair<cmNodeBase*, integer>
614 followPathCreate( const NameType& path, TArgs&&... args )
615 {
616 std::pair<cmNodeBase*, integer> result= std::make_pair( node, 0 );
617 cmNodeBase*& actNode= result.first; // a local alias name, let the compiler decide
618
619 SubstringType rest= path;
620
621 // check for "root addressing"
622 if( rest.CharAtStart() == tree->separator )
623 {
624 rest.ConsumeChars( 1 );
625 while( actNode->parent != nullptr )
626 actNode= actNode->parent;
627 }
628
629 // loop over path string
630 for(;;)
631 {
632 // consume '/' and check for emptiness
633 while(rest.ConsumeChar( tree->separator ) )
634 ;
635 if( rest.IsEmpty() )
636 return result;
637
638 NameType childName= rest.template Substring<NC>( 0,
639 rest.IndexOfOrLength( tree->separator ) );
640
641 // "." or ".."?
643 if( childName[0] == '.' )
645 {
646 if( childName.Length() == 1 )
647 continue;
648 if( childName.Length() == 2 && childName[1] != '.' )
649 {
650 if ( !actNode->isRoot() )
651 actNode= actNode->parent;
652 continue;
653 }
654 }
655
656 auto childCreation= actNode->findOrCreateChild( tree, childName,
657 std::forward<TArgs>(args)... );
658
659 if( childCreation.second )
660 ++result.second;
661
662 actNode= childCreation.first;
663 rest.ConsumeChars( childName.Length() + 1);
664 }
665 }
666 }; // inner class TCursorBase
667
668 /// The mutable version of type \alib{containers::detail;StringTreeBase::TCursorBase<TConst>}.
670
671 /// The constant version of type \alib{containers::detail;StringTreeBase::TCursorBase<TConst>}.
673
674 // #############################################################################################
675 // StringTreeBase interface
676 // #############################################################################################
677 //==============================================================================================
678 /// Constructor.
679 /// @param allocator The monotonic allocator to use.
680 /// @param pathSeparator The separation character used with path strings.
681 //==============================================================================================
682 StringTreeBase( TAllocator& allocator, CharacterType pathSeparator )
683 : separator( pathSeparator )
684 , nodeTable( allocator )
685 {}
686
687 //==============================================================================================
688 /// Constructor taking a shared recycler.
689 /// @param allocator The monotonic allocator to use.
690 /// @param pRecycler The shared recycler.
691 /// @param pathSeparator The separation character used with path strings.
692 //==============================================================================================
693 template<typename TSharedRecycler= SharedRecyclerType>
694 requires ( !std::same_as<TSharedRecycler , void> )
695 StringTreeBase( TAllocator& allocator, TSharedRecycler& pRecycler, CharacterType pathSeparator )
696 : separator( pathSeparator )
697 , nodeTable( allocator, pRecycler )
698 {}
699
700 //==============================================================================================
701 /// Constructor taking a shared recycler.
702 /// @param pRecycler The shared recycler.
703 /// @param pathSeparator The separation character used with path strings.
704 /// @tparam TSharedRecycler Used to select this constructor. Deduced by the compiler.
705 //==============================================================================================
706 template<typename TSharedRecycler= SharedRecyclerType>
707 requires (!std::same_as<TSharedRecycler, void>)
708 StringTreeBase( TSharedRecycler& pRecycler, CharacterType pathSeparator )
709 : separator( pathSeparator )
710 , nodeTable( pRecycler )
711 {}
712
713 /// @return Returns the allocator received with construction.
714 TAllocator& GetAllocator() noexcept { return nodeTable.GetAllocator(); }
715
716 /// Simple helper method which checks a node name for not being <c>"."</c> or <c>".."</c>
717 /// and for not containing a separator character.
718 /// In debug-compilations, if it does, a \ref alib_mod_assert "warning is raised".
719 ///
720 /// @param name The child name to check.
721 /// @return \c true if the name is legal, false otherwise.
722 bool checkChildName( const NameType& name ) const
723 {
724 if( name.IsEmpty()
725 || ( name[0] == '.'
726 && ( name.Length() == 1 || ( name[1] == '.'
727 && name.Length() == 2 ) ) )
728 || name.IndexOf( separator) >=0 )
729 {
730 ALIB_WARNING( "STRINGTREE", "Illegal child name \"{}\".", name )
731 return false;
732 }
733 return true;
734 }
735
736}; // StringTreeBase
737
738
739} // namespace [alib::containers::detail]
constexpr integer Length() const
Definition string.inl:318
constexpr bool IsEmpty() const
Definition string.inl:367
integer IndexOf(TChar needle, integer startIdx=0) const
Definition string.inl:844
std::size_t Hashcode() const
#define ALIB_WARNINGS_UNINITIALIZED_OFF
Definition alib.inl:604
#define ALIB_ASSERT(cond, domain)
Definition alib.inl:1048
#define ALIB_WARNINGS_RESTORE
Definition alib.inl:705
#define ALIB_WARNING(domain,...)
Definition alib.inl:1046
#define ALIB_EXPORT
Definition alib.inl:488
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1049
Detail namespace of module ALib Containers.
@ Enabled
Caching is enabled.
lang::uinteger uinteger
Type alias in namespace alib.
Definition integers.inl:152
strings::TSubstring< character > Substring
Type alias in namespace alib.
NodeList children
The hook to the doubly linked list of children.
strings::TAString< CharacterType, lang::HeapAllocator > & assemblePath(strings::TAString< CharacterType, lang::HeapAllocator > &target, const NodeBase *childNode, const NodeBase *maxParent, CharacterType separatorChar) const
NodeBase(NodeBase *pParent, const NameType &pName)
uinteger qtyChildren
The number of children currently stored in this node.
uinteger deleteChild(StringTreeBase *tree, NodeBase *child)
NodeBase * findChild(StringTreeBase *tree, const NameType &childName)
std::pair< NodeBase *, bool > findOrCreateChild(StringTreeBase *tree, const NameType &childName, TArgs &&... args)
Equality functor for nodes in field nodeTable.
bool operator()(const NodeKey &lhs, const NodeKey &rhs) const
Hash functor for nodes hashed in field nodeTable.
NodeKey(NodeBase *pParent, const NameType &pName)
Node(const Node &)=delete
Deleted copy constructor.
T data
The templated custom data object stored with each node.
Node(const NodeKey &pKey, TArgs &&... args)
Node(Node &&)=delete
Deleted move constructor.
Node(NodeBase *pParent, const NameType &pName, TArgs &&... args)
TCursorBase() noexcept
Default constructor. Creates an invalid (uninitialized) object.
TCursorBase(cmTree *pTree, cmNode *pNode) noexcept
std::conditional_t<!TConst, NodeBase, const NodeBase > cmNodeBase
Constant or mutable version of type NodeBase, depending on template parameter TConst
std::pair< cmNodeBase *, integer > followPathCreate(const NameType &path, TArgs &&... args)
TCursorBase(const TCursorBase &) noexcept=default
Trivial default copy constructor.
std::conditional_t<!TConst, Node, const Node > cmNode
Constant or mutable version of type Node, depending on template parameter TConst
std::conditional_t<!TConst, StringTreeBase, const StringTreeBase > cmTree
Constant or mutable version of the base tree type, depending on template parameter TConst
TCursorBase(TCursorBase &&) noexcept=default
Trivial default move constructor.
typename strings::TSubstring< CharacterType > SubstringType
lang::BidiListHook< NodeBase > NodeList
Alias shortcut for a bidirectional list of Node elements.
StringTreeBase(TAllocator &allocator, TSharedRecycler &pRecycler, CharacterType pathSeparator)
typename decltype(nodeTable)::SharedRecyclerType SharedRecyclerType
typename TNodeHandler::CharacterType CharacterType
StringTreeBase(TSharedRecycler &pRecycler, CharacterType pathSeparator)
typename TNodeHandler::NameStringType NameStorageType
StringTreeBase(TAllocator &allocator, CharacterType pathSeparator)
const strings::TString< CharacterType > NameType
The string-type of node names and paths if provided externally for comparison.
HashTable< TAllocator, typename NodeKey::ValueDescriptor, typename NodeKey::Hash, typename NodeKey::EqualTo, lang::Caching::Enabled, TRecycling > nodeTable
bool checkChildName(const NameType &name) const
TCursorBase< false > CursorBase
The mutable version of type StringTreeBase::TCursorBase<TConst>.
TCursorBase< true > ConstCursorBase
The constant version of type StringTreeBase::TCursorBase<TConst>.
void remove() noexcept
Unhooks this node from a list.
Definition bidilist.inl:99
void next(SidiNodeBase *p)
Definition sidilist.inl:95
integer count(SidiNodeBase *end=nullptr) const noexcept
Definition sidilist.inl:159
NameType key
The name to compare when just keys are used.
NameStorageType storage
The name when stored in the hashtable.
NodeNameUnion(const NameType &n)
Constructor taking a key string.
Node root
Full version of the root node, without initialization of member T.
RootNodeSpacer()
Explicitly implement otherwise implicitly deleted constructor.
NodeBase rootBase
Base version of the root node, which becomes initialized.