Lines Matching refs:tree
13 * Each code tree is stored in a compressed form which is itself
87 /* The static literal tree. Since the bit lengths are imposed, there is no
89 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
94 /* The static distance tree. (Actually a trivial tree since all codes use
118 const ct_data *static_tree; /* static tree or NULL */
121 int elems; /* max number of elements in the tree */
140 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
142 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
144 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
145 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
163 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
164 /* Send a code of the given tree. c and tree must not have side effects */
167 # define send_code(s, c, tree) \
169 send_bits(s, tree[c].Code, tree[c].Len); }
238 int n; /* iterates over tree elements */
244 /* number of codes at each bit length for an optimal tree */
290 /* Construct the codes of the static literal tree */
298 * tree construction to get a canonical Huffman tree (longest code
303 /* The static distance tree is trivial: */
379 * Initialize the tree data structures for a new zlib stream.
412 int n; /* iterates over tree elements */
425 /* Index within the heap array of least frequent node in the Huffman tree */
432 #define pqremove(s, tree, top) \
436 pqdownheap(s, tree, SMALLEST); \
440 * Compares to subtrees, using the tree depth as tie breaker when
443 #define smaller(tree, n, m, depth) \
444 (tree[n].Freq < tree[m].Freq || \
445 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
448 * Restore the heap property by moving down the tree starting at node k,
453 local void pqdownheap(s, tree, k)
455 ct_data *tree; /* the tree to restore */
463 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
467 if (smaller(tree, v, s->heap[j], s->depth)) break;
472 /* And continue down the tree, setting j to the left son of k */
479 * Compute the optimal bit lengths for a tree and update the total bit length
482 * above are the tree nodes sorted by increasing frequency.
490 tree_desc *desc; /* the tree descriptor */
492 ct_data *tree = desc->dyn_tree;
499 int n, m; /* iterate over the tree elements */
508 * overflow in the case of the bit length tree).
510 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
514 bits = tree[tree[n].Dad].Len + 1;
516 tree[n].Len = (ush)bits;
517 /* We overwrite tree[n].Dad which is no longer needed */
524 f = tree[n].Freq;
537 s->bl_count[bits]--; /* move one leaf down the tree */
556 if ((unsigned) tree[m].Len != (unsigned) bits) {
557 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
558 s->opt_len += ((long)bits - (long)tree[m].Len)
559 *(long)tree[m].Freq;
560 tree[m].Len = (ush)bits;
568 * Generate the codes for a given tree and bit counts (which need not be
571 * the given tree and the field len is set for all tree elements.
572 * OUT assertion: the field code is set for all tree elements of non
575 local void gen_codes (tree, max_code, bl_count)
576 ct_data *tree; /* the tree to decorate */
599 int len = tree[n].Len;
602 tree[n].Code = bi_reverse(next_code[len]++, len);
604 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
605 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
610 * Construct one Huffman tree and assigns the code bit strings and lengths.
612 * IN assertion: the field freq is set for all tree elements.
619 tree_desc *desc; /* the tree descriptor */
621 ct_data *tree = desc->dyn_tree;
635 if (tree[n].Freq != 0) {
639 tree[n].Len = 0;
650 tree[node].Freq = 1;
657 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
660 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
662 /* Construct the Huffman tree by repeatedly combining the least two
665 node = elems; /* next internal node of the tree */
667 pqremove(s, tree, n); /* n = node of least frequency */
674 tree[node].Freq = tree[n].Freq + tree[m].Freq;
677 tree[n].Dad = tree[m].Dad = (ush)node;
679 if (tree == s->bl_tree) {
681 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
686 pqdownheap(s, tree, SMALLEST);
698 gen_codes ((ct_data *)tree, max_code, s->bl_count);
702 * Scan a literal or distance tree to determine the frequencies of the codes
703 * in the bit length tree.
705 local void scan_tree (s, tree, max_code)
707 ct_data *tree; /* the tree to be scanned */
710 int n; /* iterates over all tree elements */
713 int nextlen = tree[0].Len; /* length of next code */
719 tree[max_code+1].Len = (ush)0xffff; /* guard */
722 curlen = nextlen; nextlen = tree[n+1].Len;
747 * Send a literal or distance tree in compressed form, using the codes in
750 local void send_tree (s, tree, max_code)
752 ct_data *tree; /* the tree to be scanned */
755 int n; /* iterates over all tree elements */
758 int nextlen = tree[0].Len; /* length of next code */
763 /* tree[max_code+1].Len = -1; */ /* guard already set */
767 curlen = nextlen; nextlen = tree[n+1].Len;
798 * Construct the Huffman tree for the bit lengths and return the index in
810 /* Build the bit length tree: */
812 /* opt_len now includes the length of the tree representations, except
823 /* Update opt_len to include the bit length tree and counts */
833 * lengths of the bit length codes, the literal tree and the distance tree.
838 int lcodes, dcodes, blcodes; /* number of codes for each tree */
853 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
855 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
856 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
858 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
859 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
932 * the compressed block data, excluding the tree representations.
935 /* Build the bit length tree for the above two trees, and get the index
1062 const ct_data *ltree; /* literal tree */
1063 const ct_data *dtree; /* distance tree */