Machines abstraites                     Back to Summary

 

Abstract machines

Arrays                  

Structures

Linked listes    

Bidirectional linked lists

Stacks

Queues

Binary serach trees

M-ary search trees

Files

 

Abstract machines

 

To each data structure an abstract machine is defined with its set of operation.

 

  LET <Li> :  <Abstract machine>

 

<Li> : Identifier list separated by coma.

 

 

Examples

 

  L1, L2 : LISTS;

  F : QUEUE;

  V1 : ARRAY(10, 60);

  Y : LIST OF STACKS OF ARRAY (5);

 

Abstract machine on arrays

 

ELEMENT ( T [i, j, ...] )

     Access to element T[i, j, ...] of array  T.

ASS_ELEMENT ( T [I, J, ...], Val )

    Assign value Val to element T[i, j, ...].

ALLOC_ARRAY ( T )

    Array allocation. The array address is in T.

LIBER_ARRAY ( T )

    Free the array  of address T.

 

 Abstract machine on structures

 

 STRUCT(S, i) :

    Access to the i-th field of structure S.
ASS_STRUCT(S, i, Val) :

    Assign value Val to the i-th field of structure S.
ALLOC_STRUCT(S) :

    Allocation of a structure. The structure address is in S.
FREE_STRUCT(S) :

    Free the structure of address S.

 

Abstract machine on linked lists

 

ALLOCATE ( P ) :

    Create a chain and return its address in P.
FREE ( P ) :

    Free the node of address P.
NEXT ( P ) :

    Access to the 'Address' field of the node referenced by P.
VALUE ( P ) :

    Access to the 'Value' field of the node referenced by P.
ASS_ADR ( P, Q ) :

    Assign to the 'Address' field of the node referenced by P, the address Q.
ASS_VAL( P, Val ) :

    Assign to the 'Value' field of the node referenced by P, the value Val.
 

Abstract machine on bidirectional linked lists

 

ALLOCATE ( P ) :

    Create a chain and return its address in P.
FREE ( P ) :

    Free the node of address P.
NEXT ( P ) :

    Access to the 'Right address' field of the node referenced by P.
PREVIOUS ( P ) :

    Access to the 'Left address' field of the node referenced by P.
VALUE( P ) :

    Access to the 'Value' field of the node referenced by P.
ASS_VAL( P, Val ) :

    Assign to the 'Value' field of the node referenced by P, the value Val.
ASS_R_ADR ( P, Q ) :

    Assign to the 'Right address' field of the node referenced by P, the address Q.
AFF_L_ADR ( P, Q ) :

    Assign to the 'Left address' field of the node referenced by P, the address Q.
 

Abstract machine on queues

 

CREATEQUEUE ( F ) :

    Create an empty queue.
EMPTY_QUEUE ( F) :

    Test if queue F is empty.
ENQUEUE ( F, Val ) :

    Enqueue (add to tail) value Val to queue F.
DEQUEUE ( F, Val ) :

    Dequeue ( Remove from the file head ) a value from queue F et put it in Val.
Abstract machine on stacks

 

CREATESTACK ( P ) :

    Create an empty stack.
EMPTY_STACK ( P ) :

    Test if stack P is empty.
PUSH ( P, Val ) :

    Push (add to the top) value Val to stack P.
POP ( P, Val ) :

    Pop( Remove from the top) a value from stack P and put it in Val.
 

Abstract machine on binary search trees

 

ALLOCATE_NODE ( Val ) :

    Create a node value Val and return the address of the node. The others fields are to NIL.
FREE_NODE ( P ) :   

    Free the node of address P.
LC ( P ) :

    Access to field left child of node referenced by P.
RC ( P ) :

    Access to field right child of node referenced by P.
PARENT ( P ) :

    Access to field parent of node referenced by P.
NODE_VALUE ( P ) :

    Access to field value of node referenced by P.
ASS_LC ( P, Q ) :

    Assign the address Q to the field left child of node referenced by P.
ASS_RC ( P, Q ) :

    Assign the address Q to the field rightchild of node referenced by P.
ASS_PARENT ( P, Q ) :

    Assign the address Q to the field parent of node referenced by P.
ASS_NODE_VAL( P, Val ) :

    Assign the value Val to the field value of node referenced by P.
 

Abstract machine on M-ary search trees

 

ALLOCATE_NODE ( Val ) :

    Create a node value Val and return the address of the node. The others fields are to NIL.
FREE_NODE ( P ) :

    Free the node of address P.
CHILD ( P, I ) :     

    Access to the i-th child of node referenced by P.
PARENT ( P ) :

    Access to field parent of node referenced by P.
NODE_VALUE_MST ( P, I ) :

    Access to the i-th value of node referenced by P.
ASS_CHILD ( P, I, Q ) :

    Assign the address Q to the i-th child of node referenced by P.
ASS_PARENT ( P, Q ) :

    Assign the address Q to the field parent of node referenced by P.
ASS_NODE_VAL_MST( P, I, Val ) :

    Assign the value Val to i-th value of node referenced by P, la valeur Val.
DEGREE(P) :

    Number of values stocked inside the node referenced by P.
ASS_DEGREE(P, n) :

    Assign the value n to the field degree of node referenced by P.
 

Abstract machine on files

OPEN (F, Fp, Mode) :

    Open the logical file F and associate it to the physical file specifying whether the file is new ('N') or old ('A').
CLOSE(F) :

    Close file F.
READSEQ (F, V) :

    Read in buffer V the record (or block) that is in current position.
WRITESEQ (F, V) :

    Write the record (or block) V to the current position.
READDIR (F, V, n) :

    Read into V the n-th record (or block) of file F.
WRITEDIR (F, V, n) :

    Write record (or block ) V to n-th position.
ADD (F, V) :

    Add record (or block) V at the end of file F.
ENDFILE (F) :

    Predicate equal to true if the end of file F is reached, false otherwise.
ALLOC_BLOCK(F) :

    Position of a block in which we can write.
HEADER (F, i) :

    Get the i-th feature of file F.
ASS_HEADER(F, i, v) :

    Assign V as the i-th feature of file F.