$ show aio-libs/multidict
multidict is a high-performance, dual-implementation (C extension and pure Python) multi-value mapping library for Python, designed primarily for HTTP headers and URL query strings. It provides `MultiDict`, `CIMultiDict` (case-insensitive), read-only proxy variants, and the `istr` case-insensitive string subclass. The C extension, built with hand-written C and aggressive optimization, delivers O(1) lookups, insertion-order preservation, and thread-safe lock-free readers under CPython's free-threading mode. The public C API capsule enables other C extensions to create and manipulate multidicts directly. The codebase exhibits exceptional engineering discipline: behavioral parity between the two implementations, extensive test coverage including property-based (Hypothesis), concurrency stress, memory leak, and benchmark regression tests, plus a structured changelog with towncrier. While tightly coupled to CPython internals and carrying significant maintenance burden from free-threading support, the core data structure patterns and concurrency primitives are elegantly designed and potentially reusable in other C extension projects.
The LLM identified 5 files worth highlighting for reuse:
Implements a custom container (reflist_t) that collects PyObject references whose reference counts must be decremented after a critical section ends. This pattern defers Py_DECREF calls to avoid reentrancy issues (e.g., __del__ calling back into the multidict) and to allow safe release of retired hash-table entries under free-threaded Python. The design uses a small inline array spilling to heap-allocated memory, and is fully isolated: it depends only on Python's C API memory allocators and could be extracted into any C extension requiring deferred deallocation.
Provides a compact bitmap (bitmap_t) for tracking visited entries during hash-table walk operations (e.g., getall, update). Uses a stack-allocated array of 64-bit words with a heap fallback if the table size exceeds the inline capacity. This avoids polluting the hash table with per-entry marks and enables safe concurrent reads. The implementation is self-contained, using only basic C and Python memory management, and could be reused in any project needing a small, dynamically sized bit set.
Implements update_marks_t, a per-batch bookkeeping structure for bulk update/merge operations. It tracks which entries are modified or deleted so the post-update cleanup phase can handle half-deleted entries and avoid resizing races. The design handles duplicate keys across resize boundaries by recording the first and last seen index per key. This is a non-obvious solution to a subtle problem (maintaining consistency during hash-table mutation) and could be extracted into any project performing batch hash-table modifications.
Defines the public C API for multidict, exposed via a PyCapsule. The API struct is versioned (MultiDict_CAPI_VERSION) and only grows at the end to maintain ABI compatibility. Includes functions for constructing, accessing, and mutating multidicts directly from C extensions without Python API overhead. This is a well-executed pattern for exposing internal data structures to third-party extensions, with explicit version checking and inline wrapper functions for convenience. The design is isolated and could serve as a template for other projects wanting a stable C API.
The package entry point that transparently selects between the C extension (_multidict) and pure Python (_multidict_py) implementation at import time, controlled by the MULTIDICT_NO_EXTENSIONS environment variable. Provides all public type exports (MultiDict, CIMultiDict, proxies, istr, getversion, get_include). This pattern of dual-backend dispatch with a clean public API is reusable for any performance-critical library that wants a fast C path with a pure Python fallback.