Basic functions and macros, interfaces, pure and stateful datastructures
A library providing functions that unify data-structure access for Common Lisp:
access and (setf access)
Simple array operations library for Common Lisp.
A compact binomial heap implementation.
This page is moved to https://github.com/vy/bk-tree.Keywords: data structure
Extensible cache services for Common Lisp
A wrapper around native hash-tables to facilitate
in-process caching of common lisp data structures.
cl-custom-hash-table extends the hash table data structure by allowing the use of arbitrary TEST/HASH functions, in addition to the TEST functions allowed by the standard (EQ, EQL, EQUAL and EQUALP).It is different from genhash in that genhash is a complete hash table implementation with its own api. CL-CUSTOM-HASH-TABLE is primarily a compatibility layer that uses the standard hash table API, and has a simple fall-back solution built on top of standard hash tables.Homepage: https://github.com/metawilm/cl-custom-hash-tableLicense: BSD-style
An implementation of heap and priority queue data structures.
Substring search and string matching, exact and inexact and other algorithms on strings and sequences.
This is a mirror of the repository on SourceForge.
Generic interfaces for collections and iterators.
A library providing a data-table class, and useful functionality around this
An implementation of the doubly-linked list in Common Lisp.
Flexichain is an API for editable sequences. Its primary use is in end-user applications that edit sequences of objects such as text editors (characters), word processors (characters, paragraphs, sections, etc), score editors (notes, clusters, measures, etc), though it can also be used as a stack and a double-ended queue. Project page
Topics: data structure
A functional set-theoretic collections library.
Generic hashtable code
hh-redblack provides in-memory and disk-based red-black trees.Homepage: http://haphazardhouse.net/projects/hh-redblackSource: https://github.com/hargettp/hh-redblackLicense: MIT
Topics: data structure StructuredStorage
A few different kinds of queues, with optional
Long name alias for lil
Various heap/priority queue data structures
pipes implements the input stream (lazy list) data structure. It is based on ideas from Peter Norvig's Paradigms of Artificial Intelligence Programming.``Pipes'' is an implementation of a concept that goes by many names: streams or functional streams SICP, generated lists or glists, and lazy lists.
spatial-trees is a set of dynamic index data structures for spatially-extended data. The flavors provided are, as of the 0.1 release (on 2004-12-03):
R-trees, as in R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING, Antonin Guttman, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1984.
Greene-trees, as in An Implementation and Performance Analysis of Spatial Data Access Methods, Diane Greene, Proc. 5th IEEE Int. Conf. on Data Engineering, 1989.
R*-trees, as in The R*-tree: An Efficient and Robust Access Method for Points and Rectangles, Beckmann, Kriegel, Schneider and Seeger, Proc. ACM Int. Conf. on Management of Data, 1990
X-trees, as in The X-tree: An Index Structure for High-Dimensional Data, Berchtold, Keim and Kriegel, Proc. 22th Int. Conf. on Very Large Databases, 1996
Future work planned includes performance enhancements, incorporation of more index structures, and some work on supporting more optimal indexing when the entire set of data is known at index creation time; for more details, see the TODO file in the binary distribution.The code is licensed BSD-style, and is intended to be similar in spirit to Nathan Froyd's TREES Library.
You can get this via Quicklisp.As per #lisp discussion, the new official source for this is the github repository, which is a conversion of the darcs repository.
Defines a new kind of package that's named by a symbol rather than a string and that maps from existing symbols to their respective "implicitly managed" counterparts. The motivating use-case is to conceptually allow multiple definitions of the same kind on a single symbol, without conflicts.
A library for binary trees in normal and balanced flavors
functional data collections
An alternative to DOM inspired by XOM
lichteblau.com/cxml-stpDownload (tarball): Yes, see belowDownload (git clone): http://www.lichteblau.com/git/cxml-stp.git
(gitweb)This project is asdf-installable (release tarball) and available in clbuild (git version).
An alternative to DOM.
Feature overviewcxml-stp is an add-on package for cxml.
Implements STP, an alternative to W3C DOM.
STP is a data structure for well-formed XML documents
Inspired heavily by Java's XOM, but
designed for Common Lisp.
A randomized property-based testing tool for Common Lisp.
marshal: Simple (de)serialization of Lisp datastructures.
Set-like data structure.
STMX is an actively maintained, high-performance concurrency library providing Transactional Memory for Common Lisp.Home page and downloads: http://github.com/cosmos72/stmx Main features
Extremely intuitive to use and to write correct, thread-safe concurrent code
Brings database-style transactions to Common Lisp by introducing transactional memory
High performance implementation, benchmarked to exceed 7 millions transactions per CPU core per second on commodity PC hardware
Support for hardware memory transactions (requires 64-bit SBCL and CPUs with Intel TSX instructions - currently Core i5 4570, Core i7 4670, Core i7 4770 and some others). They increase STMX performance up to almost 40 millions transactions per CPU core per second
Removes the need for traditional locks, mutexes and conditions - writing correct concurrent code with them is well known to be hard
Transactional code is intrinsically deadlock-free: if two transactions conflict one of them will be re-executed
Automatic commit and rollback: if a transaction completes normally it will be committed, if it signals an error it will be rolled back
Transactions are composable: they can be executed in a larger transaction, either in sequence (all-or-nothing) or as alternatives (try them until one succeeds)
Offers freedom of choice between blocking and non-blocking transactional functions: given either behaviour, it is trivial to transform it into the other.
Features transactional versions of popular data structures: hash tables, red-black trees, stack, fifo
Includes transactional data structure for multicast publish/subscribe
Creating new transactional data structures is easy
Extensive test suite
Tested on SBCL, ABCL, CCL, CMUCL and ECL.
Very simple to install with Quicklisp
A quick-start guide and installation instructions are provided in README.md fileLicense: LLGPL What STMX is NOT
In order not to confuse programmers - less experienced ones in particular - and to avoid rising unrealistic hopes, the author himself stated the following about STMX:
it is NOT a quick hack to automagically transform existing, slow, single-threaded programs into fast, concurrent ones. No matter how much transactions can help, writing concurrent code still requires careful design and implementation - and testing. And refactoring takes time too.
it is NOT for optimization-focused programmers trying to squeeze the last cycle from their Common Lisp programs. STMX records an in-memory transaction log containing all reads and writes from/to transactional memory, then later (during commit) validates the transaction log against the latest data present in transactional memory and finally copies the transaction log onto the transactional memory while holding locks. STMX is quite optimized, but this machinery comes at an obvious performance cost with respect to hand-made, highly optimized locking code (but a good reality check is to ask yourself how many people have the skill and patience to write such code without bugs).
it is NOT supposed to be used for all data structures in a Common Lisp program. STMX is intended only for the data accessed concurrently by multiple threads while being modified by at least one thread. And even in that case, transactional memory is not always needed: it depends on the kinds of modifications.
it is NOT a serialization or persistence framework. Rather, messing with metaclasses and playing (allowed) tricks with slots contents as STMX does, quite likely does not mix well with serialization or persistence libraries such as CL-STORE, because they typically need full control on the slots of the objects to be serialized and de-serialized.
it is NOT a million dollar library from some deep-pocket company. At the moment, it is the work of a single person.
xml-emitter simply emits XML, with some
complexity for handling indentation. It can be used to produce all
sorts of useful XML output; it has an RSS 2.0 emitter built in.