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 <stddef.h>
      21             : 
      22             : #include <array>
      23             : #include <limits>
      24             : 
      25             : namespace chip {
      26             : namespace FlatTree {
      27             : 
      28             : // A flat tree allows for tree data to be stored in a single flat
      29             : // array.
      30             : 
      31             : /// Invalid indexes in a tree
      32             : static constexpr size_t kInvalidNodeIndex = std::numeric_limits<size_t>::max();
      33             : 
      34             : /// An entry represents a single element identified by a key and containing a
      35             : /// value
      36             : ///
      37             : /// In a tree representation, every entry may potentially have a child node,
      38             : /// whose index is located in [node_index].
      39             : template <typename CONTENT>
      40             : struct Entry
      41             : {
      42             :     CONTENT data;
      43             : 
      44             :     // Node index is a valid index inside a node array if a entry has
      45             :     // child elements, it is kInvalidNodeIndex otherwise;
      46             :     size_t node_index;
      47             : };
      48             : 
      49             : template <typename CONTENT>
      50             : struct Node
      51             : {
      52             :     size_t entry_count;             // number of items in [entries]
      53             :     const Entry<CONTENT> * entries; // child items of [entry_count] size
      54             : 
      55             :     /// Attempt to find the entry with given matcher.
      56             :     ///
      57             :     /// Returns nullptr if no matches can be found.
      58             :     template <typename MATCHER>
      59         498 :     const Entry<CONTENT> * find_entry(MATCHER matcher) const
      60             :     {
      61        2858 :         for (size_t i = 0; i < entry_count; i++)
      62             :         {
      63        2853 :             if (matcher(entries[i].data))
      64             :             {
      65         493 :                 return &entries[i];
      66             :             }
      67             :         }
      68           5 :         return nullptr;
      69             :     }
      70             : };
      71             : 
      72             : /// Search for a given entry in a sized array
      73             : ///
      74             : /// [data] is the flat tree array
      75             : /// [idx] is the index of the node to search. If out of bounds, nullptr is returned
      76             : /// [matcher] is the match function.
      77             : template <typename CONTENT, typename MATCHER>
      78         536 : inline const Entry<CONTENT> * FindEntry(const Node<CONTENT> * content, size_t content_size, size_t idx, MATCHER matcher)
      79             : {
      80         536 :     if (idx >= content_size)
      81             :     {
      82          38 :         return nullptr;
      83             :     }
      84         498 :     return content[idx].find_entry(matcher);
      85             : }
      86             : 
      87             : /// Search for a given entry in an array (array will do bounds check)
      88             : ///
      89             : /// [data] is the flat tree array
      90             : /// [idx] is the index of the node to search. If out of bounds, nullptr is returned
      91             : /// [matcher] is the match function.
      92             : template <typename CONTENT, typename MATCHER, size_t N>
      93             : inline const Entry<CONTENT> * FindEntry(const std::array<Node<CONTENT>, N> & data, size_t idx, MATCHER matcher)
      94             : {
      95             :     return FindEntry(data.data(), N, idx, matcher);
      96             : }
      97             : 
      98             : } // namespace FlatTree
      99             : } // namespace chip