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         2769 :         for (size_t i = 0; i < entry_count; i++)
      62              :         {
      63         2764 :             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