Line data Source code
1 : /*
2 : *
3 : * Copyright (c) 2023 Project CHIP Authors
4 : * All rights reserved.
5 : *
6 : * Licensed under the Apache License, Version 2.0 (the "License");
7 : * you may not use this file except in compliance with the License.
8 : * You may obtain a copy of the License at
9 : *
10 : * http://www.apache.org/licenses/LICENSE-2.0
11 : *
12 : * Unless required by applicable law or agreed to in writing, software
13 : * distributed under the License is distributed on an "AS IS" BASIS,
14 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 : * See the License for the specific language governing permissions and
16 : * limitations under the License.
17 : */
18 : #pragma once
19 :
20 : #include <lib/format/FlatTree.h>
21 : #include <lib/support/Span.h>
22 :
23 : namespace chip {
24 : namespace FlatTree {
25 :
26 : /// Represents a position inside a given tree, allowing for descending
27 : /// and ascending.
28 : ///
29 : /// A possition in the tree may be undefined if descending to a non-existing leaf,
30 : /// however the position still allows moving back again.
31 : ///
32 : /// DESCEND_DEPTH is the maximum remembered depth for going back up.
33 : ///
34 : /// General usage:
35 : ///
36 : /// Position<DataType, 10> position(tree, tree_size);
37 : ///
38 : /// position.Enter(ByName("foo"));
39 : /// position.Enter(ByName("bar"));
40 : /// position.Enter(ByName("baz"));
41 : ///
42 : /// position.Get() /// content of foo::bar::baz if it exists
43 : ///
44 : /// position.Exit();
45 : /// position.Exit();
46 : ///
47 : /// position.Get() /// content of foo if it exists
48 : ///
49 : /// position.Enter(ById(1234));
50 : ///
51 : /// position.Get() /// content of foo::1234
52 : ///
53 : template <typename CONTENT, size_t DESCEND_DEPTH>
54 : class Position
55 : {
56 : public:
57 56 : Position(const Node<CONTENT> * tree, size_t treeSize) : mTree(tree), mTreeSize(treeSize) {}
58 :
59 : template <size_t N>
60 : Position(const std::array<const Node<CONTENT>, N> & tree) : mTree(tree.data()), mTreeSize(N)
61 : {}
62 :
63 : // Move back to the top
64 153 : void ResetToTop()
65 : {
66 153 : mDescendDepth = 0;
67 153 : mUnknownDescendDepth = 0;
68 153 : }
69 :
70 : /// Attempt to find a child of the current position that matches
71 : /// the given matcher
72 : template <typename MATCHER>
73 : void Enter(MATCHER matcher);
74 :
75 : /// Move up the tree, undoes an 'Enter' operation.
76 : void Exit();
77 :
78 : /// Fetch the value where the node is positioned on or nullptr if that
79 : /// value is not available;
80 : const CONTENT * Get() const;
81 :
82 : /// Returns the entries visited so far
83 : ///
84 : /// WILL RETURN EMPTY if the descend depth has been
85 : /// exceeded. Callers MUST handle empty return.
86 : ///
87 : /// Span valid until one of Enter/Exit functions are called
88 : /// and as long as the Position is valid (points inside the object).
89 : chip::Span<const Entry<CONTENT> *> CurrentPath();
90 :
91 24 : bool HasValidTree() const { return mTree != nullptr; }
92 :
93 11 : size_t DescendDepth() const { return mDescendDepth + mUnknownDescendDepth; }
94 :
95 : private:
96 : // actual tree that we visit
97 : const Node<CONTENT> * mTree = nullptr;
98 : const size_t mTreeSize = 0;
99 :
100 : // Keeping track of descending into the tree, to be able to move back
101 : // last element in the array is the "current" item
102 : const Entry<CONTENT> * mPositions[DESCEND_DEPTH] = { nullptr };
103 : size_t mDescendDepth = 0; // filled amount of mDescendPositions
104 :
105 : // Descend past remembering memory or in not-found entries.
106 : size_t mUnknownDescendDepth = 0; // depth in invalid positions
107 : };
108 :
109 : template <typename CONTENT, size_t DESCEND_DEPTH>
110 920 : const CONTENT * Position<CONTENT, DESCEND_DEPTH>::Get() const
111 : {
112 920 : if (mUnknownDescendDepth > 0)
113 : {
114 137 : return nullptr;
115 : }
116 :
117 783 : if (mDescendDepth == 0)
118 : {
119 0 : return nullptr;
120 : }
121 :
122 783 : return &mPositions[mDescendDepth - 1]->data;
123 : }
124 :
125 : template <typename CONTENT, size_t DESCEND_DEPTH>
126 : template <typename MATCHER>
127 602 : void Position<CONTENT, DESCEND_DEPTH>::Enter(MATCHER matcher)
128 : {
129 602 : if (mUnknownDescendDepth > 0)
130 : {
131 : // keep descending into the unknown
132 66 : mUnknownDescendDepth++;
133 66 : return;
134 : }
135 :
136 : // To be able to descend, we have to be able to remember
137 : // the current position
138 536 : if (mDescendDepth == DESCEND_DEPTH)
139 : {
140 0 : mUnknownDescendDepth = 1;
141 0 : return;
142 : }
143 :
144 536 : size_t nodeIdx = 0; // assume root node
145 536 : if (mDescendDepth > 0)
146 : {
147 411 : nodeIdx = mPositions[mDescendDepth - 1]->node_index;
148 : }
149 :
150 536 : const Entry<CONTENT> * child = FindEntry(mTree, mTreeSize, nodeIdx, matcher);
151 :
152 536 : if (child == nullptr)
153 : {
154 43 : mUnknownDescendDepth = 1;
155 43 : return;
156 : }
157 :
158 493 : mPositions[mDescendDepth++] = child;
159 : }
160 :
161 : template <typename CONTENT, size_t DESCEND_DEPTH>
162 420 : void Position<CONTENT, DESCEND_DEPTH>::Exit()
163 : {
164 420 : if (mUnknownDescendDepth > 0)
165 : {
166 50 : mUnknownDescendDepth--;
167 50 : return;
168 : }
169 :
170 370 : if (mDescendDepth > 0)
171 : {
172 370 : mDescendDepth--;
173 : }
174 : }
175 :
176 : template <typename CONTENT, size_t DESCEND_DEPTH>
177 : chip::Span<const Entry<CONTENT> *> Position<CONTENT, DESCEND_DEPTH>::CurrentPath()
178 : {
179 : if (mUnknownDescendDepth > 0)
180 : {
181 : return chip::Span<const Entry<CONTENT> *>();
182 : }
183 :
184 : // const chip::FlatTree::Entry<{anonymous}::NamedTag>* const* to
185 : // const chip::FlatTree::Entry<{anonymous}::NamedTag>**
186 : typename chip::Span<const Entry<CONTENT> *>::pointer p = mPositions;
187 :
188 : // return chip::Span<const Entry<CONTENT> *>(mPositions, mDescendDepth);
189 : return chip::Span<const Entry<CONTENT> *>(p, mDescendDepth);
190 : }
191 :
192 : } // namespace FlatTree
193 : } // namespace chip
|
