... and that doesn't necessarily mean that malloc() failed.
We do *not* want to evict a heavy-hitter by an unfrequent element.

Note: even the implementation currently in master *did* return NULL,
so some parts of the code were just wrongly returning ENOMEM.

The implementation is now similar to set-associative caches
that x86 CPU use.  Also the API is changed a bit, leading to
slight simplification of our use patterns.