Main Page Source Files Class Hierarchy Alphabetical List Compound List Compound Members File Members Related Pages Search for 

libsrc/recombine.cxx File Reference

??? More...

#include <memory.h>
#include "udanax.h"

Include dependency graph for recombine.cxx:

Include dependency graph

Go to the source code of this file.

Functions

void takeovernephewsseq (typecorecrum *me)
 ???

void eatbrossubtreeseq (typecuc *me)
 ???

void fixdspsofbroschildren (typecuc *me, typecuc *bro)
 ???

void eatbrossubtreend (typecuc *me, typecuc *bro)
 ???

void takenephewnd (typecuc *me, typecuc *nephew)
 ???

void shellsort (typecorecrum *v[], int n)
 ???

void getorderedsons (typecuc *father, typecorecrum *sons[])
 ???

bool takeovernephewsnd (typecuc **meptr, typecuc **broptr)
 ???

void recombineseq (typecuc *father)
 ???

void recombinend (typecuc *father)
 ???

void recombine (typecuc *father)
 ???

bool randomness (float probability)
 ???

bool ishouldbother (typecuc *dest, typecuc *src)
 ???

int comparecrumsdiagonally (typecorecrum *a, typecorecrum *b)
 ???

void fixincoresubtreewids (typecuc *ptr)
 ???


Variables

long noishouldbother = 0
long notakenephewnd = 0
long noeatbrosnd = 0

Detailed Description

???

(to be defined)

Definition in file recombine.cxx.

Function Documentation

int comparecrumsdiagonally (  typecorecrum *  a,
typecorecrum *  b
) 
 

???

(to be defined)

Definition at line 503 of file recombine.cxx.

References typecorecrumhedr::cdsp, typewid::dsas, tumbleradd, tumblercmp(), and typecorecrum.

Referenced by splitcrumsp(). 

00506 {
00507     Tumbler amagnitude, bmagnitude;
00508 
00509     tumbleradd(&a->cdsp.dsas[0], &a->cdsp.dsas[1], &amagnitude);
00510     tumbleradd(&b->cdsp.dsas[0], &b->cdsp.dsas[1], &bmagnitude);
00511     return (tumblercmp(&amagnitude, &bmagnitude));
00512 }

void eatbrossubtreend (  typecuc *  me,
typecuc *  bro
)  [static]
 

???

(to be defined)

Definition at line 170 of file recombine.cxx.

References typecuc::cdsp, clear, disown(), findfather(), findleftson(), findrightbro, fixdspsofbroschildren(), freecrum(), getleftson(), getrightmostbro(), ivemodified(), typecorecrumhedr::leftbroorfather, typecuc::leftson, makeroomonleftnd(), noeatbrosnd, typecuc::numberofsons, rejuvinate, reserve(), typecorecrumhedr::rightbro, setwisp(), setwispupwards(), typecorecrum, and typedsp.

Referenced by takeovernephewsnd(). 

00173 {
00174     typedsp offset, grasp;
00175     typecuc *oldfather;
00176     typecorecrum *son;
00177 
00178     ++noeatbrosnd;
00179     reserve((typecorecrum *) bro);
00180     clear(&offset, sizeof(offset));
00181 /* L("in eatbrossubtreend calling makeroom onleftnd \n"); */
00182     makeroomonleftnd(me, &offset, &bro->cdsp, &grasp);
00183     fixdspsofbroschildren(me, bro);
00184     getleftson(bro)->leftbroorfather = getrightmostbro(getleftson(me));
00185     getrightmostbro(getleftson(me))->rightbro = getleftson(bro);
00186     bro->leftson->isleftmost = false;
00187 
00188     me->numberofsons += bro->numberofsons;
00189     for (son = findleftson(me); son; son = findrightbro(son))
00190         setwisp(son);
00191 
00192     oldfather = (typecuc *) findfather((typecorecrum *) bro);
00193     rejuvinate((typecorecrum *) bro);
00194     disown((typecorecrum *) bro);
00195     freecrum((typecorecrum *) bro);
00196     setwispupwards(me, 0);
00197     setwispupwards(oldfather, 1);
00198     ivemodified((typecorecrum *) me);
00199 /* fixincoresubtreewids(me); */
00200 }

void eatbrossubtreeseq (  typecuc *  me  )  [static]
 

???

(to be defined)

Definition at line 125 of file recombine.cxx.

References disown(), freecrum(), getleftson(), getrightbro, getrightmostbro(), typecorecrumhedr::leftbroorfather, typecuc::leftson, typecuc::numberofsons, typecorecrumhedr::rightbro, setwispupwards(), and typecorecrum.

Referenced by recombineseq(). 

00127 {
00128     typecuc *bro;
00129 
00130     bro = (typecuc *) getrightbro((typecorecrum *) me);
00131     getleftson(bro)->leftbroorfather = getrightmostbro(getleftson(me));
00132     getrightmostbro(getleftson(me))->rightbro = bro->leftson;
00133     bro->leftson->isleftmost = false;
00134 
00135     me->numberofsons += bro->numberofsons;
00136     disown((typecorecrum *) bro);
00137     freecrum((typecorecrum *) bro);
00138     setwispupwards(me, 1);
00139 }

void fixdspsofbroschildren (  typecuc *  me,
typecuc *  bro
)  [static]
 

???

(to be defined)

Definition at line 149 of file recombine.cxx.

References typecorecrumhedr::cdsp, typecuc::cdsp, typecuc::cenftype, dspadd(), dspsub(), getleftson(), getrightbro, ivemodified(), and typecorecrum.

Referenced by eatbrossubtreend(). 

00152 {
00153     typecorecrum *nephew;
00154 
00155     for (nephew = getleftson(bro); nephew; nephew = (typecorecrum *) getrightbro(nephew)) {
00156         dspadd(&bro->cdsp, &nephew->cdsp, &nephew->cdsp, me->cenftype);
00157         dspsub(&nephew->cdsp, &me->cdsp, &nephew->cdsp, me->cenftype);
00158         ivemodified(nephew);
00159     }
00160 }

void fixincoresubtreewids (  typecuc *  ptr  ) 
 

???

(to be defined)

Definition at line 522 of file recombine.cxx.

References getleftson(), getrightbro, typecuc::height, L, setwisp(), and typecorecrum.

Referenced by rearrangend(). 

00524 {
00525     typecorecrum *son;
00526 
00527     if (ptr->height == 0)
00528         return;
00529 
00530     for (son = (typecorecrum *) getleftson(ptr); son; son = (typecorecrum *) getrightbro(son))
00531         fixincoresubtreewids((typecuc *) son);
00532 
00533     if (setwisp((typecorecrum *) ptr)) {
00534 #ifndef DISTRIBUTION
00535         L("fixing %x \n", (int) ptr);
00536 #endif
00537     }
00538 }

void getorderedsons (  typecuc *  father,
typecorecrum *  sons[]
)  [static]
 

???

(to be defined)

Definition at line 283 of file recombine.cxx.

References getleftson(), getrightbro, NULL, shellsort(), and typecorecrum.

Referenced by recombinend(), and takeovernephewsnd(). 

00286 {
00287     typecorecrum *ptr;
00288     int i;
00289 
00290     sons[0] = NULL;
00291     for (ptr = getleftson(father), i = 0; ptr; ptr = (typecorecrum *) getrightbro(ptr))
00292         sons[i++] = ptr;
00293     sons[i] = NULL;
00294     shellsort(sons, i);
00295 }

bool ishouldbother (  typecuc *  dest,
typecuc *  src
) 
 

???

(to be defined)

Definition at line 476 of file recombine.cxx.

References typecuc::age, check(), typediskloafptr::diskblocknumber, DISKPTRNULL, typecuc::height, MAX2DBCINLOAF, MAXUCINLOAF, noishouldbother, typecuc::numberofsons, randomness(), RESERVED, and typecuc::sonorigin.

Referenced by recombinend(). 

00479 {
00480     ++noishouldbother;
00481 
00482     if (src->numberofsons == 0) {
00483         if (src->sonorigin.diskblocknumber == DISKPTRNULL)
00484             check(src);
00485         else
00486             return false;
00487     }
00488 
00489     if (dest->age == RESERVED || src->age == RESERVED)
00490         return false;
00491 
00492     return dest->numberofsons + src->numberofsons <= (dest->height > 1 ? MAXUCINLOAF : MAX2DBCINLOAF) && randomness(.3);
00493 }

bool randomness (  float  probability  )  [static]
 

???

(to be defined)

Definition at line 457 of file recombine.cxx.

Referenced by ishouldbother(). 

00459 {
00460     //UNUSED static float i = 0;
00461 
00462     return true;
00463 /* 
00464  * i += probability; if(i>=1.){ while (i>1){ i -= 1.; } return(true); }else{
00465  * return false; } */
00466 }

void recombine (  typecuc *  father  ) 
 

???

(to be defined)

Definition at line 439 of file recombine.cxx.

References typecuc::cenftype, GRAN, POOM, recombinend(), recombineseq(), and SPAN.

Referenced by deletend(), insertnd(), insertseq(), and rearrangend(). 

00441 {
00442     switch (father->cenftype) {
00443     case GRAN:  recombineseq(father);   break;
00444     case SPAN:  recombinend(father);    break;
00445     case POOM:  recombinend(father);    break;
00446     }
00447 }

void recombinend (  typecuc *  father  )  [static]
 

???

(to be defined)

Definition at line 402 of file recombine.cxx.

References getleftson(), getorderedsons(), getrightbro, typecuc::height, ishouldbother(), levelpull(), MAXUCINLOAF, typecuc::numberofsons, takeovernephewsnd(), and typecorecrum.

Referenced by recombine(). 

00404 {
00405 
00406     typecorecrum *ptr;
00407     typecorecrum *sons[MAXUCINLOAF];
00408     int i, j, n;
00409 
00410     if (father->height < 2 || !father->modified)
00411         return;
00412 
00413     for (ptr = getleftson(father); ptr; ptr = (typecorecrum *) getrightbro(ptr))
00414         recombinend((typecuc *) ptr);
00415 
00416     getorderedsons(father, sons);
00417     n = father->numberofsons;
00418     for (i = 0; i < n - 1; i++) {
00419         for (j = i + 1; sons[i] && j < n; j++) {
00420             if (i != j && sons[j] && ishouldbother((typecuc *) sons[i], (typecuc *) sons[j])) {
00421                 takeovernephewsnd((typecuc **) &sons[i], (typecuc **) &sons[j]);
00422 /* break; */
00423 /* break;//zzz6/16/84 reg// */
00424             }
00425         }
00426     }
00427     if (father->isapex)
00428         levelpull(father);
00429 }

void recombineseq (  typecuc *  father  )  [static]
 

???

(to be defined)

zzz reg 1999 this recombines too much

Definition at line 356 of file recombine.cxx.

References typecuc::age, eatbrossubtreeseq(), getleftson(), typecuc::height, typecuc::leftson, levelpull(), macrogetrightbro, MAXUCINLOAF, typecuc::numberofsons, RESERVED, typecuc::rightbro, roomformoresons(), takeovernephewsseq(), and typecorecrum.

Referenced by recombine(). 

00358 {
00360     typecuc *ptr;
00361 
00362     if (father->height < 3 || !father->modified)
00363         return;
00364 
00365     if (!roomformoresons(father))
00366         return;
00367 
00368     for (ptr = (typecuc *) getleftson(father); ptr; ptr = (typecuc *) macrogetrightbro((typecorecrum *) ptr))
00369         recombineseq(ptr);
00370 
00371     for (ptr = (typecuc *) getleftson(father); ptr && ptr->rightbro; ptr = (typecuc *) macrogetrightbro((typecorecrum *) ptr)) {
00372         if (ptr->age == RESERVED)
00373             continue;
00374 
00375         if (ptr->leftson && roomformoresons(ptr)) {
00376 /* if (ptr->leftson && toofewsons (ptr)) {* */
00377             if (((typecuc *) ptr->rightbro)->leftson) {
00378                 if (ptr->numberofsons + ((typecuc *) ptr->rightbro)->numberofsons <= MAXUCINLOAF) {
00379                     eatbrossubtreeseq(ptr);
00380                     break;
00381                 } else {
00382                     takeovernephewsseq((typecorecrum *) ptr);
00383                     break;
00384                 }
00385             }
00386         }
00387     }
00388     if (father->isapex)
00389         levelpull(father);
00390 }

void shellsort (  typecorecrum *  v[],
int  n
)  [static]
 

???

(to be defined)

Definition at line 246 of file recombine.cxx.

References assert, typecorecrumhedr::cdsp, typewid::dsas, GREATER, tumbleradd, tumblercmp(), and typecorecrum.

Referenced by getorderedsons(). 

00249 {
00250     typecorecrum *temp;
00251     int gap, i, j;
00252 
00253     Tumbler tarray[100], *tarrayp[100], *temptp;
00254 
00255     if (n > 100)
00256         assert(0); // fatal error in shellsort in be under recombine - n > 100
00257 
00258     for (i = 0; i < n; i++) {          /* build up a list of sumps of disp[0] and dsp[1] */
00259 /* for compare crums diagonally hack */
00260         tumbleradd(&v[i]->cdsp.dsas[0], &v[i]->cdsp.dsas[1], &tarray[i]);
00261         tarrayp[i] = &tarray[i];
00262     }
00263     for (gap = n / 2; gap > 0; gap /= 2)
00264         for (i = gap; i < n; i++)
00265             for (j = i - gap; j >= 0 && tumblercmp(tarrayp[j], tarrayp[j + gap]) == GREATER; j -= gap) {
00266                 temp = v[j];
00267                 temptp = tarrayp[j];
00268                 v[j] = v[j + gap];
00269                 tarrayp[j] = tarrayp[j + gap];
00270                 v[j + gap] = temp;
00271                 tarrayp[j + gap] = temptp;
00272             }
00273 }

void takenephewnd (  typecuc *  me,
typecuc *  nephew
)  [static]
 

???

(to be defined)

Definition at line 210 of file recombine.cxx.

References adopt(), typecorecrumhedr::cdsp, typecuc::cdsp, typecuc::cenftype, disown(), dspadd(), dspsub(), freecrum(), getfather(), ivemodified(), makeroomonleftnd(), notakenephewnd, NULL, typecuc::numberofsons, prologuend(), RIGHTMOSTSON, setwispupwards(), typecorecrum, and typedsp.

Referenced by takeovernephewsnd(). 

00213 {
00214     typedsp nephewsgrasp, grasp, offset;
00215 
00216     ++notakenephewnd;
00217 
00218     typecuc *bro = (typecuc *) getfather((typecorecrum *) nephew);
00219     disown((typecorecrum *) nephew);
00220     dspadd(&bro->cdsp, &nephew->cdsp, &nephew->cdsp, bro->cenftype);
00221     adopt((typecorecrum *) nephew, RIGHTMOSTSON, (typecorecrum *) me);
00222     prologuend((typecorecrum *) nephew, &bro->cdsp, &nephewsgrasp, (typedsp *) NULL);
00223 /* L("in takenephewnd calling makeroomnd \n"); */
00224     makeroomonleftnd(me, &offset, &nephew->cdsp, &grasp);
00225     dspsub(&nephew->cdsp, &me->cdsp, &nephew->cdsp, me->cenftype);
00226 
00227     if (!bro->numberofsons) {
00228         disown((typecorecrum *) bro);
00229         freecrum((typecorecrum *) bro);
00230     } else {
00231         setwispupwards(bro, 0);
00232     }
00233 
00234     ivemodified((typecorecrum *) nephew);
00235     setwispupwards(me, 1);
00236 }

bool takeovernephewsnd (  typecuc **  meptr,
typecuc **  broptr
)  [static]
 

???

(to be defined)

Definition at line 305 of file recombine.cxx.

References disown(), eatbrossubtreend(), findleftson(), freecrum(), getorderedsons(), typecuc::leftson, MAXUCINLOAF, NULL, typecuc::numberofsons, roomformoresons(), setwispupwards(), takenephewnd(), and typecorecrum.

Referenced by recombinend(). 

00308 {
00309     typecorecrum *sons[MAXUCINLOAF], *ptr;
00310     int i, n;
00311 
00312     typecuc *me  = *meptr;
00313     typecuc *bro = *broptr;
00314 
00315     if (!me->leftson || !bro->leftson)
00316         return false;
00317 
00318     bool ret = false;
00319     if (me->numberofsons + bro->numberofsons <= MAXUCINLOAF) {
00320         eatbrossubtreend(me, bro);
00321         *broptr = NULL;
00322         return true;
00323 
00324     } else {
00325         getorderedsons(bro, sons);
00326         findleftson(bro);              /* to make sure its in core zzzz */
00327         n = bro->numberofsons;
00328         for (i = 0; i < n && roomformoresons(me); i++) {
00329             ptr = sons[i];
00330             takenephewnd(me, (typecuc *) ptr);
00331 /* fixincoresubtreewids(me); */
00332             ret = true;
00333         }
00334     }
00335 
00336     if (bro->numberofsons)
00337         setwispupwards(bro, 0);
00338     else {
00339         disown((typecorecrum *) bro);
00340         freecrum((typecorecrum *) bro);
00341         *broptr = NULL;
00342     }
00343 
00344     setwispupwards(me, 1);
00345     return ret;
00346 }

void takeovernephewsseq (  typecorecrum *  me  )  [static]
 

???

(to be defined)

Definition at line 99 of file recombine.cxx.

References adopt(), typecuc::age, disown(), getleftson(), getrightbro, ivemodified(), RESERVED, RIGHTMOSTSON, roomformoresons(), routinegetrightbro(), setwispupwards(), and typecorecrum.

Referenced by recombineseq(). 

00101 {
00102     typecuc *ptr;
00103     typecorecrum *next;
00104 
00105     for (ptr = (typecuc *) getleftson((typecuc *) routinegetrightbro(me)); ptr && roomformoresons((typecuc *) me); ptr = (typecuc *) next) {
00106         next = (typecorecrum *) routinegetrightbro((typecorecrum *) ptr);
00107         if (ptr->age == RESERVED)
00108             continue;
00109         disown((typecorecrum *) ptr);
00110         adopt((typecorecrum *) ptr, RIGHTMOSTSON, me);
00111         ivemodified((typecorecrum *) ptr);
00112     }
00113     setwispupwards((typecuc *) getrightbro(me), 0);
00114     setwispupwards((typecuc *) me, 1);
00115 }

Variable Documentation

long noeatbrosnd = 0
 

Definition at line 87 of file recombine.cxx.

Referenced by eatbrossubtreend().

long noishouldbother = 0
 

Definition at line 85 of file recombine.cxx.

Referenced by ishouldbother().

long notakenephewnd = 0
 

Definition at line 86 of file recombine.cxx.

Referenced by takenephewnd().

Generated on Sun Aug 21 04:18:35 2005 for Udanax-Green by doxygen1.3.4