vendredi 8 octobre 2021

Memory efficient dynamic_cast without RTTI

I'm creating a library for embedded systems, because of that I can't use any RTTI features including dynamic_cast. To create a some thing like a dynamic_cast I've implemented the necessary components of RTTI myself according to this article. It might be that I did some things differently but the idea is the same.

Here's my implementation:

#include <iostream>

constexpr uint32_t primes[] = {
        2,
        3,
        5,
        7,
        11,
        13,
        17,
        19,
        23,
        29,
        31
};

#define DYNAMIC_POINTER_CAST_INIT(...)                                                           \
    virtual uint32_t dynamicPointerCastObjectId() override                                       \
    {                                                                                            \
        return DynamicPointerCastable<__VA_ARGS__>::dynamicPointerCastObjectId(); \
    }                                                                                            \
                                                                                                 \
    using DynamicPointerCastable<__VA_ARGS__>::dynamicPointerCastClassId;         \
    using DynamicPointerCastable<__VA_ARGS__>::dynamicPointerCastClassPrimeId

namespace
{
    uint32_t numberOfDynamicPointerCastables = 0;

    template <typename... Bs>
    struct genSubClassId
    {
        static uint32_t value;
    };

    template <typename B, typename... Bs>
    struct genSubClassId<B, Bs...>
    {
        static uint32_t value;
    };

    template <typename B>
    struct genSubClassId<B>
    {
        static uint32_t value;
    };
    template <>
    struct genSubClassId<>
    {
        static uint32_t value;
    };

    template <typename B, typename... Bs>
    uint32_t genSubClassId<B, Bs...>::value =
            B::dynamicPointerCastClassId() * genSubClassId<Bs...>::value;
    template <typename B>
    uint32_t genSubClassId<B>::value =
            B::dynamicPointerCastClassId();

    uint32_t genSubClassId<>::value = 1;
}

template <typename Sub, typename... Bases>
class DynamicPointerCastable
{

private:
    static uint32_t subPrimeId;

public:
    static uint32_t dynamicPointerCastClassPrimeId()
    {
        return subPrimeId;
    }

    static uint32_t dynamicPointerCastClassId()
    {
        return subPrimeId * genSubClassId<Bases...>::value;
    }

    virtual uint32_t dynamicPointerCastObjectId()
    {
        return DynamicPointerCastable<Sub, Bases...>::dynamicPointerCastClassId();
    }
};

template <typename T, typename Cast>
Cast *dynamicCastableCast(T *obj)
{
    if (obj->dynamicPointerCastObjectId() % Cast::dynamicPointerCastClassPrimeId() == 0)
        return (Cast *)obj;
    return nullptr;
}

template <typename Sub, typename... Bases>
uint32_t DynamicPointerCastable<Sub, Bases...>::subPrimeId = primes[numberOfDynamicPointerCastables++];

The basic idea is that I have a counter numberOfDynamicPointerCastables which is the index to a list of prime numbers primes (in the library this list contains 1000 prime numbers). Then the methods from DynamicPointerCastable are implemented in the sub classes with the CRTP. dynamicCastableCast then checks if the id of the class is divisible by the prime number associated with the class that you want to cast to.

Example:

struct Sub1 : public Base, public DynamicPointerCastable<Sub1, Base>
{
    DYNAMIC_POINTER_CAST_INIT(Sub1, Base);
    virtual std::string getName()
    {
        return "Sub1";
    }
};

struct SubGroup : public Base, public DynamicPointerCastable<SubGroup, Base>
{
    DYNAMIC_POINTER_CAST_INIT(SubGroup, Base);
    virtual std::string getName()
    {
        return "SubGroup";
    }
};

struct Sub2 : public SubGroup, public DynamicPointerCastable<Sub2, SubGroup>
{
    DYNAMIC_POINTER_CAST_INIT(Sub2, SubGroup);
    virtual std::string getName()
    {
        return "Sub2";
    }
};

int main()
{
    Base* sub1 = new Sub1;
    Base* sub2 = new Sub2;

    std::cout << "Expected Sub1: " << dynamicCastableCast<Base, Sub1>(sub1)->getName() << std::endl;
    std::cout << "Expected nullptr: " << dynamicCastableCast<Base, Sub2>(sub1) << std::endl;

    std::cout << "Expected Sub2: " << dynamicCastableCast<Base, SubGroup>(sub2)->getName() << std::endl;
    std::cout << "Expected Sub2: " << dynamicCastableCast<Base, Sub2>(sub2)->getName() << std::endl;
    std::cout << "Expected nullptr: " << dynamicCastableCast<Base, Sub1>(sub2) << std::endl;
}

Unfortunately tough I didn't manage to get the counter working at compile-time which means the whole array of prime numbers will be in the binary (I used gcc-11 with the flags -Os -ffunction-sections -fdata-sections -Wl,--gc-sections -DNDEBUG).

Will the compiler even be able to just include the prime numbers in the binary that are necessary when the counter would be counting the classes at compile-time?

And when yes how could I make the counter work at compile-time?

Or is there an other solution to keep the binary as small as possible?

Aucun commentaire:

Enregistrer un commentaire