Does anyone know of a easy-to-follow / lightweight event queue handler example, preferably with a ring buffer?
Edit: the purpose is handling button presses in a situation where button events “bubble up” through several layers of context and the level at which they are eventually serviced is unknown
@Pharap’s favorite game programming patterns have a chapter about a ring buffer event queue with code examples: http://gameprogrammingpatterns.com/event-queue.html.
As @drummyfish mentioned, you won’t get a much better example of an event queue (with a ring buffer) than Bob Nystrom’s explanation (make sure to read the notes in the margin too),
but one thing it doesn’t go into (which I think you might be after) is the ‘Chain-of-responsibility’ pattern,
which covers your “events “bubble up” through several layers of context and the level at which they are eventually serviced is unknown” requirement.
Typically a chain of responsibility is a linked list, or a tree.
Ordinarily linked lists and trees are quite inefficient and bring up issues of lifetime, so you may want to have a dyanamic array (i.e. std::vector/std::deque) of handlers instead.
None of the examples I could find for chain of responsibility were particularly good.
Hardly any of them had decent examples, and they all seem to assume Java or C# being used on a powerful modern computer, so they wouldn’t be particularly good for Pokitto.
Instead, here’s an example I wrote:
template<typename TEvent>
class EventHandler
{
public:
~EventHandler(void) = default;
bool handleEvent(TEvent & event) = 0;
};
template<typename TEvent>
class EventDispatcher // : EventHandler<TEvent>
{
public:
using Event = TEvent;
using Handler = EventHandler<TEvent>
private:
std::vector<Handler> eventHandlers;
public:
void register(const Handler & eventHandler)
{
this->eventHandlers.push_back(eventHandler);
}
bool handleEvent(Event & event)
{
for(auto & handler : this->eventHandlers[i])
if(handler.handleEvent(event))
return true;
return false;
}
};
// ...
class ButtonEvent
{
private:
Buttons buttons;
public:
Buttons getButtons(void) const
{
return buttons;
}
};
using ButtonHandler = EventHandler<ButtonEvent>;
using ButtonDispatcher = EventDispatcher<ButtonEvent>;
class SoundControlHandler : ButtonHandler
{
public:
bool handleEvent(ButtonEvent & event) override
{
auto buttons = event.getButtons();
if(buttons.hasAll(Buttons::Flash | Buttons::Up))
{
SoundSystem::volumeUp();
return true;
}
else if(buttons.hasAll(Buttons::Flash | Buttons::Down)
{
SoundSystem::volumeDown();
return true;
}
return false;
}
};
class GameControlHandler : ButtonHandler
{
public:
bool handleEvent(ButtonEvent & event) override
{
// Handle buttons
}
};
Bear in mind that I don’t know what all your constraints are, so I don’t know how ownership should be handled.
I.e. instead of references, std::shared_ptr might be more appropriate, or even copying.
@Pharap : could you add a small example (pseudocode even) how to use that nice event handler you just explained. I am busy making the chain of command thing at the moment ( I’ll show you my example also) and I’d like to get up to speed on the event handler as fast as possible.
Here is my chain-of-command example:
#include <iostream>
#include <vector>
#include <ctime>
#include <cmath>
#include <stdlib.h>
using namespace std;
class Component
{
Component *next; // 1. "next" pointer in the base class
public:
int value;
Component(int v, Component *n)
{
value = v;
next = n;
}
void setNext(Component *n)
{
next = n;
}
virtual void traverse()
{
cout << " (traverse asked) I am component " << value << " and I will do it.\n";
}
// 2. The "chain" method in the base class always delegates to the next obj
virtual void volunteer()
{
cout << " (volunteer asked) I delegate to "<< next->value << "\n";
next->volunteer();
}
};
class Primitive: public Component
{
public:
Primitive(int val, Component *n = 0): Component(val, n){}
/*virtual*/void volunteer()
{
cout << "Volunteer: I am primitive " << value << " and I call my component.";
Component::traverse();
// 3. Primitive objects don't handle volunteer requests 5 times out of 6
if (rand() *100 % 6 != 0)
// 3. Delegate to the base class
{
cout << "We primitives don't usually do this, but ";
Component::volunteer();
}
}
};
class Parent: public Component
{
vector < Component * > children;
public:
Parent(int val, Component *n = 0): Component(val, n){}
void add(Component *c)
{
children.push_back(c);
}
/*virtual*/void traverse()
{
cout << "Traverse: I'm parent " << value << ", and ";
Component::traverse();
for (int i = 0; i < children.size(); i++)
children[i]->traverse();
}
// 3. Parent objects never handle volunteer requests
/*virtual*/void volunteer()
{
cout << "Volunteer: I'm parent " << value << ", and ";
Component::volunteer();
}
};
int main()
{
srand(time(0)); // 1
Primitive seven(7); // |
Primitive six(6, &seven); // +-- 2
Parent three(3, &six); // | |
three.add(&six);
three.add(&seven); // | +-- 4 5
Primitive five(5, &three); // |
Primitive four(4, &five); // +-- 3
Parent two(2, &four); // | |
two.add(&four);
two.add(&five); // | +-- 6 7
Parent one(1, &two); // |
Primitive nine(9, &one); // +-- 8 9
Primitive eight(8, &nine);
one.add(&two);
one.add(&three);
one.add(&eight);
one.add(&nine);
seven.setNext(&eight);
cout << "One, please traverse: \n";
one.traverse();
cout << '\n';
cout << "One, please volunteer: \n";
one.volunteer();
cout << '\n';
cout << "One, please volunteer again: \n";
one.volunteer();
cout << '\n';
cout << "One, please volunteer yet again: \n";
one.volunteer();
}
Does it have to work on C++03, or is a C++11 example allowed?
Your version is using the ‘singly linked list’ approach that I mentioned earlier.
That’s the typical example given for GC-ed languages like C# and Java.
I’d advise against it because it’s less efficient and in C++ it presents the ‘ownership’/‘lifetime’ problem.
The ownership/lifetime problem can be summed up in three questions:
std::shared_ptr solves all three of those, but is only available from C++11 onwards.
That said, this approach will work fine if you only need to use this in a limited context and you don’t need a robust API yet.
Your example mostly works fine, apart from the fact you forgot to check if next is null, so you’ll get a crash/segfault from volunteer.
I’m going to start by making a few amendments to my earlier example.
I realised it had a few mistakes because I rushed it.
I’m in the middle of doing something else, so I don’t have time to do an in-depth explanation at the moment, but I’ll be back to explain later.
I have no idea if this actually compiles or not (there’s probably half a dozen typos that stop it from working), but the theory is sound.
It’s C++11-based, but I can adapt it to be C++03 if need be.
C++11 is the intention. This is something that will not be compilable in online IDE
This will work for a basic system, but if it needs to be more robust then you’ll need to solve the ownership issue, which my example still doesn’t do.
If you’re after something quick and easy then this example will work fine.
Ok, I’ve got time to explain now.
You probably won’t have chance to read this until morning (unless you want nightmares about event handlers coming to eat you).
I’ll start with the simple stuff and move on to the more complicated issues.
Overview
So, the ButtonDispatcher (a special kind of event dispatcher) maintains a std::vector of pointers to ButtonHandlers (a special kind of event handler).
Each handler has to be individually registered with the dispatcher.
(And in a more robust system, they also have to be unregistered when no longer needed.)
When the event is handed to the dispatcher, it goes through every registered handler, in order of registration, until it finds one that can handle the event.
A handler signals that it managed to handle the event by returning true, and signals that it couldn’t handle it or doesn’t want to handle it by returning false.
So if a handler returns true, the dispatcher stops looking.
A more robust system would allow the order of handlers to be manipulated.
Also, it’s worth noting that none of the pointers in the dispatcher’s std::vector can be nullptr because they have to be registered by reference, not by pointer, and references cannot be nullptr.
This makes the process safer and faster (you don’t need an if(handler == nullptr) in the for loop).
Dynamic Array vs Linked List
In most examples of the chain of command pattern, each handler has a pointer to another handler.
In doing this they essentially form a unidirectional linked list (with each handler being a node in the list), and this is where the ‘chain’ part of the name comes from.
This can seemingly make the handlers a bit easier to manipulate because you only have to consider two or three handlers at a time,
but as with anything in programming the complexity has to end up somewhere.
The complexity from this approach is two-fold.
Firstly you have the same old ownership problem:
And secondly, if you try to break the chain, you’re not just splitting two nodes apart, you’re splitting the whole chain, so you have to think about what that means for the whole chain.
This is why my approach uses a dynamic array (in the form of a std::vector).
It has the same overal effect: you get a list of handlers with a well-defined order, but it’s more efficient and more familiar.
To traverse a std::vector, the code boils down to copying a pointer and then incrementing it.
To traverse a linked list, you must continually copy pointers from different areas of memory, effectively jumping all over the place.
The Pokitto may not have a cache to worry about,
but that’s still length - 1 extra pointer copies.
Typically with a chain-of-responsibility you rarely alter the chain, but you iterate it often,
so you want fast iteration, not fast alteration.
(This is true in life as well.)
A final note on this:
There is precisely one advantage to the linked list approach, and that is if you want the handlers themselves to decide whether the next node should be called or not.
The Complex Parts
It’s worth noting that the dispatcher can actually be thought of as a special kind of event handler - it handles the events by asking other event handlers to handle them.
This is why I have commented out : public ButtonHandler on ButtonDispatcher - to signal that it can be thought of this way, but you should question if it’s a good idea before doing so.
As cool as a tree of handlers sounds, it’s not especially useful unless you want to be able to build a decision tree of handlers.
In a more robust system, the pointers in the std::vector would be std::shared_ptr, which prevents the case where a pointer in the dispatcher becomes invalid without the pointer being deregistered.
However, this actually only offsets the problem.
Instead of ending up with crashing or garbled nonsense, you’re left with a handler in the dispatcher that you can’t get rid of.
So, you have several choices to fix this, but only two good ones:
std::weak_ptr, and check that a pointer hasn’t deallocated before trying to use it, whilst removing any that have been deallocated.use_count() of the std::shared_ptrs and discard any that have a use_count() of 1, because that indicates that the dispatcher is the only one keeping the pointer alive.The first option is more difficult, but it’s the better option.
If you were using C++03, you wouldn’t have either of these options, so praise be C++11. :P
The not so good options that I’ve seen people attempt:
Thanks for the complete explanation. Going to go with something like this because I need to think of code size here as well + destruction of objects will be a very controlled event in this case
Fair enough, though I will say despite popular belief, templates don’t significantly increase code size.
If you’re particularly concerned about size, I’d suggest swapping out std::vector for std::array so the number of handlers a dispatcher can manage is hardcoded.
That way there’s no dynamic allocation going on.
I’ve made an example of this in the weak_ptr branch.
It’s not quite as hard as I thought. The most difficult part is deregistering a handler,
because modifying a collection whilst iterating through it is always tricky.