home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / ddjcompr / hstest / src / pq.c < prev    next >
C/C++ Source or Header  |  1991-04-18  |  4KB  |  211 lines
  1.  
  2.  
  3. /**
  4. *** PQ.C
  5. ***  fuer Beschreibung etc. siehe Dr. Dobb's 6'87
  6. ***  this has been modified slightly for huffman structures
  7. **/
  8.  
  9. #include <STDIO.H>
  10. #include "pq.h"
  11.  
  12. #include "huffman.h"
  13.  
  14. #define STATIC
  15.  
  16.  
  17. #ifndef HUFFMANN
  18.     #define PQ_SWAP(p,ptr1,ptr2) (*p->swap)(ptr1,ptr2)
  19.     #define PQ_CMP(p,ptr1,ptr2)  (*p->cmp)(ptr1,ptr2)
  20. #else
  21.  
  22.  
  23. /* 
  24. #define PQ_SWAP(p,ptr1,ptr2) huff_swap((void*)ptr1,(void*)ptr2)
  25.  
  26. STATIC void _fastcall huff_swap(struct huff_tab **c1,struct huff_tab **c2)
  27. {
  28.     void *tmp;
  29.     tmp = *c1;
  30.     *c1 = *c2;
  31.     *c2 = tmp;
  32. }
  33. */
  34.  
  35. #define PQ_SWAP(p,c1,c2)    {                            \
  36.     void *tmp;                                            \
  37.     tmp = *(struct hufftab **)c1;                        \
  38.     *(struct hufftab **)c1 = *(struct hufftab **)c2;    \
  39.     *(struct hufftab **)c2 = tmp;                        }
  40.  
  41.  
  42.  
  43.  
  44. #define PQ_CMP(p,ptr1,ptr2) ((int)(((*(struct huff_tab **)ptr2)->count - \
  45.                                     (*(struct huff_tab **)ptr1)->count ) ))
  46.  
  47. //#define PQ_CMP(p,ptr1,ptr2)  huff_cmp((void*)ptr1,(void*)ptr2)
  48. //
  49. //STATIC int _fastcall huff_cmp(struct huff_tab **c1,struct huff_tab **c2);
  50. //STATIC int _fastcall huff_cmp(struct huff_tab **c1,struct huff_tab **c2)
  51. //{
  52. //    return (*c2)->count-(*c1)->count;
  53. //}
  54. #endif
  55.  
  56.  
  57.     
  58.  
  59.  
  60.  
  61.  
  62. /*****************************************************************/
  63.  
  64. STATIC void reheap_down(register PQ *p)
  65.     {
  66.     int parent;
  67.     int child;
  68.     char *pparent;
  69.     char *pchild;
  70.     char *psibling;
  71.     char *heap;
  72.  
  73.     heap = p->heap;
  74.  
  75.     for (parent = 0,  child = 1;  child < p->nitems;  )
  76.         {
  77.         pparent = heap + (parent * p->itemsize);
  78.         pchild = heap + (child * p->itemsize);
  79.  
  80.         if (child + 1 < p->nitems)
  81.             {
  82.             psibling = pchild + p->itemsize;
  83.             if (PQ_CMP(p,pchild, psibling) < 0)
  84.                 {
  85.                 pchild = psibling;
  86.                 ++child;
  87.                 }
  88.             }
  89.  
  90.         if (PQ_CMP(p,pparent, pchild) >= 0)
  91.             break;
  92.  
  93.         PQ_SWAP(p,pparent, pchild);
  94.  
  95.         parent = child;
  96.         child = (parent * 2) + 1;
  97.         }
  98.     }
  99.  
  100. /*****************************************************************/
  101.  
  102. STATIC void reheap_up(register PQ *p)
  103.     {
  104.     int parent;
  105.     int child;
  106.     char *pparent;
  107.     char *pchild;
  108.     char *heap;
  109.  
  110.     child = p->nitems - 1;
  111.     heap = p->heap;
  112.  
  113.     while (child > 0)
  114.         {
  115.         parent = (child - 1) / 2;
  116.         pchild = heap + (child * p->itemsize);
  117.         pparent = heap + (parent * p->itemsize);
  118.  
  119.         if (PQ_CMP(p,pparent, pchild) >= 0)
  120.             break;
  121.  
  122.         PQ_SWAP(p,pparent, pchild);
  123.         child = parent;
  124.         }
  125. }
  126.  
  127. /*****************************************************************/
  128.  
  129. PQ *pq_create(numele, elesize, cmp, swap, initheap)
  130. int numele;
  131. int elesize;
  132. int (*cmp)();
  133. void (*swap)();
  134. void *initheap;
  135.     {
  136.     register PQ *p;
  137.     void *malloc();
  138.     int heapsize;
  139.  
  140.     heapsize = numele * elesize;
  141.  
  142.     if (initheap)
  143.         {
  144.         if ((p = malloc(sizeof(PQ))) == NULL)
  145.             return NULL;
  146.  
  147.         p->heap = initheap;
  148.         p->bottom = (char *)initheap + ((numele - 1) * elesize);
  149.         p->nitems = numele;
  150.         }
  151.     else 
  152.         {
  153.         if ((p = malloc(sizeof(PQ) + heapsize)) == NULL)
  154.             return NULL;
  155.         p->heap = (char *) (p + 1);
  156.         p->nitems = 0;
  157.         p->bottom = p->heap - elesize;
  158.         }
  159.  
  160.     p->cmp = cmp;
  161.     p->swap = swap;
  162.     p->itemsize = elesize;
  163.     p->maxitem = numele;
  164.     return p;
  165.     }
  166.  
  167. /*****************************************************************/
  168.  
  169. int pq_ins(register PQ *p,void *item)
  170.     {
  171.     int spaceavail = p->maxitem - p->nitems;
  172.  
  173.     if (spaceavail > 0)
  174.         {
  175.         p->nitems++;
  176.         memcpy(p->bottom += p->itemsize, item, p->itemsize);
  177.         reheap_up(p);
  178.         }
  179.     return spaceavail;
  180.     }
  181.  
  182. /*****************************************************************/
  183. int pq_del(register PQ *p,void *target)
  184.     {
  185.     int slots_in_use;
  186.  
  187.     if (slots_in_use = p->nitems)
  188.         {
  189.         memcpy(target, p->heap, p->itemsize);
  190.         memcpy(p->heap, p->bottom, p->itemsize);
  191.         p->nitems--;
  192.         p->bottom -= p->itemsize;
  193.         reheap_down(p);
  194.         }
  195.     return slots_in_use;
  196.     }
  197.  
  198. /*****************************************************************/
  199.  
  200. char *pq_look(register PQ *p)
  201.     {
  202.     return p->heap;
  203.     }
  204.  
  205. /*****************************************************************/
  206.  
  207. int pq_numele(register PQ *p)
  208.     {
  209.     return p->nitems;
  210.     }
  211.