summaryrefslogtreecommitdiff
path: root/gnu/lib/libg++/g++-include/gen/MPlex.ccP
diff options
context:
space:
mode:
Diffstat (limited to 'gnu/lib/libg++/g++-include/gen/MPlex.ccP')
-rw-r--r--gnu/lib/libg++/g++-include/gen/MPlex.ccP850
1 files changed, 850 insertions, 0 deletions
diff --git a/gnu/lib/libg++/g++-include/gen/MPlex.ccP b/gnu/lib/libg++/g++-include/gen/MPlex.ccP
new file mode 100644
index 00000000000..2008d8555a5
--- /dev/null
+++ b/gnu/lib/libg++/g++-include/gen/MPlex.ccP
@@ -0,0 +1,850 @@
+// This may look like C code, but it is really -*- C++ -*-
+/*
+Copyright (C) 1988 Free Software Foundation
+ written by Doug Lea (dl@rocky.oswego.edu)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+This file is part of GNU CC.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY. No author or distributor
+accepts responsibility to anyone for the consequences of using it
+or for whether it serves any particular purpose or works at all,
+unless he says so in writing. Refer to the GNU CC General Public
+License for full details.
+
+Everyone is granted permission to copy, modify and redistribute
+GNU CC, but only under the conditions described in the
+GNU CC General Public License. A copy of this license is
+supposed to have been given to you along with GNU CC so you
+can know your rights and responsibilities. It should be in a
+file named COPYING. Among other things, the copyright notice
+and this notice must be preserved on all copies.
+*/
+
+#ifdef __GNUG__
+#pragma implementation
+#endif
+#include "<T>.MPlex.h"
+
+// <T>MChunk support
+
+
+<T>MChunk::<T>MChunk(<T>* d,
+ int baseidx,
+ int lowidx,
+ int fenceidx,
+ int topidx)
+ : <T>IChunk(d, baseidx, lowidx, fenceidx, topidx)
+{
+ unused = fence - low;
+ unsigned msize = (top - base)/_MAP_BITS + 1;
+ map = (unsigned long *) (new long[msize]);
+ bzero((void*)map, msize * sizeof(long));
+}
+
+void <T>MChunk:: shrink_high ()
+{
+ if (fence <= low) empty_error();
+ --fence;
+ if (!valid(fence))
+ --unused;
+ else
+ free(fence);
+ reset_high();
+}
+
+void <T>MChunk:: shrink_low ()
+{
+ if (fence <= low) empty_error();
+ if (!valid(low))
+ --unused;
+ else
+ free(low);
+ ++low;
+ reset_low();
+}
+
+void <T>MChunk::clear(int lo)
+{
+ int s = top - base;
+ low = base = fence = lo;
+ top = base + s;
+ unused = 0;
+ bzero((void*)map, ((top - base)/_MAP_BITS + 1) * sizeof(long));
+}
+
+void <T>MChunk::cleardown(int hi)
+{
+ int s = top - base;
+ low = top = fence = hi;
+ base = top - s;
+ unused = 0;
+ bzero((void*)map, ((top - base)/_MAP_BITS + 1) * sizeof(long));
+}
+
+int <T>MChunk::del(int idx)
+{
+ if (idx < low || idx >= fence) index_error();
+ int v = valid(idx);
+ if (v)
+ {
+ free(idx);
+ ++unused;
+ }
+ return v;
+}
+
+
+int <T>MChunk::undel(int idx)
+{
+ if (idx < low || idx >= fence) index_error();
+ int v = valid(idx);
+ if (!v)
+ {
+ mark(idx);
+ --unused;
+ }
+ return v;
+}
+
+int <T>MChunk::unused_index() const
+{
+ if (unused_indices() == 0) index_error();
+ int slot;
+ if (low == base) // can traverse 32 slots at a time
+ {
+ int blk = 0;
+ while (map[blk] == ~0L) ++blk;
+ slot = blk * _MAP_BITS + base;
+ }
+ else
+ slot = low;
+
+ while(valid(slot)) ++slot;
+ return slot;
+}
+
+int <T>MChunk::first_index() const
+{
+ if (empty()) return fence;
+ int slot;
+ if (low == base)
+ {
+ int blk = 0;
+ while (map[blk] == 0) ++blk;
+ slot = blk * _MAP_BITS + base;
+ }
+ else
+ slot = low;
+
+ while(!valid(slot)) ++slot;
+ return slot;
+}
+
+int <T>MChunk::last_index() const
+{
+ if (empty()) return low - 1;
+ int slot;
+ if (top == fence)
+ {
+ int blk = (top - base) / _MAP_BITS;
+ while (map[blk] == 0) --blk;
+ slot = blk * _MAP_BITS + base + _MAP_BITS - 1;
+ }
+ else
+ slot = fence - 1;
+
+ while(!valid(slot)) --slot;
+ return slot;
+}
+
+
+int <T>MChunk:: OK() const
+{
+ int v = data != 0; // have some data
+ v &= map != 0; // and a map
+ v &= base <= low; // ok, index-wise
+ v &= low <= fence;
+ v &= fence <= top;
+
+ v &= ((<T>MChunk*)(nxt->prev())) == this; // and links are OK
+ v &= ((<T>MChunk*)(prv->next())) == this;
+
+ int bitcount = 0; // and unused count correct
+ for (int i = low; i < fence; ++i) if (!valid(i)) ++bitcount;
+ v &= unused == bitcount;
+
+ if (!v) error("invariant failure");
+ return(v);
+}
+
+<T>* <T>MChunk::succ(<T>* p) const
+{
+ int i = ((int) p - (int) data) / sizeof(<T>) + base + 1;
+ if (p == 0 || i < low) return 0;
+ while (i < fence && !valid(i)) ++i;
+ if (i >= fence) return 0;
+ return pointer_to(i);
+}
+
+<T>* <T>MChunk::pred(<T>* p) const
+{
+ int i = ((int) p - (int) data) / sizeof(<T>) + base - 1;
+ if (p == 0 || i >= fence) return 0;
+ while (i >= low && !valid(i)) --i;
+ if (i < low) return 0;
+ return pointer_to(i);
+}
+
+<T>* <T>MChunk::first_pointer() const
+{
+ if (empty()) return 0;
+ int slot;
+ if (low == base)
+ {
+ int blk = 0;
+ while (map[blk] == 0) ++blk;
+ slot = blk * _MAP_BITS + base;
+ }
+ else
+ slot = low;
+
+ while(!valid(slot)) ++slot;
+ return pointer_to(slot);
+}
+
+<T>* <T>MChunk::last_pointer() const
+{
+ if (empty()) return 0;
+ int slot;
+ if (top == fence)
+ {
+ int blk = (top - base) / _MAP_BITS;
+ while (map[blk] == 0) --blk;
+ slot = blk * _MAP_BITS + base + _MAP_BITS - 1;
+ }
+ else
+ slot = fence - 1;
+
+ while(!valid(slot)) --slot;
+ return pointer_to(slot);
+}
+
+<T>MPlex:: <T>MPlex()
+{
+ unused = 0;
+ lo = fnc = 0;
+ csize = DEFAULT_INITIAL_CAPACITY;
+ <T>* data = new <T>[csize];
+ hd = ch = new <T>MChunk(data, lo, lo, fnc, lo+csize);
+}
+
+<T>MPlex:: <T>MPlex(int chunksize)
+{
+ if (chunksize == 0) error("invalid constructor specification");
+ unused = 0;
+ lo = fnc = 0;
+ if (chunksize > 0)
+ {
+ csize = chunksize;
+ <T>* data = new <T>[csize];
+ hd = ch = new <T>MChunk(data, lo, lo, fnc, csize);
+ }
+ else
+ {
+ csize = -chunksize;
+ <T>* data = new <T>[csize];
+ hd = ch = new <T>MChunk(data, chunksize, lo, fnc, fnc);
+ }
+}
+
+
+<T>MPlex:: <T>MPlex(int l, int chunksize)
+{
+ if (chunksize == 0) error("invalid constructor specification");
+ unused = 0;
+ lo = fnc = l;
+ if (chunksize > 0)
+ {
+ csize = chunksize;
+ <T>* data = new <T>[csize];
+ hd = ch = new <T>MChunk(data, lo, lo, fnc, csize+lo);
+ }
+ else
+ {
+ csize = -chunksize;
+ <T>* data = new <T>[csize];
+ hd = ch = new <T>MChunk(data, chunksize+lo, lo, fnc, fnc);
+ }
+}
+
+
+void <T>MPlex::make_initial_chunks(int up)
+{
+ int need = fnc - lo;
+ hd = 0;
+ if (up)
+ {
+ int l = lo;
+ do
+ {
+ int sz;
+ if (need >= csize)
+ sz = csize;
+ else
+ sz = need;
+ <T>* data = new <T> [csize];
+ <T>MChunk* h = new <T>MChunk(data, l, l, l+sz, l+csize);
+ if (hd != 0)
+ h->link_to_next(hd);
+ else
+ hd = h;
+ l += sz;
+ need -= sz;
+ } while (need > 0);
+ }
+ else
+ {
+ int hi = fnc;
+ do
+ {
+ int sz;
+ if (need >= csize)
+ sz = csize;
+ else
+ sz = need;
+ <T>* data = new <T> [csize];
+ <T>MChunk* h = new <T>MChunk(data, hi-csize, hi-sz, hi, hi);
+ if (hd != 0)
+ h->link_to_next(hd);
+ hd = h;
+ hi -= sz;
+ need -= sz;
+ } while (need > 0);
+ }
+ ch = (<T>MChunk*) hd;
+}
+
+<T>MPlex:: <T>MPlex(int l, int hi, const <T&> initval, int chunksize)
+{
+ lo = l;
+ fnc = hi + 1;
+ if (chunksize == 0)
+ {
+ csize = fnc - l;
+ make_initial_chunks(1);
+ }
+ else if (chunksize < 0)
+ {
+ csize = -chunksize;
+ make_initial_chunks(0);
+ }
+ else
+ {
+ csize = chunksize;
+ make_initial_chunks(1);
+ }
+ unused = fnc - lo;
+ for (int i=lo; i<fnc; ++i)
+ undel_index(i);
+ fill(initval);
+}
+
+<T>MPlex::<T>MPlex(const <T>MPlex& a)
+{
+ lo = a.lo;
+ fnc = a.fnc;
+ csize = a.csize;
+ unused = fnc - lo;
+ hd = 0;
+ const <T>IChunk* p = a.hd;
+ do
+ {
+ <T>* data = new <T> [p->size()];
+ <T>MChunk* h = new <T>MChunk(data, p->base_index(),
+ p->low_index(), p->fence_index(), p->top_index());
+ if (hd != 0)
+ h->link_to_next(hd);
+ else
+ hd = h;
+ p = p->next();
+ } while (p != a.hd);
+ ch = (<T>MChunk*) hd;
+ for (int i = a.low(); i < a.fence(); a.next(i))
+ {
+ undel_index(i);
+ (*this)[i] = a[i];
+ }
+}
+
+void <T>MPlex::operator= (const <T>MPlex& a)
+{
+ if (&a != this)
+ {
+ invalidate();
+ lo = a.lo;
+ fnc = a.fnc;
+ csize = a.csize;
+ unused = fnc - lo;
+ hd = 0;
+ const <T>IChunk* p = a.hd;
+ do
+ {
+ <T>* data = new <T> [p->size()];
+ <T>MChunk* h = new <T>MChunk(data, p->base_index(),
+ p->low_index(), p->fence_index(),
+ p->top_index());
+ if (hd != 0)
+ h->link_to_next(hd);
+ else
+ hd = h;
+ p = p->next();
+ } while (p != a.hd);
+ ch = (<T>MChunk*) hd;
+ for (int i = a.low(); i < a.fence(); a.next(i))
+ {
+ undel_index(i);
+ (*this)[i] = a[i];
+ }
+ }
+}
+
+int <T>MPlex::valid(int idx) const
+{
+ const <T>MChunk* tail = (<T>MChunk*)tl();
+ const <T>MChunk* t = ch;
+ while (idx >= t->fence_index())
+ {
+ if (t == tail) return 0;
+ t = ((<T>MChunk*)(t->next()));
+ }
+ while (idx < t->low_index())
+ {
+ if (t == (<T>MChunk*)(hd)) return 0;
+ t = ((<T>MChunk*)(t->prev()));
+ }
+ set_cache(t);
+ return t-><T>MChunk::valid_index(idx);
+}
+
+void <T>MPlex::cache(int idx) const
+{
+ const <T>MChunk* tail = (<T>MChunk*)tl();
+ const <T>MChunk* t = ch;
+ while (idx >= t->fence_index())
+ {
+ if (t == tail) index_error();
+ t = ((<T>MChunk*)(t->next()));
+ }
+ while (idx < t->low_index())
+ {
+ if (t == (<T>MChunk*)hd) index_error();
+ t = ((<T>MChunk*)(t->prev()));
+ }
+ if (!t-><T>MChunk::valid_index(idx)) index_error();
+ set_cache(t);
+}
+
+void <T>MPlex::cache(const <T>* p) const
+{
+ const <T>MChunk* old = ch;
+ const <T>MChunk* t = ch;
+ while (!t->actual_pointer(p))
+ {
+ t = ((<T>MChunk*)(t->next()));
+ if (t == old) index_error();
+ }
+ if (!t-><T>MChunk::valid_pointer(p)) index_error();
+ set_cache(t);
+}
+
+int <T>MPlex::owns(Pix px) const
+{
+ <T>* p = (<T>*)px;
+ const <T>MChunk* old = ch;
+ const <T>MChunk* t = ch;
+ while (!t->actual_pointer(p))
+ {
+ t = ((<T>MChunk*)(t->next()));
+ if (t == old) return 0;
+ }
+ set_cache(t);
+ return t-><T>MChunk::valid_pointer(p);
+}
+
+int <T>MPlex::add_high(const <T&> elem)
+{
+ <T>MChunk* t = ((<T>MChunk*) tl());
+
+ if (!t->can_grow_high())
+ {
+ <T>* data = new <T> [csize];
+ t = (new <T>MChunk(data, fnc,fnc,fnc,fnc+csize));
+ t->link_to_prev(tl());
+ }
+
+ *((t-><T>MChunk::grow_high())) = elem;
+ set_cache(t);
+ return fnc++;
+}
+
+int <T>MPlex::add_low (const <T&> elem)
+{
+ <T>MChunk* t = ((<T>MChunk*) hd);
+ if (!t->can_grow_low())
+ {
+ <T>* data = new <T> [csize];
+ hd = new <T>MChunk(data, lo-csize, lo, lo, lo);
+ hd->link_to_next(t);
+ t = ((<T>MChunk*) hd);
+ }
+
+ *((t-><T>MChunk::grow_low())) = elem;
+ set_cache(t);
+ return --lo;
+}
+
+void <T>MPlex::adjust_bounds()
+{
+ <T>MChunk* t = ((<T>MChunk*) tl());
+
+ // clean up tail
+
+ t->reset_high();
+ while (t-><T>MChunk::empty() && !one_chunk())
+ {
+ <T>MChunk* pred = (<T>MChunk*)(t->prev());
+ del_chunk(t);
+ pred->reset_high();
+ t = (pred);
+ }
+ if (one_chunk())
+ t->reset_high();
+
+ int oldfnc = fnc;
+ fnc = t->fence_index();
+ unused -= oldfnc - fnc;
+
+ // and head..
+ t = ((<T>MChunk*) hd);
+ t->reset_low();
+ while (t-><T>MChunk::empty() && !one_chunk())
+ {
+ hd = (<T>MChunk*)(t->next());
+ del_chunk(t);
+ t = ((<T>MChunk*) hd);
+ t->reset_low();
+ }
+
+ int oldlo = lo;
+ lo = t->low_index();
+ unused -= lo - oldlo;
+
+
+ set_cache(t);
+}
+
+int <T>MPlex::del_high ()
+{
+ if (empty()) empty_error();
+ <T>MChunk* t = ((<T>MChunk*) tl());
+ while (t-><T>MChunk::empty() && !one_chunk()) // possible stragglers
+ {
+ <T>MChunk* pred = (<T>MChunk*)(t->prev());
+ del_chunk(t);
+ pred->reset_high();
+ t = (pred);
+ }
+ t-><T>MChunk::shrink_high();
+ while (t-><T>MChunk::empty() && !one_chunk())
+ {
+ <T>MChunk* pred = (<T>MChunk*)(t->prev());
+ del_chunk(t);
+ pred->reset_high();
+ t = (pred);
+ }
+ int oldfnc = fnc;
+ fnc = t->fence_index();
+ unused -= oldfnc - fnc - 1;
+ set_cache(t);
+ return fnc - 1;
+}
+
+int <T>MPlex::del_low ()
+{
+ if (empty()) empty_error();
+ <T>MChunk* t = ((<T>MChunk*) hd);
+ while (t-><T>MChunk::empty() && !one_chunk())
+ {
+ hd = (<T>MChunk*)(t->next());
+ del_chunk(t);
+ t = ((<T>MChunk*) hd);
+ t->reset_low();
+ }
+ t-><T>MChunk::shrink_low();
+ while (t-><T>MChunk::empty() && !one_chunk())
+ {
+ hd = (<T>MChunk*)(t->next());
+ del_chunk(t);
+ t = ((<T>MChunk*) hd);
+ t->reset_low();
+ }
+ int oldlo = lo;
+ lo = t->low_index();
+ unused -= lo - oldlo - 1;
+ set_cache(t);
+ return lo;
+}
+
+int <T>MPlex::add(const <T&> elem)
+{
+ if (unused == 0)
+ return add_high(elem);
+
+ for(<T>MChunk* t = ch;
+ t->unused_indices() == 0;
+ t = (<T>MChunk*)(t->prev()))
+ ;
+
+ int i = t->unused_index();
+ set_cache(t);
+ undel_index(i);
+ (*this)[i] = elem;
+ return i;
+}
+
+int <T>MPlex::unused_index() const
+{
+ if (unused == 0) index_error();
+
+ for(<T>MChunk* t = ch;
+ t->unused_indices() == 0;
+ t = (<T>MChunk*)(t->prev()))
+ ;
+
+ set_cache(t);
+ return t->unused_index();
+}
+
+Pix <T>MPlex::unused_Pix() const
+{
+ if (unused == 0) return 0;
+
+ for(<T>MChunk* t = ch;
+ t->unused_indices() == 0;
+ t = (<T>MChunk*)(t->prev()))
+ ;
+
+ set_cache(t);
+ return t->pointer_to(t->unused_index());
+}
+
+int <T>MPlex::del_index(int idx)
+{
+ if (idx < lo || idx >= fnc) index_error();
+ if (<T>MPlex::valid(idx))
+ {
+ ++unused;
+ ch-><T>MChunk::del(idx);
+ return 1;
+ }
+ else
+ return 0;
+}
+
+int <T>MPlex::dopred(int idx) const
+{
+
+ if (idx >= fnc) idx = fnc;
+ if (idx <= lo) return lo - 1;
+
+ const <T>MChunk* t = ch;
+
+ while (idx > t->fence_index())
+ {
+ t = ((<T>MChunk*)(t->next()));
+ }
+ while (idx <= t->low_index())
+ {
+ t = ((<T>MChunk*)(t->prev()));
+ }
+ int i = t-><T>MChunk::pred(idx);
+ while (i < t->low_index() && i >= lo)
+ {
+ t = ((<T>MChunk*)(t->prev()));
+ i = t-><T>MChunk::last_index();
+ }
+ set_cache(t);
+ return i;
+}
+
+
+int <T>MPlex::dosucc(int idx) const
+{
+ if (idx < lo) idx = lo;
+ if (idx >= fnc - 1) return fnc;
+
+ const <T>MChunk* t = ch;
+ while (idx >= t->fence_index())
+ {
+ t = ((<T>MChunk*)(t->next()));
+ }
+ while (idx < t->low_index())
+ {
+ t = ((<T>MChunk*)(t->prev()));
+ }
+ int i = t-><T>MChunk::succ(idx);
+ while (i >= t->fence_index() && i < fnc)
+ {
+ t = (<T>MChunk*)(t->next());
+ i = t-><T>MChunk::first_index();
+ }
+ set_cache(t);
+ return i;
+}
+
+void <T>MPlex::prev(Pix& i) const
+{
+ if (i == 0) return;
+
+ <T>* p = (<T>*) i;
+ const <T>MChunk* old = ch;
+ const <T>MChunk* t = ch;
+
+ while (!t->actual_pointer(p))
+ {
+ t = ((<T>MChunk*)(t->prev()));
+ if (t == old)
+ {
+ i = 0;
+ return;
+ }
+ }
+ <T>* q = t-><T>MChunk::pred(p);
+ while (q == 0 && t != (<T>MChunk*)hd)
+ {
+ t = ((<T>MChunk*)(t->prev()));
+ q = t-><T>MChunk::last_pointer();
+ }
+
+ i = Pix(q);
+ set_cache(t);
+ return;
+}
+
+void <T>MPlex::next(Pix& i) const
+{
+ if (i == 0) return;
+
+ <T>* p = (<T>*) i;
+ const <T>MChunk* tail = (<T>MChunk*)(tl());
+ const <T>MChunk* old = ch;
+ const <T>MChunk* t = ch;
+
+ while (!t->actual_pointer(p))
+ {
+ t = ((<T>MChunk*)(t->next()));
+ if (t == old)
+ {
+ i = 0;
+ return;
+ }
+ }
+ <T>* q = t-><T>MChunk::succ(p);
+ while (q == 0 && t != tail)
+ {
+ t = ((<T>MChunk*)(t->next()));
+ q = t-><T>MChunk::first_pointer();
+ }
+
+ i = Pix(q);
+ set_cache(t);
+ return;
+}
+
+
+void <T>MPlex::undel_index(int idx)
+{
+ if (idx < lo || idx >= fnc) index_error();
+
+ <T>MChunk* t = ch;
+ while (idx >= t->fence_index())
+ {
+ t = ((<T>MChunk*)(t->next()));
+ }
+ while (idx < t->low_index())
+ {
+ t = ((<T>MChunk*)(t->prev()));
+ }
+ int was_present = t-><T>MChunk::undel(idx);
+ if (!was_present)
+ {
+ --unused;
+ }
+ set_cache(t);
+ return;
+}
+
+void <T>MPlex::clear()
+{
+ if (fnc != lo)
+ {
+ <T>MChunk* t = ((<T>MChunk*)tl());
+ while (t != hd)
+ {
+ <T>MChunk* prv = (<T>MChunk*)(t->prev());
+ del_chunk(t);
+ t = prv;
+ }
+ t-><T>MChunk::clear(lo);
+ set_cache(t);
+ fnc = lo;
+ unused = 0;
+ }
+}
+
+int <T>MPlex::OK () const
+{
+ int v = hd != 0; // at least one chunk
+
+ int found_ch = 0; // to make sure ch is in list;
+
+ int count = 0; // to count unused slots
+
+ const <T>MChunk* t = (<T>MChunk*)(hd);
+
+ int gap = t->low_index() - lo;
+ v &= gap == 0; // hd lo not less than lo.
+ count += gap;
+
+ for (;;)
+ {
+ if (t == ch) ++found_ch;
+ v &= t-><T>MChunk::OK(); // each chunk is OK
+ count += t->unused_indices();
+ if (t == (<T>MChunk*)(tl()))
+ break;
+ else // and has indices less than succ
+ {
+ gap = t->next()->base_index() - t->top_index();
+ v &= gap == 0;
+ count += gap;
+
+ if (t != (<T>MChunk*)hd) // internal chunks can't grow
+ v &= !t->can_grow_low() && !t->can_grow_high();
+
+ t = (const <T>MChunk*)(t->next());
+ }
+ }
+ gap = fnc - t->fence_index();
+ v &= gap == 0;
+ count += gap;
+
+ v &= count == unused; // chunk counts agree with plex
+
+ v &= found_ch == 1;
+ if (!v) error("invariant failure");
+ return v;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-27 11:59:42 +0000