Selected C Example 20

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);       } }