README.md

Data oriented UI (part 3)

In the previous part (Part 2) I created hover and click behaviours, so we could make buttons or just any hover elements. But how to use them in the game? I don't want to store a pointer to the button. UI library could reorder elements or delete them as it wishes, I don't want this hard constraint, especially with no way to check is my pointer valid or not.

Accessing elements in the game code

Introducing ui::handle

Let's make an abstraction.

I will make a structure consisting with only one integer, like that:

struct handle
{
    uint32 id;
};

Where the 32-bit intger id will store actually two pieces of information: which array I need to look in, and what index in that array I need to extract.

enum class array_of : uint8
{
    NONE = 0,
    GROUPS,
    SHAPES,
};

handle make_handle(array_of a, uint32 index)
{
    handle result;
    result.id = ((((uint32) a) << 24) | (index & 0x00ffffff));
    return result;
}

array_of which_array(handle id)
{
    auto result = (array_of) (id.id >> 24);
    return result;
}

uint32 get_index(handle id)
{
    uint32 result = (id.id & 0x00ffffff);
    return result;
}

Now we can make a hash table.

Hash table

You can use a production-ready hash table and skip this section, if you want. But I love doing everything from scratch, so we will make one really quick. It's really not that hard to make a hash table! (It's much more difficult to make a good one, but if you don't make a crappy one, how would you make a good one someday?)

First I consider hash table will map uint64 values to ui::handles, so I add two arrays to the ui::system structure.

struct system
{
    // ...
    
    array<uint64> hash_table_keys;
    array<handle> hash_table_values;
};

We also will support two operations, adding an element, and finding one in the hash table. It's pretty straightforward to do:

void add_handle_to_hash_table(system *s, uint64 key, handle value)
{
    for (usize offset = 0; offset < s->hash_table_keys.size(); offset++)
    {
        usize index = (key + offset) % s->hash_table_keys.size();
        if (s->hash_table_values[index].id != 0) // @note it will not be 0 for any valid handle
        {
            s->hash_table_keys[index] = key;
            s->hash_table_values[index] = value; 
            break;
        }
    }
}

handle get_handle_from_hash_table(system *s, uint64 key)
{
    handle result = {};
    for (usize offset = 0; offset < s->hash_table_keys.size(); offset++)
    {
        usize index = (key + offset) % s->hash_table_keys.size();
        if (s->hash_table_keys[index] == key)
        {
            result = s->hash_table_values[index];
            break;
        }
    }
    
    return handle;
}

element *get_element(system *s, handle h)
{
    element *result = NULL;
    
    usize index = get_index(h);
    switch(which_array(h))
    {
        case array_of::GROUPS:
            result = s->groups.data() + index;
        break;
        
        case array_of::SHAPES:
            result = s->shapes.data() + index;
        break;
        
        default:
            ASSERT_FAIL();
    }
    
    return result;
}

As you can see, I use simple open-address scheme for my hash table, where I pick next slot when the slot by the key is already occupied. This scheme very basic and will not perform well under stress conditions, also it does not allow to remove elements from hash table. But it's ok, we are not hash table experts, we can address those issues later, or as I said, use a hash table from a library.

Usage

What this hash table allow us to do, is to store abstract ids on the client side, so game would not know the real handle, but only store an abstract number.

This allows us to do such queries in the game code:

if (ui::button(s, HASH("ButtonOk1"))
{
    // Do the code when this button is clicked!
}

I will define ui::button be a function, that will query the element with the name ButtonOk1 and return true when it's clicked.

bool button(system *s, uint64 id)
{
    handle h = get_handle_from_hash_table(s, id);
    element *e = get_element(s, h);
    bool result = (e && e->clickable && (s->active == e->clickable));
    return result;
}

I use uint64 as the input here, as well as in the array<uint64> hash_table_keys because it is versatile. You can use anything: consequtive numbers, hashes of strings, etc.