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