A simple generational identification number allocator.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
Michael Fiano b87b60d2cd
Update system definition.
1 month ago
src First commit. 1 month ago
LICENSE First commit. 1 month ago
README.md First commit. 1 month ago
identifier-pool.asd Update system definition. 1 month ago

README.md

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.