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 17 template<typename Element, typename Key> 18 struct HeapLink { 19 HeapLink(); 20 21 int fIndex; 22 Key fKey; 23 }; 24 25 template<typename Element, typename Key> 26 class HeapLinkImpl { 27 private: 28 typedef HeapLink<Element, Key> Link; 29 30 public: 31 inline Link* GetHeapLink(); 32 33 private: 34 Link fHeapLink; 35 }; 36 37 template<typename Element, typename Key> 38 class HeapStandardGetLink { 39 private: 40 typedef HeapLink<Element, Key> Link; 41 42 public: 43 inline Link* operator()(Element* element) const; 44 }; 45 46 template<typename Element, typename Key, 47 HeapLink<Element, Key> Element::*LinkMember> 48 class HeapMemberGetLink { 49 private: 50 typedef HeapLink<Element, Key> Link; 51 52 public: 53 inline Link* operator()(Element* element) const; 54 }; 55 56 template<typename Key> 57 class HeapLesserCompare { 58 public: 59 inline bool operator()(Key a, Key b); 60 }; 61 62 template<typename Key> 63 class HeapGreaterCompare { 64 public: 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 72 template<typename Element, typename Key, 73 typename Compare = HeapLesserCompare<Key>, 74 typename GetLink = HeapStandardGetLink<Element, Key> > 75 class Heap { 76 public: 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 90 private: 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 106 template<typename Element, typename Key> 107 HeapLink<Element, Key>::HeapLink() 108 : 109 fIndex(-1) 110 { 111 } 112 #else 113 template<typename Element, typename Key> 114 HeapLink<Element, Key>::HeapLink() 115 { 116 } 117 #endif 118 119 120 template<typename Element, typename Key> 121 HeapLink<Element, Key>* 122 HeapLinkImpl<Element, Key>::GetHeapLink() 123 { 124 return &fHeapLink; 125 } 126 127 128 template<typename Element, typename Key> 129 HeapLink<Element, Key>* 130 HeapStandardGetLink<Element, Key>::operator()(Element* element) const 131 { 132 return element->GetHeapLink(); 133 } 134 135 136 template<typename Element, typename Key, 137 HeapLink<Element, Key> Element::*LinkMember> 138 HeapLink<Element, Key>* 139 HeapMemberGetLink<Element, Key, LinkMember>::operator()(Element* element) const 140 { 141 return &(element->*LinkMember); 142 } 143 144 145 template<typename Key> 146 bool 147 HeapLesserCompare<Key>::operator()(Key a, Key b) 148 { 149 return a < b; 150 } 151 152 153 template<typename Key> 154 bool 155 HeapGreaterCompare<Key>::operator()(Key a, Key b) 156 { 157 return a > b; 158 } 159 160 161 HEAP_TEMPLATE_LIST 162 HEAP_CLASS_NAME::Heap() 163 : 164 fElements(NULL), 165 fLastElement(0), 166 fSize(0) 167 { 168 } 169 170 171 HEAP_TEMPLATE_LIST 172 HEAP_CLASS_NAME::Heap(int initialSize) 173 : 174 fElements(NULL), 175 fLastElement(0), 176 fSize(0) 177 { 178 _GrowHeap(initialSize); 179 } 180 181 182 HEAP_TEMPLATE_LIST 183 HEAP_CLASS_NAME::~Heap() 184 { 185 free(fElements); 186 } 187 188 189 HEAP_TEMPLATE_LIST 190 Element* 191 HEAP_CLASS_NAME::PeekRoot() const 192 { 193 if (fLastElement > 0) 194 return fElements[0]; 195 return NULL; 196 } 197 198 199 HEAP_TEMPLATE_LIST 200 const Key& 201 HEAP_CLASS_NAME::GetKey(Element* element) 202 { 203 return sGetLink(element)->fKey; 204 } 205 206 207 HEAP_TEMPLATE_LIST 208 void 209 HEAP_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 224 HEAP_TEMPLATE_LIST 225 void 226 HEAP_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 247 HEAP_TEMPLATE_LIST 248 status_t 249 HEAP_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 272 HEAP_TEMPLATE_LIST 273 status_t 274 HEAP_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 291 HEAP_TEMPLATE_LIST 292 void 293 HEAP_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 313 HEAP_TEMPLATE_LIST 314 void 315 HEAP_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 349 HEAP_TEMPLATE_LIST 350 Compare HEAP_CLASS_NAME::sCompare; 351 352 HEAP_TEMPLATE_LIST 353 GetLink HEAP_CLASS_NAME::sGetLink; 354 355 356 #endif // KERNEL_UTIL_HEAP_H 357 358