![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to huff.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / libc / gen|
Return to huff.c CVS log | Up to [Research Unix] / researchv10no / libc / gen |
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.