Return to huff.c CVS log

Up to [Research Unix] / researchv10no / libc / gen

Annotation of researchv10no/libc/gen/huff.c, revision 1.1

1.1     ! root        1: /*  This program gets a histogram of elements that consist
        !             2: of a pointer to a char[] and a probability or number of occurances
        !             3: for each.  The size of the char[] is up to you, you pass back
        !             4: a pointer to it (and you make it in the first place in the loading
        !             5: routine, called getstuf(**char,*float)  At the end, you will
        !             6: be presented with a NODE * pointer to the head of both the
        !             7: linked list and the top of the huffman code tree.  The linked
        !             8: list is in order of generation, from most likely to least,
        !             9: including the internodes as well as terminal nodes.  The tree
        !            10: is a tree, naturally...  
        !            11: 
        !            12:        Written by James Johnston, AT&T Bell Labs, 6/2/87.  
        !            13:        Copyrighted code, all rights reserved to AT&T per
        !            14:        employment agreement, etc, etc, etc                     */
        !            15: 
        !            16: #include <stdio.h>
        !            17: #include <huff.h>
        !            18: 
        !            19: static int compar();
        !            20: static NODE *mknd(), *loadall(), *putone(), *taketwo();
        !            21: double log();
        !            22: 
        !            23: NODE *
        !            24: huff(inrout)
        !            25: int ( *inrout)();
        !            26: {
        !            27:        NODE * active, * result, * tmp;
        !            28:        NODE ** tmps, ** arhead;
        !            29:        int i, j, k, max;
        !            30: 
        !            31:        active=(NODE *)0;
        !            32:        result=(NODE *)0;
        !            33: 
        !            34:        active=loadall(inrout);
        !            35:        /* loadall returns a pointer to the beginning */
        !            36:        tmp=active;
        !            37:        max=0;
        !            38:        /* count how many */
        !            39:        while ( tmp != (NODE *) 0 ) {
        !            40:                tmp=tmp->to;
        !            41:                max++;
        !            42:        }
        !            43:        /* load pointer array for sorting */
        !            44:        arhead= (NODE **) malloc(max*sizeof(NODE *));
        !            45:        if (arhead == (NODE **) 0 ) {
        !            46:                fprintf(stderr,"can't malloc sorting array");
        !            47:                exit();
        !            48:        }
        !            49:        tmp = active;
        !            50:        tmps=arhead;
        !            51:        while ( tmp != (NODE *) 0 ) {
        !            52:                *(tmps++)=tmp;
        !            53:                tmp = tmp -> to;
        !            54:        }
        !            55:        qsort(arhead,max,sizeof(NODE *), compar);
        !            56:        /* relink list */
        !            57: 
        !            58:        active= *arhead;
        !            59:        active->from=(NODE *) 0;
        !            60:        active->to=arhead[1];
        !            61:        for ( i=1; i<max-1; i++) {
        !            62:                arhead[i]->to=arhead[i+1];
        !            63:                arhead[i]->from=arhead[i-1];
        !            64:        }
        !            65:        arhead[max-1]->to=(NODE *)0;
        !            66:        arhead[max-1]->from=arhead[max-2];
        !            67:        /* now it's reloaded */
        !            68: 
        !            69:        free(arhead);
        !            70: 
        !            71:        /* this takes the first two elements of the list away, and puts
        !            72:        a third one in wherever it fits, in order */
        !            73:        while  (active->to != (NODE *) 0 ) {
        !            74:                tmp=taketwo(&active,&result);
        !            75:                active=putone(tmp,active);
        !            76:        }
        !            77:        /* now we're done, put the one remaining on the result list */
        !            78:        result->from=active;
        !            79:        active->to=result;
        !            80:        active->from= (NODE *) 0;
        !            81:        result=active;
        !            82:        active=(NODE *) 0;
        !            83: 
        !            84: 
        !            85: 
        !            86:        return result;
        !            87: }
        !            88: 
        !            89: static NODE *
        !            90: putone(new, active)
        !            91: NODE * new, *active;
        !            92: {
        !            93:        /* this puts tmp into place in the active list, in order of
        !            94:        probability.  This relies utterly on the list being sorted already,
        !            95:        and failure to do so will cause utter chaos*/
        !            96: 
        !            97:        NODE * tmp, *after, *tmpp;
        !            98: 
        !            99:        tmp=active;
        !           100: 
        !           101:        after = (NODE *) 0;
        !           102:        while ( ( tmp != (NODE *)0 ) &&
        !           103:            (new->prob > tmp->prob ) ) {
        !           104:                after=tmp;
        !           105:                tmp=tmp->to;
        !           106:        }
        !           107:        /* goes until you find an element more probable or you get to the end*/
        !           108:        /* now, insert tmp into the list, being careful if it's first */
        !           109:        if (after == (NODE *) 0 ) {
        !           110:                new->from=(NODE *) 0;
        !           111:                new->to=active;
        !           112:                if ( active != (NODE *) 0 ) active->from=new;
        !           113:                return new;
        !           114:                /* put it first */
        !           115:        }
        !           116:        tmp=after->to;
        !           117:        /* tmp is now the one to put after the new one */
        !           118:        if ( tmp != (NODE *) 0 ) tmp->from=new;
        !           119:        new->to=tmp;
        !           120:        /* now set up the before node, in variable after.  sheesh! */
        !           121:        after->to=new;
        !           122:        new->from=after;
        !           123:        return active;
        !           124: }
        !           125: 
        !           126: static NODE *
        !           127: taketwo(actp,resp)
        !           128: NODE ** actp, ** resp;
        !           129: {
        !           130:        NODE * active, *tmp, *result, * tmp1;
        !           131: 
        !           132:        active = *actp;
        !           133:        /* temporary active pointer */
        !           134:        result = *resp;
        !           135:        /* temp result pointer */
        !           136:        tmp=mknd();
        !           137:        /* make new node */
        !           138:        tmp->ldad=active;
        !           139:        /* load left father */
        !           140:        tmp->rdad=active->to;
        !           141:        /* load right father */
        !           142:        active->kid=tmp;
        !           143:        active->to->kid=tmp;
        !           144:        /* load kid node into fathers */
        !           145:        tmp->prob=active->prob+active->to->prob;
        !           146:        /* sum probabilities of fathers into the kid*/
        !           147:        tmp->datump=(char *) 0;
        !           148:        /* make sure that there's no character pointer in the kid */
        !           149:        *actp=active->to->to;
        !           150:        /* set the new head of the active list */
        !           151:        if ( *actp != (NODE *) 0 ) (*actp)->from=(NODE *) 0;
        !           152:        /* make the from of the new active pointer null unless there's
        !           153:                no longer an active pointer due to end of algorithm*/
        !           154: 
        !           155:        *resp=active->to;
        !           156:        /* remember which was second in line */
        !           157:        /* and set the new result pointer */
        !           158:        active->to=result;
        !           159:        if ( result != (NODE *) 0 ) result->from=active;
        !           160:        /* put head of active to head of result. */
        !           161: 
        !           162:        (*resp)->to=active;
        !           163:        /* point next on result stack to new entry */
        !           164:        active->from=(*resp);
        !           165:        (*resp)->from=(NODE *)0;
        !           166:        return tmp;
        !           167:        /* return the new, unattached, node */
        !           168: }
        !           169: 
        !           170: static NODE *
        !           171: mknd()
        !           172: {
        !           173:        NODE *temp;
        !           174:        if ( (temp=(NODE *)malloc(sizeof(NODE) ) ) == NULL )
        !           175:        {       
        !           176:                fprintf(stderr,"could not make NODE");
        !           177:                exit();
        !           178:        }
        !           179:        return temp;
        !           180: }
        !           181: static NODE * 
        !           182: loadall(inrout)
        !           183: int ( *inrout)();
        !           184: {
        !           185:        float tprob;
        !           186:        char * tdp;
        !           187:        NODE * tmp, *last,* first, * backp;
        !           188:        last = (NODE *)0;
        !           189:        while ( ((*inrout)(&tdp,&tprob) != 0) ) {
        !           190:                tmp = mknd();
        !           191:                first=tmp;
        !           192:                /* first keeps track of what will go into the return value,
        !           193:                                                                                                        eventually*/
        !           194:                tmp->to=last;
        !           195:                if (last != ( NODE * ) 0 ) last->from=tmp;
        !           196:                last=tmp;
        !           197:                tmp->datump=tdp;
        !           198:                tmp->prob=tprob;
        !           199:                tmp->ldad=tmp->rdad=tmp->kid=(NODE *) 0;
        !           200:        }
        !           201:        tmp->from = ((NODE *)0);
        !           202:        return first;
        !           203: }
        !           204: static int 
        !           205: compar(a,b)
        !           206: NODE ** a, ** b;
        !           207: {
        !           208:        if ( (*a)->prob > (*b)->prob ) return 1;
        !           209:        if ( (*a)->prob < (*b)->prob ) return -1;
        !           210:        return 0;
        !           211: }
        !           212: 

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