4
\$\begingroup\$

The recurring problem to assemble a network packet out of payload, sequence number, header, and other misc. information is mostly solved either on the heap (e.g. appending to a std::vector) or by first allocating a (hopefully large enough) buffer and then writing to that buffer. Some of the elements always stay the same or only change minimally (like the header) and therefore the scatter/gather approach offered by writev with iovec, Asio with buffer sequences or other networking interfaces allow to avoid those unnecessary copies.

There is still the problems that different parts of the message are produced in different parts of the code, especially when more than on sub-protocol is to be used. In that case we are again tempted to use dynamic memory allocation to construct the iovec. I would like to avoid those dynamic memory allocation and potentially oversized buffers for so I came up with the following in-stack stack implementation (I named it stack_stack):

template<class T, size_t length=1>
struct stack_stack {
  using next_type = stack_stack<T, length-1>;
  using prev_type = stack_stack<T, length+1>;
  const T value;
  const next_type * next = nullptr;
  static constexpr size_t ssize = length;

  struct iterator {
    using value_type = T;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::input_iterator_tag;

    iterator& operator++() {
      ptr = static_cast<const stack_stack*>(ptr)->next;
      return *this;
    }
    bool operator==(iterator other) const {
      return ptr == *other;
    }
    bool operator!=(iterator other) const {
      return ptr != *other;
    }
    pointer operator*() {return static_cast<pointer>(ptr);}

    const void* ptr;
  };
  iterator begin() const {return iterator{this};}
  iterator end() const {return iterator{nullptr};}

  prev_type push_front(T val) const {
    return {val, this};
  }
};

It keeps track of its length using template parameters and could be used like in the following example scenario:


struct ioitem {
  char* data;
  size_t size;
};

template<class stack>
void Send(const stack& b) {
  for (auto a : b) {
    std::cout << a->data << std::endl;
  }
}

template<class stack>
void SendWithHeader(const stack& b) {
  auto header = std::string("HDX1");  // This would normally some kind of constexpr 
  Send(b.push_front({header.data(), header.size()}));
}

template<class stack>
void SendWithSeqno(const stack& b) {
  auto seq_no = std::string("5");
  auto b1 = b.push_front({seq_no.data(), seq_no.size()});  // it's ok if one module addds more than one part
  auto b2 = b1.push_front({seq_no.data(), seq_no.size()});
  SendWithHeader(b2);
}

template<class stack>
void SendWithTag(const stack& b) {
  auto tag_name = std::string("my tag");  // I am just making up a protocol here
  SendWithSeqno(b.push_front({tag_name.data(), tag_name.size()}));
}

int main() {
  auto my_data = std::string("Hello World");
  auto my_Buffer = stack_stack<ioitem>{my_data.data(), my_data.size()};
  SendWithTag(my_Buffer);
}

What I would like to improve:

  1. In the Send function I could copy the stack to a statically sized array according to the size of stack::ssize. However I did not get std::copy to work.
  2. I don't like the hacks with the void* in the iterator.

Also: Is this a good way to approach this problem or is there a much better solution (without the heap) that got under my radar? I searched for similar implementations to mine but could not find anything.

\$\endgroup\$
2
\$\begingroup\$

The iterator is not behaving correctly

There are various reasons std::copy() doesn't work on stack_stack, and it all has to do with the iterator. First, you are missing difference_type. Since your iterators do not support taking the difference, set it to void:

using difference_type = void;

Second, your comparison operators are wrong. They should take a const reference to other, and you can access member variables of other directly, so:

bool operator==(const iterator &other) const {
   return ptr == other.ptr;
}

Also, while this is a trivial comparison operator, it is good to define operator!= in terms of operator==, to avoid potential mistakes:

bool operator!=(const iterator &other) const {
    return !(*this == other); // Just invert the result of operator==
}

Last, the result of operator* should be a reference to the actual data, not a pointer, so:

reference operator*() {
    return *static_cast<pointer>(ptr);
}

Now it sort of works, and std::copy() is happy. In your own code, you need to change some use of -> to . to make it print the contents of a stack, like so:

for (auto item: stack) {
    std::cout << item.data << "\n";
}

Avoiding void* hacks

Well, you have created a problem for yourself. Each element of the stack points to the next element, but it has a different type. The cleanest solution I see without changing the type system used for stack_stack is to do this:

struct iterator {
    ...
    using pointer = const stack_stack*;
    ...
    iterator& operator++() {
        ptr = reinterpret_cast<pointer>(ptr->next);
        return *this;
    }
    ...
    reference operator*() {
        return ptr->value;
    }

    pointer ptr;
};

So we removed all of the lies, except the one about the type when following ptr->next.

The cleanest approach

If you want to do it even cleaner, then you should not have a template parameter length. Maybe also don't call it a stack, it more accurately resembles one element of a singly-linked list. To keep track of the length of this list, I would create a separate type that resembles the list as a whole, and which stores the length and a pointer to the head, both of which we will update when we add elements:

template<class T>
struct stack_list {
    struct item {
        const T value;
        const item *const next;

        // Constructor which will update the head of stack_list
        item(const T &value, const item *&head): value(value), next(head) {
            head = this;
        }

        // Delete copy constructor, move and assignment operators
        item(const item &other) = delete;
        item &operator=(const item &other) = delete;
        item &operator=(const item &&other) = delete;
    };

    struct iterator {
        ... // left as an excercise to the reader
    };

    size_t size{};
    const item *head{};

    [[nodiscard]] item push_front(T value) {
        size++;
        return {value, head}
    }
}

Then you can use it like so:

auto my_data = ...;

stack_list<ioitem> sl;
auto my_buffer = sl.push_front({my_data.begin(), my_data.size()});

std::cout << "List size: " << sl.size << "\n"
          << "First element: " << sl.head->value << "\n";

Using your class for building iovecs

As you noticed you still need to convert your stack (or list) of ioitems to an array of struct iovec. So it might be better to build this array directly. If you want to do it on the stack, then the safest option is to just go with a std::array<iovec, N>, where N is large enough to handle most or all cases. If the required size can vary a lot, then you can perhaps make a class that holds a union of a std::array and a std::vector, and switches to the vector if the array is full. You might be able to use an existing library implementing small vector optimization, but since you basically always push_front(), your own implementation that starts at the back of the array might be the most efficient. It might look like:

template<size_t N = 8>
class iovec_builder {
    std::array<struct iovec, N> iov;
    size_t iovlen{};

public:
    void push_front(struct iovec item) {
        if (iovlen == N) {
            // handle array being full
        } else {
            // add starting from the back
            iovlen++;
            iov[N - iovlen] = item;
        }
    }

    struct iovec *get_iov() {
        return &iov[N - iovlen];
    }

    size_t get_iovlen() const {
        return iovlen;
    }
};

And use it like:

iovec_builder iovb;
std::string my_data("Hello World");
iovb.push_front({my_data.data(), my_data.len()});
iovb.push_front({..., ...});

struct msghdr msg{};
msg.iov = iovb.get_iov();
msg.iovlen = iovb.get_iovlen();
...
sendmsg(fd, &msg, ...);

It might waste a bit of stack space, but you'll waste more by having a linked list and having to copy it into an array.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks a lot! To make it work I had to set the copy constructor or move constructor to default. Otherwise the assignment to my_buffer fails to compile. Which one (move or copy) would you prefer? \$\endgroup\$
    – ernestum
    Sep 16 '20 at 13:45
  • \$\begingroup\$ I also found out that things get messed up if I do not store the result of push_front. When adding more than one item the last added item is repeated twice. E.g. [inserting] -> [content]: [1, 2] -> [2, 2]; [1, 2, 3] -> [3, 3, 1]; [1, 2, 3, 4] -> [4, 4, 2, 1]. Is there any way to enforce keeping the return value of push_front? \$\endgroup\$
    – ernestum
    Sep 16 '20 at 13:45
  • 1
    \$\begingroup\$ Of course you need to store the result of push_front(), because that is where your data lives! I thought that was the whole idea behind your design? \$\endgroup\$
    – G. Sliepen
    Sep 16 '20 at 16:54
  • 1
    \$\begingroup\$ You shouldn't need to make the copy or move constructors default, but you do need to have at least the regular constructor, in your stack_stack() you didn't have any explicitly defined, but if you start deleting things you have to explicitly add them, just like I did in stack_list::item. As for enforcing keeping the return value: you can't. But you can use the [[nodiscard]] attribute to let the compiler warn about not storing the result. \$\endgroup\$
    – G. Sliepen
    Sep 16 '20 at 17:01
  • \$\begingroup\$ To clarify: I had to set the copy/move constructor of item to default (not stack_list) otherwise I get an error: use of deleted function on the line auto my_buffer = sl.push_front(.... Yes the point is to store the result of push_front() on the stack but my users might not necessarily be aware of that and run into hard to find bugs. The [[nodiscard]] attribute was exactly what I was looking for. Thanks a lot! \$\endgroup\$
    – ernestum
    Sep 17 '20 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.