usr/src/lib/libg++/g++-include/gen/Plex.hP

// 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 _<T>Plex_h
#ifdef __GNUG__
#pragma once
#pragma interface
#endif
#define _<T>Plex_h 1

#include <std.h>
#include <Pix.h>
#include "<T>.defs.h"

// Plexes are made out of <T>IChunks

#include <stddef.h>

class <T>IChunk
{
//public: // kludge until C++ `protected' policies settled
protected:

  <T>*           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

  <T>IChunk*     nxt;            // circular links
  <T>IChunk*     prv;

public:

// constructors

                 <T>IChunk(<T>*     d,       // ptr to array of elements
                        int      base_idx, // initial indices
                        int      low_idx,
                        int      fence_idx,
                        int      top_idx);

  virtual       ~<T>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 <T>* p) const; // same for ptr
  int            actual_pointer(const <T>* p) const;
  virtual int    valid_pointer(const <T>* p) const;

  <T>*           pointer_to(int i) const ;   // pointer to data indexed by i
                                      // caution: i is not checked for validity
  int            index_of(const <T>* 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 <T>*   first_pointer() const;   // pointer to first valid pos or 0
  virtual <T>*   last_pointer() const;    // pointer to first valid pos or 0
  virtual <T>*   succ(<T>*  p) const;     // next pointer or 0
  virtual <T>*   pred(<T>* p) const;     // previous pointer or 0

// modification

  virtual <T>*   grow_high ();      // return spot to add an element
  virtual <T>*   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

  <T>IChunk*     next() const;
  <T>IChunk*     prev() const;

  void           link_to_prev(<T>IChunk* prev);
  void           link_to_next(<T>IChunk* next);
  void           unlink();

// state checks

  <T>*           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;
};

// <T>Plex is a partly `abstract' class: few of the virtuals
// are implemented at the Plex level, only in the subclasses

class <T>Plex
{
protected:

  <T>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(<T>IChunk*);        // delete a chunk

  <T>IChunk*       tl() const;                // last chunk;
  int              one_chunk() const;         // true if hd == tl()

public:

// constructors, etc.

                    <T>Plex();                  // no-op

  virtual           ~<T>Plex();


// Access functions

  virtual <T>&      operator [] (int idx) = 0; // access by index;
  virtual <T>&      operator () (Pix p) = 0;   // access by Pix;

  virtual <T>&      high_element () = 0;      // access high element
  virtual <T>&      low_element () = 0;       // access low element

// read-only versions for const Plexes

  virtual const <T>& operator [] (int idx) const = 0; // access by index;
  virtual const <T>& operator () (Pix p) const = 0;   // access by Pix;

  virtual const <T>& high_element () const = 0;      // access high element
  virtual const <T>& 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 <T&> elem) =0;// add new element at high end
                                                // return new high

  virtual int       add_low(const <T&> 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 <T>::~<T>


// operations on multiple elements

  virtual void      fill(const <T&> x);          // set all elements = x
  virtual void      fill(const <T&> 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 <T>Plex& a);    // concatenate a copy
  virtual void      prepend(const <T>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)

// <T>IChunk ops

inline int <T>IChunk:: size() const
{
  return top - base;
}


inline int <T>IChunk:: base_index() const
{
  return base;
}

inline  int <T>IChunk:: low_index() const
{
  return low;
}

inline  int  <T>IChunk:: fence_index() const
{
  return fence;
}

inline  int  <T>IChunk:: top_index() const
{
  return top;
}

inline  <T>* <T>IChunk:: pointer_to(int i) const
{
  return &(data[i-base]);
}

inline  int  <T>IChunk:: index_of(const <T>* p) const
{
  return ((int)p - (int)data) / sizeof(<T>) + base;
}

inline  int  <T>IChunk:: possible_index(int i) const
{
  return i >= base && i < top;
}

inline  int  <T>IChunk:: possible_pointer(const <T>* p) const
{
  return p >= data && p < &(data[top-base]);
}

inline  int  <T>IChunk:: actual_index(int i) const
{
  return i >= low && i < fence;
}

inline  int  <T>IChunk:: actual_pointer(const <T>* p) const
{
  return p >= data && p < &(data[fence-base]);
}

inline  int  <T>IChunk:: can_grow_high () const
{
  return fence < top;
}

inline  int  <T>IChunk:: can_grow_low () const
{
  return base < low;
}

inline  <T>* <T>IChunk:: invalidate()
{
  <T>* p = data;
  data = 0;
  return p;
}


inline <T>IChunk* <T>IChunk::prev() const
{
  return prv;
}

inline <T>IChunk* <T>IChunk::next() const
{
  return nxt;
}

inline void <T>IChunk::link_to_prev(<T>IChunk* prev)
{
  nxt = prev->nxt;
  prv = prev;
  nxt->prv = this;
  prv->nxt = this;
}

inline void <T>IChunk::link_to_next(<T>IChunk* next)
{
  prv = next->prv;
  nxt = next;
  nxt->prv = this;
  prv->nxt = this;
}

inline void <T>IChunk::unlink()
{
  <T>IChunk* n = nxt;
  <T>IChunk* p = prv;
  n->prv = p;
  p->nxt = n;
  prv = nxt = this;
}

inline  int <T>IChunk:: empty() const
{
  return low == fence;
}

inline  int  <T>IChunk:: full() const
{
  return top - base == fence - low;
}

inline int <T>IChunk:: first_index() const
{
  return (low == fence)? fence : low;
}

inline int <T>IChunk:: last_index() const
{
  return (low == fence)? low - 1 : fence - 1;
}

inline  int  <T>IChunk:: succ(int i) const
{
  return (i < low) ? low : i + 1;
}

inline  int  <T>IChunk:: pred(int i) const
{
  return (i > fence) ? (fence - 1) : i - 1;
}

inline  int  <T>IChunk:: valid_index(int i) const
{
  return i >= low && i < fence;
}

inline  int  <T>IChunk:: valid_pointer(const <T>* p) const
{
  return p >= &(data[low - base]) && p < &(data[fence - base]);
}

inline  <T>* <T>IChunk:: grow_high ()
{
  if (!can_grow_high()) full_error();
  return &(data[fence++ - base]);
}

inline  <T>* <T>IChunk:: grow_low ()
{
  if (!can_grow_low()) full_error();
  return &(data[--low - base]);
}

inline  void <T>IChunk:: shrink_high ()
{
  if (empty()) empty_error();
  --fence;
}

inline  void <T>IChunk:: shrink_low ()
{
  if (empty()) empty_error();
  ++low;
}

inline <T>* <T>IChunk::first_pointer() const
{
  return (low == fence)? 0 : &(data[low - base]);
}

inline <T>* <T>IChunk::last_pointer() const
{
  return (low == fence)? 0 : &(data[fence - base - 1]);
}

inline <T>* <T>IChunk::succ(<T>* p) const
{
  return ((p+1) <  &(data[low - base]) || (p+1) >= &(data[fence - base])) ?
    0 : (p+1);
}

inline <T>* <T>IChunk::pred(<T>* p) const
{
  return ((p-1) <  &(data[low - base]) || (p-1) >= &(data[fence - base])) ?
    0 : (p-1);
}


// generic Plex operations

inline <T>Plex::<T>Plex() {}

inline int <T>Plex::chunk_size() const
{
  return csize;
}

inline  int <T>Plex::ecnef () const
{
  return lo - 1;
}


inline  int <T>Plex::fence () const
{
  return fnc;
}

inline int <T>Plex::length () const
{
  return fnc - lo;
}

inline  int <T>Plex::empty () const
{
  return fnc == lo;
}

inline <T>IChunk* <T>Plex::tl() const
{
  return hd->prev();
}

inline int <T>Plex::one_chunk() const
{
  return hd == hd->prev();
}


#endif
#endif