Selected C++ Example #20
// Chapter 9 Example #2
// This C++ example illustrates the implementation of garbage
// collection in C++. Garbage collection in C++ typically
// revolves around a memory handler function that ''knows''
// which classes in the system are hoarding memory. The memory
// handler knows which classes are hoarding memory because the
// author of the application overloaded the new and delete
// functions for the class in question.
// In this example, we have a LinkedList class, which contains
// Node objects. The Node class has overloaded its standard
// allocator and deallocator (i.e., operators new and delete)
// to hoard recyclable nodes on a freelist (a class variable)
// The Node class has a free_garbage class method, which users
// of the class can call. In this example, our memory handler,
// called free_garbage, detects that memory has run out and
// tells the Node class to put the memory back.
#include <iostream.h>
#include <new.h>
#include <stdlib.h>
#include <string.h>
typedef int DATUM;
// The memory handler for the application.
void garbage_collect();
// Notice that the Node class is granting friendship to the
// LinkedList class. Granting friendship to a class or method
// is typically considered bad style since it weakens data
// hiding. In this example, it is allowed since the Node class
// is really an internal implementation detail of the LinkedList.
// To force the LinkedList class to use accessor methods for
// each access would overly convolute the code of the LinkedList
// with items such as ''head->set_next(head->get_next())''
// instead of the much more readable ''head = head->next''.
class Node {
DATUM data;
Node* next;
static Node* freelist;
friend class LinkedList;
public:
Node(DATUM&);
void* operator new(size_t);
void operator delete(void*);
static int free_garbage();
static void print_freelist();
};
// The definition of the class variable ''freelist'' attached
//to the Node class.
Node* Node::freelist = NULL;
// The overloaded new operator (the standard allocator) will
// first try to recycle a node before going to the heap and
// getting one the expensive way.
void*
Node::operator new(size_t sz)
{
Node* p;
// First try to get a node off the freelist.
if (freelist != NULL) {
p = freelist;
freelist = freelist->next;
}
else {
// If that doesn't work, get one the old-fashioned, expensive
// way by making a trip to the heap.
p = (Node*) new char[sz];
}
return(p);
}
// Be sure that ''delete 0'' works properly (a NOP),
// then add the node to the freelist for later recycling.
void
Node::operator delete(void* p)
{
if (p != NULL) {
((Node*) p) ->next = freelist;
freelist = (Node*) p;
}
}
// The constructor for Node simply initializes the two data
// members, regardless of whether or not it is a recycled node.
Node::Node(DATUM& new_data)
{
data = new_data;
next = NULL;
}
// This class method is used for diagnostics. It prints the
// current addresses out on the Node's freelist.
void
Node::print_freelist()
{
Node* temp = freelist;
cout << ''Freelist: '';
while (temp != NULL) {
cout << temp << '' '';
temp = temp->next;
}
cout << ''\n'';
}
// This class function will throw away the freelist of
// nodes if a garbage-collection handler function
// requests it. Since nodes have an overloaded delete
// operator, the global delete must be called. Note the use
// of the scope resolution operator. This function returns
// the number of bytes it put back on the heap.
int
Node::free_garbage()
{
Node* temp;
int counter = 0;
while (freelist != NULL) {
temp = freelist;
freelist = freelist->next;
// Must use global delete to prevent infinite
// recursion between deleting a node off of the
// freelist and the overloaded delete operator putting
// the node back on the freelist.
::delete temp;
counter++;
}
return(counter*sizeof(Node));
}
// The LinkedList class is a user of Nodes. Its constructor
// and destructor call the overloaded new and delete of the
// Node class. Use of LinkedList objects results in a Freelist
// of Node objects stashed away in the Node class.
class LinkedList {
Node* head;
int length;
public:
LinkedList();
LinkedList(DATUM);
~LinkedList();
int insert(DATUM);
int remove(DATUM);
void traverse() const;
};
LinkedList::LinkedList()
{
head = NULL;
length = 0;
}
LinkedList::LinkedList(DATUM first_item)
{
head = new Node(first_item);
length = 1;
}
LinkedList::~LinkedList()
{
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
delete temp;
}
}
int
LinkedList::insert(DATUM new_item)
{
Node* temp = head;
if (temp == NULL) {
head = new Node(new_item);
}
else {
while(temp->next != NULL) {
temp = temp->next;
}
temp->next = new Node(new_item);
}
return(++length);
}
int
LinkedList::remove(DATUM bad_item)
{
Node* temp = head;
if (temp == NULL) {
return(0);
}
if (head->data == bad_item) {
head = head->next;
length--;
delete temp;
}
else {
while (temp->next != NULL&&
temp->next->data != bad_item){
temp = temp->next;
}
if (temp->next == NULL) {
return(0);
}
else {
Node* p = temp->next;
temp->next = temp->next->next;
length--;
delete p;
}
} return(1);
}
void
LinkedList::traverse()const
{
Node* temp = head;
cout << ''('';
while (temp != NULL) {
cout << temp->data << '''';
temp = temp->next;
}
cout << '')\n'';
}
// The main function first installs our memory handler.
// It then works with a number of LinkedList objects, which
// results in a freelist of nodes. We attempt to allocate
// an unallocatable amount of memory. The new operator for
// the array of characters is called. It calls the equivalent
// of malloc, which fails. New detects the failure and checks if
// there is a memory handler. There is one installed
// (garbage_collect), so we execute it and try malloc again,
// hoping for success. The hope is that the garbage collector
// will free enough memory so that the second attempt by new
// to allocate the memory is successful. In this example, the
// second attempt fails. The memory handler detects that no
// additional space has been freed and thus exits from the
// application, preventing infinite attempts to free memory even
// when there is none to free.
void
main()
{
set_new_handler(garbage_collect);
LinkedList a;
LinkedList b(100);
a.traverse(); b.traverse();
a.insert(1); a.insert(2);
a.insert(3); a.insert(4);
a.insert(5); a.insert(6);
b.insert(200); b.insert(300);
b.insert(400); b.insert(500);
b.insert(600); b.insert(700);
a.traverse();b.traverse();
Node::print_freelist();
a.remove(1); b.remove(100);
a.traverse();b.traverse();
a.remove(6); b.remove(700);
a.traverse();b.traverse();
a.remove(4); b.remove(400);
a.traverse();b.traverse();
Node::print_freelist();
a.insert(99); a.insert(199);
b.insert(-45);b.insert(-44);
a.traverse(); b.traverse();
Node::print_freelist();
char* big_buf = NULL;
// This block is impossible to retrieve. New will fail and will
// call our handler, which tells the Node class to free
// its horded nodes. The call to new still fails, so we exit
// the application.
big_buf = new char[65530L];
strcpy(big_buf, ''Arthur Riel'');
cout << ''big_buf = '' << big_buf <<''.\n'';
}
// The garbage-collection routine is a cornerstone in this
// example. It possesses knowledge of what element of the
// application is hoarding memory. When the heap is out of
// space, this routine tells the hoarders to put their memory
// back on the heap. If this routine cannot find any memory to
// free, it bails out.
void
garbage_collect()
{
int space_freed;
// Get some space freed on the heap by telling the hoarding
// Node class to put its memory back.
space_freed = Node::free_garbage();
// If there's nothing to free, simply fail. Otherwise,
// return and let new try again.
if (!space_freed){
cerr << ''Fatal Memory Error!!!\n'';
exit(-1);
}
}
|
