The setup of this story is pretty elaborate, but let me explain.
In Godot script editor, there is a little side-window displaying your recently / currently open scripts. There is a few options for sorting them - by name, path or not sorting them at all. Internally, they are sorted by a string key.
I wanted to sort them by a modified date, which is a number - a uint64_t to be precise. And in descending order, so that the newest ones would end up on top.
Normally, you would just sort with a different comparison function. This is absolutely the right thing to do, but this is the Godot engine. I didn’t want to just run around adding stuff, refactoring and breaking things. No no no. What I want is to slot into the existing infrastructure with the smallest possible change.
Ascending order
To try out what I had in mind, the first simple implementation had ascending order. This is the natural order. Converting the number to a string is easy enough, although this poses some challenges of its own:
- Negative numbers don’t really work.
- It’s in the wrong order, damn it
- You should left-pad the string number with zeroes. This prevents cases like
10sorting in front of2, even though 10 is obviously larger. You should pad the numbers to the number of digits of the largest number in your compare set. This requires looping over the array one more time, which sucks.
It’s funny working with such a large numbers like timestamps. We are currently living around 1.7 billion-th second. That means this bug would occur at 10 billion-th second, which is currently ~263 years away 😄
How can I manipulate the number to reverse the order? If the key would be numerical, the easiest thing to do would be to just multiply it by -1. But the key is a string, so this approach doesn’t fly. AND the value is an unsigned integer, so it doesn’t even feel right.
Descending order
Here my genius struck. If you XOR the number with a number greater than yours that has all bits set to 1 (0xFFFFFF kinda thing), it’s like you subtracted it. Which is basically what we want.
To make things even better, in C++ we know exactly what this number is. It’s UINT64_MAX aka 0xFFFFFFFFFFFFFFFF aka 18446744073709551615. Neat!
I’ll call this number a ceiling value from now on.
So I did a XOR with the maximum uint64 value, stringified the result and set it as the comparison key. Works like a charm.
Here is the actual piece of code. It’s a little Godot-specific, like the String class, but you get the idea.
uint64_t modified_time_desc = se->get_edited_resource()->get_last_modified_time() ^ UINT64_MAX;
sd.sort_key = String::num_uint64(modified_time_desc);This solution has its limit
If the comparison value is the same length as the ceiling value (which it is) and its leftmost bit is set to 1, this simple method breaks down. Let’s explore this possibility.
Files created at the time of writing have a modified timestamp of ~1701887444 seconds. This is counted from the start of the unix epoch in 1970 and amounts to almost 54 years. Seems about right.
The ceiling value in our case is the maximum unsigned 64-bit number, which is 18446744073709551615 seconds.
- 18,446,744,073,709,551,615 seconds
- 213,503,982,334,601.28 days
- 584,942,417,355.072 years
This is a crazy high value. The unsigned 64 bit integer will serve us well for the next ~585 billion years. But the breaking point of this approach comes much sooner. The first bit of a 64 bit number being set to 1 is enough for it to fall apart.
>>> bin(0xFFFFFFFFFFFFFFFF)
'0b1111111111111111111111111111111111111111111111111111111111111111'
>>> bin(0x8000000000000000)
'0b1000000000000000000000000000000000000000000000000000000000000000'This number 0x8000000000000000 is 9223372036854775808 in decimal.
- 9,223,372,036,854,775,808 seconds
- 106,751,991,167,300.64 days
- 292,471,208,677.536 years
How I see it, we have about ~292 billion years of runway, before I have to think of something more clever. There might be an entire new universe by then 😁
If you read this far, congratulations, you are awesome! 👏