|
DataMuseum.dkPresents historical artifacts from the history of: DKUUG/EUUG Conference tapes |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about DKUUG/EUUG Conference tapes Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - metrics - downloadIndex: M T
Length: 9671 (0x25c7)
Types: TextFile
Names: »MPlex.hP«
└─⟦a05ed705a⟧ Bits:30007078 DKUUG GNU 2/12/89
└─⟦cc8755de2⟧ »./libg++-1.36.1.tar.Z«
└─⟦23757c458⟧
└─⟦this⟧ »libg++/g++-include/MPlex.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>MPlex_h
#pragma once
#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);
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();
int last_index();
int succ(int idx);
int pred(int idx);
<T>* first_pointer();
<T>* last_pointer();
<T>* succ(<T>*);
<T>* pred(<T>*);
int empty();
int full();
int valid_index(int i);
int valid_pointer(const <T>* p);
<T>* grow_high ();
<T>* grow_low ();
void shrink_high ();
void shrink_low ();
void clear(int);
int OK();
// extensions
int unused_indices(); // how many free slot in low..fence?
int unused_index(); // 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);
void cache(const <T>* p);
int dopred(int);
int dosucc(int);
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( <T>MPlex&);
void operator= ( <T>MPlex&);
// virtuals
<T>& high_element ();
<T>& low_element ();
Pix first();
Pix last();
void prev(Pix& ptr);
void next(Pix& ptr);
int owns(Pix p);
<T>& operator () (Pix p);
int low();
int high();
int valid(int idx);
void prev(int& idx);
void next(int& x);
<T>& operator [] (int index);
int Pix_to_index(Pix p);
Pix index_to_Pix(int idx);
int can_add_high();
int can_add_low();
int full();
int add_high(const <T&> elem);
int del_high ();
int add_low (const <T&> elem);
int del_low ();
void clear();
int OK ();
// extensions
int count(); // # valid elements
int available(); // # deleted elements
int unused_index(); // return index of a deleted elem
Pix unused_Pix(); // 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
};
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)
{
unsigned int i = idx - base;
return map[i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1)));
}
inline int <T>MChunk:: valid_index(int i)
{
return i >= low && i < fence && valid(i);
}
inline int <T>MChunk:: valid_pointer(const <T>* p)
{
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()
{
return fence - low - unused == 0;
}
inline int <T>MChunk::full()
{
return unused + (top - fence) + (low - base) == 0;
}
inline int <T>MChunk::succ(int idx)
{
int i = (idx < low)? low : idx + 1;
while (i < fence && !valid(i)) ++i;
return i;
}
inline int <T>MChunk::pred(int idx)
{
int i = (idx > fence)? (fence - 1) : idx - 1;
while (i >= low && !valid(i)) --i;
return i;
}
inline int <T>MChunk::unused_indices()
{
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 ()
{
return 0;
}
inline int <T>MPlex::can_add_high()
{
return 1;
}
inline int <T>MPlex::can_add_low()
{
return 1;
}
inline int <T>MPlex::available()
{
return unused;
}
inline int <T>MPlex::count()
{
return fnc - lo - unused;
}
inline <T>& <T>MPlex:: operator [] (int idx)
{
if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
return * (ch->pointer_to(idx));
}
inline int <T>MPlex::Pix_to_index(Pix p)
{
if (!ch-><T>MChunk::valid_pointer((<T>*)p)) cache((<T>*)p);
return ch->index_of((<T>*)p);
}
inline int <T>MPlex::high()
{
ch = (<T>MChunk*)tl();
return (unused == fnc - lo)? lo - 1 : ch-><T>MChunk::last_index();
}
inline int <T>MPlex::low()
{
ch = (<T>MChunk*)hd;
return (unused == fnc - lo)? fnc : ch-><T>MChunk::first_index();
}
inline <T>& <T>MPlex::low_element ()
{
if (unused == fnc - lo) index_error();
return *((hd->pointer_to(((<T>MChunk*)(hd))-><T>MChunk::first_index())));
}
inline <T>& <T>MPlex::high_element ()
{
if (unused == fnc - lo) index_error();
ch = (<T>MChunk*)tl();
return *((ch->pointer_to(ch-><T>MChunk::last_index())));
}
inline Pix <T>MPlex::index_to_Pix(int idx)
{
if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
return Pix(ch->pointer_to(idx));
}
inline void <T>MPlex::next(int& idx)
{
idx = (ch-><T>MChunk::valid_index(idx+1))? idx+1 : dosucc(idx);
}
inline void <T>MPlex::prev(int& idx)
{
idx = (ch-><T>MChunk::valid_index(idx-1))? idx-1 : dopred(idx);
}
inline Pix <T>MPlex::first()
{
return Pix(((<T>MChunk*)(hd))-><T>MChunk::first_pointer());
}
inline Pix <T>MPlex::last()
{
return Pix(((<T>MChunk*)(tl()))-><T>MChunk::last_pointer());
}
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);
}
#endif