If you're using arenas for memory management, here's a way to implement an undo system that you can write once and pretty much never have to touch again as you add features. I wrote this for a game level editor, but you can apply the technique to any user-facing program.
The concept is straightforward. Each action the user takes performs a transformation on data. All we need to do is remember what changed and we can reverse it, un-reverse it, etc. With other memory management strategies, this may not be easy to accomplish since tracking where the data is in memory becomes complex. Since arenas are just one big contiguous buffer underneath, it's trivial to generate a diff between two points in time. You can track changes to multiple arenas too - either by keeping a pointer to the relevant arena, or in the following example just tracking them directly in the Undo_State.
First, you need to generate diffs. I keep a second copy of each arena for which we want to track undos. If doing this is too great a memory cost for you, you might want to explore a more specialized way of creating diffs.
For the level editor, I had two arenas I need to track. One for the level itself, and one for the current room being edited. There was no need to track outside rooms, since the user can only edit one room at a time. The structs look something like this:
struct Room {
Arena arena;
};
struct {
Arena arena;
Room *rooms;
int num_rooms;
} level;
struct Undo_State {
char *description;
// For brevity, assume an array implementation.
Array_Diff room_diffs;
Array_Diff level_diffs;
// We need to track the sizes of the Arenas as well.
size_t room_arena_offset;
size_t level_arena_offset;
};
The level editor follows with holding snapshots of the relevant arenas:
struct {
Arena room_undo_snapshot;
Arena level_undo_snapshot;
// ...
int current_room;
// Assume we have a circular buffer implementation. It's not important for this example.
Circular_Undo_Buffer undo_states;
} level_editor;
You only need to synchronize the arenas (outside of initialization) after recording a diff. This means you can batch together multiple operations into a single undo.
void move_objects() {
move_object(object_a);
move_object(object_b);
push_undo("Move objects"); // When undone, this will undo both the moves
}
void push_undo(char *description) {
// If an undo is pushed after some undos have occurred, we clear the following undo states.
level_editor.undo_states.count = level_editor.undo_index;
Undo_state *state = circular_push_new(&level_editor.undo_states);
state->description = description;
state->level_diffs = {0};
state->room_diffs = {0};
// Get the diffs for each arena and store them in the undo state.
Arena room_arena = level.rooms[level_editor.current_room].arena;
get_diffs(
level_editor.room_undo_snapshot.buffer,
room_arena.buffer,
room_arena.size,
&state->room_diffs);
state->room_arena_offset = room_arena.offset;
get_diffs(
level_editor.level_undo_snapshot.buffer,
level.arena.buffer,
level.arena.size,
&state->level_diffs);
state->level_arena_offset = level_arena.offset;
// Note: You can also record diffs on a struct or any arbitrary block of data here.
update_undo_snapshots(); // After we have the diffs, we can synchronize the snapshot arenas.
level_editor.undo_index = level_editor.undo_states.count;
}
void update_undo_snapshots() {
Arena room_arena = level.rooms[level_editor.current_room].arena;
memcpy(
level_editor.room_undo_snapshot.buffer,
room_arena.buffer,
room_arena.offset);
level_editor.room_undo_snapshot.offset = room_arena.offset;
memcpy(
level_editor.level_undo_snapshot.buffer,
level.arena.buffer,
level.arena.offset);
level_editor.level_undo_snapshot.offset = level.arena.offset;
}
That's all you need to push undo states. No need to write bespoke undo code for each operation in the program. Let's take a look at get_diffs:
struct Diff {
uintptr_t offset;
uint64 xor_value;
};
// returns the byte offset of the first difference, -1 if no different
// works in 64 bit chunks
uintptr_t compare_memory(void *a, void *b, size_t size) {
uintptr_t pa = reinterpret_cast<uintptr_t>(a);
uintptr_t pb = reinterpret_cast<uintptr_t>(b);
for(uintptr_t offset = 0; offset < size; offset += sizeof(uintptr_t)) {
uint64 *ua = reinterpret_cast<uint64*>(pa + offset);
uint64 *ub = reinterpret_cast<uint64*>(pb + offset);
if (*ua != *ub) {
return offset;
}
}
return -1;
}
void get_diffs(void *a, void *b, size_t size, Array_Diff *diffs) {
uintptr_t pa = reinterpret_cast<uintptr_t>(a);
uintptr_t pb = reinterpret_cast<uintptr_t>(b);
uintptr_t offset = 0;
while(offset < size) {
uint64 *ua = reinterpret_cast<uint64*>(pa + offset);
uint64 *ub = reinterpret_cast<uint64*>(pb + offset);
uintptr_t this_offset = compare_memory(ua, ub, size - offset);
if (this_offset != -1) {
offset += this_offset;
ua = reinterpret_cast<uint64*>(pa + offset);
ub = reinterpret_cast<uint64*>(pb + offset);
Diff d = {};
d.offset = offset;
d.xor_val = *ua ^ *ub;
diffs->data[diffs->count++] = d;
offset += sizeof(uintptr_t);
} else {
break;
}
}
}
Each Diff is on a 8 byte block. You could optimize this with SIMD at the cost of keeping larger diffs in memory, but the more clever option would be to generate an XOR of the entire buffer and compress the result.
Now that you have your diffs, all you need to do is apply the diffs when the user calls undo and redo.
void editor_undo() {
Undo_state *undo = circular_peek(level_editor.undo_states, level_editor.undo_index - 1);
if (undo) {
--level_editor.undo_index;
Arena *room_arena = &level.rooms[level_editor.current_room].arena;
apply_diffs(
room_arena->buffer,
undo->room_arena_offset,
undo->room_arena_diffs);
room_arena->offset = undo->arena_offset;
apply_diffs(
level.arena.buffer,
undo->level_arena_offset,
undo->level_arena_diffs);
level.arena.offset = undo->arena_offset;
update_undo_snapshots();
}
}
void editor_redo() {
if (level_editor.undo_index < level_editor.undo_states.count) {
Undo_state *redo = circular_peek(room_editor.undo_states, room_editor.undo_index);
if (redo) {
++level_editor.undo_index;
Arena *room_arena = &level.rooms[level_editor.current_room].arena;
apply_diffs(
room_arena->buffer,
redo->room_arena_offset,
redo->room_arena_diffs);
room_arena->offset = redo->arena_offset;
apply_diffs(
level.arena.buffer,
redo->level_arena_offset,
redo->level_arena_diffs);
level.arena.offset = redo->arena_offset;
update_undo_snapshots();
}
}
}
void apply_diffs(void *destination, size_t size, Array_Diff diffs, bool invert = false) {
uintptr_t pdest = reinterpret_cast<uintptr_t>(destination);
for(int i = 0; i < diffs.count; ++i) {
uintptr_t offset = diffs.data[i].offset;
assert(offset < size);
uint64 xor_val = diffs[i].xor_val;
if (invert) xor_val = ~xor_val;
uint64 *ptr = reinterpret_cast<uint64*>(pdest + offset);
*ptr ^= xor_val;
}
}