![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to _distm.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / engine|
Return to _distm.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
1.2 noro 1: /*
2: * Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED
3: * All rights reserved.
4: *
5: * FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a limited,
6: * non-exclusive and royalty-free license to use, copy, modify and
7: * redistribute, solely for non-commercial and non-profit purposes, the
8: * computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
9: * conditions of this Agreement. For the avoidance of doubt, you acquire
10: * only a limited right to use the SOFTWARE hereunder, and FLL or any
11: * third party developer retains all rights, including but not limited to
12: * copyrights, in and to the SOFTWARE.
13: *
14: * (1) FLL does not grant you a license in any way for commercial
15: * purposes. You may use the SOFTWARE only for non-commercial and
16: * non-profit purposes only, such as academic, research and internal
17: * business use.
18: * (2) The SOFTWARE is protected by the Copyright Law of Japan and
19: * international copyright treaties. If you make copies of the SOFTWARE,
20: * with or without modification, as permitted hereunder, you shall affix
21: * to all such copies of the SOFTWARE the above copyright notice.
22: * (3) An explicit reference to this SOFTWARE and its copyright owner
23: * shall be made on your publication or presentation in any form of the
24: * results obtained by use of the SOFTWARE.
25: * (4) In the event that you modify the SOFTWARE, you shall notify FLL by
1.3 noro 26: * e-mail at risa-admin@sec.flab.fujitsu.co.jp of the detailed specification
1.2 noro 27: * for such modification or the source code of the modified part of the
28: * SOFTWARE.
29: *
30: * THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
31: * MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
32: * EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
33: * FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
34: * RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
35: * MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
36: * UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
37: * OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
38: * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
39: * DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
40: * ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
41: * FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
42: * DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
43: * SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
44: * OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
45: * DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
46: * PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
47: *
1.6 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/_distm.c,v 1.5 2000/12/05 06:59:16 noro Exp $
1.2 noro 49: */
1.1 noro 50: #include "ca.h"
51: #include "inline.h"
52:
53: extern int (*cmpdl)();
54: extern int do_weyl;
55:
1.5 noro 56: void dpto_dp();
1.1 noro 57: void _dptodp();
1.5 noro 58: void _adddl_dup();
1.4 noro 59: void adddl_destructive();
1.1 noro 60: void _mulmdm_dup();
61: void _free_dp();
62: void _comm_mulmd_dup();
63: void _weyl_mulmd_dup();
64: void _weyl_mulmmm_dup();
65: void _weyl_mulmdm_dup();
1.4 noro 66: void _comm_mulmd_tab();
67: void _comm_mulmd_tab_destructive();
1.1 noro 68:
69: MP _mp_free_list;
70: DP _dp_free_list;
71: DL _dl_free_list;
72: int current_dl_length;
1.6 ! noro 73:
! 74: void _free_private_storage()
! 75: {
! 76: _mp_free_list = 0;
! 77: _dp_free_list = 0;
! 78: _dl_free_list = 0;
! 79: GC_gcollect();
! 80: }
1.1 noro 81:
82: void _DL_alloc()
83: {
84: int *p;
85: int i,dl_len;
86: static int DL_alloc_count;
87:
88: /* fprintf(stderr,"DL_alloc : %d \n",++DL_alloc_count); */
89: dl_len = (current_dl_length+1);
90: p = (int *)GC_malloc(128*dl_len*sizeof(int));
91: for ( i = 0; i < 128; i++, p += dl_len ) {
92: *(DL *)p = _dl_free_list;
93: _dl_free_list = (DL)p;
94: }
95: }
96:
97: void _MP_alloc()
98: {
99: MP p;
100: int i;
101: static int MP_alloc_count;
102:
103: /* fprintf(stderr,"MP_alloc : %d \n",++MP_alloc_count); */
104: p = (MP)GC_malloc(1024*sizeof(struct oMP));
105: for ( i = 0; i < 1024; i++ ) {
106: p[i].next = _mp_free_list; _mp_free_list = &p[i];
107: }
108: }
109:
110: void _DP_alloc()
111: {
112: DP p;
113: int i;
114: static int DP_alloc_count;
115:
116: /* fprintf(stderr,"DP_alloc : %d \n",++DP_alloc_count); */
117: p = (DP)GC_malloc(1024*sizeof(struct oDP));
118: for ( i = 0; i < 1024; i++ ) {
119: p[i].body = (MP)_dp_free_list; _dp_free_list = &p[i];
120: }
121: }
122:
123: /* merge p1 and p2 into pr */
124:
125: void _addmd_destructive(mod,p1,p2,pr)
126: int mod;
127: DP p1,p2,*pr;
128: {
129: int n;
130: MP m1,m2,mr,mr0,s;
131: int t;
132:
133: if ( !p1 )
134: *pr = p2;
135: else if ( !p2 )
136: *pr = p1;
137: else {
138: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2), mr0 = 0; m1 && m2; )
139: switch ( (*cmpdl)(n,m1->dl,m2->dl) ) {
140: case 0:
141: t = (ITOS(C(m1))+ITOS(C(m2))) - mod;
142: if ( t < 0 )
143: t += mod;
144: s = m1; m1 = NEXT(m1);
145: if ( t ) {
146: _NEXTMP2(mr0,mr,s); C(mr) = STOI(t);
147: } else {
1.5 noro 148: _FREEDL(s->dl); _FREEMP(s);
1.1 noro 149: }
1.5 noro 150: s = m2; m2 = NEXT(m2); _FREEDL(s->dl); _FREEMP(s);
1.1 noro 151: break;
152: case 1:
153: s = m1; m1 = NEXT(m1); _NEXTMP2(mr0,mr,s);
154: break;
155: case -1:
156: s = m2; m2 = NEXT(m2); _NEXTMP2(mr0,mr,s);
157: break;
158: }
159: if ( !mr0 )
160: if ( m1 )
161: mr0 = m1;
162: else if ( m2 )
163: mr0 = m2;
164: else {
165: *pr = 0;
166: return;
167: }
168: else if ( m1 )
169: NEXT(mr) = m1;
170: else if ( m2 )
171: NEXT(mr) = m2;
172: else
173: NEXT(mr) = 0;
174: _MKDP(NV(p1),mr0,*pr);
175: if ( *pr )
176: (*pr)->sugar = MAX(p1->sugar,p2->sugar);
1.5 noro 177: _FREEDP(p1); _FREEDP(p2);
1.1 noro 178: }
179: }
180:
181: void _mulmd_dup(mod,p1,p2,pr)
182: int mod;
183: DP p1,p2,*pr;
184: {
185: if ( !do_weyl )
186: _comm_mulmd_dup(mod,p1,p2,pr);
187: else
188: _weyl_mulmd_dup(mod,p1,p2,pr);
189: }
190:
191: void _comm_mulmd_dup(mod,p1,p2,pr)
192: int mod;
193: DP p1,p2,*pr;
194: {
195: MP m;
196: DP s,t,u;
197: int i,l,l1;
198: static MP *w;
199: static int wlen;
200:
201: if ( !p1 || !p2 )
202: *pr = 0;
203: else {
204: for ( m = BDY(p1), l1 = 0; m; m = NEXT(m), l1++ );
205: for ( m = BDY(p2), l = 0; m; m = NEXT(m), l++ );
206: if ( l1 < l ) {
207: t = p1; p1 = p2; p2 = t;
208: l = l1;
209: }
210: if ( l > wlen ) {
211: if ( w ) GC_free(w);
212: w = (MP *)MALLOC(l*sizeof(MP));
213: wlen = l;
214: }
215: for ( m = BDY(p2), i = 0; i < l; m = NEXT(m), i++ )
216: w[i] = m;
217: for ( s = 0, i = l-1; i >= 0; i-- ) {
218: _mulmdm_dup(mod,p1,w[i],&t); _addmd_destructive(mod,s,t,&u); s = u;
219: }
220: bzero(w,l*sizeof(MP));
221: *pr = s;
222: }
223: }
224:
225: void _weyl_mulmd_dup(mod,p1,p2,pr)
226: int mod;
227: DP p1,p2,*pr;
228: {
229: MP m;
230: DP s,t,u;
231: int i,l,l1;
232: static MP *w;
233: static int wlen;
234:
235: if ( !p1 || !p2 )
236: *pr = 0;
237: else {
1.4 noro 238: for ( m = BDY(p1), l = 0; m; m = NEXT(m), l++ );
1.1 noro 239: if ( l > wlen ) {
240: if ( w ) GC_free(w);
241: w = (MP *)MALLOC(l*sizeof(MP));
242: wlen = l;
243: }
1.4 noro 244: for ( m = BDY(p1), i = 0; i < l; m = NEXT(m), i++ )
1.1 noro 245: w[i] = m;
246: for ( s = 0, i = l-1; i >= 0; i-- ) {
1.4 noro 247: _weyl_mulmdm_dup(mod,w[i],p2,&t); _addmd_destructive(mod,s,t,&u); s = u;
1.1 noro 248: }
249: bzero(w,l*sizeof(MP));
250: *pr = s;
251: }
252: }
253:
254: void _mulmdm_dup(mod,p,m0,pr)
255: int mod;
256: DP p;
257: MP m0;
258: DP *pr;
259: {
260: MP m,mr,mr0;
261: DL d,dt,dm;
262: int c,n,r,i;
263: int *pt,*p1,*p2;
264:
265: if ( !p )
266: *pr = 0;
267: else {
268: for ( mr0 = 0, m = BDY(p), c = ITOS(C(m0)), d = m0->dl, n = NV(p);
269: m; m = NEXT(m) ) {
270: _NEXTMP(mr0,mr);
271: C(mr) = STOI(dmar(ITOS(C(m)),c,0,mod));
272: _NEWDL_NOINIT(dt,n); mr->dl = dt;
273: dm = m->dl;
274: dt->td = d->td + dm->td;
275: for ( i = 0, pt = dt->d, p1=d->d, p2 = dm->d; i < n; i++ )
276: *pt++ = *p1++ + *p2++;
277: }
278: NEXT(mr) = 0; _MKDP(NV(p),mr0,*pr);
279: if ( *pr )
280: (*pr)->sugar = p->sugar + m0->dl->td;
281: }
282: }
283:
1.4 noro 284: void _weyl_mulmmm_dup_bug();
285:
286: void _weyl_mulmdm_dup(mod,m0,p,pr)
1.1 noro 287: int mod;
1.4 noro 288: MP m0;
1.1 noro 289: DP p;
290: DP *pr;
291: {
292: DP r,t,t1;
293: MP m;
1.4 noro 294: DL d0;
295: int n,n2,l,i,j,tlen;
296: static MP *w,*psum;
297: static struct cdlm *tab;
1.1 noro 298: static int wlen;
1.4 noro 299: static int rtlen;
1.1 noro 300:
301: if ( !p )
302: *pr = 0;
303: else {
304: for ( m = BDY(p), l = 0; m; m = NEXT(m), l++ );
305: if ( l > wlen ) {
306: if ( w ) GC_free(w);
307: w = (MP *)MALLOC(l*sizeof(MP));
308: wlen = l;
309: }
310: for ( m = BDY(p), i = 0; i < l; m = NEXT(m), i++ )
311: w[i] = m;
1.4 noro 312: n = NV(p); n2 = n>>1;
313: d0 = m0->dl;
314:
315: for ( i = 0, tlen = 1; i < n2; i++ )
316: tlen *= d0->d[n2+i]+1;
317: if ( tlen > rtlen ) {
318: if ( tab ) GC_free(tab);
319: if ( psum ) GC_free(psum);
320: rtlen = tlen;
321: tab = (struct cdlm *)MALLOC(rtlen*sizeof(struct cdlm));
322: psum = (MP *)MALLOC(rtlen*sizeof(MP));
1.1 noro 323: }
1.4 noro 324: bzero(psum,tlen*sizeof(MP));
325: for ( i = l-1; i >= 0; i-- ) {
326: bzero(tab,tlen*sizeof(struct cdlm));
327: _weyl_mulmmm_dup(mod,m0,w[i],n,tab,tlen);
328: for ( j = 0; j < tlen; j++ ) {
329: if ( tab[j].c ) {
330: _NEWMP(m); m->dl = tab[j].d;
331: C(m) = STOI(tab[j].c); NEXT(m) = psum[j];
332: psum[j] = m;
333: }
334: }
335: }
336: for ( j = tlen-1, r = 0; j >= 0; j-- )
337: if ( psum[j] ) {
338: _MKDP(n,psum[j],t); _addmd_destructive(mod,r,t,&t1); r = t1;
339: }
1.1 noro 340: if ( r )
341: r->sugar = p->sugar + m0->dl->td;
342: *pr = r;
343: }
344: }
1.4 noro 345:
1.1 noro 346: /* m0 = x0^d0*x1^d1*... * dx0^d(n/2)*dx1^d(n/2+1)*... */
347:
1.4 noro 348: void _weyl_mulmmm_dup(mod,m0,m1,n,rtab,rtablen)
1.1 noro 349: int mod;
350: MP m0,m1;
351: int n;
1.4 noro 352: struct cdlm *rtab;
353: int rtablen;
1.1 noro 354: {
355: MP m,mr,mr0;
356: DP r,t,t1;
357: int c,c0,c1,cc;
1.4 noro 358: DL d,d0,d1,dt;
359: int i,j,a,b,k,l,n2,s,min,h,curlen;
360: struct cdlm *p;
361: static int *ctab;
362: static struct cdlm *tab;
1.1 noro 363: static int tablen;
1.4 noro 364: static struct cdlm *tmptab;
365: static int tmptablen;
1.1 noro 366:
1.4 noro 367: if ( !m0 || !m1 ) {
368: rtab[0].c = 0;
369: rtab[0].d = 0;
370: return;
371: }
372: c0 = ITOS(C(m0)); c1 = ITOS(C(m1));
373: c = dmar(c0,c1,0,mod);
374: d0 = m0->dl; d1 = m1->dl;
375: n2 = n>>1;
376: curlen = 1;
377:
378: _NEWDL(d,n);
379: if ( n & 1 )
380: /* offset of h-degree */
381: d->td = d->d[n-1] = d0->d[n-1]+d1->d[n-1];
382: else
383: d->td = 0;
384: rtab[0].c = c;
385: rtab[0].d = d;
386:
387: if ( rtablen > tmptablen ) {
388: if ( tmptab ) GC_free(tmptab);
389: tmptab = (struct cdlm *)MALLOC(rtablen*sizeof(struct cdlm));
390: tmptablen = rtablen;
391: }
1.1 noro 392:
1.4 noro 393: for ( i = 0; i < n2; i++ ) {
394: a = d0->d[i]; b = d1->d[n2+i];
395: k = d0->d[n2+i]; l = d1->d[i];
396: if ( !k || !l ) {
397: a += l;
398: b += k;
399: s = a+b;
400: for ( j = 0, p = rtab; j < curlen; j++, p++ ) {
401: if ( p->c ) {
402: dt = p->d;
403: dt->d[i] = a;
404: dt->d[n2+i] = b;
405: dt->td += s;
406: }
407: }
408: curlen *= k+1;
409: continue;
410: }
411: if ( k+1 > tablen ) {
412: if ( tab ) GC_free(tab);
413: if ( ctab ) GC_free(ctab);
414: tablen = k+1;
415: tab = (struct cdlm *)MALLOC(tablen*sizeof(struct cdlm));
416: ctab = (int *)MALLOC(tablen*sizeof(int));
417: }
418: /* degree of xi^a*(Di^k*xi^l)*Di^b */
419: s = a+k+l+b;
420: /* compute xi^a*(Di^k*xi^l)*Di^b */
421: min = MIN(k,l);
422: mkwcm(k,l,mod,ctab);
423: bzero(tab,(k+1)*sizeof(struct cdlm));
424: /* n&1 != 0 => homogenized computation; dx-xd=h^2 */
1.1 noro 425: if ( n & 1 )
1.4 noro 426: for ( j = 0; j <= min; j++ ) {
427: _NEWDL(d,n);
428: d->d[i] = l-j+a; d->d[n2+i] = k-j+b;
429: d->td = s;
430: d->d[n-1] = s-(d->d[i]+d->d[n2+i]);
431: tab[j].d = d;
432: tab[j].c = ctab[j];
433: }
1.1 noro 434: else
1.4 noro 435: for ( j = 0; j <= min; j++ ) {
436: _NEWDL(d,n);
437: d->d[i] = l-j+a; d->d[n2+i] = k-j+b;
438: d->td = d->d[i]+d->d[n2+i]; /* XXX */
439: tab[j].d = d;
440: tab[j].c = ctab[j];
441: }
442: #if 0
443: _comm_mulmd_tab(mod,n,rtab,curlen,tab,k+1,tmptab);
444: for ( j = 0; j < curlen; j++ )
1.5 noro 445: if ( rtab[j].d ) { _FREEDL(rtab[j].d); }
1.4 noro 446: for ( j = 0; j <= min; j++ )
1.5 noro 447: if ( tab[j].d ) { _FREEDL(tab[j].d); }
1.4 noro 448: curlen *= k+1;
449: bcopy(tmptab,rtab,curlen*sizeof(struct cdlm));
450: #else
451: _comm_mulmd_tab_destructive(mod,n,rtab,curlen,tab,k+1);
452: for ( j = 0; j <= min; j++ )
1.5 noro 453: if ( tab[j].d ) { _FREEDL(tab[j].d); }
1.4 noro 454: curlen *= k+1;
455: #endif
456: }
457: }
458:
459: /* direct product of two cdlm tables
460: rt[] = [
461: t[0]*t1[0],...,t[n-1]*t1[0],
462: t[0]*t1[1],...,t[n-1]*t1[1],
463: ...
464: t[0]*t1[n1-1],...,t[n-1]*t1[n1-1]
465: ]
466: */
467:
468: void _comm_mulmd_tab(mod,nv,t,n,t1,n1,rt)
469: int mod;
470: int nv;
471: struct cdlm *t;
472: int n;
473: struct cdlm *t1;
474: int n1;
475: struct cdlm *rt;
476: {
477: int i,j;
478: struct cdlm *p;
479: int c;
480: DL d;
481:
482: bzero(rt,n*n1*sizeof(struct cdlm));
483: for ( j = 0, p = rt; j < n1; j++ ) {
484: c = t1[j].c;
485: d = t1[j].d;
486: if ( !c )
487: break;
488: for ( i = 0; i < n; i++, p++ ) {
489: if ( t[i].c ) {
490: p->c = dmar(t[i].c,c,0,mod);
1.5 noro 491: _adddl_dup(nv,t[i].d,d,&p->d);
1.4 noro 492: }
493: }
494: }
495: }
496:
497: void _comm_mulmd_tab_destructive(mod,nv,t,n,t1,n1)
498: int mod;
499: int nv;
500: struct cdlm *t;
501: int n;
502: struct cdlm *t1;
503: int n1;
504: {
505: int i,j;
506: struct cdlm *p;
507: int c;
508: DL d;
509:
510: for ( j = 1, p = t+n; j < n1; j++ ) {
511: c = t1[j].c;
512: d = t1[j].d;
513: if ( !c )
514: break;
515: for ( i = 0; i < n; i++, p++ ) {
516: if ( t[i].c ) {
517: p->c = dmar(t[i].c,c,0,mod);
1.5 noro 518: _adddl_dup(nv,t[i].d,d,&p->d);
1.1 noro 519: }
520: }
521: }
1.4 noro 522: c = t1[0].c;
523: d = t1[0].d;
524: for ( i = 0, p = t; i < n; i++, p++ )
525: if ( t[i].c ) {
526: p->c = dmar(t[i].c,c,0,mod);
527: /* t[i].d += d */
528: adddl_destructive(nv,t[i].d,d);
529: }
1.1 noro 530: }
531:
1.5 noro 532: void dlto_dl(d,dr)
533: DL d;
534: DL *dr;
1.1 noro 535: {
536: int i,n;
1.5 noro 537: DL t;
1.1 noro 538:
1.5 noro 539: n = current_dl_length;
540: _NEWDL(t,n); *dr = t;
541: t->td = d->td;
1.1 noro 542: for ( i = 0; i < n; i++ )
1.5 noro 543: t->d[i] = d->d[i];
1.1 noro 544: }
545:
546: void _dltodl(d,dr)
547: DL d;
548: DL *dr;
549: {
550: int i,n;
551: DL t;
552:
553: n = current_dl_length;
554: NEWDL(t,n); *dr = t;
555: t->td = d->td;
556: for ( i = 0; i < n; i++ )
557: t->d[i] = d->d[i];
558: }
559:
1.5 noro 560: void _adddl_dup(n,d1,d2,dr)
1.1 noro 561: int n;
562: DL d1,d2;
563: DL *dr;
564: {
565: DL dt;
566: int i;
567:
1.4 noro 568: _NEWDL(dt,n);
569: *dr = dt;
1.1 noro 570: dt->td = d1->td + d2->td;
571: for ( i = 0; i < n; i++ )
572: dt->d[i] = d1->d[i]+d2->d[i];
1.4 noro 573: }
574:
575: void _free_dlarray(a,n)
576: DL *a;
577: int n;
578: {
579: int i;
580:
1.5 noro 581: for ( i = 0; i < n; i++ ) { _FREEDL(a[i]); }
1.1 noro 582: }
583:
584: void _free_dp(f)
585: DP f;
586: {
587: MP m,s;
588:
589: if ( !f )
590: return;
591: m = f->body;
592: while ( m ) {
1.5 noro 593: s = m; m = NEXT(m); _FREEDL(s->dl); _FREEMP(s);
594: }
595: _FREEDP(f);
596: }
597:
598: void dpto_dp(p,r)
599: DP p;
600: DP *r;
601: {
602: MP m,mr0,mr;
603:
604: if ( !p )
605: *r = 0;
606: else {
607: current_dl_length = NV(p);
608: for ( m = BDY(p), mr0 = 0; m; m = NEXT(m) ) {
609: _NEXTMP(mr0,mr);
610: dlto_dl(m->dl,&mr->dl);
611: mr->c = m->c;
612: }
613: NEXT(mr) = 0;
614: _MKDP(p->nv,mr0,*r);
615: (*r)->sugar = p->sugar;
1.1 noro 616: }
617: }
618:
619: void _dptodp(p,r)
620: DP p;
621: DP *r;
622: {
623: MP m,mr0,mr;
624:
625: if ( !p )
626: *r = 0;
627: else {
628: for ( m = BDY(p), mr0 = 0; m; m = NEXT(m) ) {
629: NEXTMP(mr0,mr);
630: _dltodl(m->dl,&mr->dl);
631: mr->c = m->c;
632: }
633: NEXT(mr) = 0;
634: MKDP(p->nv,mr0,*r);
635: (*r)->sugar = p->sugar;
636: }
637: }
638:
1.5 noro 639: /*
640: * destructive merge of two list
641: *
642: * p1, p2 : list of DL
643: * return : a merged list
644: */
645:
646: NODE _symb_merge(m1,m2,n)
647: NODE m1,m2;
648: int n;
649: {
650: NODE top,prev,cur,m,t;
651:
652: if ( !m1 )
653: return m2;
654: else if ( !m2 )
655: return m1;
656: else {
657: switch ( (*cmpdl)(n,(DL)BDY(m1),(DL)BDY(m2)) ) {
658: case 0:
659: top = m1; _FREEDL((DL)BDY(m2)); m = NEXT(m2);
660: break;
661: case 1:
662: top = m1; m = m2;
663: break;
664: case -1:
665: top = m2; m = m1;
1.1 noro 666: break;
667: }
1.5 noro 668: prev = top; cur = NEXT(top);
669: /* BDY(prev) > BDY(m) always holds */
670: while ( cur && m ) {
671: switch ( (*cmpdl)(n,(DL)BDY(cur),(DL)BDY(m)) ) {
672: case 0:
673: _FREEDL(BDY(m)); m = NEXT(m);
674: prev = cur; cur = NEXT(cur);
675: break;
676: case 1:
677: t = NEXT(cur); NEXT(cur) = m; m = t;
678: prev = cur; cur = NEXT(cur);
679: break;
680: case -1:
681: NEXT(prev) = m; m = cur;
682: prev = NEXT(prev); cur = NEXT(prev);
683: break;
1.1 noro 684: }
685: }
1.5 noro 686: if ( !cur )
687: NEXT(prev) = m;
688: return top;
1.1 noro 689: }
690: }