From: Koji Arai <jca02266@gmail.com>
Date: Thu, 5 Jun 2008 14:45:39 +0000 (+0900)
Subject: use the struct heap_t
X-Git-Url: http://git.osdn.net/view?p=lha%2Folha.git;a=commitdiff_plain;h=bec880a0b546618c74535869301086dedb9c2cd8

use the struct heap_t
---

diff --git a/maketree.c b/maketree.c
index 158e576..4e28898 100644
--- a/maketree.c
+++ b/maketree.c
@@ -3,8 +3,12 @@
 ***********************************************************/
 #include "ar.h"
 
-static int n, heapsize;
-static short heap[NC + 1];
+struct heap_t {
+    short buf[NC + 1];          /* buf[0] is not used */
+    int size;
+};
+
+static int n;
 static ushort *freq, *sortptr, len_cnt[17];
 static uchar *len;
 
@@ -55,21 +59,21 @@ make_len(int root)
 }
 
 static void
-downheap(int i)
+downheap(struct heap_t *heap, int i)
         /* priority queue; send i-th entry down heap */
 {
     int j, k;
 
-    k = heap[i];
-    while ((j = 2 * i) <= heapsize) {
-        if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
+    k = heap->buf[i];
+    while ((j = 2 * i) <= heap->size) {
+        if (j < heap->size && freq[heap->buf[j]] > freq[heap->buf[j + 1]])
             j++;
-        if (freq[k] <= freq[heap[j]])
+        if (freq[k] <= freq[heap->buf[j]])
             break;
-        heap[i] = heap[j];
+        heap->buf[i] = heap->buf[j];
         i = j;
     }
-    heap[i] = k;
+    heap->buf[i] = k;
 }
 
 static void
@@ -90,41 +94,44 @@ make_tree(int nparm, ushort freqparm[], uchar lenparm[], ushort codeparm[])
         /* make tree, calculate len[], return root */
 {
     int i, j, k, avail;
+    struct heap_t heap;
 
     n = nparm;
     freq = freqparm;
     len = lenparm;
     avail = n;
-    heapsize = 0;
-    heap[1] = 0;
+    heap.size = 0;
+    heap.buf[1] = 0;
     for (i = 0; i < n; i++) {
         len[i] = 0;
         if (freq[i])
-            heap[++heapsize] = i;
+            heap.buf[++heap.size] = i;
     }
-    if (heapsize < 2) {
-        codeparm[heap[1]] = 0;
-        return heap[1];
+    if (heap.size < 2) {
+        codeparm[heap.buf[1]] = 0;
+        return heap.buf[1];
     }
-    for (i = heapsize / 2; i >= 1; i--)
-        downheap(i);            /* make priority queue */
+    for (i = heap.size / 2; i >= 1; i--)
+        downheap(&heap, i);            /* make priority queue */
     sortptr = codeparm;
     do {                        /* while queue has at least two entries */
-        i = heap[1];            /* take out least-freq entry */
+        i = heap.buf[1];        /* take out least-freq entry */
         if (i < n)
             *sortptr++ = i;
-        heap[1] = heap[heapsize--];
-        downheap(1);
-        j = heap[1];            /* next least-freq entry */
+        heap.buf[1] = heap.buf[heap.size--];
+        downheap(&heap, 1);
+
+        j = heap.buf[1];       /* next least-freq entry */
         if (j < n)
             *sortptr++ = j;
+
         k = avail++;            /* generate new node */
         freq[k] = freq[i] + freq[j];
-        heap[1] = k;
-        downheap(1);            /* put into queue */
+        heap.buf[1] = k;
+        downheap(&heap, 1);     /* put into queue */
         left[k] = i;
         right[k] = j;
-    } while (heapsize > 1);
+    } while (heap.size > 1);
     sortptr = codeparm;
     make_len(k);
     make_code(nparm, lenparm, codeparm);