From: moudgill@cs.cornell.edu ( Mayan Moudgill)
Subject: Code for adding chunk based memory management to C++ classes
Summary: Two mechanisms for adding free-list based memory management to a class
Keywords: memory management, free list, blocks, c++, templates, cfront 3.0
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Sun, 3 Jan 1993 02:10:11 GMT

I've written to easy to use "bolt-on" classes that use templates and
inheritance. These classes provide overloaded new() and delete() operators
for the class that implement free list based memory management.

The memory management routines keep a list of blocks of the right
size around. Every time a block is "delete'd" it is added
to that list. A request for a block is satisfied from the
free list (if there is a block on the list), or malloc'd from
the system.

The two implementations are PerClassFreeList and PerSizeFreeList.
The first maintains a free list per class. The second
maintains a free list per size (thus, if more than one class had the same
size, they would all use the same free list).

To add PerClassFreeList memory management to a class:

   #include "PerClassFreeList.H"

   class Foo : public PerClassFreeList<Foo> {
     ...
     /* Foo has no new() or delete() operations defined */
   };

The base class PerClassFreeList<Foo> provides new() and delete()
operators. It also provides a free() operator that frees
(in the sense of malloc) the entire free list, and free(n) that
frees at most n blocks from the free list.

To add PerSizeFreeList memory management to a class:

   #include "PerSizeFreeList1.H"

   class Foo : public PerSizeFreeList<Foo> {
     ...
     /* Foo has no new() or delete() operations defined */
   };

   #include "PerSizeFreeList2.H"

Notice the location of the two include files. They *MUST* be included
as shown---PerSizeFreeList1.H before, and PerSizeFreeList2.H after
the object being declared.

Any comments/suggestions will be extremely welcome.
:)
Mayan

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	Size/PerSizeFreeList-Test.C
#	Size/PerSizeFreeList1.H
#	Size/PerSizeFreeList2.C
#	Size/PerSizeFreeList2.H
#	Class/PerClassFreeList-Test.C
#	Class/PerClassFreeList.C
#	Class/PerClassFreeList.H
# This archive created: Sat Jan  2 20:49:40 1993
export PATH; PATH=/bin:$PATH
if test -f 'Size/PerSizeFreeList-Test.C'
then
	echo shar: will not over-write existing file "'Size/PerSizeFreeList-Test.C'"
else
sed 's/^X//' << \SHAR_EOF > 'Size/PerSizeFreeList-Test.C'
X#include <iostream.h>
X#include <string.h>
X#include <iostream.h>
X#include "PerSizeFreeList1.H"
X
Xclass Student : public PerSizeFreeList<Student> {
Xprivate:
X    char   _name[36];
X    short  _age;
Xpublic:
X	   Student(char * name,  int age)
X      : _age(age)
X      {
X	 strncpy(_name,name,35);
X	 _name[35] = 0;
X      }
X
Xfriend ostream& operator<<(ostream& o, Student* s)
X   {
X   void * t = s;
X      o << t;
X      o << ':';
X      o <<  s->_name;
X      o << ' ';
X      o << s->_age;
X      return o;
X   }
X};
X
X#include "PerSizeFreeList2.H"
Xtypedef PerSizeFreeList_Imp<24u> dummy;
X
X
Xmain()
X{
XStudent * s1 = new Student("alpha", 10);
XStudent * s2 = new Student("beta", 20);
X   cout << s1 << '\n' << s2 << endl;
X   delete s1;
XStudent * s3 = new Student("nu", 13);
XStudent * s4 = new Student("mu", 23);
X   cout << s3 << '\n' << s4 << endl;
X   cout << Student::free() << endl;
X   delete s2;
X   delete s3;
X   delete s4;
X   cout << Student::free(1) << endl;
X   cout << Student::free() << endl;
X}
SHAR_EOF
if test 979 -ne "`wc -c < 'Size/PerSizeFreeList-Test.C'`"
then
	echo shar: error transmitting "'Size/PerSizeFreeList-Test.C'" '(should have been 979 characters)'
fi
fi # end of overwriting check
if test -f 'Size/PerSizeFreeList1.H'
then
	echo shar: will not over-write existing file "'Size/PerSizeFreeList1.H'"
else
sed 's/^X//' << \SHAR_EOF > 'Size/PerSizeFreeList1.H'
X#ifndef mPERSIZEFREELIST1_H
X#define mPERSIZEFREELIST1_H
X
X/* 26th December, 1992 Mayan Moudgill.
X   I'm designing a class for "bolting-on" to an existing class,
X   so as to give it free list based memory management.
X   (I would use Mixin instead of Bolton except that the Mixin is
X   used for _dynamic_ inheritance.)
X
X
X   Purpose:
X   Given a class Foo whose memory is to be managed in the
X   following fashion:
X      1. delete(f) takes f (of type Foo *), and adds it to a free list
X      2. new() returns first member of free list (if any) else allocates
X	    from heap
X
X   Additionally, the memory management routines contain
X      1. free() returns all free list members to heap
X      2. free(n) return n free list members to heap
X   They both return the number actually freed.
X   
X   Usage:
X      #include "PerSizeFreeList1.H"
X
X      class Foo : PerSizeFreeList<Foo> {
X	 .
X	 .
X	 .
X      };
X
X      #include "PerSizeFreeList2.H"
X
X   This class differs from PerClassFreeList in that there is one free_list
X   per *size* of allocated, not one per class. Thus, if you have 2 classes,
X   both of the same size, they will use the same free list if memory operations
X   are bolted on using PerSizeFreeList.
X*/
X
X/* There is an extremely nasty bug in cfront 3.0.1 which forces the
X   use of the _dispatch() to actually call the right functions from
X   PerSizeFreeList_Imp (see PerSizeFreeList2.H). The problem
X   causes all but the first member function in ParSizeFreeList to use
X   the wrong sized PerSizeFreeList_Imp. To check wether your complier
X   has a similar bug define BUG_CONFIRM, compile and run, and see whether
X   all the sizes are the same.
X
X   A workaround (sent by USL support) has been applied. It may or
X   may not work with your compiler.
X*/
X
X/* uncomment next line, compile and run to see if bug exists */
X// #define BUG_CONFIRM
X
X#include <malloc.h>
X
Xtemplate<class T>
Xclass PerSizeFreeList {
Xprivate:
Xpublic:
X   inline
X   void *            operator new(size_t);
X   inline
X   void              operator delete(void *);
X   static inline
X   int               free();
X   static inline
X   int               free(unsigned);
X};
X
X#endif
SHAR_EOF
if test 2142 -ne "`wc -c < 'Size/PerSizeFreeList1.H'`"
then
	echo shar: error transmitting "'Size/PerSizeFreeList1.H'" '(should have been 2142 characters)'
fi
fi # end of overwriting check
if test -f 'Size/PerSizeFreeList2.C'
then
	echo shar: will not over-write existing file "'Size/PerSizeFreeList2.C'"
else
sed 's/^X//' << \SHAR_EOF > 'Size/PerSizeFreeList2.C'
X#ifndef mPERSIZEFREELIST2_H
X#include "PerSizeFreeList2.H"
X#endif
X
Xtemplate<size_t size>
Xvoid *   PerSizeFreeList_Imp<size>::_free_list = 0;
X
Xtemplate<size_t size>
Xint      PerSizeFreeList_Imp<size>::free()
X{
Xvoid *   p = _free_list;
Xint      n = 0;
X#ifdef BUG_CONFIRM
X   cerr << "free():  " << size << endl;
X#endif
X   while( p != 0 ) {
X   void *   q = p;
X      p = *((void **) p);
X      ::free(q);
X      n++;
X   }
X   _free_list = 0;
X   return n;
X}
X
Xtemplate<size_t size>
Xint      PerSizeFreeList_Imp<size>::free(unsigned num)
X{
Xvoid *   p = _free_list;
Xint      n = 0;
X#ifdef BUG_CONFIRM
X   cerr << "free(n): " << size << endl;
X#endif
X   while( p != 0 && n < num) {
X   void *   q = p;
X      p = *((void **) p);
X      ::free(q);
X      n++;
X   }
X   _free_list = p;
X   return n;
X}
SHAR_EOF
if test 778 -ne "`wc -c < 'Size/PerSizeFreeList2.C'`"
then
	echo shar: error transmitting "'Size/PerSizeFreeList2.C'" '(should have been 778 characters)'
fi
fi # end of overwriting check
if test -f 'Size/PerSizeFreeList2.H'
then
	echo shar: will not over-write existing file "'Size/PerSizeFreeList2.H'"
else
sed 's/^X//' << \SHAR_EOF > 'Size/PerSizeFreeList2.H'
X#ifndef mPERSIZEFREELIST2_H
X#define mPERSIZEFREELIST2_H
X
X#ifndef mPERSIZEFREELIST1_H
X#include "PerSizeFreeList1.H"
X#endif
X
X#include <iostream.h>
X
X/* 26th December, 1992 Mayan Moudgill.
X   See PerClassFreeList1.H for details
X*/
X
Xtemplate <size_t size>
Xclass PerSizeFreeList_Imp {
Xprivate:
X   static void *     _free_list;
Xpublic:
X   static int        free();
X   static int        free(unsigned);
X
X   static
X   inline void *     alloc(size_t sz)
X      {
X      void *  obj;
X#ifdef BUG_CONFIRM
X	 cerr << "alloc:   " << size << endl;
X#endif
X	 (void) sz;
X	 if( _free_list == 0 ) {
X	    obj = malloc(size);              // is sz+sz%4 == size? it should.
X	 }
X	 else {
X	    obj = _free_list;
X	    _free_list = *((void **) obj); // Its not type safe--so what?
X	 }
X	 return obj;
X      }
X   static
X   inline void       dealloc(void * obj)
X      {
X#ifdef BUG_CONFIRM
X	 cerr << "dealloc: " << size << endl;
X#endif
X	 *((void **) obj) = _free_list;
X	 _free_list = obj;                 // Neither is this--so what?
X      }
X};
X
Xtemplate<class T>
Xvoid *    PerSizeFreeList<T>::operator new(size_t sz)
X{
X   return PerSizeFreeList_Imp<unsigned(sizeof(T))>::alloc(sz);
X}
X
Xtemplate<class T>
Xvoid      PerSizeFreeList<T>::operator delete(void * obj)
X{
X   PerSizeFreeList_Imp<unsigned(sizeof(T))>::dealloc(obj);
X}
X
Xtemplate<class T>
Xint       PerSizeFreeList<T>::free()
X{
X   return PerSizeFreeList_Imp<unsigned(sizeof(T))>::free();
X}
X
Xtemplate<class T>
Xint       PerSizeFreeList<T>::free(unsigned n)
X{
X   return PerSizeFreeList_Imp<unsigned(sizeof(T))>::free(n);
X}
X
X#endif
SHAR_EOF
if test 1548 -ne "`wc -c < 'Size/PerSizeFreeList2.H'`"
then
	echo shar: error transmitting "'Size/PerSizeFreeList2.H'" '(should have been 1548 characters)'
fi
fi # end of overwriting check
if test -f 'Class/PerClassFreeList-Test.C'
then
	echo shar: will not over-write existing file "'Class/PerClassFreeList-Test.C'"
else
sed 's/^X//' << \SHAR_EOF > 'Class/PerClassFreeList-Test.C'
X#include "PerClassFreeList.H"
X#include <string.h>
X#include <iostream.h>
X
Xclass Student : public PerClassFreeList<Student> {
Xprivate:
X    char   _name[36];
X    short  _age;
Xpublic:
X	   Student(char * name,  int age)
X      : _age(age)
X      {
X	 strncpy(_name,name,35);
X	 _name[35] = 0;
X      }
X
Xfriend ostream& operator<<(ostream& o, Student& s)
X   {
X      /* broken up so that it gets inlined */
X      o << s._name;
X      o << ' ';
X      o << s._age;
X      return o;
X   }
Xfriend ostream& operator<<(ostream& o, Student* s)
X   {
X      o << (void *)s;
X      o << ':';
X      o <<  s->_name;
X      o << ' ';
X      o << s->_age;
X      return o;
X   }
X};
X
Xmain()
X{
XStudent * s1 = new Student("alpha", 10);
XStudent * s2 = new Student("beta", 20);
X   cout << s1 << '\n' << s2 << endl;
X   delete s1;
XStudent * s3 = new Student("nu", 13);
XStudent * s4 = new Student("mu", 23);
X   cout << s3 << '\n' << s4 << endl;
X   cout << Student::free() << endl;
X   delete s2;
X   delete s3;
X   delete s4;
X   cout << Student::free(1) << endl;
X   cout << Student::free() << endl;
X}
SHAR_EOF
if test 1055 -ne "`wc -c < 'Class/PerClassFreeList-Test.C'`"
then
	echo shar: error transmitting "'Class/PerClassFreeList-Test.C'" '(should have been 1055 characters)'
fi
fi # end of overwriting check
if test -f 'Class/PerClassFreeList.C'
then
	echo shar: will not over-write existing file "'Class/PerClassFreeList.C'"
else
sed 's/^X//' << \SHAR_EOF > 'Class/PerClassFreeList.C'
X#ifndef mPERCLASSFREELIST_H
X#include "PerClassFreeList.H"
X#endif
X
Xtemplate<class T>
Xvoid *   PerClassFreeList<T>::_free_list = 0;
X
Xtemplate<class T>
Xint      PerClassFreeList<T>::free()
X{
Xvoid *   p = _free_list;
Xint      n = 0;
X   while( p != 0 ) {
X   void *   q = p;
X      p = *((void **) p);
X      ::free(q);
X      n++;
X   }
X   _free_list = 0;
X   return n;
X}
X
Xtemplate<class T>
Xint      PerClassFreeList<T>::free(unsigned num)
X{
Xvoid *   p = _free_list;
Xint      n = 0;
X   while( p != 0 && n < num) {
X   void *   q = p;
X      p = *((void **) p);
X      ::free(q);
X      n++;
X   }
X   _free_list = p;
X   return n;
X}
SHAR_EOF
if test 616 -ne "`wc -c < 'Class/PerClassFreeList.C'`"
then
	echo shar: error transmitting "'Class/PerClassFreeList.C'" '(should have been 616 characters)'
fi
fi # end of overwriting check
if test -f 'Class/PerClassFreeList.H'
then
	echo shar: will not over-write existing file "'Class/PerClassFreeList.H'"
else
sed 's/^X//' << \SHAR_EOF > 'Class/PerClassFreeList.H'
X#ifndef mPERCLASSFREELIST_H
X#define mPERCLASSFREELIST_H
X
X/* 26th December, 1992 Mayan Moudgill.
X   I'm designing a class for "bolting-on" to an existing class,
X   so as to give it free list based memory management.
X   (I would use Mixin instead of Bolton except that the Mixin is
X   used for _dynamic_ inheritance.)
X
X   Purpose:
X   Given a class Foo whose memory is to be managed in the
X   following fashion:
X      1. delete(f) takes f (of type Foo *), and adds it to a free list
X      2. new() returns first member of free list (if any) else allocates
X	    from heap
X
X   Additionally, the memory management routines contain
X      1. free() returns all free list members to heap
X      2. free(n) return n free list members to heap
X   They both return the number actually freed.
X   
X   Usage:
X      #include "PerClassFreeList.H"
X
X      class Foo : PerClassFreeList<Foo> {
X	 .
X	 .
X	 .
X      };
X*/
X
X#include <malloc.h>
X
Xtemplate <class T>
Xclass PerClassFreeList {
Xprivate:
X   static void *     _free_list;
Xpublic:
X   static int        free();
X   static int        free(unsigned);
X
X   inline void *     operator new(size_t sz)
X      {
X      void *  obj;
X	 if( _free_list == 0 ) {
X	    obj = malloc(sz);
X	 }
X	 else {
X	    obj = _free_list;
X	    _free_list = *((void **) obj); // Its not type safe--so what?
X	 }
X	 return obj;
X      }
X   inline void       operator delete(void * obj)
X      {
X	 *((void **) obj) = _free_list;
X	 _free_list = obj;                 // Neither is this--so what?
X      }
X};
X
X#endif
SHAR_EOF
if test 1502 -ne "`wc -c < 'Class/PerClassFreeList.H'`"
then
	echo shar: error transmitting "'Class/PerClassFreeList.H'" '(should have been 1502 characters)'
fi
fi # end of overwriting check
#	End of shell archive
exit 0