1/* 2 * Copyright 2013 Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Paweł Dziepak, pdziepak@quarnos.org 7 */ 8#ifndef KERNEL_UTIL_HEAP_H 9#define KERNEL_UTIL_HEAP_H 10 11 12#include <debug.h> 13 14#include <SupportDefs.h> 15 16 17template<typename Element, typename Key> 18struct HeapLink { 19 HeapLink(); 20 21 int fIndex; 22 Key fKey; 23}; 24 25template<typename Element, typename Key> 26class HeapLinkImpl { 27private: 28 typedef HeapLink<Element, Key> Link; 29 30public: 31 inline Link* GetHeapLink(); 32 33private: 34 Link fHeapLink; 35}; 36 37template<typename Element, typename Key> 38class HeapStandardGetLink { 39private: 40 typedef HeapLink<Element, Key> Link; 41 42public: 43 inline Link* operator()(Element* element) const; 44}; 45 46template<typename Element, typename Key, 47 HeapLink<Element, Key> Element::*LinkMember> 48class HeapMemberGetLink { 49private: 50 typedef HeapLink<Element, Key> Link; 51 52public: 53 inline Link* operator()(Element* element) const; 54}; 55 56template<typename Key> 57class HeapLesserCompare { 58public: 59 inline bool operator()(Key a, Key b); 60}; 61 62template<typename Key> 63class HeapGreaterCompare { 64public: 65 inline bool operator()(Key a, Key b); 66}; 67 68#define HEAP_TEMPLATE_LIST \ 69 template<typename Element, typename Key, typename Compare, typename GetLink> 70#define HEAP_CLASS_NAME Heap<Element, Key, Compare, GetLink> 71 72template<typename Element, typename Key, 73 typename Compare = HeapLesserCompare<Key>, 74 typename GetLink = HeapStandardGetLink<Element, Key> > 75class Heap { 76public: 77 Heap(); 78 Heap(int initialSize); 79 ~Heap(); 80 81 inline Element* PeekRoot() const; 82 83 static const Key& GetKey(Element* element); 84 85 inline void ModifyKey(Element* element, Key newKey); 86 87 inline void RemoveRoot(); 88 inline status_t Insert(Element* element, Key key); 89 90private: 91 status_t _GrowHeap(int minimalSize = 0); 92 93 void _MoveUp(HeapLink<Element, Key>* link); 94 void _MoveDown(HeapLink<Element, Key>* link); 95 96 Element** fElements; 97 int fLastElement; 98 int fSize; 99 100 static Compare sCompare; 101 static GetLink sGetLink; 102}; 103 104 105#if KDEBUG 106template<typename Element, typename Key> 107HeapLink<Element, Key>::HeapLink() 108 : 109 fIndex(-1) 110{ 111} 112#else 113template<typename Element, typename Key> 114HeapLink<Element, Key>::HeapLink() 115{ 116} 117#endif 118 119 120template<typename Element, typename Key> 121HeapLink<Element, Key>* 122HeapLinkImpl<Element, Key>::GetHeapLink() 123{ 124 return &fHeapLink; 125} 126 127 128template<typename Element, typename Key> 129HeapLink<Element, Key>* 130HeapStandardGetLink<Element, Key>::operator()(Element* element) const 131{ 132 return element->GetHeapLink(); 133} 134 135 136template<typename Element, typename Key, 137 HeapLink<Element, Key> Element::*LinkMember> 138HeapLink<Element, Key>* 139HeapMemberGetLink<Element, Key, LinkMember>::operator()(Element* element) const 140{ 141 return &(element->*LinkMember); 142} 143 144 145template<typename Key> 146bool 147HeapLesserCompare<Key>::operator()(Key a, Key b) 148{ 149 return a < b; 150} 151 152 153template<typename Key> 154bool 155HeapGreaterCompare<Key>::operator()(Key a, Key b) 156{ 157 return a > b; 158} 159 160 161HEAP_TEMPLATE_LIST 162HEAP_CLASS_NAME::Heap() 163 : 164 fElements(NULL), 165 fLastElement(0), 166 fSize(0) 167{ 168} 169 170 171HEAP_TEMPLATE_LIST 172HEAP_CLASS_NAME::Heap(int initialSize) 173 : 174 fElements(NULL), 175 fLastElement(0), 176 fSize(0) 177{ 178 _GrowHeap(initialSize); 179} 180 181 182HEAP_TEMPLATE_LIST 183HEAP_CLASS_NAME::~Heap() 184{ 185 free(fElements); 186} 187 188 189HEAP_TEMPLATE_LIST 190Element* 191HEAP_CLASS_NAME::PeekRoot() const 192{ 193 if (fLastElement > 0) 194 return fElements[0]; 195 return NULL; 196} 197 198 199HEAP_TEMPLATE_LIST 200const Key& 201HEAP_CLASS_NAME::GetKey(Element* element) 202{ 203 return sGetLink(element)->fKey; 204} 205 206 207HEAP_TEMPLATE_LIST 208void 209HEAP_CLASS_NAME::ModifyKey(Element* element, Key newKey) 210{ 211 HeapLink<Element, Key>* link = sGetLink(element); 212 213 ASSERT(link->fIndex >= 0 && link->fIndex < fLastElement); 214 Key oldKey = link->fKey; 215 link->fKey = newKey; 216 217 if (sCompare(newKey, oldKey)) 218 _MoveUp(link); 219 else if (sCompare(oldKey, newKey)) 220 _MoveDown(link); 221} 222 223 224HEAP_TEMPLATE_LIST 225void 226HEAP_CLASS_NAME::RemoveRoot() 227{ 228 ASSERT(fLastElement > 0); 229 230#if KDEBUG 231 Element* element = PeekRoot(); 232 HeapLink<Element, Key>* link = sGetLink(element); 233 ASSERT(link->fIndex != -1); 234 link->fIndex = -1; 235#endif 236 237 fLastElement--; 238 if (fLastElement > 0) { 239 Element* lastElement = fElements[fLastElement]; 240 fElements[0] = lastElement; 241 sGetLink(lastElement)->fIndex = 0; 242 _MoveDown(sGetLink(lastElement)); 243 } 244} 245 246 247HEAP_TEMPLATE_LIST 248status_t 249HEAP_CLASS_NAME::Insert(Element* element, Key key) 250{ 251 if (fLastElement == fSize) { 252 status_t result = _GrowHeap(); 253 if (result != B_OK) 254 return result; 255 } 256 257 ASSERT(fLastElement != fSize); 258 259 HeapLink<Element, Key>* link = sGetLink(element); 260 261 ASSERT(link->fIndex == -1); 262 263 fElements[fLastElement] = element; 264 link->fIndex = fLastElement++; 265 link->fKey = key; 266 _MoveUp(link); 267 268 return B_OK; 269} 270 271 272HEAP_TEMPLATE_LIST 273status_t 274HEAP_CLASS_NAME::_GrowHeap(int minimalSize) 275{ 276 int newSize = max_c(max_c(fSize * 2, 4), minimalSize); 277 278 size_t arraySize = newSize * sizeof(Element*); 279 Element** newBuffer 280 = reinterpret_cast<Element**>(realloc(fElements, arraySize)); 281 if (newBuffer == NULL) 282 return B_NO_MEMORY; 283 284 fElements = newBuffer; 285 fSize = newSize; 286 287 return B_OK; 288} 289 290 291HEAP_TEMPLATE_LIST 292void 293HEAP_CLASS_NAME::_MoveUp(HeapLink<Element, Key>* link) 294{ 295 while (true) { 296 int parent = (link->fIndex - 1) / 2; 297 if (link->fIndex > 0 298 && sCompare(link->fKey, sGetLink(fElements[parent])->fKey)) { 299 300 sGetLink(fElements[parent])->fIndex = link->fIndex; 301 302 Element* element = fElements[link->fIndex]; 303 fElements[link->fIndex] = fElements[parent]; 304 fElements[parent] = element; 305 306 link->fIndex = parent; 307 } else 308 break; 309 } 310} 311 312 313HEAP_TEMPLATE_LIST 314void 315HEAP_CLASS_NAME::_MoveDown(HeapLink<Element, Key>* link) 316{ 317 int current; 318 319 while (true) { 320 current = link->fIndex; 321 322 int child = 2 * link->fIndex + 1; 323 if (child < fLastElement 324 && sCompare(sGetLink(fElements[child])->fKey, link->fKey)) { 325 current = child; 326 } 327 328 child = 2 * link->fIndex + 2; 329 if (child < fLastElement 330 && sCompare(sGetLink(fElements[child])->fKey, 331 sGetLink(fElements[current])->fKey)) { 332 current = child; 333 } 334 335 if (link->fIndex == current) 336 break; 337 338 sGetLink(fElements[current])->fIndex = link->fIndex; 339 340 Element* element = fElements[link->fIndex]; 341 fElements[link->fIndex] = fElements[current]; 342 fElements[current] = element; 343 344 link->fIndex = current; 345 } 346} 347 348 349HEAP_TEMPLATE_LIST 350Compare HEAP_CLASS_NAME::sCompare; 351 352HEAP_TEMPLATE_LIST 353GetLink HEAP_CLASS_NAME::sGetLink; 354 355 356#endif // KERNEL_UTIL_HEAP_H 357 358