/Note: I am deprecating this library in preference to Versioned-Objects which can do everything this can and more. I’ll keep this here for a while until I have something that really puts it to shame with Versioned-Objects. That is all./
Versioned-Arrays is a library allowing you to use arrays in a relatively cheap manner. See my blog post on it for more in depth treatment of the ideas behind it.
Basically it allows you to modify parts of a “versioned array,” which is a small wrapper around a Lisp array, and the resultant modified array, and the original array, only requires O(N+m) storage where N is the number of elements in the array and m is the number of edits that are made in between the two versions. It works very well for problems where you are interested in a set of arrays that are only a few edits apart. In fact in this case, the asymptotic behavior is constant time, just like with normal mutable arrays.
Arrays are created with make-versioned-array, elements are accessed with
varef, and arrays are modified using modf.
The library should be thread safe, but keep in mind, a given array has a single lock that is held even for reads. Thus contention can be a problem.
This is an ASDF package.
Not many dependencies, yay:
- bordeaux-threads
- Modf
Additional dependencies for the test suite:
- Iterate
- Stefil
This is a pretty simple piece of code so I am publishing it under the 3 clause BSD license. It follows:
Copyright (c) 2011, Zach Kost-Smith All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
- Neither the name of the <organization> nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.