1. Forum
  2. Usenet
  3. COMP.LANG.C++

  • Immutable array with header

    From Marcel Mueller@21:1/5 to All on Sun Jun 23 14:37:00 2024
    Quite often I have the following requirement:

    I need a data structure that holds a single header H together with N
    elements E. N is constant but not constexpr so just using std::array is
    not an option.

    Use cases:
    - A reference counted store for (small) images. The reference count, the
    data size and maybe some meta information is the header while the
    picture data is just raw storage.
    - A reference counted string with refcount and size as header and an
    array of the char type as data.

    Normally this always requires two allocations for each object, one for
    the header and one for the data. When holding millions of small objects
    this can be a considerable overhead.

    In good old C this was usually handled by

    struct Storage
    { H Header;
    E Data[];
    };

    But this does not work for C++ types with constructors/destructors.
    new Storage() is not valid.

    There is a dirty hack by writing a custom operator new that takes an
    additional argument for N.

    class Storage
    {public:
    H Header;
    size_t n;
    E Data[];
    void* operator new(std::size_t sz, std::size_t N);
    void operator delete(void* ptr);
    };

    The drawback is that ~Storage() must know N to call ~E(). In order to
    work the operator new needs to store N somewhere in Storage which is not
    the idea of an allocation operator.

    Furthermore the size calculation in operator new needs offsetof(Storage,
    Data), which is likely to be UB when Storage and H are no trivial types.
    The size passed to operator new is not sufficient because the offset
    might be different due to tail padding or tail optimization (e.g if E is
    just char) or alignment requirements of E.


    Any other ideas?


    Marcel

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paavo Helde@21:1/5 to Marcel Mueller on Mon Jun 24 21:01:22 2024
    On 23.06.2024 15:37, Marcel Mueller wrote:
    Quite often I have the following requirement:

    I need a data structure that holds a single header H together with N
    elements E. N is constant but not constexpr so just using std::array is
    not an option.

    Use cases:
    - A reference counted store for (small) images. The reference count, the
    data size and maybe some meta information is the header while the
    picture data is just raw storage.
    - A reference counted string with refcount and size as header and an
    array of the char type as data.

    Normally this always requires two allocations for each object, one for
    the header and one for the data. When holding millions of small objects
    this can be a considerable overhead.

    If you allocate this dynamically, then you will access it by some kind
    of smart pointer. Make the destruction logic part of the smart pointer destructor, and you don't need to hack around with operator new/delete.

    See the implementation of std::shared_ptr. Here, std::make_shared
    allocates only one piece of memory and puts both the reference count and
    the object there, using placement new. The std::shared_ptr destructor
    will decrement the refcount and will eventually both destroy the object
    and release the memory block. The only difference in your case is that
    you need to allocate multiple objects instead of one. If the header only consists of reference count, you should actually be fine with

    auto shared = std::make_shared<E[]>(N);

    (supported since C++20)

    hth

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)