Eli   Documents Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads

General Information

 o Eli: Translator Construction Made Easy
 o Global Index
 o Frequently Asked Questions
 o Typical Eli Usage Errors

Tutorials

 o Quick Reference Card
 o Guide For new Eli Users
 o Release Notes of Eli
 o Tutorial on Name Analysis
 o Tutorial on Type Analysis
 o Typical Eli Usage Errors

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual
 o Typical Eli Usage Errors

Libraries

 o Eli library routines
 o Specification Module Library

Translation Tasks

 o Lexical analysis specification
 o Syntactic Analysis Manual
 o Computation in Trees

Tools

 o LIGA Control Language
 o Debugging Information for LIDO
 o Graphical ORder TOol

 o FunnelWeb User's Manual

 o Pattern-based Text Generator
 o Property Definition Language
 o Operator Identification Language
 o Tree Grammar Specification Language
 o Command Line Processing
 o COLA Options Reference Manual

 o Generating Unparsing Code

 o Monitoring a Processor's Execution

Administration

 o System Administration Guide

Mail Home

Abstract data types to be used in specifications

Previous Chapter Next Chapter Table of Contents


Linear Lists of Any Type

This module implements linear lists whose elements are of an arbitrary type that is specified by a generic instantiation parameter. Any assignable type can be chosen.

Storage for lists is allocated when needed. The module implementation uses efficient dynamic storage allocation of the obstack module. The module does not implement automatic garbage collection. Storage used by one instance of this module can be deallocated completely.

One subset of the functions provided by this module is strictly functional, i.e. list values are not modified. Another subset of functions modifies existing list values, e.g. inserts elements into a list. It is explicitly mentioned which functions may cause such side-effects on their arguments.

The module is instantiated by

   $/Adt/List.gnrc +instance=TYPE +referto=HDR :inst
where TYPE is the name of the element type and HDR.h is a file that defines the element type, e.g.
   $/Adt/List.gnrc+instance=DefTableKey +referto=deftbl :inst
If the element type is predefined in C the referto parameter is omitted, e.g.
   $/Adt/List.gnrc+instance=int :inst

All entities exported by this module can be used in specifications of type .lido, .init, .finl, and .con. They can also be used in .pdl specifications or in C modules if the interface file TYPEList.h is imported there.

A module PtrList is available. It produces list implementations with the same interface as the List module does. PtrList is only applicable if the element type TYPE is a pointer type. An instantiation of PtrList implements the lists by lists of VoidPtr (void*) using an instantiation of the List module. Hence, several instances of PtrList use one single implementation. The created interface files TYPEList.h provide macros for casting the element type to and from VoidPtr. The module PtrList is instantiated in the same way as the List module is:

   $/Adt/PtrList.gnrc +instance=TYPE +referto=HDR :inst

The modules export the following type names and macros:

TYPEList
A pointer type representing lists.

TYPEListPtr
A pointer type pointing to TYPEList objects.

TYPEMapFct
A function type for mapping: TYPE -> TYPE.

TYPECmpFctType
A function type for comparison: TYPE, TYPE -> int Function of this type have to yield 0 if the two values are equal, 1 if the left argument is greater than the right, -1 if the left argument is less than the right.

TYPESumFct
A function type for combining elements: TYPE, TYPE -> TYPE

NULLTYPEList
Denotes the empty list.

NullTYPEList ()
Denotes the empty list.

SingleTYPEList(e)
Creates a list containing only the element e.

The following list processing functions are supplied by the module:

void FinlTYPEList (void)
Deallocates all TYPELists (for all possible values of TYPE).

TYPEList ConsTYPEList (TYPE e, TYPEList l)
Constructs a TYPEList of an element e and a given tail l. e is the first element of the list.

TYPE HeadTYPEList (TYPEList l)
Returns the first element of the list l. The list l must not be empty.

TYPEList TailTYPEList (TYPEList l)
Returns the tail of the list l. If l is empty, an empty list is returned.

int LengthTYPEList (TYPEList l)
Returns the number of elements in the list l.

TYPE IthElemTYPEList (TYPEList l, int i);
Returns the i-th element of the List l. The head of l is referred to as 1. If the value of i is greater than the length of the list, an error is reported and the program exits.

TYPEList CopyTYPEList (TYPEList l, TYPEMapFct cp)
Copies the list l. Elements are copied by calls of cp.

TYPEList AppTYPEList (TYPEList l1, TYPEList l2)
Concatenates two lists l1 and l2. The resulting list contains l2 at the end of a copy of list l1. Hence, no argument is modified.

TYPEList AppElTYPEList (TYPEList l, TYPE e)
Appends an element e to the list l. The list l is not copied, it is modified as a side-effect of this function.

void InsertAfterTYPEList (TYPEList l, TYPE e)
This function requires a non-empty list l. The element e is inserted just after the first element of l. The list l is modified as a side-effect of this function.

TYPEList OrderedInsertTYPEList (TYPEList l, TYPE e, TYPECmpFctType fcmp)
Inserts the element e into the list l maintaining l in ascending order with respect to the compare fcmp. The updated list is returned. The list l may be modified as a side-effect of this function.

TYPEListPtr RefEndConsTYPEList (TYPEListPtr addr, TYPE e);
Appends an element e to the end of a list given by its address addr. The address where the next element may be appended is returned. The list is modified as a side-effect of this function.

TYPEListPtr RefEndAppTYPEList (TYPEListPtr addr, TYPEList l);
Appends a list l to the end of a list given by its address addr. The address where the next element may be appended is returned. The list is modified as a side-effect of this function.

int ElemInTYPEList (TYPE e, TYPEList l, TYPECmpFctType cmpfct);
This function returns 1 iff the element e is in the list l. List elements are compared by the function cmpfct.

TYPEList AddToSetTYPEList (TYPE e, TYPEList l, TYPECmpFctType cmpfct)
If l contains e then l is returned. Otherwise a list is returned that contains e and the elements of l. The comparison function cmpfct is used to check whether l already contains e. The list l is not modified.

TYPEList AddToOrderedSetTYPEList (TYPE e, TYPEList l, TYPECmpFctType cmpfct)
If l contains e then l is returned. Otherwise a list is returned that contains e and the elements of l. The comparison function cmpfct is used to check whether l already contains e. l is assumed to be ordered increasingly in the sense of cmpfct. The list l may be modified as a side-effect of this function.

TYPEList MapTYPEList (TYPEList l, TYPEMapFct f);
Returns a new list obtained by applying f to each element of l.

int CompTYPEList (TYPEList l1, TYPEList l2, TYPECmpFctType f);
Compares the lists l1 and l2 lexicographically by applying f to the corresponding elements.

TYPE SumTYPEList (TYPEList l, TYPESumFct f, TYPE a);
Applies the binary function f to the elements of the list: f( f(... f(a, e1), e2, ...), en) If l is empty a is returned.

It should be pointed out that the functions AppElTYPEList, InsertAfterTYPEList, OrderedInsertTYPEList, RefEndConsTYPEList, RefEndAppTYPEList, AddToOrderedSetTYPEList modify existing lists and hence cause side-effects. If the non modified original list values are still to be used they have to be copied (CopyTYPEList) before they are modified. The other functions can be used in a strictly functional style.


Previous Chapter Next Chapter Table of Contents