Return to list.c CVS log

Up to [Research Unix] / researchv10no / cmd / cfront / libstring

Annotation of researchv10no/cmd/cfront/libstring/list.c, revision 1.1

1.1     ! root        1: #include "list.h"
        !             2: 
        !             3: LstHead::~LstHead() {}
        !             4: 
        !             5: void   // don't specify head or tail
        !             6: LstHead::insert(lnk *nl)
        !             7: {
        !             8:        if (t) {
        !             9:                nl->nxt = h();
        !            10:                nl->prv = t;
        !            11:                h()->prv = nl;
        !            12:                t->nxt = nl;
        !            13:        } else t = nl->nxt = nl->prv = nl;
        !            14:        sz++;
        !            15: }
        !            16: 
        !            17: lnk *
        !            18: LstHead::get()
        !            19: {
        !            20:        if (!t)
        !            21:                return NULL;
        !            22:        lnk     *oh = h();
        !            23:        if ( t == h() )
        !            24:                t = NULL;
        !            25:        else {
        !            26:                lnk     *nh = oh->nxt;
        !            27:                nh->prv = t;
        !            28:                t->nxt = nh;
        !            29:        }
        !            30:        if (cache == oh) cache = NULL;
        !            31:        else cacheNo--;
        !            32:        sz--;
        !            33:        return oh;
        !            34: }
        !            35: 
        !            36: lnk *
        !            37: LstHead::unput()
        !            38: {
        !            39:        if (!t)
        !            40:                return NULL;
        !            41:        lnk     *ot = t;
        !            42:        lnk     *hh = h();
        !            43:        if ( h() == ot )
        !            44:                t = NULL;
        !            45:        else {
        !            46:                lnk     *nt = t->prv;
        !            47:                hh->prv = t = nt;
        !            48:                t->nxt = hh;
        !            49:        }
        !            50:        if (cache == ot) cache = NULL;
        !            51:        sz--;
        !            52:        return ot;
        !            53: }
        !            54: 
        !            55: lnk*
        !            56: LstHead::getAt(int ii)
        !            57: {
        !            58:        register        count;
        !            59:        int     forward;
        !            60:        register lnk*   from;
        !            61:        if (ii >= sz) abort();  // out of bounds
        !            62:        if (ii >= sz - ii) {
        !            63:                count = sz - ii - 1;
        !            64:                forward = FALSE;
        !            65:                from = t;
        !            66:        } else {
        !            67:                count = ii;
        !            68:                forward = TRUE;
        !            69:                from = h();
        !            70:        }
        !            71:        if (cache) {
        !            72:                register        altCount = ii - cacheNo;
        !            73:                register        a1 = altCount > 0 ? altCount : -altCount;
        !            74:                if (a1 < count) {
        !            75:                        count = a1;
        !            76:                        forward = a1 == altCount;
        !            77:                        from = cache;
        !            78:                }
        !            79:        }
        !            80:        if (forward)
        !            81:                while (count--)
        !            82:                        from = from->nxt;
        !            83:        else
        !            84:                while (count--)
        !            85:                        from = from->prv;
        !            86:        cache = from;
        !            87:        cacheNo = ii;
        !            88:        return from;
        !            89: }
        !            90: 
        !            91: void
        !            92: List::sepWork()
        !            93: {
        !            94:        abort();        // Only derived functions should be called.
        !            95: }
        !            96: void
        !            97: List::newIt(lstiter *a, int i)
        !            98: {
        !            99:        a->nextIt = fI;
        !           100:        a->aList = this;
        !           101:        fI = a;
        !           102:        a->index = i;
        !           103:        a->pred = i == 0 || i == length() ? tail() : it->getAt(i - 1);
        !           104: }
        !           105: void
        !           106: List::removeIt(lstiter *a)
        !           107: {
        !           108:        if (fI == a)
        !           109:                fI = a->nextIt;
        !           110:        else {
        !           111:                for (register lstiter* anIt = fI; anIt->nextIt != a;
        !           112:                                anIt = anIt->nextIt) ;
        !           113:                anIt->nextIt = a->nextIt;
        !           114:        }
        !           115:        a->nextIt = 0;
        !           116:        a->aList = 0;
        !           117:        a->pred = 0;
        !           118:        a->index = 0;
        !           119: }
        !           120: List::~List()
        !           121: {
        !           122:        if (--it->refCount == 0)
        !           123:                delete it;
        !           124:        register lstiter*       s;
        !           125:        for (register lstiter* anIt = fI; anIt; anIt = s) {
        !           126:                s = anIt->nextIt;
        !           127:                anIt->nextIt = 0;
        !           128:                anIt->aList = 0;
        !           129:                anIt->pred = 0;
        !           130:                anIt->index = 0;
        !           131:        }
        !           132: }
        !           133: List&
        !           134: List::operator=(List& ll)
        !           135: {
        !           136:        LstHead *head = ll.it;
        !           137:        head->refCount++;
        !           138:        if (--it->refCount == 0)
        !           139:                delete it;
        !           140:        it = head;
        !           141:        for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
        !           142:                anIt->index = 0;
        !           143:                anIt->pred = tail();
        !           144:        }
        !           145:        return *this;
        !           146: }
        !           147: List&
        !           148: List::unget(lnk* aLink)
        !           149: {
        !           150:        separate();
        !           151:        it->unget(aLink);
        !           152:        for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
        !           153:                if (anIt->index == 0)
        !           154:                        anIt->pred = aLink;
        !           155:                anIt->index++;
        !           156:        }
        !           157:        return *this;
        !           158: }
        !           159: List&
        !           160: List::put(lnk* aLink)
        !           161: {
        !           162:        separate();
        !           163:        it->put(aLink);
        !           164:        for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt)
        !           165:                if (anIt->index == 0)
        !           166:                        anIt->pred = aLink;
        !           167:        return *this;
        !           168: }
        !           169: 
        !           170: lnk*
        !           171: List::get()
        !           172: {
        !           173:        separate();
        !           174:        lnk*    ans = it->get();
        !           175:        for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
        !           176:                if (anIt->index <= 1)   // 0 in case the List is empty
        !           177:                        anIt->pred = tail();    // tail() returns NULL
        !           178:                if (anIt->index > 0)
        !           179:                        anIt->index--;
        !           180:        }
        !           181:        return ans;
        !           182: }
        !           183: 
        !           184: lnk*
        !           185: List::unput()
        !           186: {
        !           187:        separate();
        !           188:        lnk*    ans = it->unput();
        !           189:        for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
        !           190:                if (anIt->pred == ans)  // head or tail
        !           191:                        anIt->pred = tail();
        !           192:                if (anIt->index > length())
        !           193:                        anIt->index--;
        !           194:        }
        !           195:        return ans;
        !           196: }
        !           197: 
        !           198: lstiter&
        !           199: lstiter::operator=(lstiter& a)
        !           200: {
        !           201:        if (!a.aList)
        !           202:                abort();        /* invalid list iterator */
        !           203:        if (aList) aList->removeIt(this);
        !           204:        a.aList->newIt(this);
        !           205:        pred = a.pred;
        !           206:        index = a.index;
        !           207:        return *this;
        !           208: }
        !           209: lstiter::lstiter(lstiter& a)
        !           210: {
        !           211:        if (!a.aList)
        !           212:                abort();        /* invalid list iterator */
        !           213:        a.aList->newIt(this);
        !           214:        pred = a.pred;
        !           215:        index = a.index;
        !           216: }
        !           217: lstiter::lstiter(List& a, int i)
        !           218: {
        !           219:        a.newIt(this, i);
        !           220: }
        !           221: lstiter::~lstiter()
        !           222: {
        !           223:        if (aList) aList->removeIt(this);
        !           224: }
        !           225: void
        !           226: lstiter::reset(int i)
        !           227: {
        !           228:        index = i;
        !           229:        pred = i == 0 || i == aList->length() ? aList->tail() :
        !           230:                aList->it->getAt(i - 1);
        !           231: }
        !           232: void
        !           233: lstiter::insert(lnk *x)
        !           234: {
        !           235:        aList->separate();
        !           236:        if (pred) {
        !           237:                x->init(pred, pred->nxt);
        !           238:                pred->nxt->prv = x;
        !           239:                pred->nxt = x;
        !           240:                for (register lstiter *other = aList->firstIt(); other;
        !           241:                                other = other->nextIt)
        !           242:                        if (this != other && index < other->index)
        !           243:                                other->index++;
        !           244:        } else {
        !           245:                x->init(x, x);
        !           246:                for (register lstiter *other = aList->firstIt(); other;
        !           247:                                other = other->nextIt)
        !           248:                        other->pred = x;
        !           249:        }
        !           250:        if (atEnd())
        !           251:                aList->it->t = x;
        !           252:        pred = x;
        !           253:        index++;
        !           254:        aList->it->sz++;
        !           255: }
        !           256: void
        !           257: lstiter::r_insert(lnk *x)
        !           258: {
        !           259:        aList->separate();
        !           260:        for (register lstiter *other = aList->firstIt(); other;
        !           261:                        other = other->nextIt)
        !           262:                if (other != this) {
        !           263:                        if (other->pred == pred)
        !           264:                                other->pred = x;
        !           265:                        if (other->index >= index)
        !           266:                                other->index++;
        !           267:                }
        !           268:        if (pred) {
        !           269:                x->init(pred, pred->nxt);
        !           270:                pred->nxt->prv = x;
        !           271:                pred->nxt = x;
        !           272:        } else {
        !           273:                x->init(x, x);
        !           274:                pred = x;
        !           275:        }
        !           276:        if (atEnd())
        !           277:                aList->it->t = x;
        !           278:        aList->it->sz++;
        !           279: }
        !           280: lnk *
        !           281: lstiter::remove()
        !           282: {
        !           283:        if (r_atEnd())
        !           284:                return NULL;
        !           285:        aList->separate();
        !           286:        lnk     *doomed = pred;
        !           287:        int     oldIndex = index;
        !           288:        if (pred == pred->nxt) {        // this is only item
        !           289:                aList->it->t = 0;
        !           290:                for (register lstiter *anIter = aList->firstIt(); anIter;
        !           291:                                anIter = anIter->nextIt) {
        !           292:                        anIter->pred = 0;
        !           293:                        anIter->index = 0;
        !           294:                }
        !           295:        } else {
        !           296:                if (doomed == aList->it->t)     // deleting tail
        !           297:                        aList->it->t = doomed->prv;
        !           298:                for (register lstiter *anIter = aList->firstIt(); anIter;
        !           299:                                anIter = anIter->nextIt) {
        !           300:                        if (anIter->pred == doomed)
        !           301:                                anIter->pred = doomed->prv;
        !           302:                        if (anIter->index >= oldIndex)
        !           303:                                anIter->index--;
        !           304:                }
        !           305:                pred->nxt = doomed->nxt;
        !           306:                doomed->nxt->prv = pred;
        !           307:        }
        !           308:        aList->it->sz--;
        !           309:        return doomed;
        !           310: }
        !           311: lnk *
        !           312: lstiter::r_remove()
        !           313: {
        !           314:        if (atEnd())
        !           315:                return NULL;
        !           316:        aList->separate();
        !           317:        lnk     *doomed = pred->nxt;
        !           318:        int     deletingHead = doomed == aList->it->h();
        !           319:        if (pred == pred->nxt) {        // this is only item
        !           320:                aList->it->t = 0;
        !           321:                for (register lstiter *anIter = aList->firstIt(); anIter;
        !           322:                                anIter = anIter->nextIt) {
        !           323:                        anIter->pred = 0;
        !           324:                        anIter->index = 0;
        !           325:                }
        !           326:        } else {
        !           327:                if (doomed == aList->it->t)     // deleting tail
        !           328:                        aList->it->t = doomed->prv;
        !           329:                for (register lstiter *anIt = aList->firstIt(); anIt;
        !           330:                                anIt = anIt->nextIt) {
        !           331:                        if (anIt->pred == doomed)
        !           332:                                anIt->pred = doomed->prv;
        !           333:                        if (anIt->index > index) anIt->index--;
        !           334:                }
        !           335:                pred->nxt = doomed->nxt;
        !           336:                doomed->nxt->prv = pred;
        !           337:        }
        !           338:        aList->it->sz--;
        !           339:        return doomed;
        !           340: }
        !           341: lnk *
        !           342: lstiter::next()
        !           343: {
        !           344:        if (atEnd()) return NULL;
        !           345:        pred = pred->nxt;
        !           346:        index++;
        !           347:        return pred;
        !           348: }
        !           349: lnk *
        !           350: lstiter::r_next()
        !           351: {
        !           352:        if (r_atEnd()) return NULL;
        !           353:        lnk     *op = pred;
        !           354:        pred = pred->prv;
        !           355:        index--;
        !           356:        return op;
        !           357: }
        !           358: lnk *
        !           359: lstiter::r_peek()
        !           360: {
        !           361:        if (r_atEnd())
        !           362:                return NULL;
        !           363:        return pred;
        !           364: }
        !           365: lnk *
        !           366: lstiter::peek()
        !           367: {
        !           368:        if (atEnd())
        !           369:                return NULL;
        !           370:        return pred->nxt;
        !           371: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.