IBM
Contents Index Previous Next



Abstract Data Types for List Processing


The abstract data types defined in this "package" are intended for processing of linked lists. Linked lists are commonly appearing in applications and are one of the basic data structures in computer science. With these data types, you can concentrate on using the lists and do not have to worry about the implementation details, as all list manipulations are hidden in operators in the data types.

Note:

This data type is not implemented in a way that makes it possible to be used in the SDL Explorer. It can be used in OS integrations, but it is not recommended, due to the risk for memory leaks.

Purpose

Definitions

A queue is a list in which the members are ordered. The ordering is entirely performed by the user. The available operations make it possible to access members of the queue and insert members into or remove members from any position. Furthermore, the operators suppress the implementation aspects. That is, the fact that the queue is implemented as a doubly linked list with a queue head. The operators also prevent the unwary user from trying to access, for instance, the successor of the last member or the predecessor of the first member.

The entities which may be members of a queue are called object instances. An object instance is a passive entity containing user defined information. This information is described in the object description.

In SDL these definitions are implemented using sorts called Queue, ObjectInstance, and ObjectDescr, where ObjectDescr should be defined by the user. ObjectDescr should have the structure given in the example below (Example 545).

The data types for list processing may be included in any SDL system using Analyzer #include statements, where the files containing the definitions of the data types are included. The definitions should be placed in the order given in the example below:

Example 545 : Including ADT for List Processing

/*#include 'list1.pr'*/
NEWTYPE ObjectDescr /*#NAME 'ObjectDescr'*/
  STRUCT
    SysVar SysTypeObject;
    /* other user defined components */
ENDNEWTYPE;
/*#include 'list2.pr'*/

The file list1.pr contains the definition of the sort Queue (and the help sorts ObjectType and SysTypeObject), while the file list2.pr contains the definition of the type ObjectInstance.

Available Sorts

When the data types for list processing are included, two new sorts, Queue and ObjectInstance, are mainly defined, together with the type ObjectDescr defined by the user. The user can declare variables of type Queue and type ObjectInstance, but should never declare a variable of type ObjectDescr.

Variables of the sorts Queue and ObjectInstance are references (pointers) to the representation of the queue or the object instance. In both sorts there is a null value, the literal NULL, which indicates that a variable refers to no queue or no object instance. The default value for Queue and ObjectInstance variables is NULL.

A variable of sort ObjectInstance can refer to a data area containing the components defined in the struct ObjectDescr. The example below shows how to manipulate these components.

Example 546 : ADT for List Processing, Struct ObjectDescr

/*#include 'list1.pr'*/
NEWTYPE ObjectDescr /*#NAME 'ObjectDescr'*/
  STRUCT
    SysVar SysTypeObject;
    Component1  Integer;
    Component2  Boolean;
ENDNEWTYPE;
/*#include 'list2.pr'*/

DCL O1 ObjectInstance;

TASK
  O1 := NewObject;  /* see next section */

TASK
  O1!ref!Component1 := 23,
  O1!ref!Component2 := false;

TASK
  IntVar := O1!ref!Component1,
  BoolVar := O1!ref!Component2;

A component is thus referenced by the syntax:

ObjectInstanceVariable ! ref ! ComponentName

Caution!

You should never directly manipulate the component SysVar in the struct ObjectDescr. It contains information about if and how the object instance is inserted into a queue and should only be used by the queue handling operators.

Assignments and test for equality may be performed for queues and for object instances. The assignments:

Q1 := Q2;  O1 := O2;

mean that Q1 now refers to the same queue as Q2 and that O1 now refers to the same object instance as O2. Assignment is thus implemented as copying of the reference to the queue (and not as copying of the contents of the queue). The same is true for object instances.

The test for equality is in the same way implemented as a test if the left and right hand expression reference the same queue or the same object instance (and not if two queue or object instances have the same contents).

Due to the order in which the sorts are defined, a component of sort Queue can be a part of the ObjectDescr struct, while components of type ObjectInstance cannot be part of ObjectDescr.

If you want several different types of objects in a queue, with different contents, the #UNION directive (see Union) may be used according to the following example:

Example 547 : Unions and Queues

NEWTYPE Ob1 STRUCT
  Comp1Ob1 integer;
  Comp2Ob1 boolean;
ENDNEWTYPE;

NEWTYPE Ob2 STRUCT
  Comp1Ob2 character;
  Comp2Ob2 charstring;
ENDNEWTYPE;

NEWTYPE Ob /*#UNION*/ STRUCT
  Tag integer;
  C1  Ob1;
  C2  Ob2;
ENDNEWTYPE;

NEWTYPE ObjectDescr /*#NAME 'ObjectDescr'*/
  STRUCT
    SysVar SysTypeObject;
    U      Ob;
/*#ADT (X)*/
ENDNEWTYPE;

The components may now be reached using:

O1 ! ref ! U ! Tag
O1 ! ref ! U ! C1 ! Comp1Ob1
O1 ! ref ! U ! C2 ! Comp2Ob1

Available Operators

Operators in the Sort Queue

In the sort Queue, the following literals and operators are available:

null
NewQueue

Cardinal     : Queue -> Integer;
DisposeQueue : Queue -> Queue;
Empty        : Queue -> Boolean;
FirstInQueue : Queue -> ObjectInstance;
Follow       :
     Queue, ObjectInstance, ObjectInstance -> Queue;
IntoAsFirst  : Queue, ObjectInstance -> Queue;
IntoAsLast   : Queue, ObjectInstance -> Queue;
LastInQueue  : Queue -> ObjectInstance;
Member       : Queue, ObjectInstance ->  Boolean;
Precede      :
     Queue, ObjectInstance, ObjectInstance -> Queue;
Predecessor  : ObjectInstance -> ObjectInstance;
Remove       : ObjectInstance -> ObjectInstance;
Successor    : ObjectInstance -> ObjectInstance;

Operators in the Sort ObjectInstance

In the sort ObjectInstance, the following literals and operators are available:

null
NewObject

DisposeObject: ObjectInstance -> ObjectInstance;

The operators defined in the sorts Queue and ObjectInstance have the behavior described below. All operators will check the consistency of the parameters. Each queue and object instance parameter should, for example, be /= null. If an error is detected the operator will cause an SDL dynamic error that will be treated as any other dynamic error found in an SDL system.

NewQueue: -> Queue

The literal NewQueue is used as an operator with no parameters and returns a reference to a new empty queue. The data area used to represent the queue is taken from an avail stack maintained by the list processing sorts. Only if the avail stack is empty new dynamic memory is allocated.

Cardinal: Queue -> Integer

This operator takes a reference to a queue as parameter and returns the number of components in the queue.

DisposeQueue: Queue -> Queue

This operator take a reference to a queue as parameter and returns all object instances and the data area used to represent the queue to the avail stack mentioned in the presentation of NewQueue. DisposeQueue always returns the value null.

Note:

Any references to an object instance or to a queue that is returned to the avail stack is now invalid and any use of such a reference is erroneous and has an unpredictable result.

Empty: Queue -> Boolean

This operator takes a reference to a queue as parameter and returns false if the queue contains any object instances. Otherwise the operator returns true.

FirstInQueue: Queue -> ObjectInstance

This operator takes a reference to a queue as parameter and returns a reference to the first object instance in the queue. If the queue is empty, null is returned.

Follow: Queue, ObjectInstance, ObjectInstance -> Queue

Follow takes a reference to a queue and to two object instances and inserts the first object instance directly after the second object instance. It is assumed and checked that the second object instance is a member of the queue given as parameter, and that the first object instance is not a member of any queue prior to the call.

Note:

The operator Member is used to check that the second object instance is member of the queue.

IntoAsFirst: Queue, ObjectInstance -> Queue

This operator takes a reference to a queue and to an object instance and inserts the object instance as the first object in the queue. The queue given as parameter is returned as result from the operator. It is assumed and checked that the object instance is not a member of any queue prior to the call.

IntoAsLast: Queue, ObjectInstance -> Queue

This operator takes a reference to a queue and to an object instance and inserts the object instance as last object in the queue. The queue given as parameter is returned as result from the operator. It is assumed and checked that the object instance is not a member of any queue prior to the call.

LastInQueue: Queue -> ObjectInstance

This operator takes a reference to a queue as parameter and returns a reference to the last object instance in the queue. If the queue is empty, null is returned.

Member: Queue, ObjectInstance -> Boolean

This operator takes a reference to a queue and to an object instance and returns true if the object instance is member of the queue, otherwise it returns false.

Precede: Queue, ObjectInstance, ObjectInstance-> Queue

Precede takes a reference to a queue and to two object instances and inserts the first object instance directly before the second object instance. It is assumed and checked that the second object instance is a member of the queue given as parameter, and that the first object instance is not a member of any queue prior to the call.

Note:

The operator Member is used to check that the second object instance is member of the queue.

Predecessor: ObjectInstance -> ObjectInstance

This operator takes a reference to an object instance and returns a reference to the object instance immediately before the current object instance. If the object instance given as parameter is the first object in the queue, null is returned. It is assumed and checked that the object instance given as parameter is a member of a queue.

Remove: ObjectInstance -> ObjectInstance

Remove takes a reference to an object instance and removes it from the queue it is currently a member of. A reference to the object instance is returned as result from the operator. It is assumed and checked that the object instance given as parameter is a member of a queue.

Successor: ObjectInstance -> ObjectInstance

This operator takes a reference to an object instance and returns a reference to the object instance immediately after the current object instance. If the object instance given as parameter is the last object in the queue, null is returned. It is assumed and checked that the object instance given as parameter is a member of a queue.

NewObject: -> ObjectInstance

The literal NewObject is used as an operator with no parameters and returns a reference to a new object instance, which is not member of any queue. The data area used to represent the object instance is taken from an avail stack maintained by the list processing sorts. Only if the avail stack is empty new dynamic memory is allocated.

DisposeObject: ObjectInstance -> ObjectInstance

This operator take a reference to an object instance as parameter and returns it to the avail stack mentioned above. DisposeObject always returns the value null.

Note:

Any references to an object instance that is returned to the available stack are now invalid and any use of such a reference is erroneous and has an unpredictable result.

Examples of Use

In this section a number of examples will be given to give some indications of how to use the list processing "package". The following sort definitions are assumed to be included in the system diagram:

/*#include 'list1.pr' */

NEWTYPE ObjectDescr /*#NAME 'ObjectDescr'*/
  STRUCT
    SysVar SysTypeObject;
    Number Integer;
    Name   Charstring;
ENDNEWTYPE;

/*#include 'list2.pr' */

Example 548 : Creating a Queue

To create a new queue and insert two objects in the queue, so that the first object has Number = 23 and Name = 'xyz' and the second object has Number = 139 and Name = 'Telelogic', you could use the following code (assuming appropriate variable declarations):

TASK
  Q := NewQueue,
  O1 := NewObject,
  O1!ref!Number := 23,
  O1!ref!Name := 'xyz',
  Q := IntoAsFirst(Q, O1),
  O1 := NewObject,
  O1!ref!Number := 139,
  O1!ref!Name := 'Telelogic',
  Q := IntoAsLast(Q, O1);

Example 549 : Removing from Queue

To remove the last object instance from a queue, assuming the queue is not empty, you could use the following code:

TASK
  O1 := Remove(LastInQueue(Q));

Example 550 : Looking in Queue

You may look at the component Name in the first object instance in the queue in the following way:

TASK
  O1 := FirstInQueue(Q),
  StringVar := O1!ref!Name;

or if the reference to O1 is not going to be used any further

TASK
  StringVar := FirstInQueue(Q)!ref!Name;

Example 551 : Searching in Queue

The result of the following algorithm is that O1 will be a reference to the first object instance that has the value IntVar in the component Number. If no such object is found O1 is assigned the value null.

TASK O1 := FirstInQueue(Q);
NextObject:
DECISION O1 /= null;
  (true) :
    DECISION O1!ref!Number /= IntVar;
      (true):
        TASK O1 := Successor(O1);
        JOIN NextObject;
      (false):
    ENDDECISION;
  (false):
ENDDECISION;

Example 552 : Removing Duplicates from Queue

The algorithm below removes all duplicates from a queue (and returns them to the avail stack). A duplicate is here defined as an object instance with the same Number as a previous object in the queue.

TASK O1 := FirstInQueue(Q);
NextObject:
DECISION O1 /= null;
  (true) :
    TASK O2 := Successor(O1);
    NextTry:
    DECISION O2 /= null;
      (true):
        DECISION O1!ref!Number = O2!ref!Number;
          (true):
            TASK Temp := O2,
                 O2 := Successor(O2),
                 Temp := DisposeObject (
                         Remove(Temp));
          (false):
            TASK O2 := Successor(O2);
        ENDDECISION;
        JOIN NextTry;
      (false):
        TASK O1 := Successor(O1);
        JOIN NextObject;
    ENDDECISION;
  (false) :
ENDDECISION;

Connection to the Monitor

Trace printouts are available for the operators in this abstract data type. By assigning a trace value greater or equal to eight (8) using the monitor command Set-Trace, each call to an operator in this data type causes a printout of the name of the current operator. Note that some of the operators may call some other operator to perform its task.

You may use the monitor command Examine-Variable to examine the values stored in a variable of type ObjectInstance. By typing an additional index number after the variable Queue the value of the ObjectInstance at that position of the queue is printed.

Accessing List Operators from C

The sorts Queue, ObjectInstance, and ObjectDescr, and all the operators and the literals NewQueue and NewObject have the same name in C as in SDL, as #NAME directives are used. The literal null is the sort Queue and is translated to QueueNull(), while the literal null in sort ObjectInstance is translated to ObjectInstanceNull().

In C you access a component in an ObjectInstance using the -> operator:

OI_Var -> Component

As an example of an algorithm in C, consider the algorithm in Example 551. A reference to the first object instance that has the value IntVar in the component Number is computed:

#(O1) = FirstInQueue(#(Q));
while ( #(O1) != ObjectInstanceNull () ) {
  if ( #(O1)->Number == #(IntVar) ) break;
  #(O1) = Successor(#(O1));
}

http://www.ibm.com/rational
Contents Index Previous Next