Code Capsules

Dynamic Memory Management, Part 2

Chuck Allison

Chuck Allison is a regular columnist with CUJ and a software architect for the Family History Department of the Church of Jesus Christ of Latter Day Saints Church Headquarters in Salt Lake City. He has a B.S. and M.S. in mathematics, has been programming since 1975, and has been teaching and developing in C since 1984. His current interest is object-oriented technology and education. He is a member of X3J16, the ANSI C++ Standards Committee. Chuck can be reached on the Internet at 72640.1507@compuserv.com.

In last month's article I explored some of the finer points of using heap memory in C programs, and then introduced the new and delete operators of C++. The word operators is key. In C, you allocate dynamic memory via the library functions malloc, calloc, and realloc. You must explicitly pass the size of the objects you're working with to these functions. Since new is an operator in C++, the compiler figures out how much memory is needed — you just deal with objects.

To get a pointer to a dynamic object of any type, just ask for it:

   T *tp = new T;

Using new does two things:

1) Allocates memory for the object

2) Calls the appropriate constructor

Arrays are easy, too:

   const size_t SIZE = 100;
   T *tap = new T[SIZE];

In this case new calls the default constructor to initialize each array element, in order of increasing index.

Even multi-dimensional arrays are a snap. For example, to allocate a 2-by-3 array, you can do something like:

   const size_t NROWS = 2;
   const size_t NCOLS = 3;
   T (*p)[NCOLS] =
      new T[NROWS][NCOLS];

You can now use p with array syntax, as in

   T t;
   ...
   p[0][1] = t;

(If p's declaration syntax is puzzling to you, see the Code Capsule, "Pointers and Arrays," CUJ, September 1993.)

To dispose of a heap object, you use the delete operator:

   delete tp;      // scalar version
   delete [] tap;  // array version

A call to delete invokes the appropriate destructor before deallocating memory. The array version, delete[], destroys the array elements in decreasing index order. It is important to use the correct version of delete when returning memory to the heap.

In this month's article I discuss some of the things you should be aware of when using the heap in C++.

Deep vs. Shallow Copy

The simple string class in Listing 1 and Listing 2 holds its data in an underlying C-style string. Since the string can grow and shrink, the class allocates the data buffer from the heap. The test program in Listing 3 exposes a problem with this class, however. Somehow a string which is either initialized or assigned from another stays "connected" to the original — changing one changes the other. If you look closely at the class definition, you'll notice that I did not define a copy constructor or an assignment operator. A copy constructor has the signature

   string(const string&);

and executes whenever a new string object is initialized with the value of another, as in

   string t = s;

The assignment operator has the following signature:

   string& operator=(const string&);

The compiler automatically generates these functions if you don't. These automatic versions use memberwise semantics, which means that when you initialize a string object with another's value, each member of the receiving object is initialized with the value of the corresponding member in the original object. If the data member is an instance of a type that has a copy constructor, that constructor gets called. In the case of string, the data members are built-in types, so no constructor is called for each member; the pointer and counter are just copied as scalar values. This simple copy operation results in the situation shown in Figure 1.

The string objects s and t actually share the underlying C-string buffer, since the compiler-generated copy constructor just copied s.data to t.data. This is called a shallow copy. Sharing private data this way is not only inconvenient, but dangerous. If s should go out of scope before t does, the string destructor will turn t.data into a dangling pointer, as depicted in Figure 2.

What you really want is a "deep copy," which creates a separate copy of the underlying character buffer for each initialization or assignment. A deep copy requires a special copy constructor and assignment operator, both of which allocate a new buffer for the receiving object, and copy the characters from the original with strcpy. (See Listing 4 - Listing 6. ) In general, when an object contains a pointer to heap memory, you should define a custom copy constructor and assignment operator, not to mention a destructor and other constructors as necessary.

Virtual Destructors

The essence of object-oriented programming is polymorphism, a fancy word for being able to invoke different but related behavior through a single interface. For example, the universal interface of a brake pedal allows you to stop any motor vehicle, even though the mechanics of stopping may differ from vehicle to vehicle, depending on the type of brake system (disc, drum, air, etc.). You can stop a car without even knowing what type of brake system it has, and without understanding what happens under the hood. In programming, polymorphism allows a higher degree of reuse and maintainability than traditional procedural systems.

C++ supports polymorphism through virtual functions. The program in Listing 7 uses an array of pointers that can point to objects of either of two class types: B (base) or D (derived). As the program traverses the array the appropriate member function executes transparently. If the current pointer refers to a B object, B::f executes, otherwise D::f does.

A user interface library might support objects for data entry, such as tables, popup menus, or single data cells. A data entry form might consist of a collection of such objects in a particular layout. It would be convenient if a form-management system could simply traverse its objects (lets call them "fields") to invoke a particular action, without having to know what type of field each object was. With this sort of capability, you could refresh a form display by doing this:

   for (int i = 0; i < nfields; ++i)
       fields[i]->display();

The appropriate display member function would be called depending on the specific type of the object that fields[i] refered to.

Novices to C++ often don't realize that destructors need to be virtual too. To illustrate, the programs in Listing 8 - Listing 12 contain skeletal definitions of the following class hierarchy:

   field           (Listing 8)
      cell        (Listing 9)
      column      (Listing 10)
         popmenu  (Listing 11)
      table        (Listing 12)

field is an abstract class, a class that exists only to unite the other classes as derived classes in a single hierarchy. A form object contains an array of pointers to dynamic field objects, and knows nothing about the other concrete types (see Listing 13 and Listing 14) . The test program in Listing 15 merely creates a form with a few fields so that you can observe what happens when the form is destroyed. The statement

   delete fields[i]

in Form::~Form() as usual calls a destructor and then deallocates the associated memory. Because the destructors are virtual, the correct destructor gets called according to the dynamic type of the referenced object. By contrast, Listing 16 shows that only the base part of each object is destroyed when the destructor is not virtual. In general, all base classes should have a virtual destructor, because you never know when a user might access derived objects on the heap through a base class pointer.

Handling Memory Allocation Failures

Traditional C++ compilers return a null pointer when new fails to allocate memory:

   T *tp = new T;
   if (t == 0)
   {
   cerr << "memory exhausted" << endl;
   abort();
}

Since inserting code like this can be quite tedious in applications that make heavy use of the heap, programmers of such applications often don't bother to check if the pointer is valid. Even if you religiously check every call to new, what do you do when memory fails within a constructor? Constructors don't return a value, so it can be awkward to pass that information down the line to client code.

One alternative is to define a new handler, a function that executes whenever memory runs out. To install a function as a new_handler, pass it to the standard library function set_new_handler (see Listing 17) . A typical custom new handler tries to free up some memory and then returns, allowing new to try again. But if it can't come up with any more memory, then you should probably abort the program.

A standard-conforming C++ compiler throws a bad_alloc exception when memory fails. Some compilers allow you to revert to the traditional "return-null" behavior by calling set_new_handler(0) (see Listing 18) . The program in Listing 19 does not handle the bad_alloc exception, so the standard library function terminate executes, aborting the program. Listing 20 shows how to catch a bad_alloc exception (except that the Borland compiler I use calls it xalloc, which was its old name). For more information on exceptions, see the Code Capsule "C++ Exceptions," CUJ, July 1994.

Overriding new and delete

The Standard C++ library defines six functions for allocating and deallocating memory. When you use the new operator, it calculates the number of bytes needed and in turn calls one of these functions to allocate those bytes. The six functions are:

   // Scalar versions
   void *operator new(size_t);
   void operator delete(void *);

   // Array versions
   void *operator new[](size_t);
   void operator delete[](void *);

   // Placement new
   void *operator new(size_t, void *);
   void *operator new[](size_t, void *);

Whenever you allocate an object of a built-in type from the heap, new calls the first function shown above to get the memory. You can easily implement this new via the malloc() function from Standard C (see Listing 21) . Likewise, deleting a dynamic, built-in object results in a call to ::operator delete(void *). Listing 21 also illustrates that you can override these functions. You override a function by defining it with the same signature as a previously-defined function. Any function you define with the same signature as one of the above replaces the library version of that function in your program.

Listing 22 shows a typical implementation of the default ::operator new and ::operator delete functions. The bad_alloc exception mentioned previously is thrown from the default new handler, which ::operator new calls if the allocation fails. As you might expect, the array versions of these functions are called whenever you deal with dynamic arrays of built-in types.

You can also replace the various versions of operator new and operator delete on a per-class basis. As Listing 23 shows, you just include declarations of the functions you want to replace in the class definition. The test program in Listing 24 creates and destroys both scalar objects and arrays of both base and derived classes so you can observe the interaction of constructors and destructors with class-specific versions of operator new and delete (see Listing 25) .

Placement new

Sometimes you want to create an object at a pre-determined address. The location could be in a region of RAM mapped to some device, or within a class-specific heap. You can construct such an object using the placement syntax for the new operator. For example, to construct a T at address p, do the following:

   #include <new.h>
   T *tp = new (p) T;

In this case, no version of operator new executes, since the memory is already available. In fact, the default version of operator new associated with this use of new ignores its size parameter and just returns the address parameter:

   void *operator new(size_t, void *p)
   {
      return p;
   }

You may need to include this code in your program since not all compilers provide this function yet. As Listing 26 illustrates, you can overload placement new with as many parameters as you like.

You can use placement new to keep a class's assignment operator in sync with its copy constructor without duplicating the code that initializes a new object. You explicitly invoke the destructor on the object's this pointer and reconstruct the new copy in-place, with placement new:

   T& T::operator=(const T& x)
   {
      if (this != &x)
      {
         this->T::~T();
         new (this) T(x);
      }
      return *this;
   }

Class-specific Storage Management

A common use for placement new is in managing class-specific heaps. As I illustrated last month, to save the overhead inherent in creating dynamic objects, it is often a good idea to allocate one large chunk off the heap and manage it yourself for allocating smaller objects. This action results in critical savings of time and space for container classes. The program in Listing 27 uses a class template for an expandable vector. To save overhead, the program allocates storage to hold a pre-determined number (CHUNK) of elements. Whenever you append an element to the vector, the program just constructs that element at the next available location:

   new (arena + length_++) T(x);

The program only calls the real operator new when it is time to expand the underlying storage pool:

   T *new_arena = (T*) ::operator new(sizeof(T) *
                                   new_capacity);

When it comes time to destroy a single element, you don't want to deallocate any memory, since it is part of the storage arena and can be reused. Instead, all you do is explicitly invoke the destructor:

   (arena+i)->T::~T();

The test program and sample output are in Listing 28 and Listing 29 respectively.

Summary

Using the new and delete operators is more convenient than using malloc and free, but there are a few gotchas to watch out for, namely:

1) Be sure to do deep copies for objects with members that point to the heap.

2) Make base class destructors virtual.

3) Always define a bad_alloc exception handler.

4) Override new and delete and/or their array versions for custom control of the heap.

I haven't exhausted all there is to say about dynamic memory in C++. In a future article I'll discuss smart pointers and garbage collection.

Answer to Last Month's Exercise

Last month I asked you to write a generic memory pool manager in C with the following interface:

Pool *pool_create(size_t elem_size, size_t init_alloc,
               size_t extent);

Creates a pool to manage elements of size elem_size. Allocates init_alloc elements initially, and increases the pool by extent elements as needed.

void *pool_get_elem(Pool *p);

Returns a pointer to the next free element in the pool, and updates the free pointer.

void pool_release_elem(Pool *p, void *elem);

Returns an element to the pool.

void pool_free(Pool *p);

Releases all the memory used by the pool.

My solution is in Listing 30 - Listing 31. Like the less generic solution in last month's article, it allocates a region large enough to hold a given number of elements, and then links them together by placing in each element a pointer to the subsequent element, as represented by Figure 3. The following structure definition allows me to interpret the contents as a pointer:

struct Overlay
{
   void *next;
};

For example, to return a pointer to the next free space and then advance past it, the function pool_get_elem does this:

   new_node = p">free_ptr;
   p">free_ptr = ((Overlay *) p">free_ptr)">next;
   return new_node;

See the cross-reference program (xref2.c) in last month's article for hints on where to put calls to the pool interface.

Figure 1 Result of a shallow copy between string objects S and T

Figure 2 Dangling pointer resulting from shallow copy and subsequent deletion of string S

Figure 3 Memory pool resulting from solution to last month's puzzle

Listing 1 A simple string class

// str.h

#include <stddef.h>

class ostream;
class istream;

class string {
public:
    string();
    string(const char*);
    ~string();

    friend string operator+(const string&, const string&);
    string& operator+=(const string&);
    friend int operator==(const string&, const string&);
    friend int operator!=(const string&, const string&);
    friend ostream& operator<<(ostream&, const string&);
    friend istream& operator>>(istream&, string&);
    char& operator[](size_t);
    size_t length() const;

private:
    char* data;
    size_t count;
    void clone(const char *);
};

inline string::string()
{
    *(data = new char[1])= '\0';
    count= 0;
}

inline string::string(const char *s)
{
    clone(s);
}

inline string::~string()
{
    delete [] data;
}

inline int operator!=(const string& s1, const string& s2)
{
    return !(s1 == s2);
}

inline char& string::operator[](size_t pos)
{
    return data[pos];
}

inline size_t string::length() const
{
    return count;
}
/* End of File */

Listing 2 The rest of the string class implementation

// str.cpp
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <assert.h>
#include "str2.h"

string& string::operator+=(const string& s2)
{
   if (s2.count > 0)
   {
      size_t new_count = count + s2.count;
      char *buf = new char[new_count + 1];

      memcpy(buf,data,count);
      memcpy(buf+count,s2.data,s2.count);
      buf[count = new_count] = '\0';
      delete [] data;
      data = buf;
   }
   return *this;
}

string operator+(const string& s1, const string& s2)
{
   string temp(s1);
   return temp += s2;
}

int operator==(const string& s1, const string& s2)
{
   return &s1 == &s2 ||
      s1.count == s2.count &&
      strcmp(s1.data,s2.data) == 0;
}

ostream& operator<<(ostream& os, const string& s1)
{
   os.write(s1.data,s1.count);
   return os;
}

istream& operator>>(istream& is, string& s1)
{
   const size_t BUFSIZ = 256;
   char buf[BUFSIZ];

   is.getline(buf,BUFSIZ);
   delete [] s1.data;
   s1.clone(buf);
   return is;
}

void string::clone(const char *s)
{
   // Assumes data is deallocated
   assert(s);
   count = strlen(s);
   data = new char[count + 1];
   strcpy(data,s);
}

// End of File

Listing 3 Exposes the string class's shallow copy

// tstr.cpp
#include <iostream.h>
#include "str.h"

main()
{
   string s("hello"), t = s;

   t[0] = 'j';
   cout << "s == "<< s << endl;
   cout << "t ==" << t << endl;
   return 0;
}

/* Output:
s == jello
t == jello
*/
// End of File

Listing 4 String class with a copy constructor and assignment operator

// str2.h

#include <stddef.h>

class ostream;
class istream;

class string {
public:
    // Add these:
    string(const string&);
    string& operator=(const string&);

    // The rest as in Listing 1
};

// Add this:
inline string::string(const string& s2)
{
    clone(s2.data);
}

// The rest as in Listing 1

/* End of File */

Listing 5 Adds implementation of assignment operator to the string class

// str2.cpp
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <assert.h>
#include "str2.h"

// Add this:
string& string::operator=(const string& s2)
{
   if (this != &s2)
   {
      delete [] data;
      clone(s2.data);
   }
   return *this;
}

// The rest as in Listing 2
// End of File

Listing 6 Tests string class with deep copy

// tstr2.cpp
#include <iostream.h>
#include "str2.h"

main()
{
   string s("hello"), t = s;

   t[0] = 'j';
   cout << "s == " << s << end1;
   cout << "t == " << t << endl:
   return 0;
}

/* Output:
s == hello
t == jello
*/

// End of File

Listing 7 Illustrates virtual functions

// virt.cpp
#include <iostream.h)

// Base class
class B
{
public:
   virtual void f()
   {
      cout << "B::f" << endl;
   }
};

// Derived class
class D : public B
{
public:
   virtual void f()
   {
      cout << "D::f" << endl;
   }
};

main()
{
   B *bp[2];  // Heterogeneous array
   B b;
   D d;

   bp[0] = &b;
   bp[1] = &d;

   for (int i = 0; i < 2; ++i)
      bp[i]->f();
   return 0;
}

/* Output:
B::f
D::f
*/

// End of File

Listing 8 The Field abstract class

// field.h: Abstract class
// for data-entry fields
#ifndef FIELD_H
#define FIELD_H

#include <iostream.h>

class Field
{
public:
   // pure virtual function
   virtual ~Field() = 0;
};

inline Field::~Field()
{
   cout << "~Field()" << endl;
}

#endif

/* End of File */

Listing 9 The Cell class

// cell.h: Single-cell data entry

#include "field.h"

class Cell : public Field
{
   char *value,
       *msg;
public:
   ~Cell();
};

inline Cell::~Cell()
{
   cout << "~Cell()" << endl;

// What the real destructor does:
// delete [] msg;
// delete [] value;
}
/* End of File */

Listing 10 The Column class

// column.h:    Scrollable vector
// of scalar cells
#ifndef COLUMN_H
#define COLUMN_H

#include "field.h"

class Column : public Field
{
protected:
   char *msg;
   char **value;

public:
   ~Column();
};

inline Column::~Column()
{
   cout << "~Column()" << endl;

// What the real destructor does:
// delete [] msg;
// for (int i = 0; i < ncells; ++i)
//     delete [] value[i];
// delete [] value;
}

#endif
/* End of File */

Listing 11 The Popmenu class

// popmenu.h: Pop-up menus
#include "column.h"

class Popmenu : public Column
{
   char *title;

public:
   ~Popmenu();
};

inline Popmenu::~Popmenu()
{
   cout << "~Popmenu()" << endl;

// What the real destructor does:
// delete [] title;
}
/* End of File */

Listing 12 The Table class

// table.h: Scrollable input tables

#include "field.h"

class Column;

class Table : public Field
{
   enum {MAXCOLUMNS = 16};

protected:
   int ncols;
   Column *columns[MAXCOLUMNS];

public:
   ~Table();
};

inline Table::~Table()
{
   cout << "~Table()" << endl;

// What the real destructor does:
// for (int i = 0; i < ncols; ++i)
//     delete columns[i];
}
/* End of File */

Listing 13 The Form class

// form.h: Data-entry forms

class Field;

class Form
{
   enum {MAXFIELDS = 32};

   Field *fields[MAXFIELDS];
   int nfields;

public:
   Form();
   ~Form();
   int add(Field *);
};

inline Form::Form()
{
   nfields = 0;
}

/* End of File */

Listing 14 More Form member functions

// form.cpp

#include <assert.h>
#include "form.h"

int Form::add(Field *fp)
{
   assert(fp);
   if (nfields >= MAXFIELDS)
      return -1;

   fields[nfields] = fp;
   return nfields++;
}

Form::~Form()
{
   // Assumes fields are on heap
   for (int i = 0; i < nfields; ++i)
      delete fields[i];
}

// End of File

Listing 15 Shows the effect of virtual destructors

// tform.cpp: Create/delete
//            some display fields

#include "form.h"
#include "cell.h"
#include "column.h"
#include "table.h"
#include "popmenu.h"

main()
{
   Form f;
   f.add(new Cell);
   f.add(new Column);
   f.add(new Table);
   f.add(new Popmenu);
   return 0;
}

/* Output:
~Cell()
~Field()
~Column()
~Field()
~Table()
~Field()
~Popmenu()
~Column()
~Field()
*/
/ End of File

Listing 16 Output from tform.cpp after removing the virtual keyword from field.h

~Field()
~Field()
~Field()
~Field()

Listing 17 Illustrates set_new_handler

// exhaust1.cpp
#include <iostream.h>
#include <stdlib.h>
#include <new.h>

inline void my_handler()
{
   cout << "Memory exhausted" << endl;
   abort();
}

main()
{
   set_new_handler(my_handler);

   for (int i = 0; ; ++i)
   {
      (void) new double[100];
      if ((i+1)%10 == 0)
         cout << (i+1) << " allocations" << endl;
   }
}

/* Output:
10 allocations
20 allocations
30 allocations
40 allocations
50 allocations
60 allocations
70 allocations
Memory exhausted
Abnormal program termination
*/

// End of File

Listing 18 Restores traditional "return-null" behavior

// exhaust2.cpp
#include <iostream.h>
#include <stdlib.h>
#include <new.h>
#include <assert.h>

main()
{
   set_new_handler(0);

   for (int i = 0; ; ++i)
   {
      double *dp = new double[100];
      if ((i+1)%10 == 0)
         cout << (i+1) <<" allocations" << endl;
      assert(dp);
   }
}

/* Output:
10 allocations
20 allocations
30 allocations
40 allocations
50 allocations
60 allocations
70 allocations
Assertion failed: dp, file exhaust3.cpp, line 15
Abnormal program termination
*/

// End of File

Listing 19 Leaves a bad_alloc exception uncaught to force terminate()

// exhaust3.cpp
#include <iostream.h>

main()
{
   for (int i = 0; ; ++i)
   {
      (void) new double[100];
      if ((i+1)%10 == 0)
         cout << (i+1) << " allocations" << endl;
   }
}

/* Output:
10 allocations
20 allocations
30 allocations
40 allocations
50 allocations
60 allocations
70 allocations
Abnormal program termination
*/
// End of File

Listing 20 Implements an xalloc handler

// exhaust4.cpp
#include <stdio.h>
#include <except.h>

main()
{
   double *dp;

   try
   {
      for (int i = 0; ; ++i)
      {
         dp = new double[100];
         if ((i+1)%10 == 0)
            printf("%d allocations\n",i+1);
      }
   }
   catch(xalloc)
   {
      delete [] dp;
      puts("bad_alloc exception");
      return 1;
   }
   catch(...)
   {
      delete [] dp;
      puts("Something else happened");
      return 1;
   }
}

/* Output:
10 allocations
20 allocations
30 allocations
40 allocations
50 allocations
60 allocations
70 allocations
bad_alloc exception
*/

// End of File

Listing 21 Replaces global operator new and operator delete

// override.cpp
#include <iostream.h>
#include <stdlib.h>

void *operator new(size_t siz)
{
   cout << "allocating " << siz << " bytes" << endl;
   return malloc(siz);
}
void operator delete(void *p)
{
   cout << "deleting memory at " << (void *)p << endl;
   free(p);
}

main()
{
   double *dp = new double;
   delete dp;
   return 0;
}

/* Output:
allocating 8 bytes
deleting memory at 0x19e0
*/
// End of File

Listing 22 Typical implementation of ::operator new and ::operator delete

// opnew.cpp
#include <stdlib.h>
#include (new.h>

void *operator new(size_t siz)
{
  // Get new_handler
   void (*new_handler)() = set_new_handler(0);
   set_new_handler(new_handler);

   for(;;)
   {
      // Return pointer upon success
      void *p = malloc(siz);
      if (p)
         return p;

      // If there is a handler, call it
      if (new_handler)
         new_handler();
      else
         return 0;
   }
}

void operator delete(void *p)
{
   if (p)
      free(p);
}
// End of File

Listing 23 A class with its own versions of new and delete

// t.h
#include <iostream.h>

class T
{
   int x;
public:
   T();
   T(int);
   ~T();

   // Override both scalar and array verions
   void *operator new(size_t);
   void operator delete(void *, size_t);
   void *operator new[](size_t);
   void operator delete[](void *);
};

inline T::T() : x(0)
{
   cout << "T::T()" << endl;
}

inline T::T(int i) : x(i)
{
   cout << "T::T(int)" << endl;
}

inline T::~T()
{
   cout << "T::~T()" << endl;
}

inline void *T::operator new(size_t siz)
{
   cout << "T::new (allocating " << siz << " bytes)" << endl;
   return ::operator new(siz);
}

inline void T::operator delete(void *p, size_t siz)
{
   cout << "T::delete (" << siz << " bytes)" << endl;
   if (p)
      ::operator delete(p);
}

inline void *T::operator new[](size_t siz)
{
   cout << "T::new[] (allocating" << siz << " bytes)" << endl;
   return ::operator new(siz);
}

inline void T::operator delete[](void *p, size_t siz)
{
   cout << "T::delete[]" << endl;
   if (p)
      ::operator delete(p);
}

class U : public T
{
   int y;
public:
   U();
   U(int);
   ~U();
};

inline U::U() : T(0), y(0)
{
   cout << "U::U()" << endl;
}

inline U::U(int i) : T(i), y(i)
{
   cout << "U::U(int)" << endl;
}

inline U::~U()
{
   cout << "U::~U()" << endl;
}

/* End of File */

Listing 24 Illustrates the behavior of class-specific new and delete (see Listing 23)

// class.cpp
#include <iostream.h>
#include "t.h"

main()
{
   cout << "allocating a T:" << endl;
   T *t1 = new T;
   cout << endl;

   cout << "allocating an array of 3 T's:" << endl;
   T *t2 = new T[3];
   cout << endl;

   cout << "allocating a T with initialization:" << endl;
   T *t3 = new T(2);
   cout << endl;

   cout << "allocating a U:" << endl;
   U *u1 = new U;
   cout << endl;

   cout << "allocating an array of 2 U's:" << endl;
   U *u2 = new U[2];
   cout << endl;

   cout << "deleting a T:" << endl;
   delete t1;
   cout << endl;

   cout << "deleting the array of 3 T's:" << endl;
   delete [] t2;
   cout << endl;

   cout << "deleting another T:" << endl;
   delete t3;
   cout << endl;

   cout << "deleting the U:" << endl;
   delete u1;
   cout << endl;

   cout << "deleting the array of 2 U's:" << endl;
   delete [] u2;
   cout << endl;

   return 0;
}

// End of File

Listing 25 Output from Listing 24

allocating a T:
T::new (allocating 2 bytes)
T::T()

allocating an array of 3 T's:
T::new[] (allocating 10 bytes)
T::T()
T::T()
T::T()

allocating a T with initialization:
T::new (allocating 2 bytes)
T::T(int)

allocating a U:
T::new (allocating 4 bytes)
T::T(int)
U::U()

allocating an array of 2 U's:
T::new[] (allocating 12 bytes)
T::T(int)
U::U()
T::T(int)
U::U()

deleting a T:
T::~T()
T::delete

deleting the array of 3 T's:
T::~T()
T::~T()
T::~T()
T::delete[]

deleting another T:
T::~T()
T::delete

deleting the U:
U::~U()
T::~T()
T::delete

deleting the array of 2 U's:
U::~U()
T::~T()
U::~U()
T::~T()
T::delete[]

Listing 26 A placement operator new with two arguments

// overload.cpp
#include <iostream.h>

void *operator new(size_t siz, void *arg1, int arg2)
{
    cout << "new: siz == " << siz
        << ", arg1 == " << (void *) arg1
        << ", arg2 == " << arg2 << endl;
    return arg1;
}

main()
{
    void *p = (void *) 0x1234;
    int *ip = new (p,100) int;
    cout << "ip == " << (void *) ip << endl;
    return 0;
}

/* Output:
new: siz == 2, arg1 == 0x1234, arg2 == 100
ip == 0x1234
*/
// End of File

Listing 27 A Vector class template that manages its own heap

#include <iostream.h>
#include <stddef.h>
#include <stdlib.h>
#include <new.h>

// Borland's <new.h> doesn't supply this:
inline void *operator new(size_t, void *p)
{
   return p;
}

// The next two are just for tracing execution:
inline void *operator new(size_t siz)
{
   cout << ">>> operator new (" << siz <<" bytes)" << endl;
   return malloc(siz);
}

inline void operator delete(void *p)
{
   cout << ">>> operator delete: " << (void *) p << endl;
   free(p);
}

template<class T>
class Vector
{
public:
   Vector();
   Vector(size_t);
   ~Vector();

   // Append & subscript:
   Vector<T>& operator+=(const T&);
   T& operator[](size_t);

   // Length-related functions:
   size_t length() const;
   void resize(size_t);
   size_t capacity() const;
   void reserve(size_t);

private:
   T *arena;        // class-specific storage arena
   size_t length_;
   size_t capacity_;

   enum {CHUNK = 10};

   // Disallow copy and assign:
   Vector(const Vector&);
   Vector<T>& operator=(const Vector<T>&);

   static size_t next_chunk(size_t n);
};

template<class T>
inline Vector<T>::Vector()
{
   // Intialize an empty vector
   arena = 0;
   length_ = capacity_ = 0;
}

template<class T>
inline Vector<T>::Vector(size_t n)
{
   // Allocate a multiple of CHUNK elements >= n
   length_ = 0;
   capacity_ = next_chunk(n);
   arena = (T *) ::operator new(sizeof(T) * capacity_);
   cout << ">>> arena created at " << (void *) arena << endl;
}

template<class T>
Vector<T>::~Vector()
{
   // Execute destructor for each element
   for (int i = 0; i < length_; ++i)
      (arena+i)->T::~T();

   ::operator delete(arena);
}

template<class T>
inline T& Vector<T>::operator[](size_t pos)
{
   if (pos >= length_)
      throw "bad index in Vector<T>::operator[]";
   return arena[pos];
}

template<class T>
inline size_t Vector<T>::length() const
{
   return length_;
}

template<class T>
inline size_t Vector<T>::capacity() const
{
   return capacity_;
}

template<class T>
void Vector<T>::reserve(size_t new_capacity)
{
   // Only allow an increase:
   if (new_capacity > capacity_)
   {
      new_capacity = next_chunk(new_capacity);
      if (new_capacity > capacity_)
      {
         // Copy elements to new space
         T *new_arena = (T*) ::operator new(sizeof(T) *
                                      new_capacity);
         cout << ">>> new arena created at "
             << (void *) new_arena << endl;
         for (int i = 0; i < length_; ++i)
            (void) new (new_arena + i) T(arena[i]);

         // Destroy old vector
         for (i = 0; i < length_; ++i)
            (arena+i)->T::~T();
         delete arena;

         // Update state
         arena = new_arena;
         capacity_ = new_capacity;
      }
   }
}

template<class T>
void Vector<T>::resize(size_t new_length)
{
   // Only allow a decrease:
   if (new_length < length_)
   {
      // Just destroy truncated elements;
      // Don't change capacity
      for (int i = new_length; i < length_; ++i)
         (arena+i)->T::~T();
      length_ = new_length;
   }
}

template<class T)
Vector(T)& Vector<T>::operator+=(const T& x)
{
   if (length_ == capacity_)
      reserve(length_ + 1);
   (void) new (arena + length_++) T(x):
   return *this;
}

template(class T)
inline size_t Vector<T>::next_chunk(size_t n)
{
   return ((n + CHUNK - 1) / CHUNK) * CHUNK;
}
/* End of File */

Listing 28 Tests the Vector class

// tvector.cpp
#include <iostream.h>
#include "vector.h"

// A user-defined class to test Vector
class Foo
{
   long x;

public:
   Foo() : x(0)
   {
      cout << "Foo::Foo()\n";
   }

   Foo(int i) : x(i)
   {}

   Foo(const Foo& f) : x(f.x)
   {
      cout << "Foo::Foo(const Foo&)\n";
   }

   ~Foo()
   {
      cout << "Foo::~Foo( )\n";
   }

   friend ostream& operator<<(ostream& os, const Foo& f)
   {
      cout << f.x; return os;
   }
};

main()
{
   // Instantiate a vector of ints
   Vector<int> v(5);
   for (int i = 0; i < 11; ++i)
      v += i;
   for (i = 0; i < v.length(); ++i)
      cout << v[i] << endl;

   // Instantiate a vector of Foo's
   Vector<Foo> v2;
   v2 += 0;
   v2 += 1;
   v2 += 2;
   for (i = 0; i < v2.1ength(); ++i)
      cout << v2[i] << endl;

   return 0;
}
// End of File

Listing 29 Output from Listing 28

>>> operator new (20 bytes)
>>> arena created at 0x181e
>>> operator new (40 bytes)
>>> new arena created at 0x1836
>>> operator delete: 0x181e
0
1
2
3
4
5
6
7
8
9
10
>>> operator new (40 bytes)
>>> new arena created at 0x1862
Foo::Foo(const Foo&)
Foo::~Foo()
Foo::Foo(const Foo&)
Foo::~Foo()
Foo::Foo(const Foo&)
Foo::~Foo()
0
1
2
Foo::~Foo()
Foo::~Foo()
Foo::~Foo()
>>> operator delete: 0x1862
>>> operator delete: 0x1836

Listing 30 C interface for a generic memory pool manager

/* pool.h */
#include <stddef.h>

/* Incomplete type: */
typedef struct Pool Pool;

/* Pool management functions */
Pool *pool_create(size_t elem_size, size_t init_alloc, size_t extent);
void *pool_get_elem(Pool *p);
void pool_release_elem(Pool *p, void *elem);
void pool_free(Pool *p);
/* End of File */

Listing 31 Generic pool manager implementation

/* pool.c: Generic memory pool manager */
#include <assert.h>
#include <stdlib.h>
#include "pool.h"

#define MAX_CHUNKS 64

typedef struct Pool
{
    size_t elem_size;
    size_t extent;
    char *free_ptr;
    void *chunks[MAX_CHUNKS];
    size_t nchunks;
} Pool;

typedef struct Overlay
{
    void *next;
} Overlay;

static void make_chunk(Pool *p, size_t nelems)
{
    int i;
    char *free_ptr;
    void *chunk;
    Overlay *current;

    /* Allocate chunk */
    assert(p);
    chunk = calloc(nelems,p->elem_size);
    assert(chunk);
    free_ptr: (char *) chunk;

    /* Link elements together */
    for (i = 0; i < nelems-1; ++i)
    {
        current = (Overlay *) free_ptr;
        current->next = free_ptr += p->elem_size;
    }
    current: (Overlay *) free_ptr;
    current->next = NULL;   /* Redundant */

    /* Update pool state */
    p->free_ptr; = (char *) chunk;
    p->chunks[p->nchunks++] = chunk;
}

Pool *pool_create(size_t elem_size, size_t init_alloc,
                   size_t extent)
{
    /* Allocate pool */
    Pool *p = malloc(sizeof(Pool));
    assert(p);
    p->elem_size = elem_size;
    p->extent = extent;
    p->nchunks = 0;

    /* Allocate first chunk */
    make_chunk(p,init_alloc);
    return p;
}

void *pool_get_elem(Pool *p)
{
    void *new_node;

    assert(p);
    if (p->free_ptr == NULL && p->nchunks < MAX_CHUNKS)
        /* Add a new chunk to pool */
        make_chunk(p,p->extent);

    assert(p->free_ptr);
    new_node = p->free_ptr;
    p->free_ptr = ((Overlay *) p->free_ptr)->next;
    return new_node;
}

void pool_release_elem(Pool *p, void *elem)
{
    /* Prepend elem to free list */
    Overlay *optr = elem;

    assert(p);
    optr->next = p->free_ptr;
    p->free_ptr= (char *) elem;
}

void pool_free(Pool *p)
{
    int i;

    assert(p);
    for (i = 0; i < p->nchunks; ++i)
        free(p->chunks[i]);
    free(p);
}
/* End of File */