Keymap cache design

[gedankenexperimenter]

Iterate through active layers (from the top active layer, which might be below the real top active layer). For each layer, use its iterator to check every key (sparse layers only have to check entries once), and if the cached layer number is less than that layer's number, look up the Key value. If the key is not transparent, cache the layer number and key. While checking each cache entry, update the cached value of bottom_mapped_layer so we know when it's safe to stop checking lower layers. I'm pretty sure that value is only needed during this loop.

When activating a layer, only that one layer needs to update the cache, but when a layer is deactivated, we need to clear that layer's entries from the cache, and update everything. Layer 0 might need to be special, to avoid an extra lookup on layer 0 for each deactivated cache entry. Probably, it's better to invalidate the cache by clobbering entries for layer N with a lookup of layer 0, just to simplify the rest. Actually, no, I don't think so; when searching we do a lookup if the cached layer number is less than or equal to our current value? No, I was right the first time; that would cause extra unnecessary lookups on upper layers.

[gedankenexperimenter]

Improved design:

Caches

• top active layer (one byte)
• active layer values (one byte/key)
• mapped keys (two bytes/key)

The last two could be implemented separately, or as a single LayerKey array — I don't know which would be more efficient. To invalidate a cache entry we write all ones to both the active layers entry and the mapped keys entry for that key.

Layer changes

There are four different layer transitions possible:

• activate layer n
• deactivate layer n
• shift to layer n
• move to layer n

Activate layer

When activating a layer, we search the active layers cache for values below the target layer, and invalidate them (and in the mapped keys cache).

If the target layer is higher than the current top active layer, update top active layer.

Deactivate layer

When a layer is _de_activated, search the active layers cache for entries equal to the target layer, and invalidate them.

If the target layer is equal to the current top active layer, find the next lower active layer, and update the top active layer.

Shift to layer

When shifting to a layer, update the top active layer, but don't set its bit in the layer state array. Search the active layers array for values not equal to the target layer, and invalidate them (probably everything).

Move to layer

Unset layer state bits higher than the target layer, set state bit for target, set top active layer, and invalidate everything not equal to the target layer.

Lookups

When doing a lookup, we check the mapped keys cache for an address. If it's Key_Transparent, we ask the active layers, starting with top active layer for a lookup, passing them the caches by reference. If a layer finds a non-transparent entry, it returns true, but it could update any or all of the keymap cache entries. This works well for sparse layers, so they don't waste lookups, especially in EEPROM.

[gedankenexperimenter]

EEPROM layers

Layers defined in EEPROM should be initialized with a reference (not a pointer) to a PROGMEM layer, which will be a fallback. When initializing the EEPROM layer (at runtime, of course), we read a byte that identifies the index number of the fallback layer pointer. If that pointer is nullptr, initialization should fall back to PROGMEM layer 0, since that's the only one that's guaranteed to exist.

[gedankenexperimenter]

…or maybe it can be a pointer, but we can check for null, which means no fallback (all undefined keys are transparent).

[gedankenexperimenter]

Furthermore, the keymap will need to store two Layer* arrays: one for PROGMEM, and one for EEPROM, only one of which is active at a time.