Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/retrie.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: retrie.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:18  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.10  2002/07/26 04:32:01  jrush
 * Replaced gerror() with assert()
 *
 * Revision 1.9  2002/05/28 04:22:29  jrush
 * Adjusted source files to comply with GPL licensing.
 *
 * Revision 1.8  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.7  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.6  2002/04/10 18:01:54  jrush
 * Renamed class typeisa to IStreamAddr.
 *
 * 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"

/* all findcbc* routines are recursive with depth of ** recursion == height of enfilade being searched */

/* Model-T like retrieves */
    static CrumContext *
findcbcseqcrum(
    typecorecrum *ptr,
    typedsp      *offsetptr,
    Tumbler      *address)
{
    if (!ptr)
        assert(0); // findcbcseqcrum called with NULL ptr

    for (; getrightbro(ptr); ptr = ptr->rightbro) {
        if (whereoncrum(ptr, offsetptr, address, WIDTH) <= THRUME)
            break;

        dspadd(offsetptr, &ptr->cwid, offsetptr, (int) ptr->cenftype);
    }

    if (ptr->height != 0) {
        ptr = findleftson((typecuc *) ptr);
        return findcbcseqcrum(ptr, offsetptr, address);
    } else
        return createcrumcontext(ptr, offsetptr);
}

    static Context *
findcbcseq(
    typecorecrum *ptr,
    typedsp      *offsetptr,
    Tumbler      *address)
{
    for (; getrightbro(ptr); ptr = ptr->rightbro) {
        if (whereoncrum(ptr, offsetptr, address, WIDTH) <= THRUME)
            break;

        dspadd(offsetptr, &ptr->cwid, offsetptr, (int) ptr->cenftype);
    }

    if (ptr->height != 0) {
        ptr = findleftson((typecuc *) ptr);
        return findcbcseq(ptr, offsetptr, address);
    } else
        return makecontextfromcbc((typecbc *) ptr, (typewid *) offsetptr);
}

    static Context *
findcbcnd(
    typecorecrum *father,
    typewid      *offsetptr,
    Tumbler      *address,
    int           index)
{
    typecorecrum *ptr;
    typewid       grasp;
    Context      *retr = NULL;
    int           cmp;

    if ((cmp = whereoncrum(father, offsetptr, address, index)) < ONMYLEFTBORDER || cmp > THRUME)
        return NULL;

    if (father->height != 0) {
        prologuend(father, offsetptr, &grasp, (typedsp *) NULL);
        for (ptr = findleftson((typecuc *) father); ptr; ptr = getrightbro(ptr))
            if ((retr = findcbcnd(ptr, &grasp, address, index)) != 0)
                break;

    } else                           /* FOUND IT! */
        retr = makecontextfromcbc((typecbc *) father, offsetptr);

    return retr;
}

    static bool                                   /* 6-28-84 old code */
crumqualifies2d(
    typecorecrum         *crumptr,
    typedsp              *offset,
    Tumbler              *span1start,
    Tumbler              *span1end,
    int                   index1,
    Tumbler              *span2start,
    Tumbler              *span2end,
    int                   index2,
    type2dbottomcruminfo *infoptr)
/* NOTE in retrieves this is ---40% -- of cpu */
{
    int startcmp, endcmp;

/* foocrum("entering crumqualifies2d\n",crumptr); */
    if ((crumptr->height == 0) && infoptr && !tumblereq(&infoptr->homedoc, &(((type2dcbc *) crumptr)->c2dinfo.homedoc))) {
#ifndef DISTRIBUTION
        L("mumble homedoc");
#endif
/* foo("returningfalse case a"); */
        return false;
    }

    endcmp = iszerotumbler(span1end) ? TOMYRIGHT : whereoncrum(crumptr, offset, span1end, index1);
    if (endcmp <= /*=*/ ONMYLEFTBORDER)
        return false;

    startcmp = whereoncrum(crumptr, offset, span1start, index1);
    if ((startcmp > THRUME /* && endcmp > THRUME */ ))
        return false;

    endcmp = iszerotumbler(span2end) ? TOMYRIGHT : whereoncrum(crumptr, offset, span2end, index2);
    if (endcmp < ONMYLEFTBORDER) /* <= was < 12/20/84 */
        return false;

    startcmp = whereoncrum(crumptr, offset, span2start, index2);
    if ((startcmp > THRUME /* && endcmp > THRUME */ ))
        return false;

    return true;
}

    static void
findcbcinarea2d(
    typecorecrum        *crumptr,
    typedsp             *offsetptr,
    Tumbler             *span1start,
    Tumbler             *span1end,
    int                  index1,
    Tumbler             *span2start,
    Tumbler             *span2end,
    int                  index2,
    Context            **headptr,
    typebottomcruminfo  *infoptr)
{
    typedsp localoffset;
    Context *context;

#ifndef DISTRIBUTION
/* foo(" entering findcbcinarea2d\n"); */
/* footumbler("span1start = ",span1start); */
/* footumbler("span1end = ",span1end); */
/* footumbler("span2start = ",span2start); */
/* footumbler("span2end = ",span2end); */
/* foodsp("offset = ",offsetptr,crumptr->cenftype); */
    if (infoptr) {
        L("not NULL infoptr versions mumble specialcase 11/27/84 shouldent happen till we try something fancier\n");
        assert(0); // findcbcinarea2d
    }
#else
    if (infoptr)
        assert(0); // !NULL
#endif

    for (; crumptr; crumptr = getrightbro(crumptr)) {
        if (!crumqualifies2d(crumptr, offsetptr, span1start, span1end, index1, span2start, span2end, index2, (type2dbottomcruminfo *) infoptr))
            continue;

/* foocrum("crumqualifies in findcbcinarea2d\n",crumptr); */
        if (crumptr->height != 0) {
            dspadd(offsetptr, &crumptr->cdsp, &localoffset, (int) crumptr->cenftype);
            findcbcinarea2d(findleftson((typecuc *) crumptr), &localoffset, span1start, span1end, index1, span2start, span2end, index2, headptr, infoptr);
        } else {
/* foo("make context in findcbcinarea2d\n"); */
            context = makecontextfromcbc((typecbc *) crumptr, (typewid *) offsetptr);
            incontextlistnd(headptr, context, index1);
        }
    }

/* contextfree(context); */
/* foo("leaving findcbcinarea2d\n"); */
}

    CrumContext *
retrievecrums(
    typecuc *fullcrumptr,
    Tumbler *address,
    int      index)
{
    typedsp offset;
    clear(&offset, sizeof(typedsp));

    if (fullcrumptr->cenftype == GRAN)
        return findcbcseqcrum((typecorecrum *) fullcrumptr, &offset, address);
    else {
        assert(0); // retrivecrum - bad enftype
        return NULL;                 /* for lint */
    }
}

    Context *
retrieve(
    typecuc *fullcrumptr,
    Tumbler *address,
    int      index)
    /* index:: used when enftype == SPAN or POOM */
{
    typedsp offset;

    clear(&offset, sizeof(typedsp));
    switch (fullcrumptr->cenftype) {
    case GRAN:
        return findcbcseq((typecorecrum *) fullcrumptr, &offset, address);
    case SPAN:
    case POOM:
        return findcbcnd((typecorecrum *) fullcrumptr, &offset, address, index);
    default:
        assert(0); // retrieve - bad enftype
        return NULL;
    }
}

    static Context *
retrieveinarea(
    typecuc            *fullcrumptr,
    Tumbler            *span1start,
    Tumbler            *span1end,
    int                 index1,
    Tumbler            *span2start,
    Tumbler            *span2end,
    int                 index2,
    typebottomcruminfo *infoptr)
{
/* foo("entering retrieveinarea\n"); */
    typedsp offset;
    clear(&offset, sizeof(offset));

    Context *context = NULL;

    switch (fullcrumptr->cenftype) {
    case SPAN:
    case POOM:
        findcbcinarea2d((typecorecrum *) fullcrumptr, &offset, span1start, span1end, index1, span2start, span2end,
                        index2, &context, infoptr);
        break;
    default:
/* L("%s\n", enftypestring (fullcrumptr->cenftype)); */
        assert(0); // retrieveinarea - wrong enftype
    }
/* foo("leaving retrieveinarea\n"); */

    return context;
}

    Context *
retrieverestricted(
    typecuc     *fullcrumptr,
    typespan    *span1ptr,
    int          index1,
    typespan    *span2ptr,
    int          index2,
    IStreamAddr *docisaptr)
{
    Tumbler span1start, span1end, span2start, span2end;
    type2dbottomcruminfo info, *infoptr;

    if (span1ptr) {
        movetumbler(&span1ptr->stream, &span1start);
        tumbleradd(&span1start, &span1ptr->width, &span1end);
    } else {
        tumblerclear(&span1start);
        tumblerclear(&span1end);
    }

    if (span2ptr) {
        movetumbler(&span2ptr->stream, &span2start);
        tumbleradd(&span2start, &span2ptr->width, &span2end);
    } else {
        tumblerclear(&span2start);
        tumblerclear(&span2end);
    }

    if (docisaptr) {
        movetumbler(docisaptr, &info.homedoc /* shouldberestrictiondoc */ );
        infoptr = &info;
    } else {
        infoptr = NULL;
    }

    return retrieveinarea(fullcrumptr, &span1start, &span1end, index1, &span2start, &span2end, index2,
                          (typebottomcruminfo *) infoptr);
}

    static Context *
findlastcbcseq(
    typecorecrum *fullcrumptr)
{
    Tumbler offset;
    tumblerclear(&offset);

    typecorecrum *ptr;
    for (ptr = fullcrumptr; ptr; ptr = findleftson((typecuc *) ptr)) {
        for (; getrightbro(ptr); ptr = ptr->rightbro)
            tumbleradd(&offset, &ptr->cwid.dsas[WIDTH], &offset);

        if (ptr->height == 0)
            return makecontextfromcbc((typecbc *) ptr, (typewid *) &offset);
    }

    assert(0); // in findlastcbcseq couldn't find anything
    return NULL;                     /* for lint */
}

    static bool
crumintersectsspanseq(
    typecorecrum *crumptr,
    Tumbler      *offsetptr,
    Tumbler      *spanstart,
    Tumbler      *spanend)
{
    if (iszerotumbler(&crumptr->cwid.dsas[WIDTH]))
        return false;

    return (whereoncrum(crumptr, (typewid *) offsetptr, spanstart, WIDTH) < ONMYRIGHTBORDER)
            && (whereoncrum(crumptr, (typewid *) offsetptr, spanend, WIDTH) >
                /*=*/ ONMYLEFTBORDER);
}

    static void
findcbcinspanseq(
    typecorecrum *crumptr,
    typewid      *offsetptr,
    Tumbler      *spanstart,
    Tumbler      *spanend,
    Context     **headptr)
{
    typewid localoffset;
    Context *context;

    movewisp(offsetptr, &localoffset);
    for (; crumptr; crumptr = getrightbro(crumptr)) {
        if (!crumintersectsspanseq(crumptr, (Tumbler *) & localoffset, spanstart, spanend)) {
            dspadd(&localoffset, &crumptr->cwid, &localoffset, (int) crumptr->cenftype);
            continue;
        }

        if (crumptr->height == 0) {
            context = makecontextfromcbc((typecbc *) crumptr, offsetptr);
            oncontextlistseq(headptr, context);
        } else {
            findcbcinspanseq(findleftson((typecuc *) crumptr), &localoffset, spanstart, spanend, headptr);
        }

        dspadd(&localoffset, &crumptr->cwid, &localoffset, (int) crumptr->cenftype);
    }
}

    Context *
retrieveinspan(
    typecuc *fullcrumptr,
    Tumbler *spanstart,
    Tumbler *spanend,
    int      index)
{
    typedsp offset;
    clear(&offset, sizeof(offset));

    Context *context = NULL;

    switch (fullcrumptr->cenftype) {
    case GRAN:
        findcbcinspanseq((typecorecrum *) fullcrumptr, &offset, spanstart, spanend, &context);
        if (tumblercmp(spanend, &fullcrumptr->cwid.dsas[WIDTH]) == GREATER) {
            Context *c = findlastcbcseq((typecorecrum *) fullcrumptr);
            oncontextlistseq(&context, c);
        }
        return context;
    default:
        assert(0); // retrieveinspan - wrong enftype
        return NULL;
    }
}

/* sets grasp & reach from ptr & offset */
/* reach may be NULL so that we won't set it */
    void
prologuend(
    typecorecrum *ptr,
    typedsp      *offset,
    typedsp      *grasp,
    typedsp      *reach)
{
    dspadd(offset, &ptr->cdsp, grasp, (int) ptr->cenftype);
    if (reach)
        dspadd(grasp, &ptr->cwid, reach, (int) ptr->cenftype);
}

#define intervalcmppart1(left,address) cmp = tumblercmp ((address), (left)); if (cmp == LESS) return (TOMYLEFT); else if (cmp == EQUAL) return (ONMYLEFTBORDER);

#define intervalcmppart2(right,address) cmp = tumblercmp ((address), (right)); if (cmp == LESS) return (THRUME); else if (cmp == EQUAL) return (ONMYRIGHTBORDER); else return (TOMYRIGHT);

    int
whereoncrum(
    typecorecrum *ptr,
    typewid      *offset,
    Tumbler      *address,
    int           index)
/* speed up by subsuming intervalcmp */
    /* index:: used when enftype == SPAN or POOM */
{
    Tumbler left, right;
    int cmp;

    switch (ptr->cenftype) {
    case GRAN:
        tumbleradd(&offset->dsas[WIDTH], &ptr->cwid.dsas[WIDTH], &right);
        return intervalcmp(&offset->dsas[WIDTH], &right, address);

    case SPAN:
    case POOM:
        tumbleradd(&offset->dsas[index], &ptr->cdsp.dsas[index], &left);
        cmp = tumblercmp(address, &left);
        if (cmp == LESS) {
            return TOMYLEFT;
        } else if (cmp == EQUAL) {
            return ONMYLEFTBORDER;
        }

/* intervalcmppart1(&left,address); */
        tumbleradd(&left, &ptr->cwid.dsas[index], &right);
        cmp = tumblercmp(address, &right);
        if (cmp == LESS) {
            return THRUME;
        } else if (cmp == EQUAL) {
            return ONMYRIGHTBORDER;
        } else {
            return TOMYRIGHT;
        }

/* intervalcmppart2(&right,address); */
/* #ifndef DISTRIBUTION assert(0); "whereoncrum:can't get here" #else assert(0); #endif */
/* 
 * tumbleradd(&offset->dsas[index],&ptr->cdsp.dsas[index], &left); tumbleradd 
 * (&left, &ptr->cwid.dsas[index], &right); return (intervalcmp (&left,
 * &right, address)); */
    default:
        assert(0); // whereoncrum: bad enftype
    }

    assert(0); // whereoncrum: can't get here either
    return 0;                        /* for lint */
}

---