Line data    Source code

       1             : /*
       2             :  *
       3             :  *    Copyright (c) 2020 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             : 
      19             : /**
      20             :  *    @file
      21             :  *      Defines a data structure that can store a set of uint64_t values
      22             :  *      in not contiguous indexes. The set is initialized with a constant
      23             :  *      capacity. The data structure supports serialize/deserialize operations,
      24             :  *      where, serialize converts the set to a base64 string, and deserializing
      25             :  *      the base64 string reconstructs the original set.
      26             :  *
      27             :  *      The data is stored such that serialized data can be deserialized correctly
      28             :  *      on different machine architectures.
      29             :  *
      30             :  */
      31             : 
      32             : #pragma once
      33             : 
      34             : #include <lib/support/CodeUtils.h>
      35             : #include <lib/support/Span.h>
      36             : 
      37             : namespace chip {
      38             : 
      39             : class SerializableU64SetBase
      40             : {
      41             : 
      42             : public:
      43             :     SerializableU64SetBase(uint64_t * data, uint16_t capacity, uint64_t emptyValue) :
      44             :         mData(data), mCapacity(capacity), mEmptyValue(emptyValue), mNextAvailable(0)
      45             :     {
      46             :         for (uint16_t i = 0; i < capacity; i++)
      47             :         {
      48             :             data[i] = emptyValue;
      49             :         }
      50             :     }
      51             : 
      52             :     /**
      53             :      * @brief
      54             :      *   Serialize the sparse array by calling a callback with a ByteSpan to
      55             :      *   serialize.  We ensure that this ByteSpan is architecture-agnostic, so
      56             :      *   it can be deserialized anywhere later.
      57             :      *
      58             :      *   Only the values till mNextAvailable index are encoded.
      59             :      *   The empty indexes between 0, and mNextAvailable, are also
      60             :      *   encoded.
      61             :      *
      62             :      * @param[in] callback the serialization callback to call.
      63             :      */
      64             :     template <typename F>
      65             :     CHIP_ERROR Serialize(F callback)
      66             :     {
      67             :         // Ensure that we are holding little-endian data while the serialization
      68             :         // callback runs.
      69             :         SwapByteOrderIfNeeded();
      70             : 
      71             :         CHIP_ERROR err = callback(ByteSpan(reinterpret_cast<uint8_t *>(mData), SerializedSize()));
      72             : 
      73             :         SwapByteOrderIfNeeded();
      74             :         return err;
      75             :     }
      76             : 
      77             :     /**
      78             :      * @brief
      79             :      *   Deserialize a previously serialized byte buffer into the sparse array.
      80             :      *   The mNextAvailable index is calculated based on how many
      81             :      *   values are in the deserialized array.
      82             :      *
      83             :      * @param[in] serialized Serialized buffer
      84             :      */
      85             :     CHIP_ERROR Deserialize(ByteSpan serialized);
      86             : 
      87             :     /**
      88             :      * @brief
      89             :      *   Get the length of the byte data if the array is serialized.
      90             :      */
      91             :     size_t SerializedSize() const { return sizeof(uint64_t) * mNextAvailable; }
      92             : 
      93             :     /**
      94             :      * @brief
      95             :      *   Get the maximum length of the byte data if the array were full and serialized.
      96             :      */
      97           0 :     size_t MaxSerializedSize() const { return sizeof(uint64_t) * mCapacity; }
      98             : 
      99             :     /**
     100             :      * @brief
     101             :      *   Check if the value is in the array.
     102             :      *
     103             :      * @param[in] value Value to find
     104             :      * @return True, if it's prsent in the array.
     105             :      */
     106             :     bool Contains(uint64_t value) { return FindIndex(value) != mCapacity; }
     107             : 
     108             :     /**
     109             :      * @brief
     110             :      *   Insert the value in the array. If the value is duplicate, it
     111             :      *   won't be inserted.
     112             :      *
     113             :      * @return CHIP_NO_ERROR in case of success, or the error code
     114             :      */
     115             :     CHIP_ERROR Insert(uint64_t value);
     116             : 
     117             :     /**
     118             :      * @brief
     119             :      *   Delete the value from the array.
     120             :      */
     121             :     void Remove(uint64_t value);
     122             : 
     123             : private:
     124             :     uint64_t * const mData;
     125             :     const uint16_t mCapacity;
     126             :     const uint64_t mEmptyValue;
     127             :     uint16_t mNextAvailable;
     128             : 
     129             :     uint16_t FirstAvailableForUniqueId(uint64_t value);
     130             : 
     131             :     /**
     132             :      * @brief
     133             :      *   Find index of the value in the array.
     134             :      *
     135             :      * @param[in] value Value to find
     136             :      * @return index of the value if found, or max length (mCapacity) of the array
     137             :      */
     138             :     uint16_t FindIndex(uint64_t value);
     139             : 
     140             :     void SwapByteOrderIfNeeded();
     141             : };
     142             : 
     143             : template <uint16_t kCapacity, uint64_t kEmptyValue = 0>
     144             : class SerializableU64Set : public SerializableU64SetBase
     145             : {
     146             : public:
     147             :     SerializableU64Set() : SerializableU64SetBase(mBuffer, kCapacity, kEmptyValue)
     148             :     {
     149             :         /**
     150             :          * Check that requested capacity (kCapacity) will not exceed maximum number of uint64_t
     151             :          * values that can fit in a meory of size UINT16_MAX. This is required, since APIs in
     152             :          * this class are using uint16_t type for buffer sizes.
     153             :          */
     154             :         nlSTATIC_ASSERT_PRINT(kCapacity < UINT16_MAX / sizeof(uint64_t),
     155             :                               "Serializable u64 set capacity cannot be more than UINT16_MAX / sizeof(uint64_t)");
     156             :     }
     157             : 
     158             : private:
     159             :     uint64_t mBuffer[kCapacity];
     160             : };
     161             : 
     162             : } // namespace chip