summaryrefslogtreecommitdiff
path: root/gnu/lib/libg++/g++-include/gen/MPlex.hP
diff options
context:
space:
mode:
Diffstat (limited to 'gnu/lib/libg++/g++-include/gen/MPlex.hP')
-rw-r--r--gnu/lib/libg++/g++-include/gen/MPlex.hP422
1 files changed, 422 insertions, 0 deletions
diff --git a/gnu/lib/libg++/g++-include/gen/MPlex.hP b/gnu/lib/libg++/g++-include/gen/MPlex.hP
new file mode 100644
index 00000000000..83e28637435
--- /dev/null
+++ b/gnu/lib/libg++/g++-include/gen/MPlex.hP
@@ -0,0 +1,422 @@
+// 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>MPlex_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>MPlex_h 1
+
+
+#include "<T>.Plex.h"
+
+
+// Number of bits per long, used in MChunk bit map operations
+
+#define _MAP_BITS 32
+
+
+class <T>MChunk : public <T>IChunk
+{
+protected:
+
+ unsigned long* map; // bitmap of slots
+ int unused; // number of unused internal slots
+
+ void mark(int); // bitmap operations
+ void free(int);
+ int valid(int) const;
+
+public:
+
+ <T>MChunk(<T>* d, // ptr to array of elements
+ int base_idx, // initial indices
+ int low_idx, // & initially clear map
+ int fence_idx,
+ int top_idx);
+
+ ~<T>MChunk();
+
+// virtuals
+
+ int first_index() const;
+ int last_index() const;
+ int succ(int idx) const;
+ int pred(int idx) const;
+ <T>* first_pointer() const;
+ <T>* last_pointer() const;
+ <T>* succ(<T>*) const;
+ <T>* pred(<T>*) const;
+ int empty() const;
+ int full() const;
+ int valid_index(int i) const;
+ int valid_pointer(const <T>* p) const;
+ <T>* grow_high ();
+ <T>* grow_low ();
+ void shrink_high ();
+ void shrink_low ();
+ void clear(int);
+ void cleardown(int);
+ int OK() const;
+
+// extensions
+
+ int unused_indices() const; // how many free slot in low..fence?
+
+ int unused_index() const; // return index of free slot
+
+ int del(int i); // delete data indexed by i
+ // return true if was present
+ int undel(int idx); // un-delete data indexed by i
+ // return true if already present
+
+ void reset_low(); // reset low = lowest valid index;
+ void reset_high(); // same for high
+
+};
+
+
+class <T>MPlex: public <T>Plex
+{
+ <T>MChunk* ch; // cached chunk
+ int unused; // # of free slots between low & fence
+
+ void make_initial_chunks(int up = 1);
+ void cache(int idx) const;
+ void cache(const <T>* p) const;
+ int dopred(int) const;
+ int dosucc(int) const;
+
+ void set_cache(const <T>MChunk* t) const; // logically,
+ // not physically const
+
+public:
+ <T>MPlex(); // set low = 0;
+ // fence = 0;
+ // csize = default
+
+ <T>MPlex(int ch_size); // low = 0;
+ // fence = 0;
+ // csize = ch_size
+
+ <T>MPlex(int lo, // low = lo;
+ int ch_size); // fence=lo
+ // csize = ch_size
+
+ <T>MPlex(int lo, // low = lo
+ int hi, // fence = hi+1
+ const <T&> initval,// fill with initval,
+ int ch_size = 0); // csize= ch_size
+ // or fence-lo if 0
+
+ <T>MPlex(const <T>MPlex&);
+
+ void operator= (const <T>MPlex&);
+
+// virtuals
+
+ <T>& high_element ();
+ <T>& low_element ();
+ const <T>& high_element () const;
+ const <T>& low_element () const;
+
+ Pix first() const;
+ Pix last() const ;
+ void prev(Pix& ptr) const;
+ void next(Pix& ptr) const;
+ int owns(Pix p) const;
+ <T>& operator () (Pix p);
+ const <T>& operator () (Pix p) const;
+
+ int low() const;
+ int high() const;
+ int valid(int idx) const;
+ void prev(int& idx) const;
+ void next(int& x) const;
+ <T>& operator [] (int index);
+ const <T>& operator [] (int index) const;
+
+ int Pix_to_index(Pix p) const;
+ Pix index_to_Pix(int idx) const;
+
+ int can_add_high() const;
+ int can_add_low() const;
+ int full() const;
+
+ int add_high(const <T&> elem);
+ int del_high ();
+ int add_low (const <T&> elem);
+ int del_low ();
+ void clear();
+
+ int OK () const;
+
+// extensions
+
+ int count() const; // # valid elements
+ int available() const; // # deleted elements
+
+ int unused_index()const; // return index of a deleted elem
+ Pix unused_Pix() const; // return Pix of a deleted elem
+
+ int del_index(int idx); // logically delete at idx;
+ // return true if was present
+ int del_Pix(Pix p); // delete at p
+
+ void undel_index(int idx); // undelete at idx;
+ void undel_Pix(Pix p); // undelete at p;
+
+ void adjust_bounds(); // reset lo, hi to lowest &
+ // highest valid indices
+
+ int add(const <T&> elem); // add anywhere
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>MChunk:: ~<T>MChunk()
+{
+ delete map;
+}
+
+inline void <T>MChunk::mark(int idx)
+{
+ unsigned int i = idx - base;
+ map[i / _MAP_BITS] |= 1 << (i & (_MAP_BITS - 1));
+}
+
+inline void <T>MChunk::free(int idx)
+{
+ unsigned int i = idx - base;
+ map[i / _MAP_BITS] &= ~(1 << (i & (_MAP_BITS - 1)));
+}
+
+inline int <T>MChunk::valid(int idx) const
+{
+ unsigned int i = idx - base;
+ return map[i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1)));
+}
+
+inline int <T>MChunk:: valid_index(int i) const
+{
+ return i >= low && i < fence && valid(i);
+}
+
+inline int <T>MChunk:: valid_pointer(const <T>* p) const
+{
+ int i = ((int)p - (int)data) / sizeof(<T>);
+ return i >= 0 && i < (fence - base) &&
+ (map[(unsigned)i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1))));
+}
+
+inline int <T>MChunk::empty() const
+{
+ return fence - low - unused == 0;
+}
+
+inline int <T>MChunk::full() const
+{
+ return unused + (top - fence) + (low - base) == 0;
+}
+
+inline int <T>MChunk::succ(int idx) const
+{
+ int i = (idx < low)? low : idx + 1;
+ while (i < fence && !valid(i)) ++i;
+ return i;
+}
+
+inline int <T>MChunk::pred(int idx) const
+{
+ int i = (idx > fence)? (fence - 1) : idx - 1;
+ while (i >= low && !valid(i)) --i;
+ return i;
+}
+
+inline int <T>MChunk::unused_indices() const
+{
+ return unused;
+}
+
+inline <T>* <T>MChunk:: grow_high ()
+{
+ if (!can_grow_high()) full_error();
+ mark(fence);
+ return &(data[fence++ - base]);
+}
+
+inline <T>* <T>MChunk:: grow_low ()
+{
+ if (!can_grow_low()) full_error();
+ mark(--low);
+ return &(data[low - base]);
+}
+
+inline void <T>MChunk::reset_low()
+{
+ while (low < fence && !valid(low))
+ {
+ --unused;
+ ++low;
+ }
+}
+
+inline void <T>MChunk::reset_high()
+{
+ while (fence > low && !valid(fence - 1))
+ {
+ --unused;
+ --fence;
+ }
+}
+
+inline int <T>MPlex::full () const
+{
+ return 0;
+}
+
+inline int <T>MPlex::can_add_high() const
+{
+ return 1;
+}
+
+inline int <T>MPlex::can_add_low() const
+{
+ return 1;
+}
+
+inline int <T>MPlex::available() const
+{
+ return unused;
+}
+
+inline int <T>MPlex::count() const
+{
+ return fnc - lo - unused;
+}
+
+inline void <T>MPlex::set_cache(const <T>MChunk* t) const
+{
+ ((<T>MPlex*)(this))->ch = (<T>MChunk*)t;
+}
+
+inline <T>& <T>MPlex:: operator [] (int idx)
+{
+ if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
+ return * (ch->pointer_to(idx));
+}
+
+inline const <T>& <T>MPlex:: operator [] (int idx) const
+{
+ if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
+ return * ((const <T>*)(ch->pointer_to(idx)));
+}
+
+inline int <T>MPlex::Pix_to_index(Pix p) const
+{
+ if (!ch-><T>MChunk::valid_pointer((<T>*)p)) cache((<T>*)p);
+ return ch->index_of((<T>*)p);
+}
+
+inline int <T>MPlex::high() const
+{
+ return (((const <T>MChunk*)tl())-><T>MChunk::valid_index(fnc-1)) ?
+ fnc-1 : dopred(fnc-1);
+}
+
+inline int <T>MPlex::low() const
+{
+ return (((const <T>MChunk*)hd)-><T>MChunk::valid_index(lo))? lo : dosucc(lo);
+}
+
+inline <T>& <T>MPlex::low_element ()
+{
+ return (*this)[low()];
+}
+
+inline const <T>& <T>MPlex::low_element () const
+{
+ return (*this)[low()];
+}
+
+inline <T>& <T>MPlex::high_element ()
+{
+ return (*this)[high()];
+}
+
+inline const <T>& <T>MPlex::high_element () const
+{
+ return (*this)[high()];
+}
+
+inline Pix <T>MPlex::index_to_Pix(int idx) const
+{
+ if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
+ return Pix(ch->pointer_to(idx));
+}
+
+inline void <T>MPlex::next(int& idx) const
+{
+ idx = (ch-><T>MChunk::valid_index(idx+1))? idx+1 : dosucc(idx);
+}
+
+inline void <T>MPlex::prev(int& idx) const
+{
+ idx = (ch-><T>MChunk::valid_index(idx-1))? idx-1 : dopred(idx);
+}
+
+inline Pix <T>MPlex::first() const
+{
+ return index_to_Pix(low());
+}
+
+inline Pix <T>MPlex::last() const
+{
+ return index_to_Pix(high());
+}
+
+
+inline void <T>MPlex::undel_Pix(Pix p)
+{
+ undel_index(Pix_to_index(p));
+}
+
+inline int <T>MPlex::del_Pix(Pix p)
+{
+ return del_index(Pix_to_index(p));
+}
+
+inline <T>& <T>MPlex:: operator () (Pix p)
+{
+ return *((<T>*)p);
+}
+
+inline const <T>& <T>MPlex:: operator () (Pix p) const
+{
+ return *((const <T>*)p);
+}
+
+#endif
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 19:17:58 +0000