Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/credel.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: credel.cxx,v $
 * Revision 1.12  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.11  2004/09/04 16:02:17  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.10  2004/08/28 13:57:00  jrush
 * Further syncing of local copies to CVS; builds but I haven't run it yet.
 *
 * Revision 1.9  2002/07/14 08:35:23  jrush
 * Replace gerror(), qerror() 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:49:42  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 22:53:20  jrush
 * Changed from using my setmem() to the clib's memset() and removed no
 * longer-needed usefull.cxx
 *
 * Revision 1.5  2002/04/12 11:56:42  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 <memory.h>
#include <malloc.h>
#include <unistd.h>

#define NEWALLOC
#include "udanax.h"

typecorecrum *grimreaper;
int ingrimreaper      = false;
int reaplevel         = 0;
int timesaroundreaper = 0;
int crumnumber        = 0;
int reapnumber        = 0;
int nreapings         = 0;
int reservnumber      = 0;

#define MAXALLOCQUEUEARRAY 500
struct queue allocqueuearray[MAXALLOCQUEUEARRAY];

static bool isreapable(int *fuckinap, typecorecrum *localreaper);
static void reap(typecorecrum *localreaper);

    void
initqueues()
{
    for (int i = 0; i < MAXALLOCQUEUEARRAY; i++)
        qinit(&allocqueuearray[i]);

#ifdef NEWALLOC
    int num = allocsize / 3;
#else
    int num = 0;
#endif

    for (int j = 0; j < num; j += sizeof(typecuc) + sizeof(typecbc) + sizeof(type2dcbc) + 3 * sizeof(tagtype)) {
        qpush(&allocqueuearray[(sizeof(typecuc) + sizeof(tagtype) + sizeof(HEADER) - 1) / sizeof(HEADER)],
              (queue *) falloc(sizeof(typecuc) + sizeof(tagtype)));
        qpush(&allocqueuearray[(sizeof(typecbc) + sizeof(tagtype) + sizeof(HEADER) - 1) / sizeof(HEADER)],
              (queue *) falloc(sizeof(typecbc) + sizeof(tagtype)));
        qpush(&allocqueuearray[(sizeof(type2dcbc) + sizeof(tagtype) + sizeof(HEADER) - 1) / sizeof(HEADER)],
              (queue *) falloc(sizeof(type2dcbc) + sizeof(tagtype)));
    }
}

//UNUSED static void
//UNUSED dumptable()
//UNUSED {
//UNUSED     L("dumptable\n");
//UNUSED     for (int i = 0; i < MAXALLOCQUEUEARRAY; i++) {
//UNUSED         int tmp = qlength(&allocqueuearray[i]);
//UNUSED         if (tmp != 0)
//UNUSED             L("len of %d = %d\n", i, tmp);
//UNUSED     }
//UNUSED }

    static char *
allocfromqueue(
    int n)
{
    return (char *) qremove(&allocqueuearray[((n + sizeof(HEADER) - 1) / sizeof(HEADER))]);
}

    static void
freetoqueue(
    char *ptr)
{
    // Located in memory before the tag is the sizeof the block in align uints
    // including the header

    // dumptable();

    int n = ((HEADER *) (ptr - sizeof(HEADER)))->s.size - 1;
    qpush(&allocqueuearray[n], (queue *) ptr);

    // dumptable();
}

    static typecorecrum *
createcruminternal(
    int           crumheight,
    int           enftype,
    typecorecrum *allocated)
{
    unsigned crumsize = 0;

    if (crumheight == 0) {
        switch (enftype) {
        case GRAN:
            crumsize = sizeof(typecbc);
            break;
        case SPAN:
        case POOM:
            crumsize = sizeof( /* typecbc */ type2dcbc);
            break;
        default:
            L(" enftype = %d\n", enftype);
            assert(0); // createcrum illegal enftype
        }
    } else
        crumsize = sizeof(typecuc);

    typecorecrum *ptr;
    if (!allocated)
        ptr = (typecorecrum *) eallocwithtag(crumsize, (tagtype) (crumheight > 0 ? CUCTAG : CBCTAG));
    else
        ptr = allocated;

    ptr->height          = crumheight;
    ptr->isapex          = false;
    ptr->cenftype        = enftype;
    ptr->modified        = true /*false*/;
    ptr->isleftmost      = false;
    ptr->age             = NEW;
    ptr->leftbroorfather = NULL;
    ptr->rightbro        = NULL;

    clear(&ptr->cdsp, sizeof(ptr->cdsp));
    clear(&ptr->cwid, sizeof(ptr->cwid));

    if (crumheight > 0) {
        ((typecuc *) ptr)->numberofsons              = 0;
        ((typecuc *) ptr)->leftson                   = NULL;
        ((typecuc *) ptr)->sonorigin.diskblocknumber = DISKPTRNULL;

    } else {
        if (enftype == GRAN) {
            clear(&((typecbc *) ptr)->cinfo, sizeof(((typecbc *) ptr)->cinfo));
            ((typecbc *) ptr)->cinfo.infotype = GRANCLEARLYILLEGALINFO;
        } else
            clear(&((type2dcbc *) ptr)->c2dinfo, sizeof(((type2dcbc *) ptr)->c2dinfo));
    }
    ++crumnumber;

    return ptr;
}

    void
initcrum(
    int           crumheight,
    int           enftype,
    typecorecrum *ptr)
{
    createcruminternal(crumheight, enftype, ptr);
}

    static void
xgrabmorecore()
{
    char *tmp = (char *) sbrk(incrementalallocsize);
    if (!tmp)
        assert(0); // no more memory in xgrabmorecore

    ((HEADER *) tmp)->s.size = (incrementalallocsize + sizeof(HEADER) - 1) / sizeof(HEADER);
    ffree(tmp + sizeof(HEADER));

    L("xgrabmorecore got another %d\n", incrementalallocsize);
}

    static void
grimlyreap()
{
    typecorecrum *ptr;
    int eh;

    ingrimreaper = true;
    if (reaplevel++)
#ifndef DISTRIBUTION
        if (reaplevel == 1)
            L("Recursive grimreaper call.\n");
#endif

    if (!grimreaper)
        assert(0); // nothing to reap!

    reapnumber = 0;
    timesaroundreaper = 0;
    for (ptr = grimreaper; grimreaper; grimreaper = (typecorecrum *) grimreaper->nextcrum) {
        if (grimreaper == ptr) {
            ++timesaroundreaper;
        }
        if (timesaroundreaper > 10) {
            L("urk in grimlyreap\n");
/* lookatalloc(); */
            xgrabmorecore();
            break;
// * #ifndef DISTRIBUTION assert(0); /* I'm getting bored in grimlyreap */); #else
// * assert(0); /* memory fouled */); #endif */
        }

        if (grimreaper->age == RESERVED)
            continue;

        if (isreapable(&eh, grimreaper)) {
            reap(grimreaper);
            reapnumber = 0;
            timesaroundreaper = 0;
            --reaplevel;
            break;
        } else {
            if (eh) {
/* dump(grimreaper); */
            }
        }

        ++reapnumber;
        grimreaper->age++;
    }

    ingrimreaper = false;
}

    static int *
ealloc(
    unsigned nbytes)
{                                      /* with tag */
    /* L("ealloc called with %d\n", nbytes); */

    for (;;) {
        char *ret;

        if ((ret = allocfromqueue(nbytes + sizeof(tagtype))) != 0) {
            ret += sizeof(tagtype);
            return (int *) ret;
        }
        ret = (char *)falloc(nbytes + sizeof(tagtype));

        if (ret) {
            // memset(ret + sizeof(tagtype), 0xF9, nbytes);
            *(tagtype *) ret = false;
            return (int *) (ret + sizeof(tagtype));
        }
        if (grimreaper == NULL) {
            xgrabmorecore();
            /*
             * assert(0); // Why am I out of room?
             */
        }
        grimlyreap();
    }
}

    void
efree(
    char *ptr)
{                                      /* with tag */
/* ffree(ptr); */
    if (*(ptr - sizeof(tagtype)) == CBCTAG || *(ptr - sizeof(tagtype)) == CUCTAG) {
#ifdef NEWALLOC
        freetoqueue(ptr - sizeof(tagtype));
#else
        ffree(ptr - sizeof(tagtype));
#endif
    } else {
        free(ptr - sizeof(tagtype));
    }
}

/* 
 * void etag(ptr, tag) char * ptr; tagtype tag; { *(ptr -sizeof(tagtype)) =
 * tag; } */

    int *
eallocwithtag(
    unsigned nbytes,
    tagtype  tag)
{
    char *ret = NULL;

    if (tag == CBCTAG || tag == CUCTAG) {
        ret = (char *) ealloc(nbytes);

    } else {
        ret = (char *) malloc(nbytes + sizeof(tagtype));
        ret += sizeof(tagtype);
    }

/* etag((char*)ret,tag); */

    *(ret - sizeof(tagtype)) = tag;
    return (int *) ret;
}

    static bool
isreapable(
    int          *fuckinap,
    typecorecrum *localreaper)
{
    register typecorecrum *p;
    typecuc *father;

    *fuckinap = 0;
    if (!localreaper)
        assert(0); // localreaper NULL

    if (localreaper->age < OLD || localreaper->age == RESERVED) {
        *fuckinap = 1;
        return false;
    }

    if (localreaper->isapex) {
        if (localreaper->cenftype != POOM)
            return false;

        if (localreaper->modified) {
            if (!((typecuc *) localreaper)->leftson) {
#ifndef DISTRIBUTION
                dump(localreaper);
                L("in isreapable modified and no son in apex");
#endif
                return false;
            }

            for (p = ((typecuc *) localreaper)->leftson; p; p = p->rightbro) {
                if (p->modified)
                    return false;

                if (p->age < OLD || p->age == RESERVED)
                    return false;

                if (p->height > 0 && ((typecuc *) p)->leftson)
                    return false;

                if (p->height == 0 && p->cenftype == GRAN && ((typecbc *) p)->cinfo.infotype == GRANORGL && ((typecbc *) p)->cinfo.granstuff.orglstuff.orglincore)
                    return false;
            }
            return true;

        } else {
            for (p = ((typecuc *) localreaper)->leftson; p; p = p->rightbro) {
                if (p->modified)
                    return false;

                if (p->age < OLD || p->age == RESERVED)
                    return false;

                if (p->height > 0 && ((typecuc *) p)->leftson)
                    return false;

                if (p->height == 0 && p->cenftype == GRAN && ((typecbc *) p)->cinfo.infotype == GRANORGL && ((typecbc *) p)->cinfo.granstuff.orglstuff.orglincore)
                    return false;
            }
            return true;
        }
    }

/* if height == 0 and not cinfo.orglincore return true */
    if (!localreaper)
        assert(0); // in isreapable localreaper is NULL

    father = weakfindfather((typecorecrum *) localreaper);
    if (!father) {
        L("in isreapable no father !! \n");
        return false;
    }

    if (localreaper->height == 0) {
        if (localreaper->cenftype == GRAN) {
            if (((typecbc *) localreaper)->cinfo.infotype == GRANORGL) {
                if (((typecbc *) localreaper)->cinfo.granstuff.orglstuff.orglincore)
                    return false;
            }
        }

        for (p = weakfindleftmostbro(localreaper); p; p = p->rightbro) {
            if (p->age < OLD || p->age == RESERVED)
                return false;

            if (p->height == 0 && p->cenftype == GRAN && ((typecbc *) p)->cinfo.infotype == GRANORGL && ((typecbc *) p)->cinfo.granstuff.orglstuff.orglincore)
                return false;
        }
        return true;

    } else {                           /* != 0 */
        if (father->modified) {
            for (p = weakfindleftmostbro(localreaper); p; p = p->rightbro) {
                if (p->modified)
                    return false;

                if (p->age < OLD || p->age == RESERVED)
                    return false;

                if (p->height > 0 && ((typecuc *) p)->leftson)
                    return false;
            }
            return true;

        } else {                       /* if (!father->modified) */
            for (p = weakfindleftmostbro(localreaper); p; p = p->rightbro) {
                if (p->modified)
                    return false;

                if (p->age < OLD || p->age == RESERVED)
                    return false;

                if (p->height > 0 && ((typecuc *) p)->leftson)
                    return false;
            }
            return true;
        }
    }
}

    static void
reap(
    typecorecrum *localreaper)
{
    typecuc *temp;

    if (!localreaper)
        assert(0); // localreaper NULL0

    ++nreapings;
    if (localreaper->isapex) {
        temp = (typecuc *) localreaper->leftbroorfather;
        grimreaper = grimreaper->nextcrum;
        if (!temp)
            return;

        orglwrite((typecbc *) temp);
        if (!localreaper)
            assert(0); // localreaper NULL2

        return;
    }

    temp = weakfindfather((typecorecrum *) localreaper);
    if (!temp)
        assert(0); // localreaper doesn't have a father

    if (!temp->leftson) {
        grimreaper = grimreaper->nextcrum;
        return;
    }

    subtreewrite(temp);
}

/* 
 * void efreewithtag(ptr) char * ptr; { ffree(ptr - sizeof(tagtype)); } */
    void
initgrimreaper()
{
    grimreaper = NULL;
}

    int
testforrejuvinate(
    typecorecrum *ptr)
{
    if (ptr->age == RESERVED) {
        if (!reservnumber)
            assert(0); // There shouldn't be any more reserved

        --reservnumber;
    }
    return 0;
}

    void
funcrejuvinate(
    typecorecrum *ptr)
{                                      /* inner if is testing very useful * test */
    if (ptr->age == RESERVED) {
        if (!reservnumber) {
#ifndef DISTRIBUTION
            dump(ptr);
            assert(0); // There shouldn't be any more reserved
#else
            assert(0); // memory mess
#endif
        }
        --reservnumber;
    }
    ptr->age = NEW;
}

/* protect a crum and its ancestors from being grimly reaped */
    void
reserve(
    typecorecrum *ptr)
{
#ifndef DISTRIBUTION
    foohex("reserve\n", (int) ptr);
#endif
    if (ptr->age != RESERVED) {
        ++reservnumber;
    } else {
#ifndef DISTRIBUTION
        assert(0); // reserve already reserved
#else
        assert(0); // arg!
#endif
    }
    ptr->age = RESERVED;
}

    void
testforreservedness(
    char *msg)
{                                      /* test to see if any reserved flags linger * in the memory.  if they do is a
                                        * gross * error in crum stuff */
    int numreserved = 0;
    bool first;

    typecorecrum *ptr;
    for (ptr = grimreaper, first = true; ptr && (first ? true : ptr != grimreaper); ptr = ptr->nextcrum, first = false)
        if (ptr->age == RESERVED) {
            ++numreserved;
            if (true || debug)
                dump(ptr);
        }

    if (numreserved) {
        L("numreserved = %s:  There are %d reserved crums. (reservnumber = %d)\n", msg, numreserved, reservnumber);
        assert(0); // This isn't supposed to be the case
    }

    if (reservnumber) {
        L("reservnumber = %d\n", reservnumber);
        assert(0); // reservnumber is incorrect
    }
}

/* assumes crum is disowned */
    void
subtreefree(
    typecorecrum *ptr)
{
    if (!ptr)
        assert(0); // boom in subtreefree called with ptr == NULL

    if (ptr->height > 0) {
        typecorecrum *p, *right;

        for (p = ((typecuc *) ptr)->leftson; p; p = right) {
            right = p->rightbro;
            disown(p);
            subtreefree(p);
        }

    } else if (ptr->cenftype == GRAN
           && ((typecbc *) ptr)->cinfo.infotype == GRANORGL
           && ((typecbc *) ptr)->cinfo.granstuff.orglstuff.orglincore)
        orglfree(((typecbc *) ptr)->cinfo.granstuff.orglstuff.orglptr);

    freecrum(ptr);
}

    void
freecrum(
    typecorecrum *ptr)
{
    if (ptr->age == RESERVED)
        assert(0); // freecrum called with RESERVED crum

    if (grimreaper == ptr)
        grimreaper = grimreaper->nextcrum;

    if (grimreaper == ptr)
        grimreaper = NULL;

    ptr->nextcrum->prevcrum = ptr->prevcrum;
    ptr->prevcrum->nextcrum = ptr->nextcrum;

/* zzz should it decrement usecount here sometimes? */

    --crumnumber;
    efree((char *)ptr);
}

    void
loaffree(
    typecuc *father)
{
    if (father->height <= 0 /* || !father->leftson */ )
        assert(0); // bad call

    typecorecrum *ptr, *next;
    for (ptr = father->leftson; ptr; ptr = next) {
        next = ptr->rightbro;
        disownnomodify(ptr);
        subtreefree(ptr);
    }

    father->modified = false;
}

    void
orglfree(
    typecuc *ptr)
{
    assert(ptr);         // ERROR: orglfree called with no orglptr
    assert(ptr->isapex); // ERROR: Orglfree called with non-fullcrum
    assert(((typecbc *) ptr->leftbroorfather)->cinfo.granstuff.orglstuff.diskorglptr.diskblocknumber != DISKPTRNULL); // ERROR: orglfree called with unwritten-out orgl

    ((typecbc *) ptr->leftbroorfather)->cinfo.granstuff.orglstuff.orglincore = false;
    ((typecbc *) ptr->leftbroorfather)->cinfo.granstuff.orglstuff.orglptr    = NULL;

    subtreefree((typecorecrum *) ptr);
}

    typecuc *
createenf(
    int enftype)
{
    typecuc *fullcrumptr = (typecuc *) createcrum(1, enftype);

    fullcrumptr->cenftype   = enftype;
    fullcrumptr->isapex     = true;
    fullcrumptr->isleftmost = true;

    typecorecrum *ptr = createcrum(0, enftype);

    adopt(ptr, SON, (typecorecrum *) fullcrumptr);
    if (enftype == GRAN)
        ((typecbc *) ptr)->cinfo.infotype = GRANNULL;   /* KLUGE will this work?? */

    ivemodified(ptr);

/* if(enftype == GRAN){ levelpush(fullcrumptr); adopt (createcrum(0,enftype), RIGHTBRO, fullcrumptr->leftson);
 * adopt(createcrum(0,enftype),SON,fullcrumptr->leftson->rightbro); ptr = fullcrumptr->leftson->leftson;
 * tumblerincrement(&(ptr->cwid.dsas[WIDTH]),2,1,&(ptr->cwid.dsas[WIDTH])); setwispupwards(ptr,1); } */

    return fullcrumptr;
}

    typecorecrum *
createcrum(
    int crumheight,
    int enftype)
{
    typecorecrum *ptr = createcruminternal(crumheight, enftype, (typecorecrum *) NULL);

    if (grimreaper) {
        ptr->nextcrum                  = grimreaper;
        ptr->prevcrum                  = grimreaper->prevcrum;
        grimreaper->prevcrum->nextcrum = ptr;
        grimreaper->prevcrum           = ptr;
    } else
        grimreaper = ptr->nextcrum = ptr->prevcrum = ptr;

    return ptr;
}

---