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