Return to heap.c CVS log

Up to [CSRG BSD Unix] / 40BSD / cmd / cifplot

Annotation of 40BSD/cmd/cifplot/heap.c, revision 1.1

1.1     ! root        1: /*******************************************************************
        !             2: *                                                                  *
        !             3: *    File: CIFPLOT/heap.c                                          *
        !             4: *    Written by Dan Fitzpatrick                                    *
        !             5: *    copyright 1980 -- Regents of the University of California     *
        !             6: *                                                                  *
        !             7: ********************************************************************/
        !             8: 
        !             9: #include <stdio.h>
        !            10: #include "defs.h"
        !            11: #include "structs.h"
        !            12: #include "out_structs.h"
        !            13: 
        !            14: #define INITHSIZE      256
        !            15: #define FATHER(a)      ((a)-1)/2
        !            16: #define LEFTSON(a)     ((a)+1)*2 - 1
        !            17: #define RIGHTSON(a)    ((a)+1)*2
        !            18: 
        !            19: #define COMPARE(x,s)   h.h[x]->min - h.h[s]->min
        !            20: #define LESSEQUAL(x,s) h.h[x]->min <= h.h[s]->min
        !            21: #define GREATERTHAN(x,s)       h.h[x]->min > h.h[s]->min
        !            22: #define SWITCH(x,y)    { HTemp = h.h[x]; h.h[x] = h.h[y]; h.h[y] = HTemp; }
        !            23: 
        !            24: instance *HTemp;
        !            25: 
        !            26: typedef struct temp723 {
        !            27:        instance **h;
        !            28:        int size,n;
        !            29:        } Heap;
        !            30:   
        !            31: int UnActMark = -INFINITY;
        !            32: 
        !            33: Heap h;
        !            34: 
        !            35: InitHeap()
        !            36: /* Allocate space and initalize pointers */
        !            37: {
        !            38:    h.h = (instance **) alloc(INITHSIZE*sizeof(instance *));
        !            39:    h.n = 0;
        !            40:    h.size = INITHSIZE;
        !            41:    }
        !            42: 
        !            43: PutHeap(v)
        !            44: instance *v;
        !            45: /* Put what v points to into a heap where f is a function
        !            46:    that compares values. */
        !            47: {
        !            48:     register int a,f;
        !            49: 
        !            50:     if(h.n == h.size) {
        !            51:        h.size *= 2;
        !            52:        h.h = (instance **) expand(h.h,h.size*sizeof(instance *));
        !            53:        }
        !            54:     h.h[h.n] = v;
        !            55:     a = h.n++;
        !            56:     f = FATHER(a);
        !            57:     while(a > 0  && GREATERTHAN(f,a)) {
        !            58:        SWITCH(f,a);
        !            59:        a = f;
        !            60:        f = FATHER(a);
        !            61:        }
        !            62:     }
        !            63: 
        !            64: instance *
        !            65: PeekHeap()
        !            66: {
        !            67:     if(h.n == 0) return(NIL);
        !            68:     return(h.h[0]);
        !            69:     }
        !            70: 
        !            71: instance *
        !            72: GetHeap()
        !            73: {
        !            74:     register instance *hold;
        !            75: 
        !            76:     if(h.n != 0) {
        !            77:        hold = h.h[0];
        !            78:        --h.n;
        !            79:        SWITCH(0,h.n);
        !            80:        SortHeap(0);
        !            81:        return(hold);
        !            82:        }
        !            83:      else
        !            84:        return(NIL);
        !            85:     }
        !            86: 
        !            87: SortHeap(a)
        !            88: register int a;
        !            89: {
        !            90:     register int r,l;
        !            91: 
        !            92:     while(1) {
        !            93:        if((l=LEFTSON(a)) >= h.n) return;
        !            94:        if((r=RIGHTSON(a)) >= h.n) {
        !            95:                if(GREATERTHAN(a,l))
        !            96:                        SWITCH(a,l);
        !            97:                return;
        !            98:                }
        !            99:        if(LESSEQUAL(a,r) && LESSEQUAL(a,l)) return;
        !           100:        if(LESSEQUAL(l,r)) {
        !           101:                SWITCH(a,l);
        !           102:                a = l;
        !           103:                }
        !           104:             else {
        !           105:                SWITCH(a,r);
        !           106:                a = r;
        !           107:                }
        !           108:        }
        !           109:     }
        !           110: 
        !           111: #define UHASH(x)       ABS((((int) x) % UTBLSIZE))
        !           112: 
        !           113: List UnAct[UTBLSIZE];
        !           114: int UnActCount = 111;
        !           115: 
        !           116: InitUnAct()
        !           117: {
        !           118:     int i;
        !           119:     for(i=0;i<UTBLSIZE;i++)
        !           120:        InitList(&(UnAct[i]));
        !           121:     UnActCount = 0;
        !           122:     }
        !           123: 
        !           124: FindNext(n)
        !           125: register int n;
        !           126: {
        !           127:     register instance *p;
        !           128:     register int i;
        !           129: 
        !           130:     for(i=0;i<16;i++) {
        !           131:        p = (instance *) &(UnAct[UHASH(n+i)]);
        !           132:        if(p->Link != NIL && p->Link->min == n+i) {
        !           133:            NextUnAct = MIN(n+i,Top);
        !           134:            return(NextUnAct);
        !           135:            }
        !           136:        }
        !           137:     NextUnAct = MIN(n+i,Top);
        !           138:     return(NextUnAct);
        !           139:     }
        !           140: 
        !           141: PutUnAct(e)
        !           142: instance *e;
        !           143: {
        !           144:     register instance *p;
        !           145:     register List *l;
        !           146: 
        !           147:     if(e->min < UnActMark)
        !           148:        /*
        !           149:        if(e->min == UnActMark-1)
        !           150:            /* Let's ignore floating point round off errors */
        !           151:            /*
        !           152:            e->min = UnActMark;
        !           153:          else
        !           154:          */
        !           155:            Error("Element submitted past deadline in PutUnAct",INTERNAL);
        !           156:     UnActCount++;
        !           157:     l = &(UnAct[UHASH(e->min)]);
        !           158:     e->Link = NIL;
        !           159:     if(l->Link == NIL) {
        !           160:        l->Link = (Element *) e;
        !           161:        return;
        !           162:        }
        !           163:     for(p = (instance *) l; p->Link != NIL; p=p->Link)
        !           164:        if(e->min <= p->Link->min) {
        !           165:            e->Link = p->Link;
        !           166:            p->Link = e;
        !           167:            return;
        !           168:            }
        !           169:     p->Link = e;
        !           170:     return;
        !           171:     }
        !           172: 
        !           173: instance *
        !           174: GetUnAct(i)
        !           175: int i;
        !           176: {
        !           177:     register instance *e;
        !           178:     register List *l;
        !           179: 
        !           180:     if(i < UnActMark)
        !           181:        Error("GetUnAct called in bad order",INTERNAL);
        !           182:     UnActMark = i;
        !           183:     l = &(UnAct[UHASH(i)]);
        !           184: 
        !           185:     e = (instance *) l->Link;
        !           186:     if(e==NIL) return(NIL);
        !           187:     if(e->min == i) {
        !           188:        l->Link = (Element *) e->Link;
        !           189:        e->Link = NIL;
        !           190:        --UnActCount;
        !           191:        return(e);
        !           192:        }
        !           193:     if(e->min > i) {
        !           194:        return(NIL);
        !           195:        }
        !           196:     Error("UnActiveList is out of order",INTERNAL);
        !           197:     return(NIL);
        !           198:     }
        !           199: 
        !           200: CheckUnAct() {
        !           201:     int i;
        !           202:     for(i=0;i<UTBLSIZE;i++)
        !           203:        if(UnAct[i].Link!=NIL) {
        !           204:            fprintf(stderr,"UnActiveList is NOT empty\n");
        !           205:            return;
        !           206:            }
        !           207:     fprintf(stderr,"the un active list is empty\n");
        !           208:     if(UnActCount != 0) {
        !           209:        fprintf(stderr,"the count is %d\n",UnActCount);
        !           210:        }
        !           211:     }

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