Limit req: number of cleanup calls reduced.

Doing a cleanup before every lookup seems to be too aggressive. It can lead to
premature removal of the nodes still usable, which increases the amount of work
under a mutex lock and therefore decreases performance.

In order to improve cleanup behavior, cleanup function call has been moved right
before the allocation of a new node.