identifier-pool

2022-07-08

A simple generational identification number allocator.

Upstream URL

git.mfiano.net/mfiano/identifier-pool

Author

Michael Fiano <mail@mfiano.net>

License

MIT
README

identifier-pool

A simple generational identification number allocator.

Overview

This library is able to generate increasing identifiers (integers) in such a way that previously deallocated identifiers are available to be reclaimed by the generator the next time one is allocated. Essentially, it solves the "ABA Problem": https://en.wikipedia.org/wiki/ABA_problem

It does so in a space-efficient manner, without the need for the storage of a list of deallocated identifiers. It does this by keeping deallocated identifiers around and modifying their data on deletion to build a sort of implicit linked list. That is, when an identifier is marked for deletion, the following occurs:

  • The packed version portion of its data is incremented.

  • The packed ID portion of its data is set to the integer stored in the pool's FREE-HEAD slot (FREE-HEAD can be thought of as the head of the implicit linked list). If FREE-HEAD is null, then instead, all of the bits of the ID are set. #xFFFFFF represents the "invalid" ID.

  • FREE-HEAD is set to the ID portion of its data.

This, in effect, constructs an implicit linked list of the next available identifiers that can be generated.

Install

(ql:quickload :identifier-pool)

License

Copyright © 2019-2022 Michael Fiano mail@mfiano.net

Licensed under the MIT License.

Dependencies (2)

  • dynamic-array
  • mfiano-utils

Dependents (0)

    • GitHub
    • Quicklisp