rosapps/dflat32/htree.c

   1 /* ------------------- htree.c -------------------- */
   2
   3 #include "dflat.h"
   4 #include "htree.h"
   5
   6 struct DfHTree *ht;
   7 int root;
   8 int treect;
   9
  10 /* ------ build a Huffman tree from a frequency array ------ */
  11 void DfBuildTree(void)
  12 {
  13     int i;
  14
  15     treect = 256;
  16     /* ---- preset node pointers to -1 ---- */
  17     for (i = 0; i < treect; i++)    {
  18         ht[i].parent = -1;
  19         ht[i].right  = -1;
  20         ht[i].left   = -1;
  21     }
  22     /* ---- build the huffman tree ----- */
  23     while (1)   {
  24         int h1 = -1, h2 = -1;
  25         /* ---- find the two lowest frequencies ---- */
  26         for (i = 0; i < treect; i++)   {
  27             if (i != h1) {
  28                 struct DfHTree *htt = ht+i;
  29                 /* --- find a node without a parent --- */
  30                 if (htt->cnt > 0 && htt->parent == -1)   {
  31                     /* ---- h1 & h2 -> lowest nodes ---- */
  32                     if (h1 == -1 || htt->cnt < ht[h1].cnt) {
  33                         if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)
  34                             h2 = h1;
  35                         h1 = i;
  36                     }
  37                     else if (h2 == -1 || htt->cnt < ht[h2].cnt)
  38                         h2 = i;
  39                 }
  40             }
  41         }
  42         /* --- if only h1 -> a node, that's the root --- */
  43         if (h2 == -1) {
  44             root = h1;
  45             break;
  46         }
  47         /* --- combine two nodes and add one --- */
  48         ht[h1].parent = treect;
  49         ht[h2].parent = treect;
  50         ht = realloc(ht, (treect+1) * sizeof(struct DfHTree));
  51         if (ht == NULL)
  52             break;
  53         /* --- the new node's frequency is the sum of the two
  54             nodes with the lowest frequencies --- */
  55         ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;
  56         /* - the new node points to the two that it combines */
  57         ht[treect].right = h1;
  58         ht[treect].left = h2;
  59         /* --- the new node has no parent (yet) --- */
  60         ht[treect].parent = -1;
  61         treect++;
  62     }
  63 }
  64