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