|
|
Since storage managers keep track of blocks of allocated memory, storage management sounds like a good application for pointer sets. We will build a storage manager for fixed-size memory chunks similar to the one specified in Pool(C++), for which the following is an abbreviated specification:
class Pool{
public:
Pool(size_t n);
// A Pool whose elements have size n;
// The Pool is initially empty.
void* alloc();
// Adds a new element to the Pool and
// returns a pointer to it.
void free(void* p);
// Returns the element pointed to by p
// to the Pool. p must be a pointer
// returned from alloc, or behavior is
// undefined.
~Pool();
// All elements in the Pool are returned
// to the freestore.
};
Aside from the class name--we will call our class Spool, for ``Set-based pool''--we will make two simple changes to the above interface:
#include <Objection.h>
#include "Set.h"
#include <stddef.h>
class Spool{
size_t eltsize;
Set_of_p<void> allocated;
Set_of_p<void> available;
void check()const;
public:
static Objection bad_pointer;
Spool(size_t n);
void* alloc();
void free(void* p);
Spool();
};
The type Set_of_p<void> defines a pointer set whose elements are of type void*. In addition to the element size, the representation consists of two pointer sets: allocated contains pointers to elements currently allocated to the client, while available contains pointers to elements that are available for allocation. One of the invariants of this representation is that the intersection of the two sets is the empty set. (A representation invariant is a property that the representation must satisfy on entry to and upon exit from each public friend or non-constant member function.) The private function check() is provided to check this invariant:
void Spool::check()const{
if(allocated & available)abort();
}
The ampersand (`&') operator computes the intersection of two pointer sets; that is, it returns a pointer set consisting of those pointers belonging both to allocated and available. Using a set in a conditional context (like if) causes the compiler to apply an implicit conversion to void*, which returns non-zero only if the set is non-empty.
The constructor initializes the available pointer set with 100 elements:
Spool::Spool(size_t n) : eltsize(n){
for(int i=0;i<100;i++){
available.insert(new char[eltsize]);
}
check();
}
alloc() first checks for available elements; if one exists, it returns a pointer to it, transferring the pointer from the available pointer set to the allocated pointer set. If the available pointer set is empty, alloc() allocates another hundred elements, inserts their pointers in the available pointer set, and returns one of these to the client:
void* Spool::alloc(){
check();
void* result;
if(available){
result = available.select();
available.remove(result);
allocated.insert(result);
}else{
for(int i=0;i<100;i++){
result = new char[eltsize];
available.insert(result);
}
result = alloc();
}
check();
return result;
}
Note that the function select() selects an arbitrary element from the Set.
free(p) makes sure p is currently allocated, and, if not, raises an Objection; from the flow of control, you can see that the recovery action (the action performed after returning from raise()) is to ignore the error. Otherwise, p is transferred from the allocated pointer set to the available pointer set:
void Spool::free(void* p){
check();
if(!allocated.contains(p)){
if (bad_pointer.raise() == 0) {
cerr << "Spool: bad pointer: "
<< p << endl;
exit(1);
}
}else{
allocated.remove(p);
available.insert(p);
}
check();
}
The destructor frees all available elements using an iterator to visit all the elements of the available pointer set. Any elements still allocated to the client after the Spool is destroyed become the client's responsibility to delete:
Spool::~Spool(){
check();
Set_of_piter<void> it(available);
void* p;
while(p = it.next()){
delete p;
}
check();
}
If the Spool destructor had not explicitly deleted the elements pointed to by the available pointer set, those elements would continue to exist even after the Spool (and the two pointer sets used to represent it) were destroyed, resulting in garbage and eventual heap exhaustion in a long-running program. This illustrates an important principle of pointer sets: a pointer set contains pointers only, and storage management for the objects pointed to by the pointers in a pointer set are completely the client's responsibility.
Finally, we would include the following definitions in a separate .c file:
Objection Spool::bad_pointer;
Notice that, unlike for Sets and Bags, for Set_of_p we do not have to supply a hash function for pointer sets. This is because the library is smart enough to know that the identity function is always a perfect hash function for any pointer set.
A subtle restriction on pointer sets (not illustrated by the above example) is mentioned in the BUGS section of the Set(C++) manual page: the elements pointed to by a pointer set must reside on even byte boundaries, that is, the low order bit of every pointer in a pointer set must be zero. Violating this restriction will result in unpredictable behavior. Since character pointers do not, in general, satisfy this restriction, one might be tempted to conclude that pointer sets can not be used to keep track of character strings. This conclusion is true of statically-allocated character Strings, but not of character strings allocated dynamically by operator new, since pointers obtained from new are guaranteed to satisfy the most stringent alignment restrictions:
Set_of_p<char> s;
s.insert("goodbye world"); // Don't do this!
char* p = new char[10];
...
s.insert(p); // OK
We may therefore interpret the alignment restriction as a feature rather than a bug: pointer sets were designed to manage objects allocated on the freestore.