//CacheObj.h #ifndef __CacheObj__
#define __CacheObj__ #include <iostream>
#include <stdexcept>
#include <malloc.h> /*
* memory allocation class: Pre-allocates objects and
* maintains a freelist of objects that are unused
* When an object if freed, it is put back on the freelist
* some of the memory will be only returned when the program exist;
*/
template < typename Type >
class CacheObj
{
public:
static void* operator new(std::size_t);
#if 1
static void* operator new[](std::size_t);
#endif static void operator delete(void*, std::size_t);
#if 1
static void operator delete[](void*, std::size_t);
#endif virtual ~CacheObj(){} protected:
Type *next;
static void list_free(void); private:
static void add_to_freelist(Type *);
static Type* freelist;
static std::size_t unuse_size; //未用链表的长度不会超过2 * chunk;
static const std::size_t chunk;
}; template < typename Type > Type* CacheObj< Type >::freelist = NULL;
template < typename Type > std::size_t CacheObj< Type >::unuse_size = ;
template < typename Type > const std::size_t CacheObj< Type >::chunk = ; template < typename Type >
void* CacheObj< Type >::operator new(std::size_t size)
{
/*
* new should only be asked to build a Type;
* not an object derived from T;
* check that right size is requested
*/
if(size != sizeof(Type))
{
throw std::runtime_error("CacheObj: wrong size object in operator new");
} //if list is empty: grab a new chunk of memory
//allocate allocates chunk number of objects of type Type
if(NULL == freelist)
{
#if 0
//一次申请大量数据空间，很爽啊，可是因为这种不计后果的行为，花费了大半天的时间
/*解释：
*很明显的bug例子：int *p = (int*)malloc(8*sizeof(int)); free(p); free(p+4);
*自己考虑的太不周全了
*使用一次性申请大量空间的bug出在：
* list_free()函数，其中每次free都以一个object的地址为参数,如同给出的bug示例，所以错了
*
*/
Type* array = (Type*)malloc(size * chunk);
if(NULL == array)
{
throw std::runtime_error("CacheObj: wrong size object in operator new");
}
//谢谢陈涛，大神走了还有个人讨论，终于发现问题的所在了
#endif //allocate allocates chunk number of objects of type T
for(unsigned int i = ; i != chunk; i++)
{
#if 1
Type* array = (Type*)malloc(size);
if(NULL == array)
{
throw std::runtime_error("CacheObj: wrong size object in operator new");
}
#endif
add_to_freelist(array);
#if 0
array++;
#endif
}
} Type *p = freelist;
freelist = freelist->CacheObj< Type >::next;
unuse_size--;
p->CacheObj< Type >::next = NULL;
return p;
} #if 1
template < typename Type >
void* CacheObj< Type >::operator new[](std::size_t size)
{
void *p = malloc(size);
return p;
}
#endif template <typename Type >
void CacheObj< Type >::operator delete(void* p, std::size_t)
{
if(p != )
{
add_to_freelist(static_cast< Type* >(p));
}
} #if 1
template < typename Type >
void CacheObj< Type >::operator delete[](void* p, std::size_t)
{
if(!p)
free(p);
}
#endif template < typename Type >
void CacheObj< Type >::list_free(void)
{
while(freelist)
{
Type *temp = freelist;
freelist = temp->CacheObj< Type >::next;
free(temp);
unuse_size--;
}
} //puts object at head of the freelist
template < typename Type >
void CacheObj< Type >::add_to_freelist(Type *p)
{
if(!p)
return; if(unuse_size >> == chunk)
{
free(p);
return ;
} unuse_size++;
p->CacheObj< Type >::next = freelist;
freelist = p;
} #endif
//QueueItem.h#ifndef __QUEUEITEM__
#define __QUEUEITEM__#include "CacheObj.h"template < typename Type > class Queue; //下面因为进行类模板特化，所以此处先声明template < typename Type >
std::ostream& operator<<(std::ostream&, const Queue< Type >&); //下面需要进行函数模特化，所以此处先声明template < typename Type >
class QueueItem: public CacheObj< QueueItem< Type > >
{
friend class Queue< Type >; //类模板特化
friend std::ostream& operator<< < Type >(std::ostream&, const Queue< Type >&); //函数模板特化
//private class : no public section; QueueItem(const Type &t): item(t), next(){} Type item; //value stored in this element;
QueueItem *next; //pointer to next element in the Queue; ~QueueItem(void)
{
next = NULL;
}
};template < typename Type >
class Queue
{
friend std::ostream& operator<< < Type >(std::ostream&, const Queue< Type >&); //函数模板特化
public:
//empty Queue
Queue(void):head(), tail(){} //copy control to manage pointers to QueueItems in the Queue
Queue(const Queue &Q):head(), tail()
{
copy_elems(Q);
} template < typename Iter >
Queue(Iter beg, Iter end); //成员模板 ~Queue(void); Queue& operator=(const Queue&); Type& front(void); const Type& front(void) const; //return element from head of Queue; void push(const Type&); //add element to back of Queue;
void pop(void); //remove element from head of Queue;
bool empty(void)const; //true if no elements in Queue; private:
QueueItem< Type >* head; //pointer to first element in Queue;
QueueItem< Type >* tail; //pointer to last element in Queue; //utility functions used by copy constructor, assignment, and destructor
void destroy(void); //delete all the elements;
void copy_elems(const Queue&); //copy elements from parameter template < typename Iter >
void copy_elems(Iter beg, Iter end); //成员模板，且重载上一函数
};//成员模板实现
template < typename Type >
template < typename Iter >
Queue< Type >::Queue(Iter beg, Iter end):head(), tail()
{
destroy();
copy_elems(beg, end);
}template < typename Type >
Queue< Type >::~Queue(void)
{
destroy();
}template < typename Type >
Queue< Type >& Queue< Type >::operator=(const Queue<Type>& src)
{
Queue< Type >* pt = head;
if(head != )
{
while(pt)
{
QueueItem< Type >* temp = pt;
pt = pt->next;
delete temp;
}
} head = tail = ;
copy_elems(src);
}template < typename Type >
Type& Queue< Type >::front(void)
{
return head->item;
}template < typename Type >
const Type& Queue< Type >::front(void) const
{
return head->item;
}template < typename Type >
void Queue< Type >::push(const Type& val)
{
//allocate a new QueueItem object;
QueueItem< Type >* pt = new QueueItem< Type >(val);//put item onto existing queue;
if(empty())
{
head = tail = pt; //the queue now has only one element;
}
else
{
tail->next = pt; //add new element to end of the queue;
tail = pt;
}
}//pop is unchecked: Popping off an empty Queue is undefined;
template < typename Type >
void Queue< Type >::pop(void)
{
QueueItem< Type >* p = head; //keep pointer to head so we can delete it;
head = head->next; //head now points to next element;
delete p; //delete old head element;
}template < typename Type >
bool Queue< Type >::empty(void)const
{
return head == ;
}//成员函数实现
template < typename Type >
void Queue< Type >::destroy(void)
{
while(!empty())
pop(); QueueItem< Type >::list_free();
}//copy elements from orig into this Queue;
//loop stops when pt == 0, which happens when we reach orig.tail;
template < typename Type >
void Queue< Type >::copy_elems(const Queue< Type >& orig)
{
for(QueueItem< Type >*pt = orig.head; pt = pt->next;)
{
push(pt->item);
}
}//成员模板实现
template < typename Type >
template < typename Iter >
void Queue< Type >::copy_elems(Iter beg, Iter end)
{
while(beg != end)
{
push(*beg);
++beg;
}
}//普通函数模板
template < typename Type >
std::ostream& operator<<(std::ostream &os, const Queue< Type >& q)
{
os << "< ";
QueueItem< Type >*p; for(p = q.head; p ; p = p->next)
{
os << p->item << " ";
}
os << ">";
return os;
}#endif
//test.cpp #include <iostream>
#include "QueueItem.h" int main(void)
{
int array[] = {, , , , };
Queue<int> qi(array + , array + );
short s = ;
qi.push(s);
qi.pop();
qi.pop();
qi.pop();
qi.push(s);
qi.push(s);
std::cout << qi << std::endl; return ;
}
