Category : OS/2 Files
Archive   : GPPDEV8F.ZIP
Filename : XPLEX.CCP

// This may look like C code, but it is really -*- C++ -*-
/*
Copyright (C) 1988 Free Software Foundation
written by Doug Lea ([email protected])
based on code by Marc Shapiro ([email protected])

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, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifdef __GNUG__
#pragma implementation
#endif
#include ".XPlex.h"


XPlex:: XPlex()
{
lo = fnc = 0;
csize = DEFAULT_INITIAL_CAPACITY;
* data = new [csize];
set_cache(new IChunk(data, lo, lo, fnc, lo+csize));
hd = ch;
}

XPlex:: XPlex(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));
hd = ch;
}
else
{
csize = -chunksize;
* data = new [csize];
set_cache(new IChunk(data, chunksize, lo, fnc, fnc));
hd = ch;
}
}


XPlex:: XPlex(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, csize+lo));
hd = ch;
}
else
{
csize = -chunksize;
* data = new [csize];
set_cache(new IChunk(data, chunksize+lo, lo, fnc, fnc));
hd = ch;
}
}

void XPlex::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;
* 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
{
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(hd);
}

XPlex:: XPlex(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);
}

XPlex::XPlex(const XPlex& 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 XPlex::operator= (const XPlex& 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 XPlex::cache(int idx) const
{
const IChunk* tail = tl();
const IChunk* t = ch;
while (idx >= t->fence_index())
{
if (t == tail) index_error();
t = (t->next());
}
while (idx < t->low_index())
{
if (t == hd) index_error();
t = (t->prev());
}
set_cache(t);
}


void XPlex::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 XPlex::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) { set_cache(t); return 0; }
}
set_cache(t);
return 1;
}


* XPlex::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));
}

* XPlex::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 XPlex::add_high(const elem)
{
IChunk* t = tl();
if (!t->can_grow_high())
{
if (t->IChunk::empty() && one_chunk())
t->clear(fnc);
else
{
* data = new [csize];
t = (new IChunk(data, fnc, fnc, fnc,fnc+csize));
t->link_to_prev(tl());
}
}
*((t->IChunk::grow_high())) = elem;
set_cache(t);
return fnc++;
}

int XPlex::del_high ()
{
if (empty()) empty_error();
IChunk* t = tl();
t->IChunk::shrink_high();
if (t->IChunk::empty() && !one_chunk())
{
IChunk* pred = t->prev();
del_chunk(t);
t = pred;
}
set_cache(t);
return --fnc - 1;
}

int XPlex::add_low (const elem)
{
IChunk* t = hd;
if (!t->can_grow_low())
{
if (t->IChunk::empty() && one_chunk())
t->cleardown(lo);
else
{
* data = new [csize];
hd = new IChunk(data, lo-csize, lo, lo, lo);
hd->link_to_next(t);
t = hd;
}
}
*((t->IChunk::grow_low())) = elem;
set_cache(t);
return --lo;
}


int XPlex::del_low ()
{
if (empty()) empty_error();
IChunk* t = hd;
t->IChunk::shrink_low();
if (t->IChunk::empty() && !one_chunk())
{
hd = t->next();
del_chunk(t);
t = hd;
}
set_cache(t);
return ++lo;
}

void XPlex::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 XPlex::fill(const x)
{
for (int i = lo; i < fnc; ++i) (*this)[i] = x;
}

void XPlex::fill(const x, int l, int hi)
{
for (int i = l; i <= hi; ++i) (*this)[i] = x;
}


void XPlex::clear()
{
if (fnc != lo)
{
IChunk* t = tl();
while (t != hd)
{
IChunk* prv = t->prev();
del_chunk(t);
t = prv;
}
t->IChunk::clear(lo);
set_cache(t);
fnc = lo;
}
}


int XPlex::OK () const
{
int v = hd != 0 && ch != 0; // at least one chunk

v &= fnc == tl()->fence_index();// last chunk fence == plex fence
v &= lo == ((hd))->IChunk::low_index(); // first lo == plex lo

// loop for others:
int found_ch = 0; // to make sure ch is in list;
const IChunk* t = (hd);
for (;;)
{
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;
if (!v) error("invariant failure");
return v;
}