Gem #37: Bounded Buffer package in GNAT Hierarchy (Part 2)

by Pat Rogers —AdaCore

Let's get started…

To recap Part 1, protected types add an efficient building block to the tasking facilities of Ada. Mutual exclusion is automatically provided and condition synchronization is directly expressed via entry barriers, all without the expense of task switching. As such, protected types are a natural implementation approach for a circular bounded buffer used in a concurrent programming context. The complete declaration of the generic package and encapsulated protected type are shown below, including now the private part. (We have omitted the comments in the code since we cover them in the description.)

with System;

generic
   type Element is private;
package GNAT.Bounded_Buffers is
   pragma Pure;

   type Content is array (Positive range <>) of Element;

   Default_Ceiling : constant System.Priority := System.Default_Priority;

   protected type Bounded_Buffer
      (Capacity : Positive;
       Ceiling : System.Priority)
   is
      pragma Priority (Ceiling);

      entry Insert (Item : Element);
      entry Remove (Item : out Element);

      function Empty  return Boolean;
      function Full   return Boolean;
      function Extent return Natural;

   private
      Values   : Content (1 .. Capacity);
      Next_In  : Positive := 1;
      Next_Out : Positive := 1;
      Count    : Natural  := 0;
   end Bounded_Buffer;

end GNAT.Bounded_Buffers;

The private part of type Bounded_Buffer contains the encapsulated data that can only be accessed via the exported routines. The abstraction is that of a bounded buffer, and it uses the component Values, of the array type Content, to hold the buffer values. The discriminant Capacity determines the actual upper bound on the array component, which is how different Bounded_Buffer objects can have different capacities. As a circular buffer, two array indexes are required, one to indicate where the next inserted value will be placed, and one to indicate where the next removed value will come from. These indexes are components Next_In and Next_Out, respectively. Finally, each Bounded_Buffer object contains a count of the number of elements currently held by the buffer. This counter is used to provide the condition synchronization required to prevent inserting items into a full buffer or removing items from an empty buffer. There are other ways to determine whether the buffer is full or empty but this counter-based approach is clear and is also useful for the function Extent.

The generic package body contains only the body of the protected type, and likewise, the protected body only contains the bodies of the exported entries and functions, so we omit the lines for the declarations of the package and protected type bodies and focus instead on the routines themselves.

The first routine in the protected body is that of the entry Insert. Note the barrier “Count /= Capacity” providing the condition synchronization for the state “not full”. Callers to Insert are kept waiting until the barrier is True. As is the case for any protected entry or protected procedure, callers automatically execute with mutually exclusive access to the encapsulated data.

      entry Insert (Item : Element) when Count /= Capacity is
      begin
         Values (Next_In) := Item;
         Next_In := (Next_In mod Capacity) + 1;
         Count := Count + 1;
      end Insert;

The body of Insert is straightforward. Note that we have the index Next_In wrap around the allowed index values based on the capacity. We could not use a modular type for either index because that would require a static value for the modulus, but we only have the Capacity discriminant to work with.

The body for entry Remove is similar to that of Insert, with expected differences.

      entry Remove (Item : out Element) when Count > 0 is
      begin
         Item := Values (Next_Out);
         Next_Out := (Next_Out mod Capacity) + 1;
         Count := Count - 1;
      end Remove;

An important point for each entry is the handling of the Count component. When either entry completes, the other entry is examined to see if the barrier has become true. If so, a waiting caller (if any) is allowed to execute and the process repeats itself. Thus, a very simple expression of the condition is provided by the barriers and these are automatically evaluated whenever they could possibly change.

The function bodies are even simpler than the entry bodies. It is worth repeating a point made in Part 1 of this gem, namely that the state of a protected object can change immediately after a call to such a function returns.

      function Empty return Boolean is
      begin
         return Count = 0;
      end Empty;

      function Full return Boolean is
      begin
         return Count = Capacity;
      end Full;

      function Extent return Natural is
      begin
         return Count;
      end Extent;

Clients can query the capacity of any given Bounded_Buffer object by simply reading the Capacity discriminant. The discriminant cannot be changed, so the effect is much the same as a function.

As Niklaus Wirth once wrote (citing Hoare), once you get the data structures right, the code just writes itself. Admittedly, he didn’t use those exact words, but I think you will agree that the data structures used in type Bounded_Buffer, when combined with the semantics of protected types, make the bodies of the routines trivial to write.

About the Author