|
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) |
|
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.
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.
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
-
ps1 | A pointer to the postion of the first term |
ps2 | A 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.
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
-
term1 | First input term |
term2 | Second input term |
level | The 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.
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
-
ss | Array of pointers to terms to be compressed. |
n | Number of pointers in ss. |
- Returns
- Total number of words needed for the compressed result.
Definition at line 3074 of file sort.c.
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
-
Pointer | The array of pointers to the terms to be sorted. |
number | The 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.