home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / progc / aetsk100.arj / SYSQVFNC.CC < prev    next >
C/C++ Source or Header  |  1991-11-17  |  4KB  |  206 lines
  1. /*
  2.     sysqvfnc.cpp
  3.  
  4.     queues of objects of type Qable
  5.     
  6.     copyright (c) 1991 J. Alan Eldridge
  7.     
  8.     history:
  9.     
  10.     < from sysqtmpl.h -- the template version >
  11.  
  12.     10/28/91    created
  13.     
  14.     10/30/91    changed class hierarchy so we now have:
  15.     
  16.                 SysQ<T>     queue of Ts
  17.                 SysPriQ<T>  priority queue of Ts
  18.                 SysQP<T>    queue of ptrs to T
  19.                 SysPriQP<T> priority queue of ptrs to T
  20.  
  21.     11/08/91    created this virtual function version...
  22.                 this has only classes SysQP and SysPriQP
  23. */
  24.  
  25. #include    "aedef.h"
  26. #include    "sysqvfnc.h"
  27.  
  28. SysQP::SysQP(int n, int lim)
  29. {
  30.     nused = nfree = 0;
  31.     maxnodes = lim;
  32.     head = tail = free = 0;
  33.     while (n-- > 0)
  34.         putfree(new SysQNode);
  35. }
  36.  
  37. SysQP::~SysQP()
  38. {
  39.     Qable       *t;
  40.     SysQNode    *pn;
  41.     
  42.     //  dump all nodes onto free list
  43.     while (Get(t))
  44.         ;
  45.     //  delete all nodes on free list
  46.     while ((pn = getfree(0)) != 0)
  47.         delete pn;
  48. }
  49.  
  50. SysQNode*
  51. SysQP::getfree(int alloc)
  52. {
  53.     SysQNode      *pn = 0;
  54.  
  55.     if (nfree > 0) {
  56.         pn = free;
  57.         free = free->next;
  58.         nfree--;
  59.     } else if (alloc) {
  60.         pn = new SysQNode;
  61.     }
  62.     
  63.     return pn;
  64. }
  65.  
  66. void
  67. SysQP::putfree(SysQNode *pn)
  68. {
  69.     nfree++;
  70.     pn->next = free;
  71.     free = pn;
  72. }
  73.  
  74. SysQNode*
  75. SysQP::findnode(Qable *t)
  76. {
  77.     SysQNode    *pn = head;
  78.     
  79.     while (pn && !(pn->data == t))
  80.         pn = pn->next;
  81.     
  82.     return pn;
  83. }
  84.  
  85. void
  86. SysQP::create(SysQNode *pn)
  87. {
  88.     head = tail = pn;
  89.     nused = 1;
  90.     pn->prev = pn->next = 0;
  91. }
  92.  
  93. void
  94. SysQP::insert(SysQNode *pnext, SysQNode *pn)
  95. {
  96.     //  add before 0 means put at tail
  97.  
  98.     if (!nused)
  99.         create(pn);
  100.     else {
  101.         if (pnext) {
  102.             pn->prev = pnext->prev;
  103.             if (pnext == head)
  104.                 head = pn;
  105.             else
  106.                 pnext->prev->next = pn;
  107.             pnext->prev = pn;
  108.             pn->next = pnext;
  109.         } else {
  110.             pn->prev = tail;
  111.             tail->next = pn;
  112.             tail = pn;
  113.             pn->next = 0;
  114.         }
  115.         nused++;
  116.     }
  117. }
  118.         
  119. int
  120. SysQP::Add(Qable *t)
  121. {
  122.     SysQNode    *pn = getfree(nused + nfree < maxnodes);
  123.     
  124.     if (pn) {
  125.         pn->data = t;
  126.         insert(0, pn);
  127.     }
  128.  
  129.     return !!pn;
  130. }
  131.  
  132. SysQNode*
  133. SysQP::findpred(Qable *t)
  134. {
  135.     SysQNode    *pwalk;
  136.     
  137.     pwalk = head;
  138.     while (pwalk && !(pwalk->data[0] < t[0]))
  139.         pwalk = pwalk->next;
  140.     return pwalk;
  141. }
  142.         
  143. int
  144. SysQP::Ins(Qable *t)
  145. {
  146.     SysQNode    *pn = getfree(nused + nfree < maxnodes);
  147.  
  148.     if (pn) {
  149.         pn->data = t;
  150.         insert(findpred(t), pn);
  151.     }
  152.     
  153.     return !!pn;
  154. }
  155.  
  156. int
  157. SysQP::Get(Qable* &t, int rmv)
  158. {
  159.     SysQNode    *pn = head;
  160.     
  161.     if (pn) {
  162.         t = head->data;
  163.         if (rmv) {
  164.             if ((head = head->next) != 0)
  165.                 head->prev = 0;
  166.             else
  167.                 tail = 0;
  168.             nused--;
  169.             putfree(pn);
  170.         }
  171.     }
  172.     
  173.     return !!pn;
  174. }
  175.  
  176. int
  177. SysQP::Del(Qable *t)
  178. {
  179.     SysQNode    *pn = findnode(t);
  180.     
  181.     if (pn) {
  182.         if (nused == 1)
  183.             head = tail = 0;
  184.         else if (pn == head) 
  185.             (head = head->next)->prev = 0;
  186.         else if (pn == tail)
  187.             (tail = tail->prev)->next = 0;
  188.         else {
  189.             pn->next->prev = pn->prev;
  190.             pn->prev->next = pn->next;
  191.         }
  192.         nused--;
  193.         putfree(pn);
  194.     }
  195.     
  196.     return !!pn;
  197. }
  198.  
  199. Qable *
  200. SysQP::Get(int rmv)
  201. {
  202.     Qable *pq;
  203.     
  204.     return Get(pq,rmv) ? pq : 0;
  205. }
  206.