Some thoughts on flat hierarchies in C++

The top search terms for this blog seem to be “flat hierarchy C++”, so this is something I should address.

I had originally intended on writing a crude implementation in Python, to demonstrate the consept, leaving an actual efficient implementation as an exercise for the reader (possibly implementing it myself for a future post), but perhaps it would be more useful to think about it sooner. In this post, I will write a few short sentences to outline my thoughts on implementing a flat hierarchy in C++, which will hopefully provide readers with some ideas to implement this themselves.

There are two ways of implementing flat hierarchies which I am currently interested in exploring, though I’m sure theres more. I will briefly explain these here:

1. Independent components which communicate over an anonymous shared-nothing messaging system. This works because the messaging is transparent – a component never knows which other components will receive its messages, if any. A receiving component likewise never knows which components sent the messages which it is receviing. This anonymous message sending means that components may be added or removed at will and other components will never know. Obviously it may not logically make sense to do this – if a component relies on certain messages to work and you remove the component which generates the messages, then obviously the first component cannot fnction – but it will not fail either, it will wait around until you add a component which does generate those messages back into the system. Each component is a node in a flat hierarchy.
2. An entity system. In this context, an entity system is an alternative to object oriented systems where an object is simply a collection of traits and is a technique borrowed from the game development community. How this object behaves is determined by the traits it has associated with it. Traits may be added or removed at runtime. Each object is independent and can only communicate through its traits. Since traits can be added and removed dynamically, the system maintains a flat hierarchy. Objects can be processed independently and concurrently. The building of entity systems is the subject of my “Building a Flat Hierarchy” series of posts, so be sure to check those out, if interested.

Since entity systems are reasonably complex and are being covered in their own series of blog posts, I will not talk about them here. Instead I will briefly talk about the independent component method of building a flat software hierarchy.

Depicts how components communicate with each other

Ok, so hopefully at this stage you have a reasonably good idea of why this system works. If theres still confusion, please leave a comment and I’ll try and clear things up. Time to move on to implementation details.

I’m not going to implement the entire thing and just give out the code for people to use because that would take more time than I have to write this post. Also, different projects have different requirements and a system I build now may not be ideal for whatever you have in mind. Best to leave it up to you to fine tune the details to your needs. The version presented here whould give you ideas, but it won’t be terribly good or efficient.

Lets start with a component:

class Component {
private:
     static std::map<unsigned int, std::vector<Component*> > eventMap;
protected:
     // Register for all events of type "type".
     void registerForEvent (const unsigned type);
     // Send an event.
     void send (const Event* const event);

public:
     // Event handler, called when an event, which is being listened for, is received.
     virtual void eventReceived(const Event* const event)=0;
};

And the implementation:

std::map<unsigned int, std::vector<Component*> > Component::eventMap;

void Component::registerForEvent (const unsigned int type) {
    eventMap[type].push_back(this);
}
void Component::send (const Event* const event) {
    std::vector<Component*>& components = eventMap[event->type];
    for (std::vector<Component*>::iterator i = components.begin(); i != components.end(); i++) {
        (*i)->eventReceived(event);
    }
}

All events are derived from the Event base type:

class Event {
public:
    Event (unsigned int t) : type(t) {}
    virtual ~Event () {}

    const unsigned int type;
};

Lets test this with some stupid events:

enum EventIdentifiers {
    QUIT_EVENT=0,
    PRINT_HELLO,
    PRINT_MESSAGE
};

class MessageEvent : public Event {
public:
    MessageEvent () : Event(PRINT_MESSAGE) {}
    virtual ~MessageEvent () {}

    std::string message;
};

Now I’ll implement some very simple and crude components, just to have something that can be run:

class HelloPrinter : public Component {
public:
    HelloPrinter () {
        registerForEvent(QUIT_EVENT);
        registerForEvent(PRINT_HELLO);
        registerForEvent(PRINT_MESSAGE);
    }
    virtual ~HelloPrinter () {}

    void eventReceived(const Event* const event) {
        if (event->type == QUIT_EVENT) {
            std::exit(0);
        }
        else if (event->type == PRINT_HELLO) {
            std::cout << "Hello!\n";
        }
        else if (event->type == PRINT_MESSAGE) {
            std::cout << "Message: " << static_cast<const MessageEvent*>(event)->message << "\n";
        }
    }

    void sendQuit () {
        Event event(QUIT_EVENT);
        send(&event);
    }
    void sendHello () {
        Event event(PRINT_HELLO);
        send(&event);
    }
     void sendHelloMessage (const std::string&amp; message) {
        MessageEvent event;
        event.message = message;
        send(&event);
    }
};

Ok, almost done. Lets tie it all together:

int main (int argc, char** argv) {
    HelloPrinter a, b, c;
    a.sendHello();
    b.sendHelloMessage("Hi from b");
    c.sendQuit();
}

This should print “Hello” three times followed by “Hi from b” three times and then it should quit.

Ok, I’ll be the first to admit that this implementation is extremely limited and suffers from a bunch of flaws – BUT hopefully you can see the ideas and use that to implement a much more powerful version. Before I leave you to experiment, let me briefly mention some improvements which could be made to the above code. I’m sure you can think of many more too:

• Should the sending component receive its own events? Perhaps the sender should be able to choose.
• Should events be processed right away? This is useful for simple programs, but for large systems, you may end up in situations where some components never get to process events because other events are always processed first. A good solution would be to queue up all events, instead of sending them right away and then dispatch them when all event handlers have returned.
• Should events be processed sequentially? It may be better to process them in threads. One good solution would be to have a pool of threads which will execute the event handlers. Since communication is done through immutable events, the handlers can all run at once.
• The events themselves can be constructed from a memory pool to make creating and destroying events (event large events) a fast and cheap operation.

At some point in the future, I will implement (because I will need an implementation soon) and explain an implementation which has all of those features and probably some others too. I cannot commit to a date though, could be tomorrow or it could be next year.. who knows.

I hope that seeing the idea in code has helped you understand what it is I’m talking about and hopefully this will spark your imagination and creativity and perhaps motivate you to implement your own, more advanced, efficient and powerful versions. I’d love to hear what people come up with, so if you do implement this yourself, I’d appreciate a quick comment!