C++primer中 CacheObj实现（非常有意思）

  1 //CacheObj.h
  2 
  3 #ifndef __CacheObj__                                                                                               
  4 #define __CacheObj__
  5 
  6 #include <iostream>
  7 #include <stdexcept>
  8 #include <malloc.h>
  9 
 10 
 11 /*
 12  * memory allocation class: Pre-allocates objects and
 13  * maintains a freelist of objects that are unused
 14  * When an object if freed, it is put back on the freelist
 15  * some of the memory will be only returned when the program exist;
 16  */
 17 template < typename Type >
 18 class CacheObj
 19 {
 20     public: 
 21         static void* operator new(std::size_t);
 22 #if 1
 23         static void* operator new[](std::size_t);
 24 #endif
 25         
 26         static void operator delete(void*, std::size_t);
 27 #if 1
 28         static void operator delete[](void*, std::size_t);
 29 #endif
 30 
 31         virtual ~CacheObj(){} 
 32 
 33     protected:
 34         Type *next;
 35         static void list_free(void);
 36 
 37     private:
 38         static void add_to_freelist(Type *);
 39         static Type* freelist;
 40         static std::size_t unuse_size; //未用链表的长度不会超过2 * chunk;
 41         static const std::size_t chunk;
 42 };
 43 
 44 template < typename Type > Type* CacheObj< Type >::freelist = NULL;
 45 template < typename Type > std::size_t CacheObj< Type >::unuse_size = 0;
 46 template < typename Type > const std::size_t CacheObj< Type >::chunk = 2;
 47 
 48 
 49 template < typename Type >
 50 void* CacheObj< Type >::operator new(std::size_t size)
 51 {
 52 /*
 53  * new should only be asked to build a Type;
 54  * not an object derived from T;
 55  * check that right size is requested
 56  */
 57     if(size != sizeof(Type))
 58     {
 59         throw std::runtime_error("CacheObj: wrong size object in operator new");
 60     }
 61 
 62 
 63 //if list is empty: grab a new chunk of memory
 64 //allocate allocates chunk number of objects of type Type
 65     if(NULL == freelist)
 66     {
 67 #if 0
 68 //一次申请大量数据空间，很爽啊，可是因为这种不计后果的行为，花费了大半天的时间
 69 /*解释：
 70  *很明显的bug例子：int *p = (int*)malloc(8*sizeof(int));  free(p); free(p+4);
 71  *自己考虑的太不周全了
 72  *使用一次性申请大量空间的bug出在：
 73  *  list_free()函数，其中每次free都以一个object的地址为参数,如同给出的bug示例，所以错了                            
 74  *
 75  */
 76         Type* array = (Type*)malloc(size * chunk);
 77         if(NULL == array)
 78         {
 79             throw std::runtime_error("CacheObj: wrong size object in operator new");
 80         }
 81 //谢谢陈涛，大神走了还有个人讨论，终于发现问题的所在了
 82 #endif
 83 
 84 //allocate allocates chunk number of objects of type T
 85         for(unsigned int i = 0; i != chunk; i++)
 86         {
 87 #if 1
 88             Type* array = (Type*)malloc(size);
 89             if(NULL == array)
 90             {
 91                 throw std::runtime_error("CacheObj: wrong size object in operator new");
 92             }
 93 #endif
 94             add_to_freelist(array);
 95 #if 0
 96             array++;
 97 #endif
 98         }
 99     }
100 
101     Type *p = freelist;
102     freelist = freelist->CacheObj< Type >::next;
103     unuse_size--;
104     p->CacheObj< Type >::next = NULL;
105     return p;
106 }
107 
108 #if 1
109 template < typename Type >
110 void* CacheObj< Type >::operator new[](std::size_t size)
111 {
112     void *p = malloc(size);
113     return p;
114 }
115 #endif
116 
117 template <typename Type >
118 void CacheObj< Type >::operator delete(void* p, std::size_t)
119 {
120     if(p != 0)
121     {
122         add_to_freelist(static_cast< Type* >(p));
123     }   
124 }
125 
126 #if 1
127 template < typename Type >
128 void CacheObj< Type >::operator delete[](void* p, std::size_t)
129 {
130     if(!p)
131         free(p);
132 }
133 #endif
134 
135 template < typename Type >
136 void CacheObj< Type >::list_free(void)
137 {
138     while(freelist)
139     {
140         Type *temp = freelist;
141         freelist = temp->CacheObj< Type >::next;    
142         free(temp);
143         unuse_size--;
144     }
145 }
146 
147 //puts object at head of the freelist
148 template < typename Type >
149 void CacheObj< Type >::add_to_freelist(Type *p)
150 {
151     if(!p)
152         return; 
153 
154     if(unuse_size >> 1 == chunk)
155     {       
156         free(p);
157         return ;
158     }
159 
160     unuse_size++;
161     p->CacheObj< Type >::next = freelist;
162     freelist = p;
163 }
164 
165 #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(0){}

    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(0), tail(0){}

        //copy control to manage pointers to QueueItems in the Queue
        Queue(const Queue &Q):head(0), tail(0) 
    {
        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(0), tail(0)
{
    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 != 0)
    {
        while(pt)
        {
            QueueItem< Type >* temp = pt;
            pt = pt->next;
            delete temp;
        }
    }

    head = tail = 0;
    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 == 0;
}

//成员函数实现
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

 1 //test.cpp
 2 
 3 #include <iostream>                                                                                                
 4 #include "QueueItem.h"
 5 
 6 int main(void)
 7 {
 8     int array[5] = {4, 6, 7, 8, 90}; 
 9     Queue<int> qi(array + 0, array + 5);
10     short s = 42; 
11     qi.push(s);
12     qi.pop();
13     qi.pop();
14     qi.pop();
15     qi.push(s);
16     qi.push(s);
17     std::cout << qi << std::endl;
18 
19     return 0;
20 }