FORM  4.3
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 (WORD *term1, WORD *term2, WORD level)
 
WORD CompareSymbols (WORD *term1, WORD *term2, WORD par)
 
WORD CompareHSymbols (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 ()
 
WORD * PolyRatFunSpecial (PHEAD WORD *t1, WORD *t2)
 
VOID SimpleSplitMergeRec (WORD *array, WORD num, WORD *auxarray)
 
VOID SimpleSplitMerge (WORD *array, WORD num)
 
WORD BinarySearch (WORD *array, WORD num, WORD x)
 

Variables

LONG numcompares
 
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

◆ WriteStats()

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 93 of file sort.c.

◆ NewSort()

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 592 of file sort.c.

◆ EndSort()

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 682 of file sort.c.

◆ PutIn()

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 1259 of file sort.c.

◆ Sflush()

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 1319 of file sort.c.

◆ PutOut()

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 1405 of file sort.c.

◆ FlushOut()

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 1748 of file sort.c.

◆ AddCoef()

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 1962 of file sort.c.

◆ AddPoly()

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 2089 of file sort.c.

◆ AddArgs()

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 2251 of file sort.c.

◆ Compare1()

WORD Compare1 ( 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 2536 of file sort.c.

◆ CompareSymbols()

WORD CompareSymbols ( 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 2976 of file sort.c.

◆ CompareHSymbols()

WORD CompareHSymbols ( WORD *  term1,
WORD *  term2,
WORD  par 
)

Compares terms that can have only SYMBOL and HAAKJE subterms. If term1 < term2 the return value is -1 If term1 > term2 the return value is 1 If term1 = term2 the return value is 0 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 3020 of file sort.c.

◆ ComPress()

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 3074 of file sort.c.

◆ SplitMerge()

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 3240 of file sort.c.

◆ GarbHand()

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 3462 of file sort.c.

◆ MergePatches()

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 3577 of file sort.c.

◆ 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 4333 of file sort.c.

◆ StageSort()

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 4453 of file sort.c.

◆ SortWild()

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 4552 of file sort.c.

◆ CleanUpSort()

void CleanUpSort ( int  num)

Partially or completely frees function sort buffers.

Definition at line 4644 of file sort.c.

◆ LowerSortLevel()

VOID LowerSortLevel ( )

Lowers the level in the sort system.

Definition at line 4727 of file sort.c.