// 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. */ #ifndef _Plex_h #ifdef __GNUG__ #pragma once #pragma interface #endif #define _Plex_h 1 #include #include #include ".defs.h" // Plexes are made out of IChunks #include class IChunk { //public: // kludge until C++ `protected' policies settled protected: * data; // data, from client int base; // lowest possible index int low; // lowest valid index int fence; // highest valid index + 1 int top; // highest possible index + 1 IChunk* nxt; // circular links IChunk* prv; public: // constructors IChunk(* d, // ptr to array of elements int base_idx, // initial indices int low_idx, int fence_idx, int top_idx); virtual ~IChunk(); // status reports int size() const; // number of slots virtual int empty() const ; virtual int full() const ; int can_grow_high () const ; // there is space to add data int can_grow_low () const; int base_index() const; // lowest possible index; int low_index() const; // lowest actual index; virtual int first_index() const; // lowest valid index or fence if none virtual int last_index() const; // highest valid index or low-1 if none int fence_index() const; // highest actual index + 1 int top_index() const; // highest possible index + 1 // indexing conversion int possible_index(int i) const; // i between base and top int actual_index(int i) const; // i between low and fence virtual int valid_index(int i) const; // i not deleted (mainly for mchunks) int possible_pointer(const * p) const; // same for ptr int actual_pointer(const * p) const; virtual int valid_pointer(const * p) const; * pointer_to(int i) const ; // pointer to data indexed by i // caution: i is not checked for validity int index_of(const * p) const; // index of data pointed to by p // caution: p is not checked for validity virtual int succ(int idx) const; // next valid index or fence if none virtual int pred(int idx) const; // previous index or low - 1 if none virtual * first_pointer() const; // pointer to first valid pos or 0 virtual * last_pointer() const; // pointer to first valid pos or 0 virtual * succ(* p) const; // next pointer or 0 virtual * pred(* p) const; // previous pointer or 0 // modification virtual * grow_high (); // return spot to add an element virtual * grow_low (); virtual void shrink_high (); // logically delete top index virtual void shrink_low (); virtual void clear(int lo); // reset to empty ch with base = lo virtual void cleardown(int hi); // reset to empty ch with top = hi void re_index(int lo); // re-index so lo is new low // chunk traversal IChunk* next() const; IChunk* prev() const; void link_to_prev(IChunk* prev); void link_to_next(IChunk* next); void unlink(); // state checks * invalidate(); // mark self as invalid; return data // for possible deletion virtual int OK() const; // representation invariant volatile void error(const char*) const; volatile void empty_error() const; volatile void full_error() const; volatile void index_error() const; }; // Plex is a partly `abstract' class: few of the virtuals // are implemented at the Plex level, only in the subclasses class Plex { protected: IChunk* hd; // a chunk holding the data int lo; // lowest index int fnc; // highest index + 1 int csize; // size of the chunk void invalidate(); // mark so OK() is false void del_chunk(IChunk*); // delete a chunk IChunk* tl() const; // last chunk; int one_chunk() const; // true if hd == tl() public: // constructors, etc. Plex(); // no-op virtual ~Plex(); // Access functions virtual & operator [] (int idx) = 0; // access by index; virtual & operator () (Pix p) = 0; // access by Pix; virtual & high_element () = 0; // access high element virtual & low_element () = 0; // access low element // read-only versions for const Plexes virtual const & operator [] (int idx) const = 0; // access by index; virtual const & operator () (Pix p) const = 0; // access by Pix; virtual const & high_element () const = 0; // access high element virtual const & low_element () const = 0; // access low element // Index functions virtual int valid (int idx) const = 0; // idx is an OK index virtual int low() const = 0; // lowest index or fence if none virtual int high() const = 0; // highest index or low-1 if none int ecnef() const; // low limit index (low-1) int fence() const; // high limit index (high+1) virtual void prev(int& idx) const= 0; // set idx to preceding index // caution: pred may be out of bounds virtual void next(int& idx) const = 0; // set to next index // caution: succ may be out of bounds virtual Pix first() const = 0; // Pix to low element or 0 virtual Pix last() const = 0; // Pix to high element or 0 virtual void prev(Pix& pix) const = 0; // preceding pix or 0 virtual void next(Pix& pix) const = 0; // next pix or 0 virtual int owns(Pix p) const = 0; // p is an OK Pix // index<->Pix virtual int Pix_to_index(Pix p) const = 0; // get index via Pix virtual Pix index_to_Pix(int idx) const = 0; // Pix via index // Growth virtual int add_high(const elem) =0;// add new element at high end // return new high virtual int add_low(const elem) = 0; // add new low element, // return new low // Shrinkage virtual int del_high() = 0; // remove the element at high end // return new high virtual int del_low() = 0; // delete low element, return new lo // caution: del_low/high // does not necessarily // immediately call ::~ // operations on multiple elements virtual void fill(const x); // set all elements = x virtual void fill(const x, int from, int to); // fill from to to virtual void clear() = 0; // reset to zero-sized Plex virtual int reset_low(int newlow); // change low index,return old virtual void reverse(); // reverse in-place virtual void append(const Plex& a); // concatenate a copy virtual void prepend(const Plex& a); // prepend a copy // status virtual int can_add_high() const = 0; virtual int can_add_low() const = 0; int length () const; // number of slots int empty () const; // is the plex empty? virtual int full() const = 0; // it it full? int chunk_size() const; // report chunk size; virtual int OK() const = 0; // representation invariant volatile void error(const char* msg) const; volatile void index_error() const; volatile void empty_error() const; volatile void full_error() const; }; #if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES) // IChunk ops inline int IChunk:: size() const { return top - base; } inline int IChunk:: base_index() const { return base; } inline int IChunk:: low_index() const { return low; } inline int IChunk:: fence_index() const { return fence; } inline int IChunk:: top_index() const { return top; } inline * IChunk:: pointer_to(int i) const { return &(data[i-base]); } inline int IChunk:: index_of(const * p) const { return ((int)p - (int)data) / sizeof() + base; } inline int IChunk:: possible_index(int i) const { return i >= base && i < top; } inline int IChunk:: possible_pointer(const * p) const { return p >= data && p < &(data[top-base]); } inline int IChunk:: actual_index(int i) const { return i >= low && i < fence; } inline int IChunk:: actual_pointer(const * p) const { return p >= data && p < &(data[fence-base]); } inline int IChunk:: can_grow_high () const { return fence < top; } inline int IChunk:: can_grow_low () const { return base < low; } inline * IChunk:: invalidate() { * p = data; data = 0; return p; } inline IChunk* IChunk::prev() const { return prv; } inline IChunk* IChunk::next() const { return nxt; } inline void IChunk::link_to_prev(IChunk* prev) { nxt = prev->nxt; prv = prev; nxt->prv = this; prv->nxt = this; } inline void IChunk::link_to_next(IChunk* next) { prv = next->prv; nxt = next; nxt->prv = this; prv->nxt = this; } inline void IChunk::unlink() { IChunk* n = nxt; IChunk* p = prv; n->prv = p; p->nxt = n; prv = nxt = this; } inline int IChunk:: empty() const { return low == fence; } inline int IChunk:: full() const { return top - base == fence - low; } inline int IChunk:: first_index() const { return (low == fence)? fence : low; } inline int IChunk:: last_index() const { return (low == fence)? low - 1 : fence - 1; } inline int IChunk:: succ(int i) const { return (i < low) ? low : i + 1; } inline int IChunk:: pred(int i) const { return (i > fence) ? (fence - 1) : i - 1; } inline int IChunk:: valid_index(int i) const { return i >= low && i < fence; } inline int IChunk:: valid_pointer(const * p) const { return p >= &(data[low - base]) && p < &(data[fence - base]); } inline * IChunk:: grow_high () { if (!can_grow_high()) full_error(); return &(data[fence++ - base]); } inline * IChunk:: grow_low () { if (!can_grow_low()) full_error(); return &(data[--low - base]); } inline void IChunk:: shrink_high () { if (empty()) empty_error(); --fence; } inline void IChunk:: shrink_low () { if (empty()) empty_error(); ++low; } inline * IChunk::first_pointer() const { return (low == fence)? 0 : &(data[low - base]); } inline * IChunk::last_pointer() const { return (low == fence)? 0 : &(data[fence - base - 1]); } inline * IChunk::succ(* p) const { return ((p+1) < &(data[low - base]) || (p+1) >= &(data[fence - base])) ? 0 : (p+1); } inline * IChunk::pred(* p) const { return ((p-1) < &(data[low - base]) || (p-1) >= &(data[fence - base])) ? 0 : (p-1); } // generic Plex operations inline Plex::Plex() {} inline int Plex::chunk_size() const { return csize; } inline int Plex::ecnef () const { return lo - 1; } inline int Plex::fence () const { return fnc; } inline int Plex::length () const { return fnc - lo; } inline int Plex::empty () const { return fnc == lo; } inline IChunk* Plex::tl() const { return hd->prev(); } inline int Plex::one_chunk() const { return hd == hd->prev(); } #endif #endif