• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

vermaseren / form / 9364948935

04 Jun 2024 09:49AM UTC coverage: 49.979% (-0.02%) from 49.999%
9364948935

Pull #526

github

web-flow
Merge 7062bd769 into 83e3d4185
Pull Request #526: RFC: better debugging

52 of 415 new or added lines in 46 files covered. (12.53%)

32 existing lines in 2 files now uncovered.

41391 of 82816 relevant lines covered (49.98%)

878690.77 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.13
/sources/comtool.c
1
/** @file comtool.c
2
 * 
3
 *  Utility routines for the compiler.
4
 */
5
/* #[ License : */
6
/*
7
 *   Copyright (C) 1984-2023 J.A.M. Vermaseren
8
 *   When using this file you are requested to refer to the publication
9
 *   J.A.M.Vermaseren "New features of FORM" math-ph/0010025
10
 *   This is considered a matter of courtesy as the development was paid
11
 *   for by FOM the Dutch physics granting agency and we would like to
12
 *   be able to track its scientific use to convince FOM of its value
13
 *   for the community.
14
 *
15
 *   This file is part of FORM.
16
 *
17
 *   FORM is free software: you can redistribute it and/or modify it under the
18
 *   terms of the GNU General Public License as published by the Free Software
19
 *   Foundation, either version 3 of the License, or (at your option) any later
20
 *   version.
21
 *
22
 *   FORM is distributed in the hope that it will be useful, but WITHOUT ANY
23
 *   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
24
 *   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
25
 *   details.
26
 *
27
 *   You should have received a copy of the GNU General Public License along
28
 *   with FORM.  If not, see <http://www.gnu.org/licenses/>.
29
 */
30
/* #] License : */ 
31
/*
32
          #[ Includes :
33
*/
34

35
#include "form3.h"
36

37
/*
38
          #] Includes : 
39
          #[ inicbufs :
40
*/
41

42
/**
43
 * Creates a new compiler buffer and returns its ID number.
44
 *
45
 * @return  The ID number for the new compiler buffer.
46
 */
47
int inicbufs(VOID)
24,139✔
48
{
49
        int i, num = AC.cbufList.num;
24,139✔
50
        CBUF *C = cbuf;
24,139✔
51
        for ( i = 0; i < num; i++, C++ ) {
207,277✔
52
                if ( C->Buffer == 0 ) break;
183,138✔
53
        }
54
        if ( i >= num ) C = (CBUF *)FromList(&AC.cbufList);
24,139✔
55
        else num = i;
56
        C->BufferSize = 2000;
24,139✔
57
        C->Buffer = (WORD *)Malloc1(C->BufferSize*sizeof(WORD),"compiler buffer-1");
24,139✔
58
        C->Pointer = C->Buffer;
24,139✔
59
        C->Top = C->Buffer + C->BufferSize;
24,139✔
60
        C->maxlhs = 10;
24,139✔
61
        C->lhs = (WORD **)Malloc1(C->maxlhs*sizeof(WORD *),"compiler buffer-2");
24,139✔
62
        C->numlhs = 0;
24,139✔
63
        C->mnumlhs = 0;
24,139✔
64
        C->maxrhs = 25;
24,139✔
65
        C->rhs = (WORD **)Malloc1(C->maxrhs*(sizeof(WORD *)+2*sizeof(LONG)+2*sizeof(WORD)),"compiler buffer-3");
24,139✔
66
        C->CanCommu = (LONG *)(C->rhs+C->maxrhs);
24,139✔
67
        C->NumTerms = C->CanCommu+C->maxrhs;
24,139✔
68
        C->numdum = (WORD *)(C->NumTerms+C->maxrhs);
24,139✔
69
        C->dimension = C->numdum + C->maxrhs;
24,139✔
70
        C->numrhs = 0;
24,139✔
71
        C->mnumrhs = 0;
24,139✔
72
        C->rhs[0] = C->rhs[1] = C->Pointer;
24,139✔
73
        C->boomlijst = 0;
24,139✔
74
        RedoTree(C,C->maxrhs);
24,139✔
75
        ClearTree(num);
24,139✔
76
        return(num);
24,139✔
77
}
78

79
/*
80
          #] inicbufs : 
81
          #[ finishcbuf :
82
*/
83

84
/**
85
 * Frees a compiler buffer.
86
 *
87
 * @param  num  The ID number for the buffer to be freed.
88
 */
89
void finishcbuf(WORD num)
21✔
90
{
91
        CBUF *C = cbuf+num;
21✔
92
        if ( C->Buffer ) M_free(C->Buffer,"compiler buffer-1");
21✔
93
        if ( C->rhs ) M_free(C->rhs,"compiler buffer-3");
21✔
94
        if ( C->lhs ) M_free(C->lhs,"compiler buffer-2");
21✔
95
        if ( C->boomlijst ) M_free(C->boomlijst,"boomlijst");
21✔
96
        C->Top = C->Pointer = C->Buffer = 0;
21✔
97
        C->rhs = C->lhs = 0;
21✔
98
        C->CanCommu = 0;
21✔
99
        C->NumTerms = 0;
21✔
100
        C->BufferSize = 0;
21✔
101
        C->boomlijst = 0;
21✔
102
        C->numlhs = C->numrhs = C->maxlhs = C->maxrhs = C->mnumlhs =
21✔
103
        C->mnumrhs = C->numtree = C->rootnum = C->MaxTreeSize = 0;
21✔
104
}
21✔
105

106
/*
107
          #] finishcbuf : 
108
          #[ clearcbuf :
109
*/
110

111
/**
112
 * Clears contents in a compiler buffer.
113
 *
114
 * @param  num  The ID number for the buffer to be cleared.
115
 */
116
void clearcbuf(WORD num)
3,475✔
117
{
118
        CBUF *C = cbuf+num;
3,475✔
119
        if ( C->boomlijst ) M_free(C->boomlijst,"boomlijst");
3,475✔
120
        C->Pointer = C->Buffer;
3,475✔
121
        C->numrhs = C->numlhs = 0;
3,475✔
122
        C->mnumlhs = 0;
3,475✔
123
        C->boomlijst = 0;
3,475✔
124
        C->mnumrhs = 0;
3,475✔
125
        C->rhs[0] = C->rhs[1] = C->Pointer;
3,475✔
126
        C->numtree = C->rootnum = C->MaxTreeSize = 0;
3,475✔
127
        RedoTree(C,C->maxrhs);
3,475✔
128
        ClearTree(num);
3,475✔
129
}
3,475✔
130

131
/*
132
          #] clearcbuf : 
133
          #[ DoubleCbuffer :
134
*/
135

136
/**
137
 * Doubles a compiler buffer.
138
 *
139
 * @param  num  The ID number for the buffer to be doubled.
140
 * @param  w    The pointer to the end (exclusive) of the current buffer. The
141
 *              contents in the range of [cbuf[num].Buffer,w) will be kept.
142
 */
143
WORD *DoubleCbuffer(int num, WORD *w,int par)
463✔
144
{
145
        CBUF *C = cbuf + num;
463✔
146
        LONG newsize = C->BufferSize*2;
463✔
147
        WORD *newbuffer = (WORD *)Malloc1(newsize*sizeof(WORD),"compiler buffer-4");
463✔
148
        WORD *w1, *w2;
463✔
149
        LONG offset, j, i;
463✔
150
        DUMMYUSE(par)
463✔
151
/*
152
        MLOCK(ErrorMessageLock);
153
                MesPrint(" doubleCbuffer: par = %d",par);
154
        MUNLOCK(ErrorMessageLock);
155
*/
156
        w1 = C->Buffer; w2 = newbuffer;
463✔
157
        i = w - w1;
463✔
158
        j = i & 7;
463✔
159
        while ( --j >= 0 ) *w2++ = *w1++;
1,629✔
160
        i >>= 3;
463✔
161
        while ( --i >= 0 ) {
1,252,308✔
162
                *w2++ = *w1++; *w2++ = *w1++; *w2++ = *w1++; *w2++ = *w1++;
1,251,845✔
163
                *w2++ = *w1++; *w2++ = *w1++; *w2++ = *w1++; *w2++ = *w1++;
1,251,845✔
164
        }
165
        offset = newbuffer - C->Buffer;
463✔
166
        for ( i = 0; i <= C->numlhs; i++ ) C->lhs[i] += offset;
7,107✔
167
        for ( i = 1; i <= C->numrhs; i++ ) C->rhs[i] += offset;
218,951✔
168
        w1 = C->Buffer;
463✔
169
        C->Pointer += offset;
463✔
170
        C->Top = newbuffer + newsize;
463✔
171
        C->BufferSize = newsize;
463✔
172
        C->Buffer = newbuffer;
463✔
173
        M_free(w1,"DoubleCbuffer");
463✔
174
        return(w2);
463✔
175
}
176

177
/*
178
          #] DoubleCbuffer : 
179
          #[ AddLHS :
180
*/
181

182
/**
183
 * Adds an LHS to a compiler buffer and returns the pointer to a buffer for the
184
 * new LHS.
185
 *
186
 * @param  num  The ID number for the buffer to get another LHS.
187
 */
188
WORD *AddLHS(int num)
29,177✔
189
{
190
        CBUF *C = cbuf + num;
29,177✔
191
        C->numlhs++;
29,177✔
192
        if ( C->numlhs >= (C->maxlhs-2) ) {
29,177✔
193
                WORD ***ppp = &(C->lhs);        /* to avoid compiler warning */
217✔
194
                if ( DoubleList((VOID ***)ppp,&(C->maxlhs),sizeof(WORD *),
217✔
NEW
195
                "statement lists") ) TERMINATE(-1);
×
196
        }
197
        C->lhs[C->numlhs] = C->Pointer;
29,177✔
198
        C->lhs[C->numlhs+1] = 0;
29,177✔
199
        return(C->Pointer);
29,177✔
200
}
201

202
/*
203
          #] AddLHS : 
204
          #[ AddRHS :
205
*/
206

207
/**
208
 * Adds an RHS to a compiler buffer and returns the pointer to a buffer for the
209
 * new RHS.
210
 *
211
 * @param  num   The ID number for the buffer to get another RHS.
212
 * @param  type  If 0, the subexpression tree will be reallocated.
213
 */
214
WORD *AddRHS(int num, int type)
9,901,170✔
215
{
216
        LONG fullsize, *lold, newsize;
9,901,170✔
217
        int i;
9,901,170✔
218
        WORD **old, *wold;
9,901,170✔
219
        CBUF *C;
9,901,170✔
220
restart:;
9,901,170✔
221
        C = cbuf + num;
9,901,170✔
222
        if ( C->numrhs >= (C->maxrhs-2) ) {
9,901,170✔
223
                if ( C->maxrhs == 0 ) newsize = 100;
310✔
224
                else                  newsize = C->maxrhs * 2;
310✔
225
                if ( newsize > MAXCOMBUFRHS ) newsize = MAXCOMBUFRHS;
310✔
226
                if ( newsize == C->maxrhs ) {
310✔
227
                        if ( AC.tablefilling ) {
×
228
                                TABLES T = functions[AC.tablefilling].tabl;
×
229
/*
230
                                We add a compiler buffer, change a few settings and continue.
231
*/
232
                                if ( T->buffersfill >= T->bufferssize ) {
×
233
                                        int new1 = 2*T->bufferssize;
×
234
                                        WORD *nbufs = (WORD *)Malloc1(new1*sizeof(WORD),"Table compile buffers");
×
235
                                        for ( i = 0; i < T->buffersfill; i++ )
×
236
                                                        nbufs[i] = T->buffers[i];
×
237
                                        for ( ; i < new1; i++ ) nbufs[i] = 0;
×
238
                                        M_free(T->buffers,"Table compile buffers");
×
239
                                        T->buffers = nbufs;
×
240
                                        T->bufferssize = new1;
×
241
                                }
242
                                T->buffers[T->buffersfill++] = T->bufnum = inicbufs();
×
243
                                AC.cbufnum = num = T->bufnum;
×
244
                                goto restart;
×
245
                        }
246
                        else {
247
                                MesPrint("@Compiler buffer overflow. Try to make modules smaller");
×
NEW
248
                                TERMINATE(-1);
×
249
                        }
250
                }
251
                old        = C->rhs;
310✔
252
                fullsize = newsize * (sizeof(WORD *) + 2*sizeof(LONG) + 2*sizeof(WORD));
310✔
253
                C->rhs = (WORD **)Malloc1(fullsize,"subexpression lists");
310✔
254
                for ( i = 0; i < C->maxrhs; i++ ) C->rhs[i] = old[i];
204,085✔
255
                lold = C->CanCommu; C->CanCommu = (LONG *)(C->rhs+newsize);
310✔
256
                for ( i = 0; i < C->maxrhs; i++ ) C->CanCommu[i] = lold[i];
204,085✔
257
                lold = C->NumTerms; C->NumTerms = (LONG *)(C->rhs+2*newsize);
310✔
258
                for ( i = 0; i < C->maxrhs; i++ ) C->NumTerms[i] = lold[i];
204,085✔
259
                wold = C->numdum; C->numdum = (WORD *)(C->NumTerms+newsize);
310✔
260
                for ( i = 0; i < C->maxrhs; i++ ) C->numdum[i] = wold[i];
204,085✔
261
                wold = C->dimension; C->dimension = (WORD *)(C->numdum+newsize);
310✔
262
                for ( i = 0; i < C->maxrhs; i++ ) C->dimension[i] = wold[i];
204,085✔
263
                if ( old ) M_free(old,"subexpression lists");
310✔
264
                C->maxrhs = newsize;
310✔
265
                if ( type == 0 ) RedoTree(C,C->maxrhs);
310✔
266
        }
267
        C->numrhs++;
9,901,170✔
268
        C->CanCommu[C->numrhs] = 0;
9,901,170✔
269
        C->NumTerms[C->numrhs] = 0;
9,901,170✔
270
        C->numdum[C->numrhs] = 0;
9,901,170✔
271
        C->dimension[C->numrhs] = 0;
9,901,170✔
272
        C->rhs[C->numrhs] = C->Pointer;
9,901,170✔
273
        return(C->Pointer);
9,901,170✔
274
}
275

276
/*
277
          #] AddRHS : 
278
          #[ AddNtoL :
279
*/
280

281
/**
282
 * Adds an LHS with the given data to the current compiler buffer.
283
 *
284
 * @param  n      The length of the data.
285
 * @param  array  The data to be added.
286
 * @return        0 if succeeds.
287
 */
288
int AddNtoL(int n, WORD *array)
15,767✔
289
{
290
        int i;
15,767✔
291
        CBUF *C = cbuf+AC.cbufnum;
15,767✔
292
#ifdef COMPBUFDEBUG
293
        MesPrint("LH: %a",n,array);
294
#endif
295
        AddLHS(AC.cbufnum);
15,767✔
296
        while ( C->Pointer+n >= C->Top ) DoubleCbuffer(AC.cbufnum,C->Pointer,1);
15,774✔
297
        for ( i = 0; i < n; i++ ) *(C->Pointer)++ = *array++;
355,004✔
298
        return(0);
15,767✔
299
}
300

301
/*
302
          #] AddNtoL : 
303
          #[ AddNtoC :
304

305
        Commentary: added the bufnum on 14-sep-2010 to make the whole a bit
306
        more flexible (JV). Still to do with AddNtoL.
307
*/
308

309
/**
310
 * Adds the given data to the last LHS/RHS in a compiler buffer.
311
 *
312
 * @param  bufnum  The ID number for the buffer where the data will be added.
313
 * @param  n       The length of the data.
314
 * @param  array   The data to be added.
315
 * @return         0 if succeeds.
316
 */
317
int AddNtoC(int bufnum, int n, WORD *array,int par)
1,175,090✔
318
{
319
        int i;
1,175,090✔
320
        WORD *w;
1,175,090✔
321
        CBUF *C = cbuf+bufnum;
1,175,090✔
322
#ifdef COMPBUFDEBUG
323
        MesPrint("RH: %a",n,array);
324
#endif
325
        while ( C->Pointer+n+1 >= C->Top ) DoubleCbuffer(bufnum,C->Pointer,50+par);
1,175,423✔
326
        w = C->Pointer;
327
        for ( i = 0; i < n; i++ ) *w++ = *array++;
21,389,060✔
328
        C->Pointer = w;
1,175,090✔
329
        return(0);
1,175,090✔
330
}
331

332
/*
333
          #] AddNtoC : 
334
          #[ InsTree :
335

336
        Routines for balanced tree searching and insertion.
337
        Compared to Knuth we have a parent link. This minimizes the
338
        number of compares. That is better for anything that is more
339
        complicated than just single numbers.
340
        There are no provisions for removing elements from the tree.
341
        The routines are:
342
        void RedoTree(size) Re-allocates the tree space. There will
343
                        be MaxTreeSize = size elements.
344
        void ClearTree()    Prunes the tree down to the root element.
345
        int InsTree(int,int)Searches for the requested element. If not found it
346
                            will allocate a new element, balance the tree if
347
                            necessary and return the called number.
348
                        If it was in the tree, it returns the tree 'value'.
349

350
        Commentary: added the bufnum on 14-sep-2010 to make the whole a bit
351
        more flexible (JV).
352
*/
353
static COMPTREE comptreezero = {0,0,0,0,0,0};
354

355
int InsTree(int bufnum, int h)
259,836✔
356
{
357
        CBUF *C = cbuf + bufnum;
259,836✔
358
        COMPTREE *boomlijst = C->boomlijst, *q = boomlijst + C->rootnum, *p, *s;
259,836✔
359
        WORD *v1, *v2, *v3;
259,836✔
360
        int ip, iq, is;
259,836✔
361

362
        if ( C->numtree + 1 >= C->MaxTreeSize ) {
259,836✔
363
                if ( C->MaxTreeSize == 0 ) {
20✔
364
                        COMPTREE *root;
×
365
                        C->MaxTreeSize = 125;
×
366
                        C->boomlijst = (COMPTREE *)Malloc1((C->MaxTreeSize+1)*sizeof(COMPTREE),
×
367
                                "ClearInsTree");
368
                        root = C->boomlijst;
×
369
                        C->numtree = 0;
×
370
                        C->rootnum = 0;
×
371
                        root->left = -1;                
×
372
                        root->right = -1;
×
373
                        root->parent = -1;
×
374
                        root->blnce = 0;
×
375
                        root->value = -1;
×
376
                        root->usage = 0;
×
377
                        for ( ip = 1; ip < C->MaxTreeSize; ip++ ) { C->boomlijst[ip] = comptreezero; }
×
378
                }
379
                else {
380
                        is = C->MaxTreeSize * 2;
20✔
381
                        s  = (COMPTREE *)Malloc1((is+1)*sizeof(COMPTREE),"InsTree");
20✔
382
                        for ( ip = 0; ip < C->MaxTreeSize; ip++ ) { s[ip] = C->boomlijst[ip]; }
3,140✔
383
                        for ( ip = C->MaxTreeSize; ip <= is; ip++ ) { s[ip] = comptreezero; }
3,140✔
384
                        if ( C->boomlijst ) M_free(C->boomlijst,"InsTree");
20✔
385
                        C->boomlijst = s;
20✔
386
                        C->MaxTreeSize = is;
20✔
387
                }
388
                boomlijst = C->boomlijst;
20✔
389
                q = boomlijst + C->rootnum;
20✔
390
        }
391

392
        if ( q->right == -1 ) { /* First element */
259,836✔
393
                C->numtree++;
1,279✔
394
                s = boomlijst+C->numtree;
1,279✔
395
                q->right = C->numtree;
1,279✔
396
                s->parent = C->rootnum;
1,279✔
397
                s->left = s->right = -1;
1,279✔
398
                s->blnce = 0;
1,279✔
399
                s->value = h;
1,279✔
400
                s->usage = 1;
1,279✔
401
                return(h);
1,279✔
402
        }
403
        ip = q->right;
404
        while ( ip >= 0 ) {
2,462,807✔
405
                p = boomlijst + ip;
2,462,807✔
406
                v1 = C->rhs[p->value]; v2 = v3 = C->rhs[h];
2,462,807✔
407
                while ( *v3 ) v3 += *v3;  /* find the 0 that indicates end-of-expr */
10,982,570✔
408
                while ( *v1 == *v2 && v2 < v3 ) { v1++; v2++; }
22,726,710✔
409
                if ( *v1 > *v2 ) {
2,462,807✔
410
                        iq = p->right;
681,841✔
411
                        if ( iq >= 0 ) { ip = iq; }
681,841✔
412
                        else {
413
                                C->numtree++;
15,201✔
414
                                is = C->numtree; 
15,201✔
415
                                p->right = is;
15,201✔
416
                                s = boomlijst + is;
15,201✔
417
                                s->parent = ip; s->left = s->right = -1;
15,201✔
418
                                s->blnce = 0;   s->value = h; s->usage = 1;
15,201✔
419
                                p->blnce++;
15,201✔
420
                                if ( p->blnce == 0 ) return(h);
15,201✔
421
                                goto balance;
13,152✔
422
                        }
423
                }
424
                else if ( *v1 < *v2 ) {
1,780,970✔
425
                        iq = p->left;
1,664,739✔
426
                        if ( iq >= 0 ) { ip = iq; }
1,664,739✔
427
                        else {
428
                                C->numtree++;
127,126✔
429
                                is = C->numtree;
127,126✔
430
                                s = boomlijst+is;
127,126✔
431
                                p->left = is;
127,126✔
432
                                s->parent = ip; s->left = s->right = -1;
127,126✔
433
                                s->blnce = 0;   s->value = h; s->usage = 1;
127,126✔
434
                                p->blnce--;
127,126✔
435
                                if ( p->blnce == 0 ) return(h);
127,126✔
436
                                goto balance;
124,993✔
437
                        }
438
                }
439
                else {
440
                        p->usage++;
116,230✔
441
                        return(p->value);
116,230✔
442
                }
443
        }
444
        MesPrint("We vallen uit de boom!");
×
NEW
445
        TERMINATE(-1);
×
446
        return(h);
×
447
balance:;
276,350✔
448
        for (;;) {
276,350✔
449
                p = boomlijst + ip;
276,350✔
450
                iq = p->parent;
276,350✔
451
                if ( iq == C->rootnum ) break;
276,350✔
452
                q = boomlijst + iq;
274,394✔
453
                if ( ip == q->left ) q->blnce--;
274,394✔
454
                else                 q->blnce++;
27,332✔
455
                if ( q->blnce == 0 ) break;
274,394✔
456
                if ( q->blnce == -2 ) {
265,251✔
457
                        if ( p->blnce == -1 ) { /* single rotation */
118,708✔
458
                                q->left = p->right;
115,432✔
459
                                p->right = iq;
115,432✔
460
                                p->parent = q->parent;
115,432✔
461
                                q->parent = ip;
115,432✔
462
                                if ( boomlijst[p->parent].left == iq ) boomlijst[p->parent].left = ip;
115,432✔
463
                                else                                   boomlijst[p->parent].right = ip;
2,577✔
464
                                if ( q->left >= 0 ) boomlijst[q->left].parent = iq;
115,432✔
465
                                q->blnce = p->blnce = 0;
115,432✔
466
                        }
467
                        else {        /* double rotation */
468
                                s = boomlijst + is;
3,276✔
469
                                q->left = s->right;
3,276✔
470
                                p->right = s->left;
3,276✔
471
                                s->right = iq;
3,276✔
472
                                s->left = ip;
3,276✔
473
                                if ( p->right >= 0 ) boomlijst[p->right].parent = ip;
3,276✔
474
                                if ( q->left >= 0 ) boomlijst[q->left].parent = iq;
3,276✔
475
                                s->parent = q->parent;
3,276✔
476
                                q->parent = is;
3,276✔
477
                                p->parent = is;
3,276✔
478
                                if ( boomlijst[s->parent].left == iq )
3,276✔
479
                                           boomlijst[s->parent].left = is;
1,642✔
480
                                else   boomlijst[s->parent].right = is;
1,634✔
481
                                if ( s->blnce > 0 ) { q->blnce = s->blnce = 0; p->blnce = -1; }
3,276✔
482
                                else if ( s->blnce < 0 ) { p->blnce = s->blnce = 0; q->blnce = 1; }
2,442✔
483
                                else { p->blnce = s->blnce = q->blnce = 0; }
1,857✔
484
                        }
485
                        break;
486
                }
487
                else if ( q->blnce == 2 ) {
146,543✔
488
                        if ( p->blnce == 1 ) {        /* single rotation */
8,338✔
489
                                q->right = p->left;
4,816✔
490
                                p->left = iq;
4,816✔
491
                                p->parent = q->parent;
4,816✔
492
                                q->parent = ip;
4,816✔
493
                                if ( boomlijst[p->parent].left == iq ) boomlijst[p->parent].left = ip;
4,816✔
494
                                else                                   boomlijst[p->parent].right = ip;
3,579✔
495
                                if ( q->right >= 0 ) boomlijst[q->right].parent = iq;
4,816✔
496
                                q->blnce = p->blnce = 0;
4,816✔
497
                        }
498
                        else {        /* double rotation */
499
                                s = boomlijst + is;
3,522✔
500
                                q->right = s->left;
3,522✔
501
                                p->left = s->right;
3,522✔
502
                                s->left = iq;
3,522✔
503
                                s->right = ip;
3,522✔
504
                                if ( p->left >= 0 ) boomlijst[p->left].parent = ip;
3,522✔
505
                                if ( q->right >= 0 ) boomlijst[q->right].parent = iq;
3,522✔
506
                                s->parent = q->parent;
3,522✔
507
                                q->parent = is;
3,522✔
508
                                p->parent = is;
3,522✔
509
                                if ( boomlijst[s->parent].left == iq ) boomlijst[s->parent].left = is;
3,522✔
510
                                else                                   boomlijst[s->parent].right = is;
1,968✔
511
                                if ( s->blnce < 0 ) { q->blnce = s->blnce = 0; p->blnce = 1; }
3,522✔
512
                                else if ( s->blnce > 0 ) { p->blnce = s->blnce = 0; q->blnce = -1; }
2,789✔
513
                                else { p->blnce = s->blnce = q->blnce = 0; }
2,025✔
514
                        }
515
                        break;
516
                }
517
                is = ip; ip = iq;
518
        }
519
        return(h);
520
}
521

522
/*
523
          #] InsTree : 
524
          #[ FindTree :
525

526
        Routines for balanced tree searching.
527
        Is like InsTree but without the insertions.
528
        Returns -1 if the element is not in the tree.
529
        The advantage of this routine over InsTree is that this routine
530
        can be run in parallel.
531
*/
532

533
int FindTree(int bufnum, WORD *subexpr)
5,471✔
534
{
535
        CBUF *C = cbuf + bufnum;
5,471✔
536
        COMPTREE *boomlijst = C->boomlijst, *q = boomlijst + C->rootnum, *p;
5,471✔
537
        WORD *v1, *v2, *v3;
5,471✔
538
        int ip, iq;
5,471✔
539

540
        ip = q->right;
5,471✔
541
        while ( ip >= 0 ) {
17,625✔
542
                p = boomlijst + ip;
17,180✔
543
                v1 = C->rhs[p->value]; v2 = v3 = subexpr;
17,180✔
544
                while ( *v3 ) v3 += *v3;  /* find the 0 that indicates end-of-expr */
34,360✔
545
                while ( *v1 == *v2 && v2 < v3 ) { v1++; v2++; }
256,005✔
546
                if ( *v1 > *v2 ) {
17,180✔
547
                        iq = p->right;
5,651✔
548
                        if ( iq >= 0 ) { ip = iq; }
5,651✔
549
                        else { return(-1); }
550
                }
551
                else if ( *v1 < *v2 ) {
11,529✔
552
                        iq = p->left;
6,686✔
553
                        if ( iq >= 0 ) { ip = iq; }
6,686✔
554
                        else { return(-1); }
555
                }
556
                else {
557
                        p->usage++;
4,843✔
558
                        return(p->value);
4,843✔
559
                }
560
        }
561
        return(-1);
562
}
563

564
/*
565
          #] FindTree : 
566
          #[ RedoTree :
567
*/
568

569
void RedoTree(CBUF *C, int size)
27,860✔
570
{
571
        COMPTREE *newboomlijst;
27,860✔
572
        int i;
27,860✔
573
        newboomlijst = (COMPTREE *)Malloc1((size+1)*sizeof(COMPTREE),"newboomlijst");
27,860✔
574
        if ( C->boomlijst ) {
27,860✔
575
                if ( C->MaxTreeSize > size ) C->MaxTreeSize = size;
246✔
576
                for ( i = 0; i < C->MaxTreeSize; i++ ) newboomlijst[i] = C->boomlijst[i];
199,071✔
577
                M_free(C->boomlijst,"boomlijst");
246✔
578
        }
579
        C->boomlijst = newboomlijst;
27,860✔
580
        C->MaxTreeSize = size;
27,860✔
581
}
27,860✔
582

583
/*
584
          #] RedoTree : 
585
          #[ ClearTree :
586
*/
587

588
void ClearTree(int i)
31,125✔
589
{
590
        CBUF *C = cbuf + i;
31,125✔
591
        COMPTREE *root = C->boomlijst;
31,125✔
592
        if ( root ) {
31,125✔
593
                C->numtree = 0;
31,125✔
594
                C->rootnum = 0;
31,125✔
595
                root->left = -1;                
31,125✔
596
                root->right = -1;
31,125✔
597
                root->parent = -1;
31,125✔
598
                root->blnce = 0;
31,125✔
599
                root->value = -1;
31,125✔
600
                root->usage = 0;
31,125✔
601
        }                
602
}
31,125✔
603

604
/*
605
          #] ClearTree : 
606
          #[ IniFbuffer :
607
*/
608
/**
609
 *        Initialize a factorization cache buffer.
610
 *        We set the size of the rhs and boomlijst buffers immediately
611
 *        to their final values.
612
 */
613

614
int IniFbuffer(WORD bufnum)
3,342✔
615
{
616
        CBUF *C = cbuf + bufnum;
3,342✔
617
        COMPTREE *root;
3,342✔
618
        int i;
3,342✔
619
        LONG fullsize;
3,342✔
620
        C->maxrhs = AM.fbuffersize;
3,342✔
621
        C->MaxTreeSize = AM.fbuffersize;
3,342✔
622

623
        /*
624
         * Note that bufnum is a return value of inicbufs(). So C has been already
625
         * initialized. (TU 20 Dec 2011)
626
         */
627
        if ( C->boomlijst ) M_free(C->boomlijst, "IniFbuffer-tree");
3,342✔
628
        if ( C->rhs ) M_free(C->rhs, "IniFbuffer-rhs");
3,342✔
629

630
        C->boomlijst = (COMPTREE *)Malloc1((C->MaxTreeSize+1)*sizeof(COMPTREE),"IniFbuffer-tree");
3,342✔
631
        root = C->boomlijst;
3,342✔
632
        C->numtree = 0;
3,342✔
633
        C->rootnum = 0;
3,342✔
634
        root->left = -1;                
3,342✔
635
        root->right = -1;
3,342✔
636
        root->parent = -1;
3,342✔
637
        root->blnce = 0;
3,342✔
638
        root->value = -1;
3,342✔
639
        root->usage = 0;
3,342✔
640
        for ( i = 1; i < C->MaxTreeSize; i++ ) { C->boomlijst[i] = comptreezero; }
3,428,892✔
641

642
        fullsize = (C->maxrhs+1) * (sizeof(WORD *) + 2*sizeof(LONG) + 2*sizeof(WORD));
3,342✔
643
        C->rhs = (WORD **)Malloc1(fullsize,"IniFbuffer-rhs");
3,342✔
644
        C->CanCommu = (LONG *)(C->rhs+C->maxrhs);
3,342✔
645
        C->NumTerms = (LONG *)(C->rhs+2*C->maxrhs);
3,342✔
646
        C->numdum = (WORD *)(C->NumTerms+C->maxrhs);
3,342✔
647
        C->dimension = (WORD *)(C->numdum+C->maxrhs);
3,342✔
648

649
        return(0);
3,342✔
650
}
651

652
/*
653
          #] IniFbuffer : 
654
          #[ numcommute :
655

656
        Returns the number of non-commuting terms in the expression
657
*/
658

659
LONG numcommute(WORD *terms, LONG *numterms)
629✔
660
{
661
        LONG num = 0;
629✔
662
        WORD *t, *m;
629✔
663
        *numterms = 0;
629✔
664
        while ( *terms ) {
6,075✔
665
                *numterms += 1;
5,446✔
666
                t = terms + 1;
5,446✔
667
                GETSTOP(terms,m);
5,446✔
668
                while ( t < m ) {
10,753✔
669
                        if ( *t >= FUNCTION ) {
5,307✔
670
                                if ( functions[*t-FUNCTION].commute ) { num++; break; }
328✔
671
                        }
672
                        t += t[1];
5,307✔
673
                }
674
                terms = terms + *terms;
5,446✔
675
        }
676
        return(num);
629✔
677
}
678

679
/*
680
          #] numcommute : 
681
*/
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc