home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / mplex.ccp < prev    next >
Encoding:
Text File  |  1993-07-23  |  15.4 KB  |  789 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.     based on code by Marc Shapiro (shapiro@sor.inria.fr)
  6.  
  7. This file is part of GNU CC.
  8.  
  9. GNU CC is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY.  No author or distributor
  11. accepts responsibility to anyone for the consequences of using it
  12. or for whether it serves any particular purpose or works at all,
  13. unless he says so in writing.  Refer to the GNU CC General Public
  14. License for full details.
  15.  
  16. Everyone is granted permission to copy, modify and redistribute
  17. GNU CC, but only under the conditions described in the
  18. GNU CC General Public License.   A copy of this license is
  19. supposed to have been given to you along with GNU CC so you
  20. can know your rights and responsibilities.  It should be in a
  21. file named COPYING.  Among other things, the copyright notice
  22. and this notice must be preserved on all copies.  
  23. */
  24.  
  25. #include "<T>.MPlex.h"
  26.  
  27. // <T>MChunk support
  28.  
  29.  
  30. <T>MChunk::<T>MChunk(<T>*    d,      
  31.                int      baseidx,
  32.                int      lowidx, 
  33.                int      fenceidx,
  34.                int      topidx)
  35.      : <T>IChunk(d, baseidx, lowidx, fenceidx, topidx)
  36. {
  37.   unused = fence - low;
  38.   unsigned msize = (top - base)/_MAP_BITS + 1;
  39.   map = (unsigned long *) (new long[msize]);
  40.   bzero((void*)map, msize * sizeof(long));
  41. }
  42.  
  43. void <T>MChunk:: shrink_high ()
  44. {
  45.   if (fence <= low) empty_error();
  46.   --fence;
  47.   if (!valid(fence)) 
  48.     --unused;
  49.   else
  50.     free(fence);
  51.   reset_high();
  52. }
  53.  
  54. void <T>MChunk:: shrink_low ()
  55. {
  56.   if (fence <= low) empty_error();
  57.   if (!valid(low)) 
  58.     --unused;
  59.   else
  60.     free(low);
  61.   ++low;
  62.   reset_low();
  63. }
  64.  
  65. void <T>MChunk::clear(int lo)
  66. {
  67.   int s = top - base;
  68.   low = base = fence = lo;
  69.   top = base + s;
  70.   unused = 0;
  71.   bzero((void*)map, ((top - base)/_MAP_BITS + 1) * sizeof(long));
  72. }
  73.  
  74. int <T>MChunk::del(int idx)
  75. {
  76.   if (idx < low || idx >= fence) index_error();
  77.   int v = valid(idx);
  78.   if (v)
  79.   {
  80.     free(idx);
  81.     ++unused;
  82.   }
  83.   return v;
  84. }
  85.  
  86.  
  87. int <T>MChunk::undel(int idx)
  88. {
  89.   if (idx < low || idx >= fence) index_error();
  90.   int v = valid(idx);
  91.   if (!v)
  92.   {
  93.     mark(idx);
  94.     --unused;
  95.   }
  96.   return v;
  97. }
  98.  
  99. int <T>MChunk::unused_index()
  100. {
  101.   if (unused_indices() == 0) index_error();
  102.   int slot;
  103.   if (low == base)              // can traverse 32 slots at a time
  104.   {
  105.     int blk = 0;
  106.     while (map[blk] == ~0L) ++blk;
  107.     slot = blk * _MAP_BITS + base;
  108.   }
  109.   else
  110.     slot = low;
  111.  
  112.   while(valid(slot)) ++slot;
  113.   return slot;
  114. }
  115.  
  116. int <T>MChunk::first_index()
  117. {
  118.   if (empty()) return fence;
  119.   int slot;
  120.   if (low == base)
  121.   {
  122.     int blk = 0;
  123.     while (map[blk] == 0) ++blk;
  124.     slot = blk * _MAP_BITS + base;
  125.   }
  126.   else
  127.     slot = low;
  128.  
  129.   while(!valid(slot)) ++slot;
  130.   return slot;
  131. }
  132.  
  133. int <T>MChunk::last_index()
  134. {
  135.   if (empty()) return low - 1;
  136.   int slot;
  137.   if (top == fence)
  138.   {
  139.     int blk = (top - base) / _MAP_BITS;
  140.     while (map[blk] == 0) --blk;
  141.     slot = blk * _MAP_BITS + base + _MAP_BITS - 1;
  142.   }
  143.   else
  144.     slot = fence - 1;
  145.  
  146.   while(!valid(slot)) --slot;
  147.   return slot;
  148. }
  149.  
  150.  
  151. int <T>MChunk:: OK()
  152. {
  153.   int v = data != 0;             // have some data
  154.   v &= map != 0;                 // and a map
  155.   v &= base <= low;              // ok, index-wise
  156.   v &= low <= fence;
  157.   v &= fence <= top;
  158.  
  159.   v &=  nxt->prev() == this;      // and links are OK
  160.   v &=  prv->next() == this;
  161.  
  162.   int bitcount = 0;              // and unused count correct
  163.   for (int i = low; i < fence; ++i) if (!valid(i)) ++bitcount;
  164.   v &= unused == bitcount;
  165.   
  166.   if (!v) error("invariant failure");
  167.   return(v);
  168. }
  169.  
  170. <T>* <T>MChunk::succ(<T>* p)
  171. {
  172.   int i = ((int) p - (int) data) / sizeof(<T>) + base + 1;
  173.   if (p == 0 || i < low) return 0;
  174.   while (i < fence && !valid(i)) ++i;
  175.   if (i >= fence) return 0;
  176.   return pointer_to(i);
  177. }
  178.  
  179. <T>* <T>MChunk::pred(<T>* p)
  180. {
  181.   int i = ((int) p - (int) data) / sizeof(<T>) + base - 1;
  182.   if (p == 0 || i >= fence) return 0;
  183.   while (i >= low && !valid(i)) --i;
  184.   if (i < low) return 0;
  185.   return pointer_to(i);
  186. }
  187.  
  188. <T>* <T>MChunk::first_pointer()
  189. {
  190.   if (empty()) return 0;
  191.   int slot;
  192.   if (low == base)
  193.   {
  194.     int blk = 0;
  195.     while (map[blk] == 0) ++blk;
  196.     slot = blk * _MAP_BITS + base;
  197.   }
  198.   else
  199.     slot = low;
  200.  
  201.   while(!valid(slot)) ++slot;
  202.   return pointer_to(slot);
  203. }
  204.  
  205. <T>* <T>MChunk::last_pointer()
  206. {
  207.   if (empty()) return 0;
  208.   int slot;
  209.   if (top == fence)
  210.   {
  211.     int blk = (top - base) / _MAP_BITS;
  212.     while (map[blk] == 0) --blk;
  213.     slot = blk * _MAP_BITS + base + _MAP_BITS - 1;
  214.   }
  215.   else
  216.     slot = fence - 1;
  217.  
  218.   while(!valid(slot)) --slot;
  219.   return pointer_to(slot);
  220. }
  221.  
  222. <T>MPlex:: <T>MPlex()
  223. {
  224.   mods = unused = 0;
  225.   lo = fnc = 0;
  226.   csize = DEFAULT_INITIAL_CAPACITY;
  227.   <T>* data = new <T>[csize];
  228.   hd = ch = new <T>MChunk(data,  lo, lo, fnc, lo+csize);
  229. }
  230.  
  231. <T>MPlex:: <T>MPlex(int chunksize)
  232. {
  233.   if (chunksize == 0) error("invalid constructor specification");
  234.   mods = unused = 0;
  235.   lo = fnc = 0;
  236.   if (chunksize > 0)
  237.   {
  238.     csize = chunksize;
  239.     <T>* data = new <T>[csize];
  240.     hd = ch = new <T>MChunk(data,  lo, lo, fnc, csize);
  241.   }
  242.   else
  243.   {
  244.     csize = -chunksize;
  245.     <T>* data = new <T>[csize];
  246.     hd = ch = new <T>MChunk(data,  chunksize, lo, fnc, fnc);
  247.   }
  248. }
  249.  
  250.  
  251. <T>MPlex:: <T>MPlex(int l, int chunksize)
  252. {
  253.   if (chunksize == 0) error("invalid constructor specification");
  254.   mods = unused = 0;
  255.   lo = fnc = l;
  256.   if (chunksize > 0)
  257.   {
  258.     csize = chunksize;
  259.     <T>* data = new <T>[csize];
  260.     hd = ch = new <T>MChunk(data,  lo, lo, fnc, csize+lo);
  261.   }
  262.   else
  263.   {
  264.     csize = -chunksize;
  265.     <T>* data = new <T>[csize];
  266.     hd = ch = new <T>MChunk(data,  chunksize+lo, lo, fnc, fnc);
  267.   }
  268. }
  269.  
  270.  
  271. void <T>MPlex::make_initial_chunks(int up = 1)
  272. {
  273.   int need = fnc - lo;
  274.   hd = 0;
  275.   if (up)
  276.   {
  277.     int l = lo;
  278.     do
  279.     {
  280.       int sz;
  281.       if (need >= csize)
  282.         sz = csize;
  283.       else
  284.         sz = need;
  285.       <T>* data = new <T> [csize];
  286.       <T>MChunk* h = new <T>MChunk(data,  l, l, l+sz, l+csize);
  287.       if (hd != 0)
  288.         h->link_to_next(hd);
  289.       else
  290.         hd = h;
  291.       l += sz;
  292.       need -= sz;
  293.     } while (need > 0);
  294.   }
  295.   else
  296.   {
  297.     int hi = fnc;
  298.     do
  299.     {
  300.       int sz;
  301.       if (need >= csize)
  302.         sz = csize;
  303.       else
  304.         sz = need;
  305.       <T>* data = new <T> [csize];
  306.       <T>MChunk* h = new <T>MChunk(data,  hi-csize, hi-sz, hi, hi);
  307.       if (hd != 0)
  308.         h->link_to_next(hd);
  309.       hd = h;
  310.       hi -= sz;
  311.       need -= sz;
  312.     } while (need > 0);
  313.   }
  314.   ch = (<T>MChunk*) hd;
  315. }
  316.  
  317. <T>MPlex:: <T>MPlex(int l, int hi, const <T&> initval, int chunksize = 0)
  318. {
  319.   mods = unused = 0;
  320.   lo = l;
  321.   fnc = hi + 1;
  322.   if (chunksize == 0)
  323.   {
  324.     csize = fnc - l;
  325.     make_initial_chunks(1);
  326.   }
  327.   else if (chunksize < 0)
  328.   {
  329.     csize = -chunksize;
  330.     make_initial_chunks(0);
  331.   }
  332.   else
  333.   {
  334.     csize = chunksize;
  335.     make_initial_chunks(1);
  336.   }
  337.   fill(initval);
  338. }
  339.  
  340. <T>MPlex::<T>MPlex(const <T>MPlex& a)
  341. {
  342.   mods = 0;
  343.   lo = a.lo;
  344.   fnc = a.fnc;
  345.   csize = a.csize;
  346.   unused = fnc - lo;
  347.   hd = 0;
  348.   <T>IChunk* p = a.hd;
  349.   do
  350.   {
  351.     <T>* data = new <T> [p->size()];
  352.     <T>MChunk* h = new <T>MChunk(data,  p->base_index(),
  353.                           p->low_index(), p->fence_index(), p->top_index());
  354.     if (hd != 0)
  355.       h->link_to_next(hd);
  356.     else
  357.       hd = h;
  358.     p = p->next();
  359.   } while (p != a.hd);
  360.   ch = (<T>MChunk*) hd;
  361.   for (int i = a.low(); i < a.fence(); a.next(i)) 
  362.   {
  363.     undel_index(i);
  364.     (*this)[i] = a[i];
  365.   }
  366. }
  367.  
  368. void <T>MPlex::operator= (const <T>MPlex& a)
  369. {
  370.   if (&a != this)
  371.   {
  372.     invalidate();
  373.     record_change();
  374.     lo = a.lo;
  375.     fnc = a.fnc;
  376.     csize = a.csize;
  377.     unused = fnc - lo;
  378.     hd = 0;
  379.     <T>IChunk* p = a.hd;
  380.     do
  381.     {
  382.       <T>* data = new <T> [p->size()];
  383.       <T>MChunk* h = new <T>MChunk(data,  p->base_index(),
  384.                             p->low_index(), p->fence_index(), p->top_index());
  385.       if (hd != 0)
  386.         h->link_to_next(hd);
  387.       else
  388.         hd = h;
  389.       p = p->next();
  390.     } while (p != a.hd);
  391.     ch = (<T>MChunk*) hd;
  392.     for (int i = a.low(); i < a.fence(); a.next(i)) 
  393.     {
  394.       undel_index(i);
  395.       (*this)[i] = a[i];
  396.     }
  397.   }
  398. }
  399.  
  400. int <T>MPlex::valid(int idx)
  401. {
  402.   <T>MChunk* tail = (<T>MChunk*)tl();
  403.   while (idx >= ch->fence_index())
  404.   {
  405.     if (ch == tail) return 0;
  406.     ch = (<T>MChunk*)(ch->next());
  407.   }
  408.   while (idx < ch->low_index())
  409.   {
  410.     if (ch == hd) return 0;
  411.     ch = (<T>MChunk*)(ch->prev());
  412.   }
  413.   return ch-><T>MChunk::valid_index(idx);
  414. }
  415.  
  416. void <T>MPlex::cache(int idx)
  417. {
  418.   <T>MChunk* tail = (<T>MChunk*)tl();
  419.   while (idx >= ch->fence_index())
  420.   {
  421.     if (ch == tail) index_error();
  422.     ch = (<T>MChunk*)(ch->next());
  423.   }
  424.   while (idx < ch->low_index())
  425.   {
  426.     if (ch == hd) index_error();
  427.     ch = (<T>MChunk*)(ch->prev());
  428.   }
  429.   if (!ch-><T>MChunk::valid_index(idx)) index_error();
  430. }
  431.  
  432. void <T>MPlex::cache(const <T>* p)
  433. {
  434.   <T>MChunk* old = ch;
  435.   while (!ch->actual_pointer(p))
  436.   {
  437.     ch = (<T>MChunk*)(ch->next());
  438.     if (ch == old) index_error();
  439.   }
  440.   if (!ch-><T>MChunk::valid_pointer(p)) index_error();
  441. }
  442.  
  443. int <T>MPlex::owns(Pix p)
  444. {
  445.   <T>MChunk* old = ch;
  446.   while (!ch->actual_pointer(p))
  447.   {
  448.     ch = (<T>MChunk*)(ch->next());
  449.     if (ch == old) return 0;
  450.   }
  451.   return ch-><T>MChunk::valid_pointer(p);
  452. }
  453.  
  454. int <T>MPlex::add_high(const <T&> elem)
  455. {
  456.   record_change();
  457.   ch = (<T>MChunk*) tl();
  458.  
  459.   if (!ch->can_grow_high())
  460.   {
  461.     <T>* data = new <T> [csize];
  462.     ch = new <T>MChunk(data, fnc,fnc,fnc,fnc+csize);
  463.     ch->link_to_prev(tl());
  464.   }
  465.  
  466.   *((ch-><T>MChunk::grow_high())) = elem;
  467.   return fnc++;
  468. }
  469.  
  470. int <T>MPlex::add_low (const <T&> elem)
  471. {
  472.   record_change();
  473.   ch = (<T>MChunk*) hd;
  474.   if (!ch->can_grow_low())
  475.   {
  476.     <T>* data = new <T> [csize];
  477.     hd = new <T>MChunk(data,  lo-csize, lo, lo, lo);
  478.     hd->link_to_next(ch);
  479.     ch = (<T>MChunk*) hd;
  480.   }
  481.  
  482.   *((ch-><T>MChunk::grow_low())) = elem;
  483.   return --lo;
  484. }
  485.  
  486. void <T>MPlex::adjust_bounds()
  487. {
  488.   ch = (<T>MChunk*) tl();
  489.   while (ch-><T>MChunk::empty() && !one_chunk())
  490.   {
  491.     <T>MChunk* pred = (<T>MChunk*)(ch->prev());
  492.     del_chunk(ch);
  493.     pred->reset_high();
  494.     ch = pred;
  495.   }
  496.   int oldfnc = fnc;
  497.   fnc = ch->fence_index();
  498.   unused -= oldfnc - fnc - 1;
  499.  
  500.   ch = (<T>MChunk*) hd;
  501.   while (ch-><T>MChunk::empty() && !one_chunk())
  502.   {
  503.     hd = (<T>MChunk*)(ch->next());
  504.     del_chunk(ch);
  505.     ch = (<T>MChunk*) hd;
  506.     ch->reset_low();
  507.   }
  508.   int oldlo = lo;
  509.   lo = ch->low_index();
  510.   unused -= lo - oldlo - 1;
  511. }
  512.  
  513. int <T>MPlex::del_high ()
  514. {
  515.   if (empty()) empty_error();
  516.   record_change();
  517.   ch = (<T>MChunk*) tl();
  518.   ch-><T>MChunk::shrink_high();
  519.   while (ch-><T>MChunk::empty() && !one_chunk())
  520.   {
  521.     <T>MChunk* pred = (<T>MChunk*)(ch->prev());
  522.     del_chunk(ch);
  523.     pred->reset_high();
  524.     ch = pred;
  525.   }
  526.   int oldfnc = fnc;
  527.   fnc = ch->fence_index();
  528.   unused -= oldfnc - fnc - 1;
  529.   return fnc - 1;
  530. }
  531.  
  532. int <T>MPlex::del_low ()
  533. {
  534.   if (empty()) empty_error();
  535.   record_change();
  536.   ch = (<T>MChunk*) hd;
  537.   ch-><T>MChunk::shrink_low();
  538.   while (ch-><T>MChunk::empty() && !one_chunk())
  539.   {
  540.     hd = (<T>MChunk*)(ch->next());
  541.     del_chunk(ch);
  542.     ch = (<T>MChunk*) hd;
  543.     ch->reset_low();
  544.   }
  545.   int oldlo = lo;
  546.   lo = ch->low_index();
  547.   unused -= lo - oldlo - 1;
  548.   return lo;
  549. }
  550.  
  551. int <T>MPlex::add(const <T&> elem)
  552. {
  553.   if (unused == 0) 
  554.     return add_high(elem);
  555.   for(;;)
  556.   {
  557.     if (ch->unused_indices() != 0) 
  558.     {
  559.       int i =  ch->unused_index();      
  560.       undel_index(i);
  561.       (*this)[i] = elem;
  562.       return i;
  563.     }
  564.     ch = (<T>MChunk*)(ch->prev());
  565.   }
  566. }
  567.  
  568. int <T>MPlex::unused_index()
  569. {
  570.   if (unused == 0) index_error();
  571.   for(;;)
  572.   {
  573.     if (ch->unused_indices() != 0) return ch->unused_index();      
  574.     ch = (<T>MChunk*)(ch->prev());
  575.   }
  576. }
  577.  
  578. Pix <T>MPlex::unused_Pix()
  579. {
  580.   if (unused == 0) return 0;
  581.   for (;;)
  582.   {
  583.     if (ch->unused_indices() != 0) return ch->pointer_to(ch->unused_index()); 
  584.     ch = (<T>MChunk*)(ch->prev());
  585.   }
  586. }
  587.  
  588. int <T>MPlex::del_index(int idx)
  589. {
  590.   if (idx < lo || idx >= fnc) index_error();
  591.   if (<T>MPlex::valid(idx))
  592.   {
  593.     ++unused;
  594.     record_change();
  595.     ch-><T>MChunk::del(idx);
  596.     return 1;
  597.   }
  598.   else
  599.     return 0;
  600. }
  601.  
  602. int <T>MPlex::dopred(int idx)
  603. {
  604.  
  605.   if (idx >= fnc) idx = fnc;
  606.   if (idx <= lo) return lo - 1;
  607.  
  608.   while (idx > ch->fence_index())
  609.   {
  610.     ch = (<T>MChunk*)(ch->next());
  611.   }
  612.   while (idx <= ch->low_index())
  613.   {
  614.     ch = (<T>MChunk*)(ch->prev());
  615.   }
  616.   int i = ch-><T>MChunk::pred(idx);
  617.   if (i >= ch->low_index() || i < lo)
  618.     return i;
  619.   for (;;)
  620.   {
  621.     ch = (<T>MChunk*)(ch->prev());
  622.     i = ch-><T>MChunk::last_index();
  623.     if (i >= ch->low_index() || i < lo)
  624.       return i;
  625.   }
  626. }
  627.  
  628.  
  629. int <T>MPlex::dosucc(int idx)
  630. {
  631.  
  632.   if (idx < lo) idx = lo;
  633.   if (idx >= fnc - 1) return fnc;
  634.  
  635.   while (idx >= ch->fence_index())
  636.   {
  637.     ch = (<T>MChunk*)(ch->next());
  638.   }
  639.   while (idx < ch->low_index())
  640.   {
  641.     ch = (<T>MChunk*)(ch->prev());
  642.   }
  643.   int i = ch-><T>MChunk::succ(idx);
  644.   if (i < ch->fence_index() || i >= fnc)
  645.     return i;
  646.   for (;;)
  647.   {
  648.     ch = (<T>MChunk*)(ch->next());
  649.     i = ch-><T>MChunk::first_index();
  650.     if (i < ch->fence_index() || i >= fnc)
  651.       return i;
  652.   }
  653. }
  654.  
  655. void <T>MPlex::prev(Pix& i)
  656. {
  657.   if (i == 0) return;
  658.   <T>* p = (<T>*) i;
  659.   <T>MChunk* old = ch;
  660.   while (!ch->actual_pointer(p))
  661.   {
  662.     ch = (<T>MChunk*)(ch->prev());
  663.     if (ch == old) { i = 0; return; }
  664.   }
  665.   <T>* q = ch-><T>MChunk::pred(p);
  666.   if (q != 0 || ch == hd)
  667.       { i = Pix(q); return; }
  668.   else
  669.   {
  670.     for(;;)
  671.     {
  672.       ch = (<T>MChunk*)(ch->prev());
  673.       q = ch-><T>MChunk::last_pointer();
  674.       if (q != 0 || ch == hd)
  675.         { i = Pix(q); return; }
  676.     }
  677.   }
  678. }
  679.  
  680. void <T>MPlex::next(Pix& i)
  681. {
  682.   if (i == 0) return;
  683.   <T>* p = (<T>*) i;
  684.   <T>MChunk* tail = (<T>MChunk*)(tl());
  685.   <T>MChunk* old = ch;
  686.   while (!ch->actual_pointer(p))
  687.   {
  688.     ch = (<T>MChunk*)(ch->next());
  689.     if (ch == old) { i = 0; return; }
  690.   }
  691.   <T>* q = ch-><T>MChunk::succ(p);
  692.   if (q != 0 || ch == tail)
  693.       { i = Pix(q); return; }
  694.   else
  695.   {
  696.     for(;;)
  697.     {
  698.       ch = (<T>MChunk*)(ch->next());
  699.       q = ch-><T>MChunk::first_pointer();
  700.       if (q != 0 || ch == tail)
  701.         { i = Pix(q); return; }
  702.     }
  703.   }
  704. }
  705.  
  706.     
  707. void <T>MPlex::undel_index(int idx)
  708. {
  709.   if (idx < lo || idx >= fnc) index_error();
  710.   while (idx >= ch->fence_index())
  711.   {
  712.     ch = (<T>MChunk*)(ch->next());
  713.   }
  714.   while (idx < ch->low_index())
  715.   {
  716.     ch = (<T>MChunk*)(ch->prev());
  717.   }
  718.   int was_present = ch-><T>MChunk::undel(idx);
  719.   if (!was_present) 
  720.   {
  721.     record_change();
  722.     --unused;
  723.   }
  724.   return;
  725. }
  726.  
  727. void <T>MPlex::clear()
  728. {
  729.   if (fnc != lo)
  730.   {
  731.     record_change();
  732.     ch = (<T>MChunk*)tl();
  733.     while (ch != hd)
  734.     {
  735.       <T>MChunk* prv = (<T>MChunk*)(ch->prev());
  736.       del_chunk(ch);
  737.       ch = prv;
  738.     }
  739.     ch-><T>MChunk::clear(lo);
  740.     fnc = lo;
  741.     unused = 0;
  742.   }
  743. }
  744.  
  745. int <T>MPlex::OK ()
  746. {
  747.   int v = hd != 0;                    // at least one chunk
  748.  
  749.   int found_ch = 0;                   // to make sure ch is in list;
  750.  
  751.   int count = 0;                      // to count unused slots
  752.  
  753.   <T>MChunk* t = (<T>MChunk*)(hd);
  754.  
  755.   int gap = t->low_index() - lo;
  756.   v &= gap == 0;                      // hd lo not less than lo.
  757.   count += gap;
  758.  
  759.   for (;;)
  760.   {
  761.     if (t == ch) ++found_ch;
  762.     v &= t-><T>MChunk::OK();             // each chunk is OK
  763.     count += t->unused_indices();
  764.     if (t == tl())
  765.       break;
  766.     else                              // and has indices less than succ
  767.     {
  768.       gap = t->next()->base_index() - t->top_index();
  769.       v &= gap == 0;
  770.       count += gap;
  771.  
  772.       if (t != hd)                  // internal chunks can't grow
  773.         v &= !t->can_grow_low() && !t->can_grow_high();
  774.  
  775.       t = (<T>MChunk*)(t->next());
  776.     }
  777.   }
  778.   gap = fnc - t->fence_index();
  779.   v &= gap == 0;
  780.   count += gap;
  781.  
  782.   v &= count == unused;              // chunk counts agree with plex
  783.  
  784.   v &= found_ch == 1;
  785.   if (!v) error("invariant failure");
  786.   return v;
  787. }
  788.  
  789.