Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/genf.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: genf.cxx,v $
 * Revision 1.10  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.9  2004/09/04 16:02:17  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.8  2002/07/14 08:32:51  jrush
 * Replace gerror() with assert(), comment out unused qerror() definition
 *
 * Revision 1.7  2002/05/28 04:22:29  jrush
 * Adjusted source files to comply with GPL licensing.
 *
 * Revision 1.6  2002/05/28 02:51:11  jrush
 * Made static any functions and global variables private to this source file
 * and commented out any unused functions.
 *
 * Revision 1.5  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.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 <stdlib.h>
#include "udanax.h"

#ifndef RESERVED
#define RESERVED -1                    /* in this file, this is used to flag calls from coredisk */
#endif

    bool
is2dcrum(
    typecorecrum *ptr)
{
    return ptr->cenftype != GRAN;
}

    typecorecrum *
getleftson(
    typecuc *ptr)
{
    rejuvinateifnotRESERVED((typecorecrum *) ptr);

    ptr = (typecuc *) ptr->leftson;
    if (ptr)
        rejuvinateifnotRESERVED((typecorecrum *) ptr);

    return (typecorecrum *) ptr;
}

    typecorecrum *
routinegetrightbro(
    typecorecrum *ptr)
{
    rejuvinateifnotRESERVED((typecorecrum *) ptr);

    ptr = ptr->rightbro;
    if (ptr)
        rejuvinateifnotRESERVED((typecorecrum *) ptr);

    return ptr;
}

    typecorecrum *
getrightmostbro(
    typecorecrum *ptr)
{
    typecorecrum *p;

    while ((p = getrightbro(ptr)) != 0)
        ptr = p;

    return ptr;
}

    static typecorecrum *
getleftbro(
    typecorecrum *ptr)
{
    rejuvinateifnotRESERVED(ptr);

    if (ptr->isleftmost)
        return NULL;

    ptr = ptr->leftbroorfather;
    if (ptr)
        rejuvinateifnotRESERVED((typecorecrum *) ptr);

    return ptr;
}

    static typecorecrum *
getleftmostbro(
    typecorecrum *ptr)
{
    typecorecrum *p;

    while ((p = getleftbro(ptr)) != 0)
        ptr = p;

    return ptr;
}

    typecuc *
getfather(
    typecorecrum *ptr)
{
    ptr = getleftmostbro(ptr)->leftbroorfather;
    if (ptr)
        rejuvinateifnotRESERVED(ptr);

    return (typecuc *) ptr;
}

    typecuc *
findfullcrum(
    typecorecrum *descendant)
{
    typecuc *ptr;

    for (ptr = (typecuc *) descendant; !isfullcrum((typecorecrum *) ptr); ptr = findfather((typecorecrum *) ptr))
        ;

    return ptr;
}

    bool
isemptyenfilade(
    typecuc *ptr)
{
    if (!isfullcrum((typecorecrum *) ptr))
        return false;

    switch (ptr->cenftype) {
    case GRAN:
        return iszerolock(ptr->cwid.dsas, (unsigned)widsize(ptr->cenftype));
    case SPAN:
    case POOM:
        return iszerolock(ptr->cwid.dsas, (unsigned) widsize(ptr->cenftype)) && iszerolock(ptr->cdsp.dsas, (unsigned) dspsize(ptr->cenftype));
    default:
        assert(0); // isempytenfilade - bad enftype
    }
    return false; // Just to keep compiler from complaining
}

/* Just does pointer following */
    typecuc * // UNUSED
functionweakfindfather(
    typecorecrum *ptr)
{
    if (!ptr)
        assert(0); // weakfindfater called with NULL

    if (isfullcrum(ptr))               /* what about spanf */
        return NULL;

    for (; ptr && !ptr->isleftmost; ptr = ptr->leftbroorfather)
        ;

    if (ptr)
        return (typecuc *) ptr->leftbroorfather;
    else
        return NULL;
}

    typecuc *
findfather(
    typecorecrum *son)
{
    typecuc *ptr;

    if ((ptr = weakfindfather(son)) != 0)
        rejuvinateifnotRESERVED((typecorecrum *) ptr);

    return ptr;
}

    typecorecrum *
findleftbro(
    typecorecrum *ptr)
{
    if (ptr->isleftmost) {
        rejuvinateifnotRESERVED(ptr);
        return NULL;
    }

    ptr = ptr->leftbroorfather;
    rejuvinateifnotRESERVED(ptr);
    return /* checkenftypes( */ ptr /* ,"") */;
}

    typecorecrum *
findleftmostbro(
    typecorecrum *ptr)
{
    while (!ptr->isleftmost) {
        ptr = ptr->leftbroorfather;
        rejuvinateifnotRESERVED(ptr);
    }
    return /* checkenftypes( */ ptr /* ,"") */;
}

    typecorecrum *
weakfindleftmostbro(
    typecorecrum *ptr)
{
    while (!ptr->isleftmost)
        ptr = ptr->leftbroorfather;

    return ptr;
}

    typecorecrum * // UNUSED
funcfindrightbro(
    typecorecrum *ptr)
{
    if (!ptr->rightbro) {
        rejuvinateifnotRESERVED(ptr);
        return NULL;
    }

    ptr = ptr->rightbro;
    rejuvinateifnotRESERVED(ptr);
    return ptr;
}

    typecorecrum * // UNUSED
weakfindrightbro(
    typecorecrum *ptr)
{
    if (!ptr->rightbro)
        return NULL;

    ptr = ptr->rightbro;
    return ptr;
}

    typecorecrum *
findrightmostbro(
    typecorecrum *leftbro)
{
    typecorecrum *temp;

    for (; leftbro && (temp = findrightbro(leftbro)); leftbro = temp)
        ;

    rejuvinateifnotRESERVED(leftbro);
    return /* checkenftypes( */ leftbro /* ,"") */;
}

    typecorecrum *
findleftson(
    typecuc *ptr)
{
    if (ptr == NULL)
        return NULL;

    int oldage = ptr->age;
    if (ptr->leftson == NULL) {
        if (ptr->sonorigin.diskblocknumber == DISKPTRNULL)
            return NULL;

        reserve((typecorecrum *) ptr);
        if (ptr->sonorigin.diskblocknumber == 0) {
            dump((typecorecrum *) ptr);
            assert(0); // trying to read 0 block
        }
        inloaf(ptr);
/* THIS IS A REAL REJUVINATE FOR A RESERVE */
        if (oldage != RESERVED)        /* zzz experimental zz */
            rejuvinate((typecorecrum *) ptr);
    }
    rejuvinateifnotRESERVED(ptr->leftson);
    return ptr->leftson;
}

    typecorecrum *
findrightmostson(
    typecuc *ptr)
{
    return findrightmostbro(findleftson(ptr));
}

    bool
toomanysons(
    typecuc * ptr)
{
    if (ptr->height)
        findleftson(ptr);

    return ptr->numberofsons > (ptr->height > 1 ? MAXUCINLOAF : (is2dcrum((typecorecrum *) ptr) ? MAX2DBCINLOAF : MAXBCINLOAF));
}

    bool
toofewsons(
    typecuc *ptr)
{
    if (ptr->height && !ptr->leftson) /* brings in leftson if not here */
        findleftson(ptr);

    return ptr->numberofsons < (ptr->height > 1 ? MAXUCINLOAF - 1 : (is2dcrum((typecorecrum *) ptr) ? MAX2DBCINLOAF : MAXBCINLOAF));
}

    bool
roomformoresons(
    typecuc *ptr)
{
    if (ptr->height && !ptr->leftson) /* brings in leftson if not here */
        findleftson(ptr);

    return ptr->numberofsons < (ptr->height > 1 ? MAXUCINLOAF : (is2dcrum((typecorecrum *) ptr) ? MAX2DBCINLOAF : MAXBCINLOAF));
}

    static void
transferloaf(
    typecuc *from,
    typecuc *to)
{
    if (from->height == 0)             /* bottom crums */
        return;

    if (from->cenftype == SPAN || from->cenftype == POOM) {
        /* the sucker dosen't know what it is yet anywow */
    }

    typecuc *ptr = (typecuc *) findleftson(from);
    int nsons = from->numberofsons;
    from->numberofsons = 0;
    to->numberofsons = nsons;
    ptr->leftbroorfather = (typecorecrum *) to;
    to->leftson = (typecorecrum *) ptr;
    from->leftson = NULL;
/* to->sonorigin = from->sonorigin; from->sonorigin = DISKPTRNULL; */
}

    void
levelpush(
    typecuc *fullcrumptr)
{
    typecuc *newcuc;
    typediskloafptr temploafptr;

#ifndef DISTRIBUTION
    L("in levelpush");
/* checkwholesubtree(fullcrumptr); */
#endif

    if (!isfullcrum((typecorecrum *) fullcrumptr))
        assert(0); // Levelpush not called with fullcrum

    newcuc = (typecuc *) createcrum((int) fullcrumptr->height, (int) fullcrumptr->cenftype);
    newcuc->isleftmost = true;

    transferloaf(fullcrumptr, newcuc);
    temploafptr = fullcrumptr->sonorigin;
    fullcrumptr->sonorigin.diskblocknumber = DISKPTRNULL;
    fullcrumptr->height++;
    adopt((typecorecrum *) newcuc, SON, (typecorecrum *) fullcrumptr);     /* adopt new under fullcurm */

    newcuc->sonorigin = temploafptr;
    setwispupwards(newcuc, 1);
    ivemodified((typecorecrum *) newcuc);
    ivemodified((typecorecrum *) fullcrumptr);  /* is this redundant */

#ifndef DISTRIBUTION
    L("leaving levelpush");
#endif
}

    void
levelpull(
    typecuc *fullcrumptr)
{
/* typecuc *ptr; */
    return;
/* 
 * if (!isfullcrum (fullcrumptr)) #ifndef DISTRIBUTION assert(0); "Levelpull not called with fullcrum"); #else assert(0); #endif if
 * (fullcrumptr->numberofsons > 1) return; if (fullcrumptr->height <= 1)
 * return; ptr = (typecuc *) findleftson (fullcrumptr); dspadd
 * (&fullcrumptr->cdsp, &ptr->cdsp, &fullcrumptr->cdsp,
 * fullcrumptr->cenftype);
 * 
 * disown (ptr); fullcrumptr->height--; transferloaf (ptr, fullcrumptr);
 * setwispupwards (fullcrumptr,1); freecrum (ptr); */
}

/* 
 * ** Remove crum from its father and siblings. ** It keeps any kids it has */

    void
disown(
    typecorecrum *crumptr)
{
    typecuc *father;

    if (isfullcrum(crumptr)) {
#ifndef DISTRIBUTION
        dump(crumptr);
        assert(0); // can't disownnomodify fullcrum
#else
        assert(0);
#endif
    }

    if (!(father = weakfindfather(crumptr))) {
#ifndef DISTRIBUTION
        dump(crumptr);
        assert(0); // disownnomodify called without a father
#else
        assert(0);
#endif
    }

    disownnomodify(crumptr);
    ivemodified((typecorecrum *) father);
}

    void
disownnomodify(
    typecorecrum *crumptr)
{
    typecuc *father;
    typecorecrum *left, *right;

    if (isfullcrum(crumptr)) {
#ifndef DISTRIBUTION
        dump(crumptr);
        assert(0); // can't disownnomodify fullcrum
#else
        assert(0);
#endif
    }

    if (!(father = weakfindfather((typecorecrum *) crumptr))) {
#ifndef DISTRIBUTION
        dump((typecorecrum *) crumptr);
        assert(0); // disownnomodify called without a father
#else
        assert(0);
#endif
    }

    right = findrightbro(crumptr);
    father->numberofsons -= 1;

    if (crumptr->isleftmost) {
        father->leftson = right;
        if (right) {
            right->leftbroorfather = (typecorecrum *) father;
            right->isleftmost = true;
        }
    } else {                           /* has left brother */
        left = findleftbro(crumptr);
        left->rightbro = right;
        if (right) {
            right->leftbroorfather = left;
        }
    }
    crumptr->leftbroorfather = crumptr->rightbro = NULL;
/* ivemodified(father) ; *//*for now till we remove this */
}

/* 
 * ** Adopt "new" crum (and his kids) into a family of which "old" ** is a
 * member. */
    void
adopt(
    typecorecrum *newcc,
    int           relative,
    typecorecrum *old)
{
    typecuc *father = NULL;
    typecorecrum *left = NULL, *right = NULL;

    assert(newcc && old);  // ERROR: adopt with NULL
    assert(newcc != old);  // ERROR: adopt with both crums same

    // assert(!isfullcrum(newcc); // adopt called with fullcrum

    newcc->cenftype = old->cenftype; // make crum know what kind it is

    switch (relative) {
    case LEFTMOSTSON:
        father = (typecuc *) old;
        left   = NULL;
        right  = findleftson(father);
        break;

    case RIGHTMOSTSON:
        father = (typecuc *) old;
        if (father->leftson)  left = findrightmostson(father);
        else                  left = NULL;
        right = NULL;
        break;

    case RIGHTBRO:
        assert(newcc->height == old->height); // ERROR: adopt 1
        left   = old;
        father = findfather(left);
        right  = findrightbro(left);
        break;

    case LEFTBRO:
        assert(newcc->height == old->height); // ERROR: adopt 2
        right  = old;
        father = findfather(right);
        left   = findleftbro(right);
        break;

    default:
        assert(false); // ERROR: bad relative
    }

    assert(father);                              // ERROR: adopt without a father!
    assert(father->height == newcc->height + 1); // ERROR: height mismatch in adopt

    if (left) {
        left->rightbro = newcc;
        newcc->leftbroorfather = left;
        newcc->isleftmost = false;
    } else {
        father->leftson = newcc;
        newcc->leftbroorfather = (typecorecrum *) father;
        newcc->isleftmost = true;
    }

    newcc->rightbro = right;
    if (right) {
        right->leftbroorfather = newcc;
        right->isleftmost = false;
    }

    ++father->numberofsons;
}

    void
ivemodified(
    typecorecrum *ptr)
{
    bool fatherflag;

    if (!ptr)
        return;

    rejuvinateifnotRESERVED(ptr);

    fatherflag = true;                 /* not really, but the incoming ptr wants to get modified */
    while (ptr) {
/* if (ptr->height == 0) *//* 10-2-84 what was this for bug */

        rejuvinateifnotRESERVED(ptr);
        if (fatherflag) {
/* if (ptr->modified) return; *//* this optimization commented out because createcrum sets flag true to fix this makesure that all created crums get ivemodified then change createcrum then fix here */
            ptr->modified = true;
        }
        fatherflag = ptr->isleftmost;
        ptr = ptr->leftbroorfather;
    }
}

---