Return to queue.c CVS log

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

Annotation of 41BSD/cmd/cifplot/queue.c, revision 1.1

1.1     ! root        1: /*******************************************************************
        !             2: *                                                                  *
        !             3: *    File: CIFPLOT/queue.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 "globals.h"
        !            12: #include "structs.h"
        !            13: #include "out_structs.h"
        !            14: 
        !            15: IMPORT Element *GetList();
        !            16: 
        !            17: InitQueue(q)
        !            18: Queue *q;
        !            19: {
        !            20:     q->QStart = NIL;
        !            21:     }
        !            22: 
        !            23: PutQueue(e,q)
        !            24: Queue *q;
        !            25: Element *e;
        !            26: /* Put element `e' into queue `q' */
        !            27: {
        !            28:     e->Link = NIL;
        !            29:     if(q->QStart == NIL) {
        !            30:        q->QStart = q->QEnd = e;
        !            31:        return;
        !            32:        }
        !            33:     q->QEnd->Link = e;
        !            34:     q->QEnd = e;
        !            35:     return;
        !            36:     }
        !            37: 
        !            38: Element *
        !            39: GetQueue(q)
        !            40: Queue *q;
        !            41: /* Return the element at the front of the queue `q'
        !            42:  * If the queue is empty return NIL */
        !            43: {
        !            44:     register Element *e;
        !            45:     e = q->QStart;
        !            46:     if(q->QStart != NIL) q->QStart = q->QStart->Link;
        !            47:     return(e);
        !            48:     }
        !            49: 
        !            50: CatQueue(q1,q2)
        !            51: Queue *q1,*q2;
        !            52: /* Tack q2 onto the end of q1 */
        !            53: {
        !            54:     if(q1->QStart == NIL)
        !            55:        q1->QStart = q2->QStart;
        !            56:      else
        !            57:        q1->QEnd->Link = q2->QStart;
        !            58:     if(q2->QStart != NIL)
        !            59:        q1->QEnd = q2->QEnd;
        !            60:     }
        !            61: 
        !            62: MoveQueue(q1,q2)
        !            63: Queue *q1,*q2;
        !            64: /* Make q1 point to the same queue as q2 */
        !            65: {
        !            66:     q1->QStart = q2->QStart;
        !            67:     q1->QEnd = q2->QEnd;
        !            68:     }
        !            69: 
        !            70: InitList(l)
        !            71: List *l;
        !            72: {
        !            73:     l->Link = NIL;
        !            74:     }
        !            75: 
        !            76: PutList(e,l,f)
        !            77: List *l;
        !            78: Element *e;
        !            79: real (*f)();
        !            80: /* Insert element `e' into list `l' maintaining the ascending
        !            81:  * order of the list where `f' is a function of two arguments
        !            82:  * giving the ordinality of the elements.
        !            83:  * So if two elements `i' & `j' are compared then
        !            84:  * f(i,j) <= 0 iff i <= j.
        !            85:  * If the ordering doesn't matter substitute 0 for f */
        !            86: {
        !            87:     Element *p;
        !            88: 
        !            89:     e->Link = NIL;
        !            90:     if(f == 0) {
        !            91:        e->Link = l->Link;
        !            92:        l->Link = e;
        !            93:        return;
        !            94:        }
        !            95:     if(l->Link == NIL) {
        !            96:        l->Link = e;
        !            97:        return;
        !            98:        }
        !            99:     
        !           100:     for(p= (Element *) l;p->Link != NIL; p=p->Link)
        !           101:        if((*f)(e,p->Link) <= 0.0) {
        !           102:            e->Link = p->Link;
        !           103:            p->Link = e;
        !           104:            return;
        !           105:            }
        !           106:     p->Link = e;
        !           107:     return;
        !           108:     }
        !           109: 
        !           110: MergeActives(i,list)
        !           111: int i;
        !           112: List *list;
        !           113: {
        !           114:     Element *p,*e;
        !           115: 
        !           116:     if(ActiveEdges[i].Link == NIL) {
        !           117:        ActiveEdges[i].Link = list->Link;
        !           118:        list->Link = NIL;
        !           119:        return;
        !           120:        }
        !           121:     e = GetList(list);
        !           122:     if(e == NIL) return;
        !           123:     
        !           124:     for(p= (Element *) &(ActiveEdges[i]);p->Link != NIL; p=p->Link)
        !           125:        if(((edge *) e)->iy <= ((edge *) p->Link)->iy) {
        !           126:            e->Link = p->Link;
        !           127:            p->Link = e;
        !           128:            e = GetList(list);
        !           129:            if(e == NIL) return;
        !           130:            }
        !           131:     p->Link = e;
        !           132:     e->Link = list->Link;
        !           133:     list->Link = NIL;
        !           134:     return;
        !           135:     }
        !           136: 
        !           137: Element *
        !           138: GetList(l)
        !           139: List *l;
        !           140: /* Return the element at the front of the list `l' */
        !           141: {
        !           142:     register Element *e;
        !           143:     e = l->Link;
        !           144:     if(e != NIL) l->Link = l->Link->Link;
        !           145:     return(e);
        !           146:     }
        !           147: 
        !           148: Element *
        !           149: PeekList(l)
        !           150: List *l;
        !           151: /* return pointer to first element in list without removing it */
        !           152: {
        !           153:     return(l->Link);
        !           154:     }
        !           155: 
        !           156: SortList(l,f)
        !           157: List *l;
        !           158: real (*f)();
        !           159: /* sort list l with fuction f as in PutList */
        !           160: {
        !           161:     register Element *e,*t1,*t2;
        !           162:     int sorted;
        !           163: 
        !           164:     if( (l->Link == NIL) || (l->Link->Link == NIL) ) return;
        !           165:     sorted = 0;
        !           166:     while(!sorted) {
        !           167:        sorted = 1;
        !           168:        for(e = (Element *) l; e->Link->Link != NIL; e=e->Link)
        !           169:            if((*f)(e->Link,e->Link->Link) > 0.0) {
        !           170:                t1 = e->Link;
        !           171:                t2 = t1->Link;
        !           172:                t1->Link = t2->Link;
        !           173:                t2->Link = t1;
        !           174:                e->Link = t2;
        !           175:                sorted = 0;
        !           176:                }
        !           177:        }
        !           178:     }
        !           179: 
        !           180: int sortcnt = 0;
        !           181: 
        !           182: SortActives(i)
        !           183: int i;
        !           184: /* Does a bubble sort on ActiveList[i] */
        !           185: {
        !           186:     register Element *e,*t1,*t2;
        !           187:     Element *last;
        !           188:     int sorted;
        !           189: 
        !           190:     if( (ActiveEdges[i].Link == NIL) || (ActiveEdges[i].Link->Link == NIL) ) return;
        !           191:     sorted = 0;
        !           192:     last = NIL;
        !           193:     while(!sorted) {
        !           194:        sorted = 1;
        !           195:        sortcnt++;
        !           196:        for(e = (Element *) &(ActiveEdges[i]); e->Link->Link != last; e=e->Link) {
        !           197:            if(((edge *) e->Link)->iy > ((edge *) e->Link->Link)->iy) {
        !           198:                change[i] = 1;
        !           199:                t1 = e->Link;
        !           200:                t2 = t1->Link;
        !           201:                t1->Link = t2->Link;
        !           202:                t2->Link = t1;
        !           203:                e->Link = t2;
        !           204:                sorted = 0;
        !           205:                }
        !           206:            }
        !           207:        last = t1;
        !           208:        }
        !           209:     }
        !           210: 
        !           211: SortSummary()
        !           212: {
        !           213:     printf("%d Sort Scans\n",sortcnt);
        !           214:     }

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