head 1.2; access; symbols perseant-exfatfs-base-20261102:1.2 perseant-exfatfs-base-20250801:1.2 perseant-exfatfs-base-20240630:1.2 cjep_sun2x:1.2.0.44 cjep_sun2x-base:1.2 cjep_staticlib_x-base1:1.2 cjep_staticlib_x:1.2.0.42 cjep_staticlib_x-base:1.2 phil-wifi-20200421:1.2 phil-wifi-20200411:1.2 phil-wifi-20200406:1.2 pgoyette-compat-merge-20190127:1.2 pgoyette-compat-20190127:1.2 pgoyette-compat-20190118:1.2 pgoyette-compat-1226:1.2 pgoyette-compat-1126:1.2 pgoyette-compat-1020:1.2 pgoyette-compat-0930:1.2 pgoyette-compat-0906:1.2 pgoyette-compat-0728:1.2 pgoyette-compat-0625:1.2 pgoyette-compat-0521:1.2 pgoyette-compat-0502:1.2 pgoyette-compat-0422:1.2 pgoyette-compat-0415:1.2 pgoyette-compat-0407:1.2 pgoyette-compat-0330:1.2 pgoyette-compat-0322:1.2 pgoyette-compat-0315:1.2 pgoyette-compat:1.2.0.40 pgoyette-compat-base:1.2 perseant-stdc-iso10646:1.2.0.38 perseant-stdc-iso10646-base:1.2 prg-localcount2-base3:1.2 prg-localcount2-base2:1.2 prg-localcount2-base1:1.2 prg-localcount2:1.2.0.36 prg-localcount2-base:1.2 pgoyette-localcount-20170426:1.2 bouyer-socketcan-base1:1.2 pgoyette-localcount-20170320:1.2 bouyer-socketcan:1.2.0.34 bouyer-socketcan-base:1.2 pgoyette-localcount-20170107:1.2 pgoyette-localcount-20161104:1.2 localcount-20160914:1.2 pgoyette-localcount-20160806:1.2 pgoyette-localcount-20160726:1.2 pgoyette-localcount:1.2.0.32 pgoyette-localcount-base:1.2 netbsd-5-2-3-RELEASE:1.2 netbsd-5-1-5-RELEASE:1.2 yamt-pagecache-base9:1.2 yamt-pagecache-tag8:1.2 tls-earlyentropy:1.2.0.28 tls-earlyentropy-base:1.2 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.2 riastradh-drm2-base3:1.2 netbsd-5-2-2-RELEASE:1.2 netbsd-5-1-4-RELEASE:1.2 netbsd-5-2-1-RELEASE:1.2 netbsd-5-1-3-RELEASE:1.2 agc-symver:1.2.0.30 agc-symver-base:1.2 tls-maxphys-base:1.2 yamt-pagecache-base8:1.2 netbsd-5-2:1.2.0.26 yamt-pagecache-base7:1.2 netbsd-5-2-RELEASE:1.2 netbsd-5-2-RC1:1.2 yamt-pagecache-base6:1.2 yamt-pagecache-base5:1.2 yamt-pagecache-base4:1.2 netbsd-5-1-2-RELEASE:1.2 netbsd-5-1-1-RELEASE:1.2 yamt-pagecache-base3:1.2 yamt-pagecache-base2:1.2 yamt-pagecache:1.2.0.24 yamt-pagecache-base:1.2 bouyer-quota2-nbase:1.2 bouyer-quota2:1.2.0.22 bouyer-quota2-base:1.2 matt-nb5-pq3:1.2.0.20 matt-nb5-pq3-base:1.2 netbsd-5-1:1.2.0.18 netbsd-5-1-RELEASE:1.2 netbsd-5-1-RC4:1.2 netbsd-5-1-RC3:1.2 netbsd-5-1-RC2:1.2 netbsd-5-1-RC1:1.2 netbsd-5-0-2-RELEASE:1.2 netbsd-5-0-1-RELEASE:1.2 jym-xensuspend-nbase:1.2 netbsd-5-0:1.2.0.16 netbsd-5-0-RELEASE:1.2 netbsd-5-0-RC4:1.2 netbsd-5-0-RC3:1.2 netbsd-5-0-RC2:1.2 jym-xensuspend:1.2.0.14 jym-xensuspend-base:1.2 netbsd-5-0-RC1:1.2 netbsd-5:1.2.0.12 netbsd-5-base:1.2 mjf-devfs2:1.2.0.10 mjf-devfs2-base:1.2 yamt-pf42-base4:1.2 yamt-pf42-base3:1.2 hpcarm-cleanup-nbase:1.2 yamt-pf42-base2:1.2 yamt-pf42:1.2.0.8 yamt-pf42-base:1.2 keiichi-mipv6:1.2.0.6 keiichi-mipv6-base:1.2 cube-autoconf:1.2.0.4 cube-autoconf-base:1.2 hpcarm-cleanup:1.2.0.2 hpcarm-cleanup-base:1.2 netbsd-1-3-PATCH003:1.1.1.1 netbsd-1-3-PATCH003-CANDIDATE2:1.1.1.1 netbsd-1-3-PATCH003-CANDIDATE1:1.1.1.1 netbsd-1-3-PATCH003-CANDIDATE0:1.1.1.1 netbsd-1-3-PATCH002:1.1.1.1 netbsd-1-3-PATCH001:1.1.1.1 netbsd-1-3-RELEASE:1.1.1.1 netbsd-1-3-BETA:1.1.1.1 netbsd-1-3:1.1.1.1.0.2 netbsd-1-3-base:1.1.1.1 netbsd-1-2-PATCH001:1.1.1.1 libg++-2-7-2:1.1.1.1 netbsd-1-2-RELEASE:1.1.1.1 netbsd-1-2-BETA:1.1.1.1 netbsd-1-2-base:1.1.1.1 netbsd-1-2:1.1.1.1.0.4 libg++-2-7-1:1.1.1.1 FSF:1.1.1; locks; strict; comment @# @; 1.2 date 98.12.12.23.50.56; author tv; state dead; branches; next 1.1; 1.1 date 96.03.09.00.01.02; author phil; state Exp; branches 1.1.1.1; next ; 1.1.1.1 date 96.03.09.00.01.02; author phil; state Exp; branches; next ; desc @@ 1.2 log @GC old gcc 2.7.2.2. @ text @// 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 the GNU C++ Library. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifdef __GNUG__ #pragma implementation #endif #include ".RPlex.h" typedef IChunk* _IChunk_ptr; RPlex:: RPlex() { lo = fnc = 0; csize = DEFAULT_INITIAL_CAPACITY; * data = new [csize]; set_cache(new IChunk(data, lo, lo, fnc, lo+csize)); hd = ch; maxch = MIN_NCHUNKS; lch = maxch / 2; fch = lch + 1; base = ch->base_index() - lch * csize; chunks = new _IChunk_ptr[maxch]; chunks[lch] = ch; } RPlex:: RPlex(int chunksize) { if (chunksize == 0) error("invalid constructor specification"); lo = fnc = 0; if (chunksize > 0) { csize = chunksize; * data = new [csize]; set_cache(new IChunk(data, lo, lo, fnc, csize+lo)); hd = ch; } else { csize = -chunksize; * data = new [csize]; set_cache(new IChunk(data, chunksize+lo, lo, fnc, fnc)); hd = ch; } maxch = MIN_NCHUNKS; lch = maxch / 2; fch = lch + 1; base = ch->base_index() - lch * csize; chunks = new _IChunk_ptr[maxch]; chunks[lch] = ch; } RPlex:: RPlex(int l, int chunksize) { if (chunksize == 0) error("invalid constructor specification"); lo = fnc = l; if (chunksize > 0) { csize = chunksize; * data = new [csize]; set_cache(new IChunk(data, lo, lo, fnc, lo+csize)); hd = ch; } else { csize = -chunksize; * data = new [csize]; set_cache(new IChunk(data, chunksize+lo, lo, fnc, fnc)); hd = ch; } maxch = MIN_NCHUNKS; lch = maxch / 2; fch = lch + 1; base = ch->base_index() - lch * csize; chunks = new _IChunk_ptr[maxch]; chunks[lch] = ch; } void RPlex::make_initial_chunks(int up) { int count = 0; int need = fnc - lo; hd = 0; if (up) { int l = lo; do { ++count; int sz; if (need >= csize) sz = csize; else sz = need; * data = new [csize]; IChunk* h = new IChunk(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 { ++count; int sz; if (need >= csize) sz = csize; else sz = need; * data = new [csize]; IChunk* h = new IChunk(data, hi-csize, hi-sz, hi, hi); if (hd != 0) h->link_to_next(hd); hd = h; hi -= sz; need -= sz; } while (need > 0); } set_cache((IChunk*)hd); maxch = MIN_NCHUNKS; if (maxch < count * 2) maxch = count * 2; chunks = new _IChunk_ptr[maxch]; lch = maxch / 3; fch = lch + count; base = ch->base_index() - csize * lch; int k = lch; do { chunks[k++] = ch; set_cache(ch->next()); } while (ch != hd); } RPlex:: RPlex(int l, int hi, const 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); } fill(initval); } RPlex::RPlex(const RPlex& a) { lo = a.lo; fnc = a.fnc; csize = a.csize; make_initial_chunks(); for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i]; } void RPlex::operator= (const RPlex& a) { if (&a != this) { invalidate(); lo = a.lo; fnc = a.fnc; csize = a.csize; make_initial_chunks(); for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i]; } } void RPlex::cache(const * p) const { const IChunk* old = ch; const IChunk* t = ch; while (!t->actual_pointer(p)) { t = (t->next()); if (t == old) index_error(); } set_cache(t); } int RPlex::owns(Pix px) const { * p = (*)px; const IChunk* old = ch; const IChunk* t = ch; while (!t->actual_pointer(p)) { t = (t->next()); if (t == old) return 0; } set_cache(t); return 1; } * RPlex::dosucc(const * p) const { if (p == 0) return 0; const IChunk* old = ch; const IChunk* t = ch; while (!t->actual_pointer(p)) { t = (t->next()); if (t == old) return 0; } int i = t->index_of(p) + 1; if (i >= fnc) return 0; if (i >= t->fence_index()) t = (t->next()); set_cache(t); return t->pointer_to(i); } * RPlex::dopred(const * p) const { if (p == 0) return 0; const IChunk* old = ch; const IChunk* t = ch; while (!t->actual_pointer(p)) { t = (t->prev()); if (t == old) return 0; } int i = t->index_of(p) - 1; if (i < lo) return 0; if (i < t->low_index()) t = (t->prev()); set_cache(t); return (t->pointer_to(i)); } int RPlex::add_high(const elem) { IChunk* t = tl(); if (!t->can_grow_high()) { if (t->IChunk::empty() && one_chunk()) { t->clear(fnc); base = t->base_index() - lch * csize; } else { * data = new [csize]; t = (new IChunk(data, fnc, fnc, fnc,fnc+csize)); t->link_to_prev(tl()); if (fch == maxch) { maxch *= 2; IChunk** newch = new _IChunk_ptr [maxch]; memcpy(newch, chunks, fch * sizeof(_IChunk_ptr)); delete chunks; chunks = newch; } chunks[fch++] = t; } } *((t->IChunk::grow_high())) = elem; set_cache(t); return fnc++; } int RPlex::del_high () { if (empty()) empty_error(); IChunk* t = tl(); if (t->IChunk::empty()) // kill straggler first { IChunk* pred = t->prev(); del_chunk(t); t = (pred); --fch; } t->IChunk::shrink_high(); if (t->IChunk::empty() && !one_chunk()) { IChunk* pred = t->prev(); del_chunk(t); t = (pred); --fch; } set_cache(t); return --fnc - 1; } int RPlex::add_low (const elem) { IChunk* t = hd; if (!t->can_grow_low()) { if (t->IChunk::empty() && one_chunk()) { t->cleardown(lo); base = t->base_index() - lch * csize; } else { * data = new [csize]; hd = new IChunk(data, lo-csize, lo, lo, lo); hd->link_to_next(t); t = ( hd); if (lch == 0) { lch = maxch; fch += maxch; maxch *= 2; IChunk** newch = new _IChunk_ptr [maxch]; memcpy(&(newch[lch]), chunks, lch * sizeof(_IChunk_ptr)); delete chunks; chunks = newch; base = t->base_index() - (lch - 1) * csize; } chunks[--lch] = t; } } *((t->IChunk::grow_low())) = elem; set_cache(t); return --lo; } int RPlex::del_low () { if (empty()) empty_error(); IChunk* t = hd; if (t->IChunk::empty()) { hd = t->next(); del_chunk(t); t = hd; ++lch; } t->IChunk::shrink_low(); if (t->IChunk::empty() && !one_chunk()) { hd = t->next(); del_chunk(t); t = hd; ++lch; } set_cache(t); return ++lo; } void RPlex::reverse() { tmp; int l = lo; int h = fnc - 1; IChunk* loch = hd; IChunk* hich = tl(); while (l < h) { * lptr = loch->pointer_to(l); * hptr = hich->pointer_to(h); tmp = *lptr; *lptr = *hptr; *hptr = tmp; if (++l >= loch->fence_index()) loch = loch->next(); if (--h < hich->low_index()) hich = hich->prev(); } } void RPlex::fill(const x) { for (int i = lo; i < fnc; ++i) (*this)[i] = x; } void RPlex::fill(const x, int lo, int hi) { for (int i = lo; i <= hi; ++i) (*this)[i] = x; } void RPlex::clear() { for (int i = lch + 1; i < fch; ++i) del_chunk(chunks[i]); fch = lch + 1; set_cache(chunks[lch]); ch->IChunk::clear(lo); fnc = lo; } int RPlex::reset_low(int l) { int old = lo; int diff = l - lo; if (diff != 0) { lo += diff; fnc += diff; IChunk* t = hd; do { t->re_index(t->low_index() + diff); t = t->next(); } while (t != hd); } base = hd->base_index() - lch * csize; return old; } int RPlex::OK () const { int v = hd != 0 && ch != 0; // at least one chunk v &= fnc == tl()->fence_index(); // last chunk fnc == plex fnc v &= lo == hd->IChunk::low_index(); // first lo == plex lo v &= base == hd->base_index() - lch * csize; // base is correct; v &= lch < fch; v &= fch <= maxch; // within allocation; // loop for others: int k = lch; // to cross-check nch int found_ch = 0; // to make sure ch is in list; const IChunk* t = (hd); for (;;) { v &= chunks[k++] == t; // each chunk is at proper index if (t == ch) ++found_ch; v &= t->IChunk::OK(); // each chunk is OK if (t == tl()) break; else // and has indices contiguous to succ { v &= t->top_index() == t->next()->base_index(); if (t != hd) // internal chunks full { v &= !t->empty(); v &= !t->can_grow_low(); v &= !t->can_grow_high(); } t = t->next(); } } v &= found_ch == 1; v &= fch == k; if (!v) error("invariant failure"); return v; } @ 1.1 log @Initial revision @ text @@ 1.1.1.1 log @Import of libg++-2.7.1. @ text @@