Some Common Lisp data structures I have found useful

This repo contains a collection of data structures I’ve found useful. Currently there is only one published. They’re independent of each other except where noted. There are ASD system declarations for each of them. Unless noted they should be portable Common Lisp.

Package names look like org.tfeb.ds.<ds>.

Ordered hash tables: OHT

Quite often I’ve found myself wanting to collect a bunch of things in order, where code may want to quickly check if a thing has previously been collected and perhaps modify the value if so. ‘Quickly’ implies a hash table, but they don’t preserve insertion order of course. An OHT is like a hash table which remembers insertion order: you can then iterate over it in insertion order.

The first implementation of this used a doubly-linked list to remember the order (doubly-linked made deletion much easier). This was never going to be thread-safe without a lock. This version tries to be thread-safe even without a lock, relying on two things: the implementation must be able to atomically increment something stored in a structure slot, and hash tables must be thread-safe.

The cost of this is that it’s quite a lot slower (6–8 times experimentally) than raw hash tables, and that, if many items are removed, iteration can be slow as there are big holes in the index. The implementation can also, theoretically, wrap around, if the atomic increment uses modular arithmetic. These are not problems for me, and the last is probably rather theoretical.

In cases where multiple threads try to insert the same key it can also create orphans: entries in one of the two underlying hash tables which can’t be referenced. You can garbage-collect these explicitly, and iterating over the OHT will also garbage-collect them.

The interface is mostly like that of hash-tables, although the functions are named the other way around.

oht is the type of ordered hash tables.

make-oht is like make-hash-table. Don’t use any options which let the table be weak, or single-threaded only.

oht-get is like gethash, and is an accessor.

oht-remove is like remhash.

oht-size, oht-rehash-size, oht-rehash-threshold, oht-test and oht-count are like the corresponding hash-table functions.

copy-oht will copy and compact an OHT object.

map-oht is like maphash: it maps in insertion order.

in-oht is an iterator for Štar: it iterates in insertion order. There is an optimizer. This will cause any orphans to be collected.

copy-oht will copy an OHT. The copy will be compacted, so there are no gaps in the index sequence, and no orphans.

gc-oht will garbage-collect any orphans in the OHT. It takes two keyword arguments.

  • gc (default true) says to actually collect orphans. If this is false it simply returns information.
  • single-threaded (default false) performs some sanity checks which might not succeed if other threads are modifying the OHT. If this is not true then gc-oht should be thread-safe.

gc-oht returns three values: the object, a count of orphans and how dense the object is as a rational between 0 and 1. Iteration over large tables with low density may be slow.

oht-thread-safe is a constant variable which is true if OHT’s are thread-safe in the current implementation.

Package, module, dependencies

OHT lives in and peovides org.tfeb.ds.oht. It depends on org.tfeb.star and org.tfeb.hax.utilities, available in all good Quicklisp distributions.

These modules are coyright 2026 Tim Bradshaw. See LICENSE for the license.