FORM  4.1
Macros | Functions | Variables
sort.c File Reference
#include "form3.h"

Go to the source code of this file.

Macros

#define NEWSPLITMERGE
 
#define INSLENGTH(x)   w[1] = FUNHEAD+ARGHEAD+x; w[FUNHEAD] = ARGHEAD+x;
 

Functions

VOID WriteStats (POSITION *plspace, WORD par)
 
WORD NewSort (PHEAD0)
 
LONG EndSort (PHEAD WORD *buffer, int par)
 
LONG PutIn (FILEHANDLE *file, POSITION *position, WORD *buffer, WORD **take, int npat)
 
WORD Sflush (FILEHANDLE *fi)
 
WORD PutOut (PHEAD WORD *term, POSITION *position, FILEHANDLE *fi, WORD ncomp)
 
WORD FlushOut (POSITION *position, FILEHANDLE *fi, int compr)
 
WORD AddCoef (PHEAD WORD **ps1, WORD **ps2)
 
WORD AddPoly (PHEAD WORD **ps1, WORD **ps2)
 
VOID AddArgs (PHEAD WORD *s1, WORD *s2, WORD *m)
 
WORD Compare1 (PHEAD WORD *term1, WORD *term2, WORD level)
 
int CompareSymbols (PHEAD WORD *term1, WORD *term2, WORD par)
 
LONG ComPress (WORD **ss, LONG *n)
 
LONG SplitMerge (PHEAD WORD **Pointer, LONG number)
 
VOID GarbHand ()
 
WORD MergePatches (WORD par)
 
WORD StoreTerm (PHEAD WORD *term)
 
VOID StageSort (FILEHANDLE *fout)
 
WORD SortWild (WORD *w, WORD nw)
 
void CleanUpSort (int num)
 
VOID LowerSortLevel ()
 

Variables

char * toterms [] = { " ", " >>", "-->" }
 

Detailed Description

Contains the sort routines. We distinguish levels of sorting. The ground level is the sorting of terms in an expression. When a term has functions, the arguments can contain terms that need sorting, which this then done by raising the level. This can happen recursively. NewSort and EndSort automatically raise and lower the level. Because the ground level does some special things, sometimes we have to raise immediately to the second level skipping the ground level.

Special routines for the parallel sorting are in the file threads.c Also the sorting of terms in polynomials is special but most of that is controled by changing the address of the compare routine. Other routines relevant for adding rational polynomials are in the file polynito.c

Definition in file sort.c.

Function Documentation

VOID WriteStats ( POSITION plspace,
WORD  par 
)

Writes the statistics.

Parameters
plspaceThe size in bytes currently occupied
parpar = 0 after a splitmerge. par = 1 after merge to sortfile. par = 2 after the sort

current expression is to be found in AR.CurExpr. terms are in S->TermsLeft. S->GenTerms.

Definition at line 91 of file sort.c.

Referenced by EndSort(), PF_Processor(), and StoreTerm().

WORD NewSort ( PHEAD0  )

Starts a new sort. At the lowest level this is a 'main sort' with the struct according to the parameters in S0. At higher levels this is a sort for functions, subroutines or dollars. We prepare the arrays and structs.

Returns
Regular convention (OK -> 0)

Definition at line 553 of file sort.c.

Referenced by DollarFactorize(), InFunction(), MakeDollarInteger(), MakeDollarMod(), PF_CollectModifiedDollars(), PF_InParallelProcessor(), PF_Processor(), PolyFunMul(), Processor(), TakeArgContent(), TakeContent(), TestMatch(), TestSub(), and TheDefine().

LONG EndSort ( PHEAD WORD *  buffer,
int  par 
)

Finishes a sort. At AR.sLevel == 0 the output is to the regular output stream. When AR.sLevel > 0, the parameter par determines the actual output. The AR.sLevel will be popped. All ongoing stages are finished and if the sortfile is open it is closed. The statistics are printed when AR.sLevel == 0 par == 0 Output to the buffer. par == 1 Sort for function arguments. The output will be copied into the buffer. It is assumed that this is in the WorkSpace. par == 2 Sort for $-variable. We return the address of the buffer that contains the output in buffer (treated like WORD **). We first catch the output in a file (unless we can intercept things after the small buffer has been sorted) Then we read from the file into a buffer. Only when par == 0 data compression can be attempted at AT.SS==AT.S0.

Parameters
bufferbuffer for output when needed
parSee above
Returns
If negative: error. If positive: number of words in output.

Definition at line 632 of file sort.c.

References ComPress(), FlushOut(), MergePatches(), PF_EndSort(), PutOut(), SplitMerge(), StageSort(), and WriteStats().

Referenced by DollarFactorize(), InFunction(), MakeDollarInteger(), MakeDollarMod(), PF_CollectModifiedDollars(), PF_InParallelProcessor(), PF_Processor(), PolyFunMul(), Processor(), TakeArgContent(), TakeContent(), TestMatch(), TestSub(), and TheDefine().

LONG PutIn ( FILEHANDLE file,
POSITION position,
WORD *  buffer,
WORD **  take,
int  npat 
)

Reads a new patch from position in file handle. It is put at buffer, anything after take is moved forward. This would be part of a term that hasn't been used yet. Because of this there should be some space before the start of the buffer

Parameters
fileThe file system from which to read
positionThe position from which to read
bufferThe buffer into which to read
takeThe unused tail should be moved before the buffer
npatThe number of the patch. Is needed if the information was compressed with gzip, because each patch has its own independent gzip encoding.

Definition at line 1154 of file sort.c.

References FiLe::handle.

Referenced by MergePatches().

WORD Sflush ( FILEHANDLE fi)

Puts the contents of a buffer to output Only to be used when there is a single patch in the large buffer.

Parameters
fiThe filesystem (or its cache) to which the patch should be written

Definition at line 1214 of file sort.c.

References FiLe::handle.

Referenced by MergePatches().

WORD PutOut ( PHEAD WORD *  term,
POSITION position,
FILEHANDLE fi,
WORD  ncomp 
)

Routine writes one term to file handle at position. It returns the new value of the position.

NOTE: For 'final output' we may have to index the brackets. See the struct BRACKETINDEX. We should maintain: 1: a list with brackets array with the brackets 2: a list of objects of type BRACKETINDEX. It contains array with either pointers or offsets to the list of brackets. starting positions in the file. The index may be tied to a maximum size. In that case we may have to prune the list occasionally.

Parameters
termThe term to be written
positionThe position in the file. Afterwards it is updated
fiThe file (or its cache) to which should be written
ncompInformation about what type of compression should be used

Definition at line 1300 of file sort.c.

References FiLe::handle, and PF_ISendSbuf().

Referenced by EndSort(), MergePatches(), PF_EndSort(), PF_InParallelProcessor(), PF_Processor(), Processor(), and TheDefine().

WORD FlushOut ( POSITION position,
FILEHANDLE fi,
int  compr 
)

Completes output to an output file and writes the trailing zero.

Parameters
positionThe position in the file after writing
fiThe file (or its cache)
comprIndicates whether there should be compression with gzip.
Returns
Regular conventions (OK -> 0).

Definition at line 1621 of file sort.c.

References FiLe::handle, BrAcKeTiNfO::indexbuffer, and PF_ISendSbuf().

Referenced by EndSort(), MergePatches(), PF_EndSort(), Processor(), and TheDefine().

WORD AddCoef ( PHEAD WORD **  ps1,
WORD **  ps2 
)

Adds the coefficients of the terms *ps1 and *ps2. The problem comes when there is not enough space for a new longer coefficient. First a local solution is tried. If this is not succesfull we need to move terms around. The possibility of a garbage collection should not be ignored, as avoiding this costs very much extra space which is nearly wasted otherwise.

If the return value is zero the terms cancelled.

The resulting term is left in *ps1.

Definition at line 1829 of file sort.c.

References GarbHand(), and NormalModulus().

Referenced by SplitMerge().

WORD AddPoly ( PHEAD WORD **  ps1,
WORD **  ps2 
)

Routine should be called when S->PolyWise != 0. It points then to the position of AR.PolyFun in both terms.

We add the contents of the arguments of the two polynomials. Special attention has to be given to special arguments. We have to reserve a space equal to the size of one term + the size of the argument of the other. The addition has to be done in this routine because not all objects are reentrant.

Newer addition (12-nov-2007). The PolyFun can have two arguments. In that case S->PolyFlag is 2 and we have to call the routine for adding rational polynomials. We have to be rather careful what happens with: The location of the output The order of the terms in the arguments At first we allow only univariate polynomials in the PolyFun. This restriction will be lifted a.s.a.p.

Parameters
ps1A pointer to the postion of the first term
ps2A pointer to the postion of the second term
Returns
If zero the terms cancel. Otherwise the new term is in *ps1.

Definition at line 1956 of file sort.c.

References AddArgs(), and GarbHand().

Referenced by SplitMerge().

VOID AddArgs ( PHEAD WORD *  s1,
WORD *  s2,
WORD *  m 
)

Adds the arguments of two occurrences of the PolyFun.

Parameters
s1Pointer to the first occurrence.
s2Pointer to the second occurrence.
mPointer to where the answer should be.

Definition at line 2115 of file sort.c.

Referenced by AddPoly(), and MergePatches().

WORD Compare1 ( PHEAD WORD *  term1,
WORD *  term2,
WORD  level 
)

Compares two terms. The answer is: 0 equal ( with exception of the coefficient if level == 0. ) >0 term1 comes first. <0 term2 comes first. Some special precautions may be needed to keep the CompCoef routine from generating overflows, although this is very unlikely in subterms. This routine should not return an error condition.

Originally this routine was called Compare. With the treatment of special polynomials with terms that contain only symbols and the need for extreme speed for the polynomial routines we made a special compare routine and now we store the address of the current compare routine in AR.CompareRoutine and have a macro Compare which makes all existing code work properly and we can just replace the routine on a thread by thread basis (each thread has its own AR struct).

Parameters
term1First input term
term2Second input term
levelThe sorting level (may influence on the result)
Returns
0 equal ( with exception of the coefficient if level == 0. ) >0 term1 comes first. <0 term2 comes first.

Definition at line 2397 of file sort.c.

References CompCoef().

Referenced by InFunction(), and StartVariables().

int CompareSymbols ( PHEAD WORD *  term1,
WORD *  term2,
WORD  par 
)

Compares the terms, based on the value of AN.polysortflag. If term1 < term2 the return value is -1 If term1 > term2 the return value is 1 If term1 = term2 the return value is 0 The coefficients may differ. The terms contain only a single subterm of type SYMBOL. If AN.polysortflag = 0 it is a 'regular' compare. If AN.polysortflag = 1 the sum of the powers is more important par is a dummy parameter to make the parameter field identical to that of Compare1 which is the regular compare routine in sort.c

Definition at line 2818 of file sort.c.

Referenced by InFunction(), and TestSub().

LONG ComPress ( WORD **  ss,
LONG *  n 
)

Gets a list of pointers to terms and compresses the terms. In n it collects the number of terms and the return value of the function is the space that is occupied.

We have to pay some special attention to the compression of terms with a PolyFun. This PolyFun should occur only straight before the coefficient, so we can use the same trick as for the coefficient to sabotage compression of this object (Replace in the history the function pointer by zero. This is safe, because terms that would be identical otherwise would have been added).

Parameters
ssArray of pointers to terms to be compressed.
nNumber of pointers in ss.
Returns
Total number of words needed for the compressed result.

Definition at line 2867 of file sort.c.

Referenced by EndSort(), and StoreTerm().

LONG SplitMerge ( PHEAD WORD **  Pointer,
LONG  number 
)

Algorithm by J.A.M.Vermaseren (31-7-1988)

Note that AN.SplitScratch and AN.InScratch are used also in GarbHand

Merge sort in memory. The input is an array of pointers. Sorting is done recursively by dividing the array in two equal parts and calling SplitMerge for each. When the parts are small enough we can do the compare and take the appropriate action. An addition is that we look for 'runs'. Sequences that are already ordered. This happens a lot when there is very little action in a module. This made FORM faster by a few percent.

Parameters
PointerThe array of pointers to the terms to be sorted.
numberThe number of pointers in Pointer.

The terms are supposed to be sitting in the small buffer and there is supposed to be an extension to this buffer for when there are two terms that should be added and the result takes more space than each of the original terms. The notation guarantees that the result never needs more space than the sum of the spaces of the original terms.

Definition at line 3033 of file sort.c.

References AddCoef(), AddPoly(), and PHEAD.

Referenced by EndSort(), and StoreTerm().

VOID GarbHand ( )

Garbage collection that takes place when the small extension is full and we need to place more terms there. When this is the case there are many holes in the small buffer and the whole can be compactified. The major complication is the buffer for SplitMerge. There are to options for temporary memory: 1: find some buffer that has enough space (maybe in the large buffer). 2: allocate a buffer. Give it back afterwards of course. If the small extension is properly dimensioned this routine should be called very rarely. Most of the time it will be called when the polyfun or polyratfun is active.

Definition at line 3209 of file sort.c.

Referenced by AddCoef(), and AddPoly().

WORD MergePatches ( WORD  par)

The general merge routine. Can be used for the large buffer and the file merging. The array S->Patches tells where the patches start S->pStop tells where they end (has to be computed first). The end of a 'line to be merged' is indicated by a zero. If the end is reached without running into a zero or a term runs over the boundary of a patch it is a file merging operation and a new piece from the file is read in.

Parameters
parIf par == 0 the sort is for file -> outputfile. If par == 1 the sort is for large buffer -> sortfile. If par == 2 the sort is for large buffer -> outputfile.

Definition at line 3324 of file sort.c.

References AddArgs(), FlushOut(), FiLe::handle, NormalModulus(), PutIn(), PutOut(), Sflush(), and StageSort().

Referenced by EndSort(), and StoreTerm().

WORD StoreTerm ( PHEAD WORD *  term)

The central routine to accept terms, store them and keep things at least partially sorted. A call to EndSort will then complete storing and sorting.

Parameters
termThe term to be stored
Returns
Regular return conventions (OK -> 0)

Definition at line 4070 of file sort.c.

References ComPress(), MergePatches(), SplitMerge(), and WriteStats().

Referenced by DollarFactorize(), Generator(), InFunction(), PF_InParallelProcessor(), PF_Processor(), PolyFunMul(), Processor(), TakeArgContent(), and TestSub().

VOID StageSort ( FILEHANDLE fout)

Prepares a stage 4 or higher sort. Stage 4 sorts occur when the sort file contains more patches than can be merged in one pass.

Definition at line 4189 of file sort.c.

References FiLe::handle.

Referenced by EndSort(), and MergePatches().

WORD SortWild ( WORD *  w,
WORD  nw 
)

Sorts the wildcard entries in the parameter w. Double entries are removed. Full space taken is nw words. Routine serves for the reading of wildcards in the compiler. The entries come in the format: (type,4,number,0) in which the zero is reserved for the future replacement of 'number'.

Parameters
wbuffer with wildcard entries.
nwnumber of wildcard entries.
Returns
Normal conventions (OK -> 0)

Definition at line 4269 of file sort.c.

void CleanUpSort ( int  num)

Partially or completely frees function sort buffers.

Definition at line 4361 of file sort.c.

Referenced by StartVariables().

VOID LowerSortLevel ( )