Database.Muesli.IdSupply

Unique DocumentKey allocation functions.

Since we use IntMaps for our indexes, a (faster) auto-incremented key will be exhausted on 32 bit machines before we reach a maxBound number of documents, because deleted keys cannot be reused.

This module should be imported qualified.

Documentation

type IdSupply = IntMap Int

A map from keys to gap sizes.

empty :: IdSupply

Holds a single gap of size maxBound - 1, starting at address 1.

reserve :: DocumentKey -> IdSupply -> IdSupply

Removes a key from the supply. Used during log loading.

alloc :: IdSupply -> (DocumentKey, IdSupply)

Allocates a fresh key from the supply.

Favours smallest numbers. For instance, after a document is deleted and garbage collected, the DocumentKey of that document typically becomes the smallest, and thus the first available. For this reason, IdSupply will normally be small and efficient.