3.1.1.1.3.2 PrefixCodeTreeAddLeaf

Links a symbol's PREFIX_CODE_NODE into its correct position in a Huffman prefix code tree.

Parameters

  • inout PREFIX_CODE_NODE treeNodes[1024]: A 1024 element PREFIX_CODE_NODE array that contains the Huffman prefix code tree's nodes.

  • in ULONG leafIndex: The index in treeNodes of the node to link into the tree.

  • in ULONG mask: The symbol's prefix code.

  • in ULONG bits: The number of bits in the symbol's prefix code.

Return Value

Returns the index in treeNodes of the next node to be processed.

Algorithm

 PREFIX_CODE_NODE node := treeNodes[0]
 ULONG i := leafIndex + 1
 ULONG childIndex
  
 while bits > 1
     bits := bits – 1
     childIndex := (mask >> bits) & 1
     if node.child[childIndex] = NIL
         node.child[childIndex] := treeNodes[i]
         treeNodes[i].leaf := FALSE
         i := i + 1
     endif
     node := node.child[childIndex]
 endwhile
 node.child[mask & 1] := treeNodes[leafIndex]
 return i