Line data Source code
1 : /*
2 : * Copyright (c) 2024 Project CHIP Authors
3 : *
4 : * Licensed under the Apache License, Version 2.0 (the "License");
5 : * you may not use this file except in compliance with the License.
6 : * You may obtain a copy of the License at
7 : *
8 : * http://www.apache.org/licenses/LICENSE-2.0
9 : *
10 : * Unless required by applicable law or agreed to in writing, software
11 : * distributed under the License is distributed on an "AS IS" BASIS,
12 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : * See the License for the specific language governing permissions and
14 : * limitations under the License.
15 : */
16 : #pragma once
17 :
18 : #include <cstddef>
19 : #include <lib/support/Span.h>
20 :
21 : #include <optional>
22 :
23 : namespace chip {
24 :
25 : /// represents a wrapper around a type `T` that contains internal
26 : /// `Span<...>` values of other sub-types. It allows searching within the container sub-spans
27 : /// to create new containers.
28 : ///
29 : /// The use case is that we very often search within nested containers, like "find-endpoint" + "find-cluster" + "find-attribute"
30 : /// and we generally only care about "does the last element exist or not"
31 : ///
32 : /// A typical example of the way this class is used looks like this:
33 : ///
34 : /// SpanSearchValue container(somePointer);
35 : ///
36 : /// const AcceptedCommandData * value =
37 : /// container
38 : /// .Find<ByEndpoint>(path.mEndpointId, mEndpointIndexHint)
39 : /// .Find<ByServerCluster>(path.mClusterId, mServerClusterHint)
40 : /// .Find<ByAcceptedCommand>(path.mCommandId, mAcceptedCommandHint)
41 : /// .Value();
42 : ///
43 : /// Where a `ByFoo` structure looks like:
44 : ///
45 : /// struct ByFoo {
46 : /// using Key = int; // the KEY inside a type
47 : /// using Type = SomeValueType; // The type that is indexed by `Key`
48 : ///
49 : /// /// Allows getting the "Span of Type" from an underlying structure.
50 : /// /// A `SpanSearchValue<Foo>` will require a `GetSpan(Foo&)`
51 : /// static Span<Type> GetSpan(ContainerType & data) { /* return ... */ }
52 : ///
53 : /// /// Checks that the `Type` value has the given `Key` or not
54 : /// static bool HasKey(const Key & id, const Type & instance) { /* return "instance has key id" */ }
55 : /// }
56 : ///
57 : /// Where we define:
58 : /// - how to get a "span of sub-elements" for an object (`GetSpan`)
59 : /// - how to determine if a given sub-element has the "correct key"
60 : template <typename T>
61 : class SpanSearchValue
62 : {
63 : public:
64 : SpanSearchValue() : mValue(nullptr) {}
65 4 : SpanSearchValue(std::nullptr_t) : mValue(nullptr) {}
66 14 : explicit SpanSearchValue(T * value) : mValue(value) {}
67 :
68 : /// Returns nullptr if such an element does not exist or non-null valid value if the element exists
69 9 : T * Value() const { return mValue; }
70 :
71 : /// Gets the first element of `TYPE::Type`
72 : template <typename TYPE>
73 3 : SpanSearchValue<typename TYPE::Type> First(unsigned & indexHint)
74 : {
75 : // if no value, searching more also yields no value
76 3 : VerifyOrReturnValue(mValue != nullptr, nullptr);
77 :
78 3 : Span<typename TYPE::Type> value_span = TYPE::GetSpan(*mValue);
79 3 : VerifyOrReturnValue(!value_span.empty(), nullptr);
80 :
81 : // found it, save the hint
82 2 : indexHint = 0;
83 2 : return SpanSearchValue<typename TYPE::Type>(&value_span[0]);
84 : }
85 :
86 : /// Find the value corresponding to `key`
87 : template <typename TYPE>
88 : SpanSearchValue<typename TYPE::Type> Find(typename TYPE::Key key, unsigned & indexHint)
89 : {
90 : VerifyOrReturnValue(mValue != nullptr, nullptr);
91 :
92 : Span<typename TYPE::Type> value_span = TYPE::GetSpan(*mValue);
93 :
94 : if (!FindIndexUsingHint(key, value_span, indexHint, TYPE::HasKey))
95 : {
96 : return nullptr;
97 : }
98 :
99 : return SpanSearchValue<typename TYPE::Type>(&value_span[indexHint]);
100 : }
101 :
102 : /// Finds the value that occurs after `key` in the underlying collection.
103 : template <typename TYPE>
104 6 : SpanSearchValue<typename TYPE::Type> Next(typename TYPE::Key key, unsigned & indexHint)
105 : {
106 6 : VerifyOrReturnValue(mValue != nullptr, nullptr);
107 :
108 6 : Span<typename TYPE::Type> value_span = TYPE::GetSpan(*mValue);
109 :
110 6 : if (!FindIndexUsingHint(key, value_span, indexHint, TYPE::HasKey))
111 : {
112 1 : return nullptr;
113 : }
114 :
115 5 : VerifyOrReturnValue((indexHint + 1) < value_span.size(), nullptr);
116 :
117 3 : indexHint++;
118 3 : return SpanSearchValue<typename TYPE::Type>(&value_span[indexHint]);
119 : }
120 :
121 : private:
122 : T * mValue = nullptr; // underlying value, NULL if such a value does not exist
123 :
124 : /// Search for the index where `needle` is located inside `haystack`
125 : ///
126 : /// using `haystackValueMatchesNeedle` to find if a given haystack value matches the given needle
127 : ///
128 : /// `in_out_hint` contains a start search point at the start and will contain the found index
129 : /// location (if found) at the end.
130 : ///
131 : /// Returns true on success (index found) false on failure (index not found). If returning
132 : /// false, the value of `in_out_hint` is unchanged
133 : template <typename N, typename H>
134 6 : static bool FindIndexUsingHint(const N & needle, Span<H> haystack, unsigned & in_out_hint,
135 : bool (*haystackValueMatchesNeedle)(const N &, const typename std::remove_const<H>::type &))
136 : {
137 : // search starts at `hint` rather than 0
138 6 : const unsigned haystackSize = static_cast<unsigned>(haystack.size());
139 6 : unsigned checkIndex = (in_out_hint < haystackSize) ? in_out_hint : 0;
140 :
141 8 : for (unsigned i = 0; i < haystackSize; i++, checkIndex++)
142 : {
143 7 : if (haystackValueMatchesNeedle(needle, haystack[checkIndex % haystackSize]))
144 : {
145 5 : in_out_hint = checkIndex % haystackSize;
146 5 : return true;
147 : }
148 : }
149 :
150 1 : return false;
151 : }
152 : };
153 :
154 : } // namespace chip
|
