home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / MPlex.ccP < prev    next >
Text File  |  1993-06-29  |  17KB  |  846 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, 675 Mass Ave, Cambridge, MA 02139, 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.   bzero((void*)map, ((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.   bzero((void*)map, ((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] == ~0L) ++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.   for(<T>MChunk* t = ch; 
  601.       t->unused_indices() == 0; 
  602.       t = (<T>MChunk*)(t->prev()))
  603.     ;
  604.  
  605.   int i =  t->unused_index();
  606.   set_cache(t);
  607.   undel_index(i);
  608.   (*this)[i] = elem;
  609.   return i;
  610. }
  611.  
  612. int <T>MPlex::unused_index() const
  613. {
  614.   if (unused == 0) index_error();
  615.  
  616.   for(<T>MChunk* t = ch; 
  617.       t->unused_indices() == 0; 
  618.       t = (<T>MChunk*)(t->prev()))
  619.     ;
  620.  
  621.   set_cache(t);
  622.   return t->unused_index();
  623. }
  624.  
  625. Pix <T>MPlex::unused_Pix() const
  626. {
  627.   if (unused == 0) return 0;
  628.  
  629.   for(<T>MChunk* t = ch; 
  630.       t->unused_indices() == 0; 
  631.       t = (<T>MChunk*)(t->prev()))
  632.     ;
  633.  
  634.   set_cache(t);
  635.   return t->pointer_to(t->unused_index()); 
  636. }
  637.  
  638. int <T>MPlex::del_index(int idx)
  639. {
  640.   if (idx < lo || idx >= fnc) index_error();
  641.   if (<T>MPlex::valid(idx))
  642.   {
  643.     ++unused;
  644.     ch-><T>MChunk::del(idx);
  645.     return 1;
  646.   }
  647.   else
  648.     return 0;
  649. }
  650.  
  651. int <T>MPlex::dopred(int idx) const
  652. {
  653.  
  654.   if (idx >= fnc) idx = fnc;
  655.   if (idx <= lo) return lo - 1;
  656.  
  657.   const <T>MChunk* t = ch;
  658.   
  659.   while (idx > t->fence_index())
  660.   {
  661.     t = ((<T>MChunk*)(t->next()));
  662.   }
  663.   while (idx <= t->low_index())
  664.   {
  665.     t = ((<T>MChunk*)(t->prev()));
  666.   }
  667.   int i = t-><T>MChunk::pred(idx);
  668.   while (i < t->low_index() && i >= lo)
  669.   {
  670.     t = ((<T>MChunk*)(t->prev()));
  671.     i = t-><T>MChunk::last_index();
  672.   }
  673.   set_cache(t);
  674.   return i;
  675. }
  676.  
  677.  
  678. int <T>MPlex::dosucc(int idx) const
  679. {
  680.   if (idx < lo) idx = lo;
  681.   if (idx >= fnc - 1) return fnc;
  682.  
  683.   const <T>MChunk* t = ch;
  684.   while (idx >= t->fence_index())
  685.   {
  686.     t = ((<T>MChunk*)(t->next()));
  687.   }
  688.   while (idx < t->low_index())
  689.   {
  690.     t = ((<T>MChunk*)(t->prev()));
  691.   }
  692.   int i = t-><T>MChunk::succ(idx);
  693.   while (i >= t->fence_index() && i < fnc)
  694.   {
  695.     t = (<T>MChunk*)(t->next());
  696.     i = t-><T>MChunk::first_index();
  697.   }
  698.   set_cache(t);
  699.   return i;
  700. }
  701.  
  702. void <T>MPlex::prev(Pix& i) const
  703. {
  704.   if (i == 0) return;
  705.  
  706.   <T>* p = (<T>*) i;
  707.   const <T>MChunk* old = ch;
  708.   const <T>MChunk* t = ch;
  709.  
  710.   while (!t->actual_pointer(p))
  711.   {
  712.     t = ((<T>MChunk*)(t->prev()));
  713.     if (t == old) 
  714.     { 
  715.       i = 0; 
  716.       return; 
  717.     }
  718.   }
  719.   <T>* q = t-><T>MChunk::pred(p);
  720.   while (q == 0 && t != (<T>MChunk*)hd)
  721.   {
  722.     t = ((<T>MChunk*)(t->prev()));
  723.     q = t-><T>MChunk::last_pointer();
  724.   }
  725.  
  726.   i = Pix(q); 
  727.   set_cache(t);
  728.   return; 
  729. }
  730.  
  731. void <T>MPlex::next(Pix& i) const
  732. {
  733.   if (i == 0) return;
  734.  
  735.   <T>* p = (<T>*) i;
  736.   const <T>MChunk* tail = (<T>MChunk*)(tl());
  737.   const <T>MChunk* old = ch;
  738.   const <T>MChunk* t = ch;
  739.  
  740.   while (!t->actual_pointer(p))
  741.   {
  742.     t = ((<T>MChunk*)(t->next()));
  743.     if (t == old) 
  744.     { 
  745.       i = 0; 
  746.       return; 
  747.     }
  748.   }
  749.   <T>* q = t-><T>MChunk::succ(p);
  750.   while  (q == 0 && t != tail)
  751.   {
  752.     t = ((<T>MChunk*)(t->next()));
  753.     q = t-><T>MChunk::first_pointer();
  754.   }
  755.  
  756.   i = Pix(q); 
  757.   set_cache(t);
  758.   return; 
  759. }
  760.  
  761.     
  762. void <T>MPlex::undel_index(int idx)
  763. {
  764.   if (idx < lo || idx >= fnc) index_error();
  765.  
  766.   <T>MChunk* t = ch;
  767.   while (idx >= t->fence_index())
  768.   {
  769.     t = ((<T>MChunk*)(t->next()));
  770.   }
  771.   while (idx < t->low_index())
  772.   {
  773.     t = ((<T>MChunk*)(t->prev()));
  774.   }
  775.   int was_present = t-><T>MChunk::undel(idx);
  776.   if (!was_present) 
  777.   {
  778.     --unused;
  779.   }
  780.   set_cache(t);
  781.   return;
  782. }
  783.  
  784. void <T>MPlex::clear()
  785. {
  786.   if (fnc != lo)
  787.   {
  788.     <T>MChunk* t = ((<T>MChunk*)tl());
  789.     while (t != hd)
  790.     {
  791.       <T>MChunk* prv = (<T>MChunk*)(t->prev());
  792.       del_chunk(t);
  793.       t = prv;
  794.     }
  795.     t-><T>MChunk::clear(lo);
  796.     set_cache(t);
  797.     fnc = lo;
  798.     unused = 0;
  799.   }
  800. }
  801.  
  802. int <T>MPlex::OK () const
  803. {
  804.   int v = hd != 0;                    // at least one chunk
  805.  
  806.   int found_ch = 0;                   // to make sure ch is in list;
  807.  
  808.   int count = 0;                      // to count unused slots
  809.  
  810.   const <T>MChunk* t = (<T>MChunk*)(hd);
  811.  
  812.   int gap = t->low_index() - lo;
  813.   v &= gap == 0;                      // hd lo not less than lo.
  814.   count += gap;
  815.  
  816.   for (;;)
  817.   {
  818.     if (t == ch) ++found_ch;
  819.     v &= t-><T>MChunk::OK();             // each chunk is OK
  820.     count += t->unused_indices();
  821.     if (t == (<T>MChunk*)(tl()))
  822.       break;
  823.     else                              // and has indices less than succ
  824.     {
  825.       gap = t->next()->base_index() - t->top_index();
  826.       v &= gap == 0;
  827.       count += gap;
  828.  
  829.       if (t != (<T>MChunk*)hd)                  // internal chunks can't grow
  830.         v &= !t->can_grow_low() && !t->can_grow_high();
  831.  
  832.       t = (const <T>MChunk*)(t->next());
  833.     }
  834.   }
  835.   gap = fnc - t->fence_index();
  836.   v &= gap == 0;
  837.   count += gap;
  838.  
  839.   v &= count == unused;              // chunk counts agree with plex
  840.  
  841.   v &= found_ch == 1;
  842.   if (!v) error("invariant failure");
  843.   return v;
  844. }
  845.  
  846.