dequesterity Files

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 
functionality.

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
libraries.

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 brad.moore@shaw.ca

0.0 DOWNLOADING
==============
The latest stable release and older releases may be downloaded from;

https://sourceforge.net/projects/dequesterity/files/

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

  mkdir sandbox
  cd sandbox
  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
worked on.

1.0 INTRODUCTION
================

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.

buffers-{high_level_implementation}_{low_level_implementation}.ads

eg., A buffer generic involving Ravenscar concurrency support using the
low level bounded buffer implementation can be found in the following generic.

Buffers/Classes/buffers-ravenscar_bounded.ads

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
high_level_implementation name.

For example, a simple unbounded buffer can be found under the filename;

Buffers/Classes/buffers-simple_unbounded.ads

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
        circular array		

  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 
		Bounded Buffer
		
  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.

   1) Active
        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
		tasks.
		
   2) Non-Blocking
        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.
		
   3) Passive
        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
		   activity.
		   
		   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.
		
   4) Passive_lite
         A passive-lite buffer is a stripped down, less sophisticated version 
		 of a passive buffer that only supports deadlock detection.
   
   5) Ravenscar
		 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

      simple_bounded
      simple_unbounded    
      simple_persistent
      simple_segmented
      simple_scattered
      indefinite_simple_bounded
      indefinite_simple_unbounded
      indefinite_simple_scattered

  b) Second Order Buffers

     - Priority Buffers

         bounded_priority
         unbounded_priority
         persistent_priority
         segmented_priority


     - Concurrent Buffers      
      
         non_blocking_bounded
         non_blocking_persistent
         non_blocking_segmented
         non_blocking_unbounded
         passive_bounded
         passive_bounded_lite
         passive_persistent
         passive_persistent_lite
         passive_segmented
         passive_segmented_lite
         passive_unbounded
         passive_unbounded_lite
         pure_non_blocking_bounded
         ravenscar_bounded
         ravenscar_persistent
         ravenscar_segmented
         ravenscar_unbounded
         active_bounded         
         active_persistent         
         active_scattered         
         active_segmented         
         active_unbounded         
         passive_scattered         
         passive_scattered_lite         
         ravenscar_scattered         
         indefinite_non_blocking_bounded
         indefinite_non_blocking_unbounded
         indefinite_passive_bounded
         indefinite_passive_unbounded
         indefinite_ravenscar_bounded
         indefinite_ravenscar_unbounded
         indefinite_simple_bounded
         indefinite_simple_unbounded
         indefinite-passive_scattered         

     - Stream Buffers

         stream_simple_bounded
         stream_simple_persistent
         stream_simple_scattered
         stream_simple_segmented
         stream_simple_unbounded

  c) Third Order Buffers

     - Concurrent Priority Buffers

         non_blocking_bounded_priority
         non_blocking_persistent_priority
         non_blocking_segmented_priority
         non_blocking_unbounded_priority
         passive_bounded_priority
         passive_lite_bounded_priority
         passive_lite_persistent_priority
         passive_lite_segmented_priority
         passive_lite_unbounded_priority
         passive_persistent_priority
         passive_segmented_priority
         passive_unbounded_priority
         persistent_priority
         pure_bounded_priority
         pure_non_blocking_bounded_priority
         ravenscar_bounded_priority
         ravenscar_persistent_priority
         ravenscar_segmented_priority
         ravenscar_unbounded_priority
         indefinite_non_blocking_bounded_priority
         indefinite_non_blocking_unbounded_priority
         indefinite_passive_bounded_priority
         indefinite_passive_unbounded_priority
         indefinite_ravenscar_bounded_priority
         indefinite_ravenscar_unbounded_priority

     - Concurrent Stream Buffers

         stream_ravenscar_bounded.ads
         stream_ravenscar_persistent.ads
         stream_ravenscar_scattered.ads
         stream_ravenscar_segmented.ads
         stream_buffers_unbounded.ads

  c) Preinstantiated Character Buffers

         string_lite_passive_bounded_buffer.ads
         string_lite_passive_persistent_buffer.ads
         string_lite_passive_segmented_buffer.ads
         string_lite_passive_unbounded_buffer.ads
         string_non_blocking_bounded_buffer.ads
         string_non_blocking_persistent_buffer.ads
         string_non_blocking_segmented_buffer.ads
         string_non_blocking_unbounded_buffer.ads
         string_passive_bounded_buffer.ads
         string_passive_persistent_buffer.ads
         string_passive_segmented_buffer.ads
         string_passive_unbounded_buffer.ads
         string_pure_non_blocking_bounded_buffer.ads
         string_ravenscar_bounded_buffer.ads
         string_ravenscar_persistent_buffer.ads
         string_ravenscar_segmented_buffer.ads
         string_ravenscar_unbounded_buffer.ads
         string_simple_bounded_buffer.ads
         string_simple_persistent_buffer.ads
         string_simple_segmented_buffer.ads
         string_simple_unbounded_buffer.ads
         string_active_bounded_buffer.ads
         string_active_persistent_buffer.ads
         string_active_segmented_buffer.ads
         string_active_unbounded_buffer.ads

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 new
   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 '"'.

  i.e.
      -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 tested on the following platforms;
- Windows, Linux, using the GNAT 2011-2016 GPL release.
- Linux and Raspian using the GNAT FSF 4.9.2-4.9.3 release.
- Irvine ICC Ada 2005 compiler on Windows,

The dequesterity libraries were designed with portability in mind and have
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
buffer generics.

7.0 LIMITATIONS
===============

  NOTE: There is currently a compiler bug in GNAT (GPL 2012-2016) that
  does not allow the definite priority_buffers (and the test_priority_buffers
  project) to compile. This does compile using the Irvine ICC compiler, 
  however. 
  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.
  

Brad Moore