headers/private/kernel/util/Heap.h

   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