/**************************************************************************** ** *A plist.h GAP source Martin Schoenert ** *H @(#)$Id: plist.h,v 3.1 1993/02/04 11:01:47 martin Rel $ ** *Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ** ** This file declares the functions that deal with plain lists. The ** interface between the various list packages and the rest of GAP are in ** "lists.c". ** ** A plain list is represented by a bag of type 'T_LIST', which has the ** following format: ** ** +-------+-------+-------+- - - -+-------+-------+- - - -+-------+ ** |logical| first |second | |last |handle | |handle | ** |length |element|element| |element| 0 | | 0 | ** +-------+-------+-------+- - - -+-------+-------+- - - -+-------+ ** ** The first handle is the logical length of the list stored as GAP ** immediate integer. The second handle is the handle of the first element ** of the list. The third handle is the handle of the second element of the ** list, and so on. If the physical length of a list is greater than the ** logical, there will be unused entries at the end of the list, comtaining ** handle 0. The physical length might be greater than the logical, because ** the physical size of a list is increased by at least 12.5\%, to avoid ** doing this too often. ** ** All the other packages of GAP may rely on this representation of plain ** lists. Nevertheless the probably ought to use the macros 'LEN_PLIST', ** 'SET_LEN_PLIST', 'ELM_PLIST', and 'SET_ELM_PLIST'. ** ** This package consists of three parts. ** ** The first part consists of the macros 'SIZE_PLEN_PLIST', ** 'PLEN_SIZE_PLIST', 'LEN_PLIST', 'SET_LEN_PLIST', 'ELM_PLIST', and ** 'SET_ELM_PLIST'. They determine the representation of plain lists. ** Everything else in this file in the rest of the {\GAP} kernel uses those ** macros to access and modify plain lists. ** ** The second part consists of the functions 'LenPlist', 'ElmPlist', ** 'ElmsPlist', 'AssPlist', 'AsssPlist', 'PosPlist', 'PlainPlist', ** 'IsDensePlist', 'IsPossPlist', 'EqPlist', and 'LtPlist'. They are the ** functions required by the generic lists package. Using these functions ** the other parts of the {\GAP} kernel can access and modify plain lists ** without actually being aware that they are dealing with a plain list. ** ** The third part consists of the functions 'MakeList', 'EvMakeList'. These ** function make it possible to make plain lists by evaluating a plain list ** literal. ** *H $Log: plist.h,v $ *H Revision 3.1 1993/02/04 11:01:47 martin *H initial revision under RCS *H */ /**************************************************************************** ** *F PLEN_SIZE_PLIST() . . . physical length from size for a plain list ** ** 'PLEN_SIZE_PLIST' computes the physical length (e.g. the number of ** elements that could be stored in a list) from the (as reported by ** 'SIZE') for a plain list. ** ** Note that 'PLEN_SIZE_PLIST' is a macro, so do not call it with arguments ** that have sideeffects. */ #define PLEN_SIZE_PLIST(SIZE) (((SIZE) - SIZE_HD) / SIZE_HD) /**************************************************************************** ** *F SIZE_PLEN_PLIST() size for a plain list with given physical length ** ** 'SIZE_PLEN_PLIST' returns the size that a plain list with room for ** elements must at least have. ** ** Note that 'SIZE_PLEN_PLIST' is a macro, so do not call it with arguments ** that have sideeffects. */ #define SIZE_PLEN_PLIST(PLEN) (SIZE_HD + (PLEN) * SIZE_HD) /**************************************************************************** ** *F LEN_PLIST() . . . . . . . . . . . . . . . length of a plain list ** ** 'LEN_PLIST' returns the logical length of the list as a C ** integer. The length is stored as GAP immediate integer as the zeroeth ** handle. ** ** Note that 'LEN_PLIST' is a macro, so do not call it with arguments that ** have sideeffects. */ #define LEN_PLIST(LIST) (HD_TO_INT(PTR(LIST)[0])) /**************************************************************************** ** *F SET_LEN_PLIST(,) . . . . . . set the length of a plain list ** ** 'SET_LEN_PLIST' sets the length of the plain list to . The ** length is stored as GAP immediate integer as the zeroeth handle. ** ** Note that 'SET_LEN_PLIST' is a macro, so do not call it with arguments ** that have sideeffects. */ #define SET_LEN_PLIST(LIST,LEN) (PTR(LIST)[0] = INT_TO_HD(LEN)) /**************************************************************************** ** *F ELM_PLIST(,) . . . . . . . . . . . . element of a plain list ** ** 'ELM_PLIST' return the -th element of the list . must ** be a positive integer less than or equal to the length of . ** ** Note that 'ELM_PLIST' is a macro, so do not call it with arguments that ** have sideeffects. */ #define ELM_PLIST(LIST,POS) (PTR(LIST)[POS]) /**************************************************************************** ** *F SET_ELM_PLIST(,,) . assign an element to a plain list ** ** 'SET_ELM_PLIST' assigns the value to the plain list at ** the position . must be a positive integer less than or equal ** to the length of . ** ** Note that 'SET_ELM_PLIST' is a macro, so do not call it with arguments ** that have sideeffects. */ #define SET_ELM_PLIST(LIST,POS,VAL) (PTR(LIST)[POS] = (VAL)) /**************************************************************************** ** *F LenPlist() . . . . . . . . . . . . . . . length of a plain list ** ** 'LenPlist' returns the length of the plain list as a C integer. ** ** 'LenPlist' is the function in 'TabLenList' for plain lists. */ extern long LenPlist P(( TypHandle hdList )); /**************************************************************************** ** *F ElmPlist(,) . . . . . . . select an element of a plain list ** ** 'ElmPlist' selects the element at position of the plain list ** . It is the responsibility of the caller to ensure that is ** a positive integer. An error is signalled if is larger than the ** length of or if has no assigned value at the position ** . ** ** 'ElmfPlist' does the same thing than 'ElmList', but need not check that ** is less than or equal to the length of , this is the ** responsibility of the caller. Also it returns 0 if has no ** assigned value at the position . ** ** 'ElmPlist' is the function in 'TabElmList' for plain lists. 'ElmfPlist' ** is the function in 'TabElmfList', 'TabElmlList', and 'TabElmrList' for ** plain lists. */ extern TypHandle ElmPlist P(( TypHandle hdList, long pos )); extern TypHandle ElmfPlist P(( TypHandle hdList, long pos )); /**************************************************************************** ** *F ElmsPlist(,) . . . . select a sublist from a plain list ** ** 'ElmsPlist' returns a new list containing the elements at the position ** given in the list from the plain list . It is the ** responsibility of the caller to ensure that is dense and ** contains only positive integers. An error is signalled if has ** no assigned value at any of the positions in , or if an element ** of is larger than the length of . ** ** 'ElmsPlist' is the function in 'TabElmsList' for plain lists. */ extern TypHandle ElmsPlist P(( TypHandle hdList, TypHandle hdPoss )); /**************************************************************************** ** *F AssPlist(,,) . . . . . . . . assign to a plain list ** ** 'AssPlist' assigns the value to the plain list at the ** position . It is the responsibility of the caller to ensure that ** is positive, and that is not 'HdVoid'. ** ** If the position is larger then the length of the list , the list is ** automatically extended. To avoid making this too often, the bag of the ** list is extended by at least '/8 + 4' handles. Thus in the loop ** ** l := []; for i in [1..1024] do l[i] := i^2; od; ** ** the list 'l' is extended only 32 times not 1024 times. ** ** 'AssPlist' is the function in 'TabAssList' for plain lists. */ extern TypHandle AssPlist P(( TypHandle hdList, long pos, TypHandle hdVal )); /**************************************************************************** ** *F AsssPlist(,,) . assign several elements to a list ** ** 'AsssPlist' assignes the values from the list at the positions ** given in the list to the list . It is the ** responsibility of the caller to ensure that is dense and ** contains only positive integers, that and have the same ** length, and that is dense. ** ** 'AsssPlist' is the function in 'TabAsssList' for plain lists. */ extern TypHandle AsssPlist P(( TypHandle hdList, TypHandle hdPoss, TypHandle hdVals )); /**************************************************************************** ** *F PosPlist(,,) . . position of an element in a list ** ** 'PosPlist' returns the position of the value in the plain list ** after the first position as a C integer. 0 is returned ** if is not in the list. ** ** 'PosPlist' is the function in 'TabPosList' for plain lists. */ extern long PosPlist P(( TypHandle hdList, TypHandle hdVal, long start )); /**************************************************************************** ** *F PlainPlist() . . . . . . . convert a plain list to a plain list ** ** 'PlainPlist' converts the plain list to a plain list. Not much ** work. ** ** 'PlainPlist' is the function in 'TabPlainList' for plain lists. */ extern void PlainPlist P(( TypHandle hdList )); /**************************************************************************** ** *F IsDensePlist() . . . . dense list test function for plain lists ** ** 'IsDensePlist' returns 1 if the plain list is a dense list and 0 ** otherwise. ** ** 'IsDensePlist' is the function in 'TabIsDenseList' for plain lists. */ extern long IsDensePlist P(( TypHandle hdList )); /**************************************************************************** ** *F IsPossPlist() . . . positions list test function for plain lists ** ** 'IsPossPlist' returns 1 if the plain list is a dense list ** containing only positive integers, and 0 otherwise. ** ** 'IsPossPlist' is the function in 'TabIsPossList' for plain lists. */ extern long IsPossPlist P(( TypHandle hdList )); /**************************************************************************** ** *F EqPlist(,) . . . . . . . . . test if two plain lists are equal ** ** 'EqList' returns 'true' if the two plain lists and are equal ** and 'false' otherwise. ** ** Is called from the 'EQ' binop so both operands are already evaluated. */ extern TypHandle EqPlist P(( TypHandle hdL, TypHandle hdR )); /**************************************************************************** ** *F LtPlist(,) . . . . . . . . . test if two plain lists are equal ** ** 'LtList' returns 'true' if the plain list is less than the plain ** list and 'false' otherwise. ** ** Is called from the 'LT' binop so both operands are already evaluated. */ extern TypHandle LtPlist P(( TypHandle hdL, TypHandle hdR )); /**************************************************************************** ** *F EvMakeList( ) . . . evaluate list literal to a list constant ** ** 'EvMakeList' evaluates the literal, i.e., not yet evaluated, list ** to a constant list. ** ** 'EvMakeList' just calls 'MakeList' telling it that the result goes into ** the variable '~'. Thus expressions in the variable list can refer to ** this variable and its subobjects to create objects that are not trees. */ extern TypHandle EvMakeList P(( TypHandle hdLiteral )); /**************************************************************************** ** *F MakeList(,,) . evaluate list literal to a constant ** ** 'MakeRec' evaluates the list literal to a constant one and ** puts the result into the bag at position . is ** either the variable '~', a list, or a record. ** ** Because of literals like 'rec( a := rec( b := 1, c := ~.a.b ) )' we must ** enter the handle of the result into the superobject before we begin to ** evaluate the list literal. ** ** A list literal is very much like a list, except that instead of the ** elements it contains the expressions, which yield the elements. ** Evaluating a list literal thus means looping over the components, ** evaluating the expressions. */ extern TypHandle MakeList P(( TypHandle hdDst, long ind, TypHandle hdLiteral )); /**************************************************************************** ** *F InitPlist() . . . . . . . . . . . . . . . . . initialize the list package ** ** Is called during the initialization to initialize the list package. */ extern void InitPlist P(( void )); /**************************************************************************** ** *E Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables ** ** Local Variables: ** mode: outline ** outline-regexp: "*A\\|*F\\|*V\\|*T\\|*E" ** fill-column: 73 ** fill-prefix: "** " ** eval: (local-set-key "\t" 'c-indent-command) ** eval: (local-set-key ";" 'electric-c-semi ) ** eval: (local-set-key "{" 'electric-c-brace) ** eval: (local-set-key "}" 'electric-c-brace) ** eval: (hide-body) ** End: */