General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
|
Abstract data types to be used in specifications
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.
|
