Windowing Systems by Example: 2 - Rectangle HQ

Last time, we decided to get started by implementing a basic Window class using our flavor of object-oriented C, in the process also creating a Context class to wrap our framebuffer details and abstract drawing[1] to our simple video device which we then used to draw some 'window' rectangles to our screen.

When we were done, I touched on some obvious ways in which what we wrote fails entirely at being a window manager. Today, we're going to start tackling one of those failures, namely the fact that our 'window manager' doesn't... you know. Manage windows. Kind of an issue.


We Need To Talk About the Children

First, I want to prepare you yet again to be a little let down: This week is going to be yet another instance of a bunch of code without much visual payoff. But I promise that once we have our fancy[2] infrastructure all worked out I promise we'll make up for it by going hog-wild with the ridiculous chrome[3].

Okay. So what's the plan? We need a way to manage the creation and organization of our windows, or else the core concept of a windowing system isn't really happening. So what we're going to want to do is create some other kind of class that will act as the parent of our windows and handle spawning and deleting them and[4] distributing mouse and keyboard events among them.

We also happen to be lacking a desktop, so why not just call the desktop the parent of our windows?

//Let's define an object for our desktop/parent class
typedef struct Desktop_struct {
    List* children;   //For storing a bunch of windows
    Context* context; //A context for drawing the windows and desktop
} Desktop;

Whoa whoa whoa. Wait up. We know what that second item is, a reference to a drawing context, that makes sense. But what the hell is that first type? Are you getting soft on us and importing libs, kid?

I'm not getting soft, we're goddamn doing this thing. We're going to get ourselves sidetracked for a moment and implement a List class for storing our list of windows. Sure, we could've just slapped an array of windows in there, but what if we end up needing to allocate more windows than we had the foresight to in the first place? Nope, this will not do. Let's get to listin'.

//A type to encapsulate a basic dynamic list
typedef struct List_struct {
    unsigned int count;  //The number of items in our list
    ListNode* root_node; //The first element in the list
} List;

//Basic list constructor
List* List_new() {
    //Malloc and/or fail null
    List* list;
    if(!(list = (List*)malloc(sizeof(List))))
        return list;

    //Fill in initial property values
    //(All we know for now is that we start out with no items) 
    list->count = 0;
    list->root_node = (ListNode*)0;

    return list;

Now just you wait a goddamned second, I hear you cry. Am I putting you on? WHAT ARE THESE ListNode THINGS.

The plan here is to keep it pretty simple with this list class and just make it an implementation of a doubly-linked list. So basically, this class is just going to wrap a bunch of linked list elements, for which we'll make -- you guessed it -- another class[5].

//A type to encapsulate an individual item in a linked list
typedef struct ListNode_struct {
    void* payload;                //Generic pointer to an object
    struct ListNode_struct* prev; //Self-referential back-pointer
    struct ListNode_struct* next; //Self-referential forward-pointer
} ListNode;

//Here's the basic ListNode constructor
ListNode* ListNode_new(void* payload) {

    //Malloc and/or fail null (I think you get the pattern at this point)
    ListNode* list_node;
    if(!(list_node = (ListNode*)malloc(sizeof(ListNode))))
        return list_node;

    //Assign initial properties
    list_node->prev = (ListNode*)0;
    list_node->next = (ListNode*)0;
    list_node->payload = payload; 

    return list_node;

Okay. There we are. We've finally hit the end of our trail and implemented the constructor for the most basic unit of this desktop/manager thing we're trying to build. We can now generate an object which holds a pointer to some other kind of object and which can potentially, but does not yet, point to others of its ilk.

I'm assuming here[6] that you already have a working knowledge of the concepts of this, the most stupidly basic data structure of them all, but if not you can take this quick refresher and get back to us.

So we can make our linked list and our list links, but we can't yet make our list links into a linked list. Before we move on back to the desktop class, we know that we're going to need to at least be able use our list to append windows as they're created and also to access them once they're there, so let's get those taken care of starting with the add method, which is pretty straightforward:

//Insert a payload at the end of the list
//Zero is fail, one is success
int List_add(List* list, void* payload) {

    //Try to make a new node, exit early on fail 
    ListNode* new_node;
    if(!(new_node = ListNode_new(payload))) 
        return 0;

    //If there aren't any items in the list yet, assign the
    //new item to the root node
    if(!list->root_node) {
        list->root_node = new_node;        
    } else {

        //Otherwise, we'll find the last node and add our new node after it
        ListNode* current_node = list->root_node;

        //Fast forward to the end of the list 
            current_node = current_node->next;

        //Make the last node and first node point to each other
        current_node->next = new_node;
        new_node->prev = current_node; 

    //Update the number of items in the list and return success

    return 1;

Easy. Make a node with the provided payload, then either stick it in the root position or use the existing root node to iterate to the end of the chain and stick the new node there, then increase our count.

Now we'll do the method to retrieve the payload of the linked-list-link for a given index. This way, among other things, we can throw this into a for-loop with an index variable to iterate its contents (in this case, our windows). [7]

//Get the payload of the list item at the given index
//Indices are zero-based
void* List_get_at(List* list, unsigned int index) {

    //If there's nothing in the list or we're requesting beyond the end of
    //the list, return nothing
    if(list->count == 0 || index >= list->count) 
        return (void*)0;

    //Iterate through the items in the list until we hit our index
    ListNode* current_node = list->root_node;

    //Iteration, making sure we don't hang on malformed lists
    for(unsigned int current_index = 0; (current_index < index) && current_node; current_index++)
        current_node = current_node->next;

    //Return the payload, guarding against malformed lists
    return current_node ? current_node->payload : (void*)0;

Okay, we can manage lists of things, now. Core concept: check. Let's put it in practice.


Gather 'Round, Children

So let's get back to that desktop class we were wanting to implement this week. As you remember, we're beginning its life as a pretty simple structure, just that list of windows we just implemented the data structure for and a context reference for drawing the child windows to. For now, all we're doing is spawning windows and drawing them, so that's all we need. Now that we have the missing link[8] implemented, let's implement that desktop constructor.

Desktop* Desktop_new(Context* context) {

    //Malloc or fail 
    Desktop* desktop;
    if(!(desktop = (Desktop*)malloc(sizeof(Desktop))))
        return desktop;

    //Use the new List constructor to create the child list
    //(or clean up and fail otherwise, of course)
    if(!(desktop->children = List_new())) {

        //Delete the new desktop object and return null 
        return (Desktop*)0;

    //Fill out other properties 
    desktop->context = context;

    return desktop;

Nothing we haven't seen before. But we said we want to spawn child windows and draw them, so let's make that happen. For the window spawning method, all we're really doing is plumbing together the Window constructor and the List_add function we just made above:

//A method to automatically create a new window in the provided desktop 
Window* Desktop_create_window(Desktop* desktop, unsigned int x, unsigned int y,  
                              unsigned int width, unsigned int height) {

    //Attempt to create the window instance
    Window* window;
    if(!(window = Window_new(x, y, width, height, desktop->context)))
        return window;

    //Attempt to add the window to the end of the desktop's children list
    //If we fail, make sure to clean up all of our allocations to this point
    if(!List_add(desktop->children, (void*)window)) {

        return (Window*)0;

    return window;

Then we just need to do the drawing. This is also basically just plumbing, in this case we're sticking together our new list access method and our window painting method. So that we see at least some visual change for all of our work today, we'll also make the desktop 'paint' itself by painting a background color beneath everything before iterating through the windows.

//Paint the desktop 
void Desktop_paint(Desktop* desktop) {
    //Loop through all of the children and call paint on each of them 
    unsigned int i;
    Window* current_window;

    //Start by clearing the desktop background
    Context_fillRect(desktop->context, 0, 0, desktop->context->width,
                     desktop->context->height, 0xFFFF9933); //Change pixel format if needed 
                                                            //Currently: ABGR

    //Get and draw windows until we stop getting valid windows out of the list 
    for(i = 0; (current_window = (Window*)List_get_at(desktop->children, i)); i++)

Now that's starting to look like some kind of actual manager of something![9]


Once More, With Feeling (And A Backdrop)

That's enough implementation of new crap today. We got our initial goals completed, namely that we now, instead of manually having to manage our own pointers for each window we want to make, have a central object which handles the spawning and drawing of windows. So let's update our main function to take advantage of that:

//Create and draw a few rectangles and exit
int main(int argc, char* argv[]) {

    //Fill this in with the info particular to your project
    //(In this case, we're still using our 'fake os' functions)
    Context context = { 0, 0, 0 };
    context.buffer = fake_os_getActiveVesaBuffer(&context.width, &context.height);

    //Create the desktop based on our new graphics context
    Desktop* desktop = Desktop_new(&context);

    //Now, we just replace the calls to the window constructor
    //with calls to the desktop window generator, which drops
    //the need for the win1, win2,... variables and gives us
    //centralized management basically for free
    Desktop_create_window(desktop, 10, 10, 300, 200);
    Desktop_create_window(desktop, 100, 150, 400, 400);
    Desktop_create_window(desktop, 200, 100, 200, 600);

    //And what's more, now we don't even have to deal with drawing 
    //each window individually. We can just ask the desktop to do
    //it all for us.

    return 0;

Sit back, wipe the sweat off of your brow, and crack your knuckles if you need it, because that's it for code today. If we give it a quick compile, we get this fancy new result:


I Am Serious. And Don't Call Me Shirley.

Even less new to see than last week. Why am I even wasting my time?

In this case, beauty is far more than skin deep. Don't be fooled by the fact that ultimately we really only added a blue background to last week's work. While it wouldn't be at all obvious from looking at it, by giving this thing a central source of window control we've actually set ourselves up to be able to handle all of the important tasks that our windowing system needs to perform.

The thing is, our windows need to know about each other, or, in this case, we need something that knows about all of our windows. Without some way of knowing how all of our windows are related to each other, we could never do any calculations of what the proper depth sorting of each of them is. We could never request that a window be raised or lowered, because we'd have no idea what we need to put that window ahead of or behind. And what's more, we'd have nothing to make that request to.

Next week, we're going to expand on both the desktop class and the list class that it uses in order to start implementing actual window operations: hiding, showing, raising, lowering and all of the other good stuff that makes windowing useful.

As always, full code for all of these articles can be found over in the git repo. Feel free to play with it and shoehorn into your own OS project, or, if you don't have time for that kind of foolishness, use the included build scripts to compile to JavaScript and run it right in your browser.