1 /* -*- C++ -*- */
2 
3 #ifndef HL_COALESCEHEAP_H
4 #define HL_COALESCEHEAP_H
5 
6 /*
7 
8   Heap Layers: An Extensible Memory Allocation Infrastructure
9 
10   Copyright (C) 2000-2003 by Emery Berger
11   http://www.cs.umass.edu/~emery
12   emery@cs.umass.edu
13 
14   This program is free software; you can redistribute it and/or modify
15   it under the terms of the GNU General Public License as published by
16   the Free Software Foundation; either version 2 of the License, or
17   (at your option) any later version.
18 
19   This program is distributed in the hope that it will be useful,
20   but WITHOUT ANY WARRANTY; without even the implied warranty of
21   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22   GNU General Public License for more details.
23 
24   You should have received a copy of the GNU General Public License
25   along with this program; if not, write to the Free Software
26   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
27 
28 */
29 
30 #include <assert.h>
31 
32 #include "heaplayers.h"
33 
34 /**
35  * @class CoalesceHeap
36  * @brief Applies splitting and coalescing.
37  * @see CoalesceableHeap
38  * @see RequireCoalesceable
39  */
40 
41 namespace HL {
42 
43   template <class super>
44   class CoalesceHeap : public super {
45   public:
46 
malloc(const size_t sz)47     inline void * malloc (const size_t sz)
48     {
49       void * ptr = super::malloc (sz);
50       if (ptr != NULL) {
51         super::markInUse (ptr);
52         void * splitPiece = split (ptr, sz);
53         if (splitPiece != NULL) {
54           super::markFree (splitPiece);
55           super::free (splitPiece);
56         }
57       }
58       return ptr;
59     }
60 
61 
free(void * ptr)62     inline void free (void * ptr)
63     {
64       // Try to coalesce this object with its predecessor & successor.
65       if ((super::getNext(super::getPrev(ptr)) != ptr) || (super::getPrev(super::getNext(ptr)) != ptr)) {
66         // We're done with this object.
67         super::free (ptr);
68         return;
69       }
70       assert (super::getPrev(super::getNext(ptr)) == ptr);
71       // Try to coalesce with the previous object..
72       void * prev = super::getPrev(ptr);
73       void * next = super::getNext (ptr);
74       assert (prev != ptr);
75 
76       if (super::isPrevFree(ptr)) {
77         assert (super::isFree(prev));
78         super::remove (prev);
79         coalesce (prev, ptr);
80         ptr = prev;
81       }
82       if (super::isFree(next)) {
83         super::remove (next);
84         coalesce (ptr, next);
85       }
86 
87       super::markFree (ptr);
88 
89       // We're done with this object.
90       super::free (ptr);
91     }
92 
93   private:
94 
95 
96     // Combine the first object with the second.
coalesce(void * first,const void * second)97     inline static void coalesce (void * first, const void * second) {
98       // A few sanity checks first.
99       assert (super::getNext(first) == second);
100       assert (super::getPrev(second) == first);
101       // Now coalesce.
102       size_t newSize = ((size_t) second - (size_t) first) + super::getSize(second);
103       super::setSize (first, newSize);
104       setPrevSize (super::getNext(first), newSize);
105     }
106 
107     // Split an object if it is big enough.
split(void * obj,const size_t requestedSize)108     inline static void * split (void * obj, const size_t requestedSize) {
109       assert (super::getSize(obj) >= requestedSize);
110       // We split aggressively (for now; this could be a parameter).
111       const size_t actualSize = super::getSize(obj);
112       if (actualSize - requestedSize >= sizeof(typename super::Header) + sizeof(double)) {
113         // Split the object.
114         super::setSize(obj, requestedSize);
115         void * splitPiece = (char *) obj + requestedSize + sizeof(typename super::Header);
116         super::makeObject ((void *) super::getHeader(splitPiece),
117           requestedSize,
118           actualSize - requestedSize - sizeof(typename super::Header));
119         assert (!super::isFree(splitPiece));
120         // Now that we have a new successor (splitPiece), we need to
121         // mark obj as in use.
122         (super::getHeader(splitPiece))->markPrevInUse();
123         assert (super::getSize(splitPiece) >= sizeof(double));
124         assert (super::getSize(obj) >= requestedSize);
125         return splitPiece;
126       } else {
127         return NULL;
128       }
129     }
130 
131   };
132 
133 }
134 
135 #endif
136