Dequesterity is a set of Ada 2005 generics that provide various forms of
general purpose buffer containers. Buffers may be used as deques, queues,
ring buffers, stacks, double ended stacks, vectors, priority queues,
and similar abstractions.
The generics are combinable and pluggable such that lower level buffer
implementations may be combined with higher level buffer generics to
create a wide selection of buffer types with specific sets of
Lower level buffer implementations include bounded and unbounded buffer
forms. Higher level buffer implementations add can concurrency support,
priority queuing, and streaming of heterogeneous objects.
Buffer instances may be streamed, or may be accessed remotely using the
Distributed Systems Annex.
Most buffers can store their state persistently. Some buffer
implementations operate entirely on secondary (file based) storage.
The buffers may be instantiated with user defined types, and indefinite
buffer forms also exist.
The interface to the buffers is modelled after the Ada 2005 container
Dequesterity is free software. See the file COPYING for copying permission.
Most of the source code is released under the GMGPL (GNAT Modified GPL)
See the individual source files for details.
Any comments on the generics would be greatly appreciated.
Please send comments to email@example.com
The latest stable release and older releases may be downloaded from;
For those who want the current development versions of the source they
can download using git (http://git-scm.com/) by issuing the following commands
git clone git://git.code.sf.net/p/dequesterity/code dequesterity-src
The current development version typically will correspond to the latest
stable release, but may at times be unstable when new features are being
What is a buffer?
A Buffer is a general purpose container that is implemented as a circular
array of elements, where the element type can be specified by the client.
Many forms of buffer generics are provided, allowing one to select an
implementation with a very specific set of features.
Each buffer exists as a separate generic library unit. The buffer
implementations are designed to be swappable and combinable, so that various
feature sets may be provided simply by combining lower level implementations
that have desired features.
What buffers exist?
There currently exist 70 generic buffers types, 10 stream buffer types,
and 25 preinstantiated string buffer types.
The generic buffers may be instantiated with user defined types.
The priority buffers maintain a list of objects that are sorted by a
user defined sorting criteria.
The stream buffers allow storing heterogeneous objects into a buffer. Any
streamable object may be stored and retrieved into a stream buffer.
The string buffers are instantiations of the generic buffers for the
Ada Character and String types. It is thought that character based buffers
would be somewhat common, and the string buffers also provide a good example
on how to instantiate and use the generic buffers.
All buffers intended for client usage may be found under the "Classes"
subfolder under the "Buffers" folder.
The buffers folder provides the parent package for all the instantiations,
depending on whether indefinite buffers are needed or not.
All buffers involving constrained element types are child packages of
Buffers.ads. All buffers involving unconstrained element types,
(i.e. indefinite buffers) are child packages of Indefinite_Buffers.ads.
The buffer generic filenames are named using the following convention.
eg., A buffer generic involving Ravenscar concurrency support using the
low level bounded buffer implementation can be found in the following generic.
Some of the buffer generics only utilize low level implementations without
specifying a high level implementation. These buffer types are called
simple buffers, and thus the name "simple" is specifed in the position for the
For example, a simple unbounded buffer can be found under the filename;
2.0 Buffer Classification
The low-level (simple) implementations include the following types;
1) Bounded Buffer
A buffer that is statically bounded in size, implemented as a
2) Unbounded Buffer
An unbounded buffer is a buffer that has a maximum capacity, but
whose storage is internally allocated from the heap. An unbounded buffer
can grow in size, or shrink as necessary to accomodate the data being
stored. An unbounded buffer is internally implemented as an access to
3) Segmented Buffer
A segmented buffer expands on the idea of an unbounded buffer. An
unbounded buffer is a single allocation of a buffer, whereas a segmented
buffer consists of numerous segments, where each segment is itself an
unbounded buffer. Such a buffer can be useful for example for processing
large images in memory. It may not be possible to allocate a single
unbounded buffer to hold a large array of data, but it may be possible
to perform many smaller allocations to store the same data in memory.
Like an unbounded buffer, the storage of a segmented buffer can grow
or shrink to accomodate the current amount of data stored in the buffer.
4) Persistent Buffer
A persistent buffer is a buffer that is not stored in memory. Rather,
it is stored entirely on disk, and manipulated on secondary storage.
5) Scattered Buffer
This is more of an experimental buffer type that allows an assortment
of other buffers of other types to be treated as a single buffer.
This is more of a special purpose buffer, that may not be of interest
to general client usage.
An intermediate level of buffer abstractions include the priority buffers.
A priority buffer maintains a sorted order for the objects in the buffer.
Low level buffers may be combined with priority buffers to produce the
desired behaviour. Priority buffers may also be used to instantiate the
higher level concurrent buffer forms.
The higher level concurrency generics provide the following abstractions.
This concurrency generic implements a buffer as a task. This
generic is more of an academic example that demonstrates how task
interfaces can be utilized to provide concurrency. It is not
generally recommended that clients consider this generic for use,
since other generics provide similar functionality, without requiring
This generic provides concurrency, but has no blocking calls.
A call to read from a buffer that has no data will return reporting
that no data has been read. Similarly, an attempt to write data into
a full buffer will immediately return indicating that the call failed.
This concurrency type may be useful for creating Shared_Passive
partitions. A Non-Blocking buffer is Ravenscar compliant, since there
are no entries associated with the buffer.
A passive buffer provides concurrency with blocking calls on reads
on an empty buffer, and writes to a full buffer. A passive buffer
allows for multiple producers and consumers, and provides two
different modes of operation.
a) mode 1: Deadlock Detection Capable
b) mode 2: Allow Oversized requests
If the buffer object is declared with deadlock detection capability,
it means any conditional entry calls or timed entry calls can be
cancelled without modifying the state of the buffer.
Deadlock can be detected through the use of timed entry calls.
Deadlock will not occur through calls to the buffer, but if for some
reason the buffer if full, and consumer task are not dequeing
data from the buffer, then producer tasks can break out of a blocking
write, and resume activity. Similarly, if producer tasks are not
enqueueing data into the buffer, consumer threads blocked on read
requests for an empty buffer can break out of the request and resume
The oversized write mode does not support timed entry calls, but
in exchange, supports reading and writing vectors of elements of any
size into the buffer. The size of the vector may in fact be larger
than the capacity of the buffer. Producers and consumers and handled
transparently using logic in a protected type, without requiring any
additional tasks to coordinate the oversized reads and writes.
A passive-lite buffer is a stripped down, less sophisticated version
of a passive buffer that only supports deadlock detection.
A Ravenscar buffer is a buffer that supports a single reader and a
single writer, with blocking calls for writes when the buffer is full,
and blocking calls for read requests when the buffer is empty.
3.0 BUFFER LIST
a) Simple (Low Level) Buffers
b) Second Order Buffers
- Priority Buffers
- Concurrent Buffers
- Stream Buffers
c) Third Order Buffers
- Concurrent Priority Buffers
- Concurrent Stream Buffers
c) Preinstantiated Character Buffers
4.0 BUILD INSTRUCTIONS
- For the Irvine ICC Ada 2005 compiler on Windows, execute the
following script to create the Ada 2005 versions of the executables;
icm scan -subdir "*.ad?"
icm make buffer_demo
icm make ravenscar_test
icm make test_priority_buffers
icm make test_indefinite_priority_buffers
You can add other compile flags as well, such as
-compile_flags=\"-predef=(f32,lf64) -opt -debug -nochecks\"
to turn on optimization, debug, and disable checks.
To compile for Irvine ICC on Linux, the script is the same, except
that if compile options are used then the options should be enclosed
with single quotes, and \" should be replaced with '"'.
-compile_flags='"-predef=(f32,lf64) -opt -debug -nochecks"'
- For GNAT Pro, GNAT GPL or GNAT AUX, load the appropriate .gpr file
and build the executable from within the ide, or alternatively use gnatmake to
perform the equivalent actions described in the .gpr file.
5.0 SUPPORTED TARGETS AND COMPILERS
The generics have been compiled and run on Windows and Linux, using the
GNAT 2011 GPL release, and the Irvine ICC Ada 2005 compiler on Windows though in
theory any Ada 2005 compiler should be able to compile the code since
there are no dependencies on the GNAT run-time.
6.0 TEST EXECUTABLES
Buffer_Demo instantiates a selection of the buffer generics and illustrates
some possible usages.
Test_Buffers is a more comprehensive test, but can take quite some time to
compile due to all the various combinations of generic instantiations.
Ravenscar_Test is a simple test program that illustrates a producer/consumer
application using one the ravenscar buffer generics.
test_priority_buffers allows a simple insertion test into a priority buffer
for a variety of the priority buffer generics.
test_indefinite_priority_buffers similarly allows insertions of an indefinite
string type into a sorted priority buffer, for a variety of the indefinite
NOTE: There is currently a compiler bug in GNAT (GPL 2012) that does
not allow the definite priority_buffers (and the test_priority_buffers
project) to compile. This does compile using the Irvine ICC compiler,
On the other hand, the test_indefinite_priority_buffers project does
compile under GNAT. So until the GNAT bug is fixed, which hopefully
will be in the Ada2013 GPL version of GNAT, the indefinite priority
buffers should be used instead of the definite priority buffer
generics, or alternatively, use the ICCAda compiler. Note also that
any definite type can be used to instantiate an indefinite priority
buffer, though the definite versions would ordinarly be preferable,
since they do not involve the use of access types.