Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/recombine.cxx

Go to the documentation of this file.

/**********************************************************************
 * Copyright 2002 Jeff Rush <jrush@taupro.com>
 * Original Copyright 1979-2002 Udanax.com
 *
 * This file is part of the Udanax xanalogical storage system.
 *
 * Udanax is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Udanax is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Udanax; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 **********************************************************************/

/* Modification History:
 * $Log: recombine.cxx,v $
 * Revision 1.11  2004/09/11 13:59:21  jrush
 * Changed all fprintf's to stderr to use the Nana library L() macro.  Also
 * removed a 2-3 minor compiler warnings.
 *
 * Revision 1.10  2004/09/04 16:02:18  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.9  2002/07/26 04:32:01  jrush
 * Replaced gerror() with assert()
 *
 * Revision 1.8  2002/05/28 04:22:29  jrush
 * Adjusted source files to comply with GPL licensing.
 *
 * Revision 1.7  2002/05/28 02:52:23  jrush
 * Made static any functions and global variables private to this source file
 * and commented out any unused functions.
 *
 * Revision 1.6  2002/04/12 11:56:43  jrush
 * Reorganized include file layout, renamed xanadu.h to udanax.h and
 * typecontext/typecrumcontext to C++ class Context/CrumContext.
 *
 * Revision 1.5  2002/04/09 21:45:46  jrush
 * Renamed class 'tumbler' to 'Tumbler', for consistency with Python sources,
 * and changed typeisa from typedef to a subclass, in preparation for cleaning
 * up the type/class tree.
 *
 * Revision 1.4  2002/04/06 19:51:30  jrush
 * Renamed TRUE/FALSE constant use to the C++ standard of true/false.
 *
 * Revision 1.3  2002/04/06 15:01:17  jrush
 * Changed INT to just 'int'.
 *
 * Revision 1.2  2002/02/14 09:27:43  jrush
 * Cleaned up source:
 *
 * 1. ran thru the indent tool to achieve a standard look,
 * 2. added structured comments at top for use with DOxygen reporting
 *    as well as CVS keywords,
 * 3. fixed compiler warnings re ambiguous assign/compares,
 *    needed casts and unused/uninitialized variables,
 * 4. fixed funcs that didn't specify a return type,
 * 5. centralized prototypes in protos.h, removing incomplete ones,
 * 6. cleaned up use of bool/BOOLEAN type to suit C++ type,
 * 7. fixed initializer nesting in tumbler constants,
 * 8. renamed vars that conflict with C++ keywords (new, this),
 * 9. fixed global/extern confusion re some global vars.
 *
 */

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

// Globals used by corediskout.cxx only
long noishouldbother = 0;
long notakenephewnd  = 0;
long noeatbrosnd     = 0;

/* GRANfilade recombine */

    static void
takeovernephewsseq(
    typecorecrum *me)
{
    typecuc *ptr;
    typecorecrum *next;

    for (ptr = (typecuc *) getleftson((typecuc *) routinegetrightbro(me)); ptr && roomformoresons((typecuc *) me); ptr = (typecuc *) next) {
        next = (typecorecrum *) routinegetrightbro((typecorecrum *) ptr);
        if (ptr->age == RESERVED)
            continue;
        disown((typecorecrum *) ptr);
        adopt((typecorecrum *) ptr, RIGHTMOSTSON, me);
        ivemodified((typecorecrum *) ptr);
    }
    setwispupwards((typecuc *) getrightbro(me), 0);
    setwispupwards((typecuc *) me, 1);
}

    static void
eatbrossubtreeseq(
    typecuc *me)
{
    typecuc *bro;

    bro = (typecuc *) getrightbro((typecorecrum *) me);
    getleftson(bro)->leftbroorfather = getrightmostbro(getleftson(me));
    getrightmostbro(getleftson(me))->rightbro = bro->leftson;
    bro->leftson->isleftmost = false;

    me->numberofsons += bro->numberofsons;
    disown((typecorecrum *) bro);
    freecrum((typecorecrum *) bro);
    setwispupwards(me, 1);
}

    static void
fixdspsofbroschildren(
    typecuc *me,
    typecuc *bro)
{
    typecorecrum *nephew;

    for (nephew = getleftson(bro); nephew; nephew = (typecorecrum *) getrightbro(nephew)) {
        dspadd(&bro->cdsp, &nephew->cdsp, &nephew->cdsp, me->cenftype);
        dspsub(&nephew->cdsp, &me->cdsp, &nephew->cdsp, me->cenftype);
        ivemodified(nephew);
    }
}

    static void
eatbrossubtreend(
    typecuc *me,
    typecuc *bro)
{
    typedsp offset, grasp;
    typecuc *oldfather;
    typecorecrum *son;

    ++noeatbrosnd;
    reserve((typecorecrum *) bro);
    clear(&offset, sizeof(offset));
/* L("in eatbrossubtreend calling makeroom onleftnd \n"); */
    makeroomonleftnd(me, &offset, &bro->cdsp, &grasp);
    fixdspsofbroschildren(me, bro);
    getleftson(bro)->leftbroorfather = getrightmostbro(getleftson(me));
    getrightmostbro(getleftson(me))->rightbro = getleftson(bro);
    bro->leftson->isleftmost = false;

    me->numberofsons += bro->numberofsons;
    for (son = findleftson(me); son; son = findrightbro(son))
        setwisp(son);

    oldfather = (typecuc *) findfather((typecorecrum *) bro);
    rejuvinate((typecorecrum *) bro);
    disown((typecorecrum *) bro);
    freecrum((typecorecrum *) bro);
    setwispupwards(me, 0);
    setwispupwards(oldfather, 1);
    ivemodified((typecorecrum *) me);
/* fixincoresubtreewids(me); */
}

    static void
takenephewnd(
    typecuc *me,
    typecuc *nephew)
{
    typedsp nephewsgrasp, grasp, offset;

    ++notakenephewnd;

    typecuc *bro = (typecuc *) getfather((typecorecrum *) nephew);
    disown((typecorecrum *) nephew);
    dspadd(&bro->cdsp, &nephew->cdsp, &nephew->cdsp, bro->cenftype);
    adopt((typecorecrum *) nephew, RIGHTMOSTSON, (typecorecrum *) me);
    prologuend((typecorecrum *) nephew, &bro->cdsp, &nephewsgrasp, (typedsp *) NULL);
/* L("in takenephewnd calling makeroomnd \n"); */
    makeroomonleftnd(me, &offset, &nephew->cdsp, &grasp);
    dspsub(&nephew->cdsp, &me->cdsp, &nephew->cdsp, me->cenftype);

    if (!bro->numberofsons) {
        disown((typecorecrum *) bro);
        freecrum((typecorecrum *) bro);
    } else {
        setwispupwards(bro, 0);
    }

    ivemodified((typecorecrum *) nephew);
    setwispupwards(me, 1);
}

    static void
shellsort(
    typecorecrum *v[],
    int           n)
{
    typecorecrum *temp;
    int gap, i, j;

    Tumbler tarray[100], *tarrayp[100], *temptp;

    if (n > 100)
        assert(0); // fatal error in shellsort in be under recombine - n > 100

    for (i = 0; i < n; i++) {          /* build up a list of sumps of disp[0] and dsp[1] */
/* for compare crums diagonally hack */
        tumbleradd(&v[i]->cdsp.dsas[0], &v[i]->cdsp.dsas[1], &tarray[i]);
        tarrayp[i] = &tarray[i];
    }
    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && tumblercmp(tarrayp[j], tarrayp[j + gap]) == GREATER; j -= gap) {
                temp = v[j];
                temptp = tarrayp[j];
                v[j] = v[j + gap];
                tarrayp[j] = tarrayp[j + gap];
                v[j + gap] = temp;
                tarrayp[j + gap] = temptp;
            }
}

    static void
getorderedsons(
    typecuc      *father,
    typecorecrum *sons[])
{
    typecorecrum *ptr;
    int i;

    sons[0] = NULL;
    for (ptr = getleftson(father), i = 0; ptr; ptr = (typecorecrum *) getrightbro(ptr))
        sons[i++] = ptr;
    sons[i] = NULL;
    shellsort(sons, i);
}

    static bool
takeovernephewsnd(
    typecuc **meptr,
    typecuc **broptr)
{
    typecorecrum *sons[MAXUCINLOAF], *ptr;
    int i, n;

    typecuc *me  = *meptr;
    typecuc *bro = *broptr;

    if (!me->leftson || !bro->leftson)
        return false;

    bool ret = false;
    if (me->numberofsons + bro->numberofsons <= MAXUCINLOAF) {
        eatbrossubtreend(me, bro);
        *broptr = NULL;
        return true;

    } else {
        getorderedsons(bro, sons);
        findleftson(bro);              /* to make sure its in core zzzz */
        n = bro->numberofsons;
        for (i = 0; i < n && roomformoresons(me); i++) {
            ptr = sons[i];
            takenephewnd(me, (typecuc *) ptr);
/* fixincoresubtreewids(me); */
            ret = true;
        }
    }

    if (bro->numberofsons)
        setwispupwards(bro, 0);
    else {
        disown((typecorecrum *) bro);
        freecrum((typecorecrum *) bro);
        *broptr = NULL;
    }

    setwispupwards(me, 1);
    return ret;
}

    static void
recombineseq(
    typecuc *father)
{
    typecuc *ptr;

    if (father->height < 3 || !father->modified)
        return;

    if (!roomformoresons(father))
        return;

    for (ptr = (typecuc *) getleftson(father); ptr; ptr = (typecuc *) macrogetrightbro((typecorecrum *) ptr))
        recombineseq(ptr);

    for (ptr = (typecuc *) getleftson(father); ptr && ptr->rightbro; ptr = (typecuc *) macrogetrightbro((typecorecrum *) ptr)) {
        if (ptr->age == RESERVED)
            continue;

        if (ptr->leftson && roomformoresons(ptr)) {
/* if (ptr->leftson && toofewsons (ptr)) {* */
            if (((typecuc *) ptr->rightbro)->leftson) {
                if (ptr->numberofsons + ((typecuc *) ptr->rightbro)->numberofsons <= MAXUCINLOAF) {
                    eatbrossubtreeseq(ptr);
                    break;
                } else {
                    takeovernephewsseq((typecorecrum *) ptr);
                    break;
                }
            }
        }
    }
    if (father->isapex)
        levelpull(father);
}

/* 2d recombine */

    static void
recombinend(
    typecuc *father)
{

    typecorecrum *ptr;
    typecorecrum *sons[MAXUCINLOAF];
    int i, j, n;

    if (father->height < 2 || !father->modified)
        return;

    for (ptr = getleftson(father); ptr; ptr = (typecorecrum *) getrightbro(ptr))
        recombinend((typecuc *) ptr);

    getorderedsons(father, sons);
    n = father->numberofsons;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; sons[i] && j < n; j++) {
            if (i != j && sons[j] && ishouldbother((typecuc *) sons[i], (typecuc *) sons[j])) {
                takeovernephewsnd((typecuc **) &sons[i], (typecuc **) &sons[j]);
/* break; */
/* break;//zzz6/16/84 reg// */
            }
        }
    }
    if (father->isapex)
        levelpull(father);
}

    void
recombine(
    typecuc *father)
{
    switch (father->cenftype) {
    case GRAN:  recombineseq(father);   break;
    case SPAN:  recombinend(father);    break;
    case POOM:  recombinend(father);    break;
    }
}

    static bool
randomness(
    float probability)
{
    //UNUSED static float i = 0;

    return true;
/* 
 * i += probability; if(i>=1.){ while (i>1){ i -= 1.; } return(true); }else{
 * return false; } */
}

    bool
ishouldbother(
    typecuc *dest,
    typecuc *src)
{
    ++noishouldbother;

    if (src->numberofsons == 0) {
        if (src->sonorigin.diskblocknumber == DISKPTRNULL)
            check(src);
        else
            return false;
    }

    if (dest->age == RESERVED || src->age == RESERVED)
        return false;

    return dest->numberofsons + src->numberofsons <= (dest->height > 1 ? MAXUCINLOAF : MAX2DBCINLOAF) && randomness(.3);
}

    int
comparecrumsdiagonally(
    typecorecrum *a,
    typecorecrum *b)
{
    Tumbler amagnitude, bmagnitude;

    tumbleradd(&a->cdsp.dsas[0], &a->cdsp.dsas[1], &amagnitude);
    tumbleradd(&b->cdsp.dsas[0], &b->cdsp.dsas[1], &bmagnitude);
    return (tumblercmp(&amagnitude, &bmagnitude));
}

    void
fixincoresubtreewids(
    typecuc *ptr)
{
    typecorecrum *son;

    if (ptr->height == 0)
        return;

    for (son = (typecorecrum *) getleftson(ptr); son; son = (typecorecrum *) getrightbro(son))
        fixincoresubtreewids((typecuc *) son);

    if (setwisp((typecorecrum *) ptr)) {
#ifndef DISTRIBUTION
        L("fixing %x \n", (int) ptr);
#endif
    }
}

---