Windowing Systems by Example: 3 - I Like to Move It

Hello, and welcome back to WSBE, if you've been following along for the last couple of articles! If you're just joining us, this is a series of articles in which we're exploring the design and implementation of a simple windowing system step-by-step in C (for use, ex: in a hobby OS[1]).

Thus far, we've begun by creating a minimal window class along with a drawing abstraction class with which those windows could display themselves. Then, last week, we focused on structure a bit and implemented a 'desktop' class to do the job of organizing all of our child windows and serve as a central hub for window management actions, and also built a simple linked list class which we needed for storing the windows in that desktop.

Some may have found last week a bit boring as we didn't really get a big change in terms of output, but, as we mentioned at the end of that article, it laid a good amount of groundwork that we need in order to implement some core window management functions. So hold onto your butt, because that's what we're going to dive into today.


There's a Mouse in the House

No more beating around the bush: Today we're going to make our windows raise-able and move-able[2]. To be able to trigger such actions, we're going to need to bring some input onto the scene in the form of the mouse, at long last. As such, we'll begin by expanding our desktop class with a method that will allow the desktop to react to actions by the mouse device and serve as the source from which all events will flow[3].

So, the code. We're going to add some properties to the desktop class to facilitate the mouse handling we're about to do by storing the mouse status[4].

typedef struct Desktop_struct {
    List* children;            //old
    Context* context;          //old
    uint8_t last_button_state; //To track whether the mouse was last down or up
    uint16_t mouse_x;          //Current position of cursor on desktop
    uint16_t mouse_y;          
} Desktop;

Now to put that into use. For our mouse handling method, we'll start by addressing window raising. For this, we want to detect a button up->down transition. If we pass that test[5], we want to find if our mouse is within the bounds of a child. Our desktop's child list ordering represents relative depth on screen, so the easiest way to do this is to iterate backwards[6] through that list until the current child's bounds encompass the current mouse location. If the mouse is within the bounds of multiple windows it doesn't matter because we'll detect the higher window first, break the loop and never encounter the lower window. Cheap occlusion is best occlusion.

//Interface method between windowing system and mouse device
void Desktop_process_mouse(Desktop* desktop, uint16_t mouse_x,
                           uint16_t mouse_y, uint8_t mouse_buttons) {

    //For window iterating
    int i;
    Window* child;

    //Capture the reported mouse coordinates
    desktop->mouse_x = mouse_x;
    desktop->mouse_y = mouse_y;

    //Check to see if mouse button has been depressed since last mouse update
    if(mouse_buttons) {
        //If so, check for a button up -> down transition
        if(!desktop->last_button_state) {

            //Here's that window bounds-checking loop we were talking about
            for(i = desktop->children->count - 1; i >= 0; i--) {

                child = (Window*)List_get_at(desktop->children, i);

                //Bounds check on the current window
                if(mouse_x >= child->x && mouse_x < (child->x + child->width) &&
                   mouse_y >= child->y && mouse_y < (child->y + child->height)) {

                    //Mouse was depressed on this window, so do the raising
                    List_remove_at(desktop->children, i); //Pull window out of list
                    List_add(desktop->children, (void*)child); //Insert at the top 

                    //Since we hit a window, we can stop looking

    //Now that we've handled any changes the mouse may have caused, we need to
    //update the screen to reflect those changes 

    //Update the stored mouse button state to match the current state 
    desktop->last_button_state = mouse_buttons;

So, pretty much what we said. Oh, and we also implemented window raising, almost by accident it was that easy. I told you that the groundwork in making this desktop object would pay off for this stuff, and it did. Since we're just drawing windows from back to front right now, to raise a window we just have to pop it out of the list and stash it back at the end of the list. When we redraw, it's now the last thing drawn.

Oh, okay, so yeah our list class doesn't actually have a List_remove_at() function. But come on, we already made a lookup function, so we already know how to find an element in the list by index. To implement removal at an index, we just do the same thing but then repoint the nodes on either side of that list node:

void* List_remove_at(List* list, unsigned int index) {

    //The same damn lookup as List_get_at
    void* payload; 

    if(list->count == 0 || index >= list->count) 
        return (void*)0;

    ListNode* current_node = list->root_node;

    for(unsigned int current_index = 0; (current_index < index) && current_node; current_index++)
        current_node = current_node->next;

    //This is where we differ from List_get_at by stashing the payload,
    //re-pointing the current node's neighbors to each other and 
    //freeing the removed node 

    //Return early if we got a null node somehow
        return (void*)0;

    //Stash the payload so we don't lose it when we delete the node     
    payload =  current_node->payload;
    //Re-point neighbors to each other 
        current_node->prev->next = current_node->next;

        current_node->next->prev = current_node->prev;

    //If the item was the root item, we need to make
    //the node following it the new root
    if(index == 0)
        list->root_node = current_node->next;

    //Now that we've clipped the node out of the list, we should free its memory

    //Make sure the count of items is up-to-date

    //Finally, return the payload
    return payload;

It looks a little long, but it's that easy. We're literally now completely finished with the core implementation of window raising. Done[7]. I guess... move on to moving things? It is kind of the title of the article.


Everything in Its Right Place

Basic window movement is going to be just about as trivial to implement as raising was, and is going to be a simple extension of that code. That code already provides us a mechanism for determining what window was under the mouse when the button was pressed.

All we need to do is capture what window that was and assume that we're dragging it until we detect that the the mouse button has been released. Finally, if we're in the middle of a drag we just have to update the dragged window's location before we redraw. First, we need some dragging status info properties, then we can write the logic:

typedef struct Desktop_struct {
    //[All of the old properties here]
    Window* drag_child;  //-The window being dragged or null if no drag
    uint16_t drag_off_x; //-Offset between the corner of the window and
    uint16_t drag_off_y; // where the mouse button went down
} Desktop;
//Now, the updates to the mouse handler
void Desktop_process_mouse(Desktop* desktop, uint16_t mouse_x,
                           uint16_t mouse_y, uint8_t mouse_buttons) {

    //[Var declaration and mouse coordinate capture]

    if(mouse_buttons) {
        if(!desktop->last_button_state) {
            for(i = desktop->children->count - 1; i >= 0; i--) {

                child = (Window*)List_get_at(desktop->children, i);

                if(mouse_x >= child->x && mouse_x < (child->x + child->width) &&
                   mouse_y >= child->y && mouse_y < (child->y + child->height)) {

                    //[Raise window in list]

                    //Get the offset and the dragged window
                    desktop->drag_off_x = mouse_x - child->x;
                    desktop->drag_off_y = mouse_y - child->y;
                    desktop->drag_child = child;

                    //Since we hit a window, we can stop looking
    } else { //We add an else to the button being down to cancel the drag

        desktop->drag_child = (Window*)0;

    //Update drag window to match the mouse if we have an active drag window
    if(desktop->drag_child) {

        //Applying the offset makes sure that the corner of the
        //window doesn't awkwardly suddenly snap to the mouse location
        desktop->drag_child->x = mouse_x - desktop->drag_off_x;
        desktop->drag_child->y = mouse_y - desktop->drag_off_y;
    //[Paint changes and update captured button status]

There. Moving done. Granted, this will make the windows move no matter where we press the mouse down on them whereas your standard window manager will just have a draggable titlebar or something, but we'll address that when we start adding window chrome.

Now we should be all good to wire this stuff up to our application's entry point, but there's a couple of exceedingly minor things we're missing[8].


A Whole Lot of Flash for Nothing

As it stands, we've been setting the 'window' color in the Window_paint() method, which worked fine because we only painted once. But we need a stable place to set that now that we're redrawing on every mouse event, or the windows are going to all change color every time we move the mouse[9]

//Update the window properties to keep stable track of the drawing color
typedef struct Window_struct {  
    //[All of the old properties...]
    uint32_t fill_color; //What it says on the box
} Window;

Now to assign that value in a more stable place. The Window constructor will do fine:

//Window constructor
Window* Window_new(uint16_t x, uint16_t y,  
                   uint16_t width, uint16_t height, Context* context) {

    //[Window allocation...]
    //[Init other properties...]

    //Moving the color assignment to the window constructor
    //so that we don't get a different color on every redraw
    window->fill_color = 0xFF000000 |            //Opacity
                         pseudo_rand_8() << 16 | //B
                         pseudo_rand_8() << 8  | //G
                         pseudo_rand_8();        //R

    return window;

//And make sure we update the paint method to match
void Window_paint(Window* window) {

    Context_fillRect(window->context, window->x, window->y,
                     window->width, window->height, window->fill_color);

Now our desktop won't look like the accouterments to some sweet 90s warehouse party.


But Wait, There's More

Will the minutia never end? There's one more thing it would be nice to have if we're going to be using the mouse to click on things and that would be... a mouse. An actual mouse cursor, if we're going to be specific.

Some day, we're going to draw a really cool and unique cursor that will put all UI design of the last 30 years to shame[10]. But right now, we don't even have line drawing going on much less bitmaps, so we're going to keep it ultra-simple and just use those mouse coordinates we stashed to draw a small black rectangle at the end of our desktop painting loop:

 void Desktop_paint(Desktop* desktop) {
    //[Var declaration...]

    //[Clear desktop...]
    //[Draw list of children...]
    //Simple ugly mouse. As usual color is ABGR so adjust to your system
    Context_fillRect(desktop->context, desktop->mouse_x,
                     desktop->mouse_y, 10, 10, 0xFF000000);


A Better Mousetrap

As always, our final task is to tie everything together by using what we've built in our entry code. This time, we don't have to do much except for query the OS for mouse activity and then feed that data to the desktop's mouse handler as it comes.

The standard way you would probably get the mouse activity in most environments would be to call a function that waits for the mouse driver to detect activity within a loop, but my code has to compile down to JavaScript and JS is not a huge fan of polling loops so my 'fake_os' calls used in the code below take a callback instead. Since that's kind of an unreasonable assumption for most other uses, I'm providing an example of the polling implementation as well.

//Our desktop object needs to be sharable by our main function
//as well as our mouse event callback. You wouldn't need to worry
//about this if you're polling instead.
Desktop* desktop;

//The callback that our mouse device will trigger on mouse updates
void main_mouse_callback(uint16_t mouse_x, uint16_t mouse_y, uint8_t buttons) {

    Desktop_process_mouse(desktop, mouse_x, mouse_y, buttons);

//The new and improved entry point
int main(int argc, char* argv[]) {

    //Init the context, desktop, and some windows as usual
    Context context = { 0, 0, 0 };
    context.buffer = fake_os_getActiveVesaBuffer(&context.width, &context.height);
    desktop = Desktop_new(&context);
    Desktop_create_window(desktop, 10, 10, 300, 200);
    Desktop_create_window(desktop, 100, 150, 400, 400);
    Desktop_create_window(desktop, 200, 100, 200, 600);

    //Do an initial paint

    //Install the desktop mouse handler callback into the mouse driver

    //If you were doing a more standard top level event loop
    //(eg: weren't dealing with the quirks of making this thing
    //compile to JS), it would look more like this:
    //    while(1) {
    //        fake_os_waitForMouseUpdate(&mouse_x, &mouse_y, &buttons);
    //        Desktop_process_mouse(desktop, mouse_x, mouse_y, buttons);
    //    }

    //In a real OS, since we wouldn't want this thread unloaded and 
    //thereby lose our callback code, you would probably want to
    //hang here or something if using a callback model
    return 0; 

Now we're all plumbed up and ready to go. Build it. Try it out. My god, it's actually starting to look like a... sort-of window... thingy.


Sweet, Sweet Payoff

And so your patience from last week has been rewarded! You move your mouse on the table, it moves a thingy on the screen. You click the mouse on a rectangle, the rectangle pops up for action. You hold the mouse button down on a rectangle and you can fling it all over the place. This is progress. This is tangible.

But I have bad news, buckaroo. This still sucks[11]. And there's one reason in particular. It's slow as shit.

I don't know, you say to yourself. Seems pretty snappy to me.

But get this: Every time the screen gets redrawn, we're redrawing all of the desktop, then all of window 1, all of window 2, all of window 3 and the mouse rectangle. So every time we move the mouse, we do the work of writing (1024x768 + 300x200 + 400x400 + 200x600 + 10x10) = over 1.1 million pixels into the framebuffer. Into a framebuffer that, in its entirety[12], only contains about 2/3 that number of pixels.

Imagine it takes ten average CPU instruction times for us to set the value of a pixel in framebuffer RAM. If all we did was move the cursor two pixels to the left, all we need to update are the 100 pixels of the cursor and the strip of 20 pixels we exposed of the desktop or window that was below it. But instead of the 1,200 instructions that would've taken, we took over 11,000,000 and wasted at least 10,998,800 instructions that could've been used to handle actual useful background processes.

And that's only for drawing a flat desktop, three flat-colored window rectangles, and the mouse. Imagine how bad those numbers are going to get when you have 30 windows that are painting themselves full of widgets on the screen.

So, be happy. We're most assuredly making progress. But next week, we're going to go even further and investigate the use of clipping to make our drawing more realistically efficient. See you then!

Fun Time Programmin Puzzles: If you play around with dragging the windows, you'll notice that they 'disappear' when they cross the top or left of the screen. If you want to solve an easy challenge, see if you can find any sign of why this happens and fix it.

As always, the source, ready for easy immediate use in your browser thanks to the black magic that is emscripten, can be found here at my github. You'll notice that we've started splitting up the code by class to keep our expanding code more manageable. All we did was put the core structs and method declarations for each class into their own headers and the implementations of those methods into separate source files, so it shouldn't be too bad to follow.