Create a `SpanSearchValue` class that allows tree-searching without extra intermediate `if null/missing` checks. (#36754)
* Start adding the fluent tree object
* Start adding unit tests
* Add test file
* more testing
* update sizes hint and make use of things into CodegenDataModelProvider
* Restyle
* Fix some commments
* More merge fixes
* Remove some odd copy&paste comments
* Update src/lib/support/FluentTreeObject.h
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
* Update src/lib/support/FluentTreeObject.h
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
* Fix up comments a bit
* Simplify FluentTreeObject a bit
* Extra wrapper not needed
* Cleaned up comments
* Restyled by clang-format
* Sed rename FluentTreeObject to SpanSearchValue
* Also rename files
* Restyle
* Very slight reduction in complexity that reduces extra flash usage by a few bytes
* Another minor source code size decrease
* Even slightly smaller code
* Restyle
* Fix comment typo
* make cc32xx compile optimized for size by default, so we can treak flash usage as such
* Restyled by gn
* Update src/data-model-providers/codegen/CodegenDataModelProvider.cpp
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
* Update src/lib/support/SpanSearchValue.h
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
* Update src/lib/support/SpanSearchValue.h
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
* Update src/lib/support/SpanSearchValue.h
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
* Rename tree to searchable
* Fix comment
* Restyled by clang-format
---------
Co-authored-by: Andrei Litvin <andreilitvin@google.com>
Co-authored-by: Boris Zbarsky <bzbarsky@apple.com>
Co-authored-by: Restyled.io <commits@restyled.io>
diff --git a/src/data-model-providers/codegen/CodegenDataModelProvider.cpp b/src/data-model-providers/codegen/CodegenDataModelProvider.cpp
index 95bac8f..b599ba1 100644
--- a/src/data-model-providers/codegen/CodegenDataModelProvider.cpp
+++ b/src/data-model-providers/codegen/CodegenDataModelProvider.cpp
@@ -35,6 +35,7 @@
#include <lib/core/CHIPError.h>
#include <lib/core/DataModelTypes.h>
#include <lib/support/CodeUtils.h>
+#include <lib/support/SpanSearchValue.h>
#include <optional>
#include <variant>
@@ -106,6 +107,19 @@
namespace {
+/// Search by device type within a span of EmberAfDeviceType (finds the device type that matches the given
+/// DataModel::DeviceTypeEntry)
+struct ByDeviceType
+{
+ using Key = DataModel::DeviceTypeEntry;
+ using Type = const EmberAfDeviceType;
+ static Span<Type> GetSpan(Span<const EmberAfDeviceType> & data) { return data; }
+ static bool HasKey(const Key & id, const Type & instance)
+ {
+ return (instance.deviceId == id.deviceTypeId) && (instance.deviceVersion == id.deviceTypeRevision);
+ }
+};
+
const CommandId * AcceptedCommands(const EmberAfCluster & cluster)
{
return cluster.acceptedCommandList;
@@ -268,51 +282,17 @@
// to a common type is probably better. Need to figure out dependencies since
// this would make ember return datamodel-provider types.
// See: https://github.com/project-chip/connectedhomeip/issues/35889
-DataModel::DeviceTypeEntry DeviceTypeEntryFromEmber(const EmberAfDeviceType & other)
+std::optional<DataModel::DeviceTypeEntry> DeviceTypeEntryFromEmber(const EmberAfDeviceType * other)
{
- DataModel::DeviceTypeEntry entry;
-
- entry.deviceTypeId = other.deviceId;
- entry.deviceTypeRevision = other.deviceVersion;
-
- return entry;
-}
-
-// Explicitly compare for identical entries. note that types are different,
-// so you must do `a == b` and the `b == a` will not work.
-bool operator==(const DataModel::DeviceTypeEntry & a, const EmberAfDeviceType & b)
-{
- return (a.deviceTypeId == b.deviceId) && (a.deviceTypeRevision == b.deviceVersion);
-}
-
-/// Find the `index` where one of the following holds:
-/// - types[index - 1] == previous OR
-/// - index == types.size() // i.e. not found or there is no next
-///
-/// hintWherePreviousMayBe represents a search hint where previous may exist.
-unsigned FindNextDeviceTypeIndex(Span<const EmberAfDeviceType> types, const DataModel::DeviceTypeEntry & previous,
- unsigned hintWherePreviousMayBe)
-{
- if (hintWherePreviousMayBe < types.size())
+ if (other == nullptr)
{
- // this is a valid hint ... see if we are lucky
- if (previous == types[hintWherePreviousMayBe])
- {
- return hintWherePreviousMayBe + 1; // return the next index
- }
+ return std::nullopt;
}
- // hint was not useful. We have to do a full search
- for (unsigned idx = 0; idx < types.size(); idx++)
- {
- if (previous == types[idx])
- {
- return idx + 1;
- }
- }
-
- // cast should be safe as we know we do not have that many types
- return static_cast<unsigned>(types.size());
+ return DataModel::DeviceTypeEntry{
+ .deviceTypeId = other->deviceId,
+ .deviceTypeRevision = other->deviceVersion,
+ };
}
const ConcreteCommandPath kInvalidCommandPath(kInvalidEndpointId, kInvalidClusterId, kInvalidCommandId);
@@ -894,15 +874,9 @@
CHIP_ERROR err = CHIP_NO_ERROR;
Span<const EmberAfDeviceType> deviceTypes = emberAfDeviceTypeListFromEndpointIndex(*endpoint_index, err);
+ SpanSearchValue<chip::Span<const EmberAfDeviceType>> searchable(&deviceTypes);
- if (deviceTypes.empty())
- {
- return std::nullopt;
- }
-
- // we start at the beginning
- mDeviceTypeIterationHint = 0;
- return DeviceTypeEntryFromEmber(deviceTypes[0]);
+ return DeviceTypeEntryFromEmber(searchable.First<ByDeviceType>(mDeviceTypeIterationHint).Value());
}
std::optional<DataModel::DeviceTypeEntry> CodegenDataModelProvider::NextDeviceType(EndpointId endpoint,
@@ -917,18 +891,11 @@
return std::nullopt;
}
- CHIP_ERROR err = CHIP_NO_ERROR;
- Span<const EmberAfDeviceType> deviceTypes = emberAfDeviceTypeListFromEndpointIndex(*endpoint_index, err);
+ CHIP_ERROR err = CHIP_NO_ERROR;
+ chip::Span<const EmberAfDeviceType> deviceTypes = emberAfDeviceTypeListFromEndpointIndex(*endpoint_index, err);
+ SpanSearchValue<chip::Span<const EmberAfDeviceType>> searchable(&deviceTypes);
- unsigned idx = FindNextDeviceTypeIndex(deviceTypes, previous, mDeviceTypeIterationHint);
-
- if (idx >= deviceTypes.size())
- {
- return std::nullopt;
- }
-
- mDeviceTypeIterationHint = idx;
- return DeviceTypeEntryFromEmber(deviceTypes[idx]);
+ return DeviceTypeEntryFromEmber(searchable.Next<ByDeviceType>(previous, mDeviceTypeIterationHint).Value());
}
std::optional<DataModel::Provider::SemanticTag> CodegenDataModelProvider::GetFirstSemanticTag(EndpointId endpoint)
diff --git a/src/lib/support/BUILD.gn b/src/lib/support/BUILD.gn
index a8daba8..29a381d 100644
--- a/src/lib/support/BUILD.gn
+++ b/src/lib/support/BUILD.gn
@@ -236,6 +236,7 @@
"ScopedBuffer.h",
"SetupDiscriminator.h",
"SortUtils.h",
+ "SpanSearchValue.h",
"StateMachine.h",
"StringBuilder.cpp",
"StringBuilder.h",
diff --git a/src/lib/support/SpanSearchValue.h b/src/lib/support/SpanSearchValue.h
new file mode 100644
index 0000000..e11a9e6
--- /dev/null
+++ b/src/lib/support/SpanSearchValue.h
@@ -0,0 +1,154 @@
+/*
+ * Copyright (c) 2024 Project CHIP Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <cstddef>
+#include <lib/support/Span.h>
+
+#include <optional>
+
+namespace chip {
+
+/// represents a wrapper around a type `T` that contains internal
+/// `Span<...>` values of other sub-types. It allows searching within the container sub-spans
+/// to create new containers.
+///
+/// The use case is that we very often search within nested containers, like "find-endpoint" + "find-cluster" + "find-attribute"
+/// and we generally only care about "does the last element exist or not"
+///
+/// A typical example of the way this class is used looks like this:
+///
+/// SpanSearchValue container(somePointer);
+///
+/// const AcceptedCommandData * value =
+/// container
+/// .Find<ByEndpoint>(path.mEndpointId, mEndpointIndexHint)
+/// .Find<ByServerCluster>(path.mClusterId, mServerClusterHint)
+/// .Find<ByAcceptedCommand>(path.mCommandId, mAcceptedCommandHint)
+/// .Value();
+///
+/// Where a `ByFoo` structure looks like:
+///
+/// struct ByFoo {
+/// using Key = int; // the KEY inside a type
+/// using Type = SomeValueType; // The type that is indexed by `Key`
+///
+/// /// Allows getting the "Span of Type" from an underlying structure.
+/// /// A `SpanSearchValue<Foo>` will require a `GetSpan(Foo&)`
+/// static Span<Type> GetSpan(ContainerType & data) { /* return ... */ }
+///
+/// /// Checks that the `Type` value has the given `Key` or not
+/// static bool HasKey(const Key & id, const Type & instance) { /* return "instance has key id" */ }
+/// }
+///
+/// Where we define:
+/// - how to get a "span of sub-elements" for an object (`GetSpan`)
+/// - how to determine if a given sub-element has the "correct key"
+template <typename T>
+class SpanSearchValue
+{
+public:
+ SpanSearchValue() : mValue(nullptr) {}
+ SpanSearchValue(std::nullptr_t) : mValue(nullptr) {}
+ explicit SpanSearchValue(T * value) : mValue(value) {}
+
+ /// Returns nullptr if such an element does not exist or non-null valid value if the element exists
+ T * Value() const { return mValue; }
+
+ /// Gets the first element of `TYPE::Type`
+ template <typename TYPE>
+ SpanSearchValue<typename TYPE::Type> First(unsigned & indexHint)
+ {
+ // if no value, searching more also yields no value
+ VerifyOrReturnValue(mValue != nullptr, nullptr);
+
+ Span<typename TYPE::Type> value_span = TYPE::GetSpan(*mValue);
+ VerifyOrReturnValue(!value_span.empty(), nullptr);
+
+ // found it, save the hint
+ indexHint = 0;
+ return SpanSearchValue<typename TYPE::Type>(&value_span[0]);
+ }
+
+ /// Find the value corresponding to `key`
+ template <typename TYPE>
+ SpanSearchValue<typename TYPE::Type> Find(typename TYPE::Key key, unsigned & indexHint)
+ {
+ VerifyOrReturnValue(mValue != nullptr, nullptr);
+
+ Span<typename TYPE::Type> value_span = TYPE::GetSpan(*mValue);
+
+ if (!FindIndexUsingHint(key, value_span, indexHint, TYPE::HasKey))
+ {
+ return nullptr;
+ }
+
+ return SpanSearchValue<typename TYPE::Type>(&value_span[indexHint]);
+ }
+
+ /// Finds the value that occurs after `key` in the underlying collection.
+ template <typename TYPE>
+ SpanSearchValue<typename TYPE::Type> Next(typename TYPE::Key key, unsigned & indexHint)
+ {
+ VerifyOrReturnValue(mValue != nullptr, nullptr);
+
+ Span<typename TYPE::Type> value_span = TYPE::GetSpan(*mValue);
+
+ if (!FindIndexUsingHint(key, value_span, indexHint, TYPE::HasKey))
+ {
+ return nullptr;
+ }
+
+ VerifyOrReturnValue((indexHint + 1) < value_span.size(), nullptr);
+
+ indexHint++;
+ return SpanSearchValue<typename TYPE::Type>(&value_span[indexHint]);
+ }
+
+private:
+ T * mValue = nullptr; // underlying value, NULL if such a value does not exist
+
+ /// Search for the index where `needle` is located inside `haystack`
+ ///
+ /// using `haystackValueMatchesNeedle` to find if a given haystack value matches the given needle
+ ///
+ /// `in_out_hint` contains a start search point at the start and will contain the found index
+ /// location (if found) at the end.
+ ///
+ /// Returns true on success (index found) false on failure (index not found). If returning
+ /// false, the value of `in_out_hint` is unchanged
+ template <typename N, typename H>
+ static bool FindIndexUsingHint(const N & needle, Span<H> haystack, unsigned & in_out_hint,
+ bool (*haystackValueMatchesNeedle)(const N &, const typename std::remove_const<H>::type &))
+ {
+ // search starts at `hint` rather than 0
+ const unsigned haystackSize = static_cast<unsigned>(haystack.size());
+ unsigned checkIndex = (in_out_hint < haystackSize) ? in_out_hint : 0;
+
+ for (unsigned i = 0; i < haystackSize; i++, checkIndex++)
+ {
+ if (haystackValueMatchesNeedle(needle, haystack[checkIndex % haystackSize]))
+ {
+ in_out_hint = checkIndex % haystackSize;
+ return true;
+ }
+ }
+
+ return false;
+ }
+};
+
+} // namespace chip
diff --git a/src/lib/support/tests/BUILD.gn b/src/lib/support/tests/BUILD.gn
index c6bfddb..d814f70 100644
--- a/src/lib/support/tests/BUILD.gn
+++ b/src/lib/support/tests/BUILD.gn
@@ -56,6 +56,7 @@
"TestScopedBuffer.cpp",
"TestSorting.cpp",
"TestSpan.cpp",
+ "TestSpanSearchValue.cpp",
"TestStateMachine.cpp",
"TestStaticSupportSmartPtr.cpp",
"TestStringBuilder.cpp",
diff --git a/src/lib/support/tests/TestSpanSearchValue.cpp b/src/lib/support/tests/TestSpanSearchValue.cpp
new file mode 100644
index 0000000..469c590
--- /dev/null
+++ b/src/lib/support/tests/TestSpanSearchValue.cpp
@@ -0,0 +1,187 @@
+/*
+ * Copyright (c) 2024 Project CHIP Authors
+ * All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include "pw_unit_test/framework.h"
+#include <pw_unit_test/framework.h>
+
+#include <lib/core/DataModelTypes.h>
+#include <lib/core/StringBuilderAdapters.h>
+#include <lib/support/SpanSearchValue.h>
+
+namespace {
+
+using namespace chip;
+
+struct ClusterData
+{
+ const ClusterId id;
+ const char * name;
+};
+
+struct EndpointData
+{
+ const EndpointId id;
+
+ const char * name;
+ Span<const ClusterData> serverClusters;
+ Span<const ClusterData> clientClusters;
+};
+
+struct EndpointItemsWrapper
+{
+ Span<const EndpointData> data;
+
+ template <size_t N>
+ EndpointItemsWrapper(EndpointData (&d)[N]) : data(d)
+ {}
+};
+
+const ClusterData gClusterList1[] = {
+ {
+ .id = 100,
+ .name = "one hundred",
+ },
+ {
+ .id = 200,
+ .name = "two hundred",
+ },
+};
+
+const ClusterData gClusterList2[] = {
+ {
+ .id = 1,
+ .name = "just one",
+ },
+};
+
+EndpointData gEndpointDataItems[] = {
+ {
+ .id = 123,
+ .name = "foo",
+ .serverClusters = Span<const ClusterData>(gClusterList1),
+ .clientClusters = Span<const ClusterData>(gClusterList2),
+ },
+ {
+ .id = 456,
+ .name = "bar",
+ .serverClusters = Span<const ClusterData>(gClusterList2),
+ .clientClusters = Span<const ClusterData>(),
+ },
+ {
+ .id = 1000,
+ .name = "Empty",
+ .serverClusters = Span<const ClusterData>(),
+ .clientClusters = Span<const ClusterData>(),
+ },
+};
+
+/// search index definitions
+struct ByEndpoint
+{
+ using Key = EndpointId;
+ using Type = const EndpointData;
+ static Span<Type> GetSpan(EndpointItemsWrapper & data) { return data.data; }
+ static bool HasKey(const Key & id, const Type & instance) { return instance.id == id; }
+};
+
+struct ByServerCluster
+{
+ using Key = ClusterId;
+ using Type = const ClusterData;
+ static Span<Type> GetSpan(const EndpointData & data) { return data.serverClusters; }
+ static bool HasKey(const Key & id, const Type & instance) { return instance.id == id; }
+};
+
+struct ByClientCluster
+{
+ using Key = ClusterId;
+ using Type = const ClusterData;
+ static Span<Type> GetSpan(const EndpointData & data) { return data.clientClusters; }
+ static bool HasKey(const Key & id, const Type & instance) { return instance.id == id; }
+};
+
+} // namespace
+
+TEST(TestSpanSearchValue, TestFunctionality)
+{
+ EndpointItemsWrapper wrapper(gEndpointDataItems);
+ SpanSearchValue<EndpointItemsWrapper> tree(&wrapper);
+
+ EXPECT_EQ(tree.Value(), &wrapper); // value getting to start matches
+
+ // search first items
+ {
+ unsigned hint1 = 0;
+ auto ep = tree.First<ByEndpoint>(hint1);
+
+ unsigned hint2 = 0;
+ auto cl = ep.First<ByServerCluster>(hint2);
+
+ ASSERT_NE(cl.Value(), nullptr);
+ EXPECT_EQ(cl.Value()->id, 100u);
+ EXPECT_STREQ(cl.Value()->name, "one hundred");
+ }
+
+ // one level search, with hint
+ {
+ unsigned hint = 0;
+ ASSERT_NE(tree.Find<ByEndpoint>(123, hint).Value(), nullptr);
+ ASSERT_STREQ(tree.Find<ByEndpoint>(123, hint).Value()->name, "foo");
+ EXPECT_EQ(hint, 0u);
+
+ ASSERT_NE(tree.Find<ByEndpoint>(456, hint).Value(), nullptr);
+ EXPECT_EQ(hint, 1u);
+ EXPECT_STREQ(tree.Find<ByEndpoint>(456, hint).Value()->name, "bar");
+ EXPECT_EQ(hint, 1u);
+
+ // hint is ignored here
+ EXPECT_STREQ(tree.Find<ByEndpoint>(123, hint).Value()->name, "foo");
+ EXPECT_EQ(hint, 0u);
+
+ EXPECT_STREQ(tree.Find<ByEndpoint>(1000, hint).Value()->name, "Empty");
+ EXPECT_EQ(hint, 2u);
+
+ // Invalid searches
+ EXPECT_EQ(tree.Find<ByEndpoint>(12345, hint).Value(), nullptr);
+ EXPECT_EQ(tree.Find<ByEndpoint>(0, hint).Value(), nullptr);
+ }
+
+ // searches for "next"
+ {
+ unsigned hint = 0;
+ auto next = tree.Next<ByEndpoint>(123, hint);
+
+ ASSERT_NE(next.Value(), nullptr);
+ EXPECT_EQ(hint, 1u);
+ EXPECT_EQ(next.Value()->id, 456u);
+ EXPECT_STREQ(next.Value()->name, "bar");
+
+ next = tree.Next<ByEndpoint>(456, hint);
+ ASSERT_NE(next.Value(), nullptr);
+ EXPECT_EQ(hint, 2u);
+ EXPECT_EQ(next.Value()->id, 1000u);
+ EXPECT_STREQ(next.Value()->name, "Empty");
+
+ /// search at the end
+ next = tree.Next<ByEndpoint>(1000, hint);
+ EXPECT_EQ(next.Value(), nullptr);
+
+ // null value preserves the failure
+ unsigned clusterHint = 0;
+ auto sub_item = next.Find<ByServerCluster>(123, clusterHint);
+ EXPECT_EQ(sub_item.Value(), nullptr);
+ }
+}
diff --git a/src/platform/cc32xx/args.gni b/src/platform/cc32xx/args.gni
index 288aa5a..d819c03 100755
--- a/src/platform/cc32xx/args.gni
+++ b/src/platform/cc32xx/args.gni
@@ -34,3 +34,6 @@
chip_inet_config_enable_dns_resolver = false
chip_build_tests = false
+
+# small binaries even in CI
+optimize_debug_level = "s"
