headers/private/kernel/util/AVLTreeMap.h

   1 /*
   2  * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@gmx.de>.
   3  * Distributed under the terms of the MIT License.
   4  */
   5 #ifndef _KERNEL_UTIL_AVL_TREE_MAP_H
   6 #define _KERNEL_UTIL_AVL_TREE_MAP_H
   7
   8
   9 #include <util/MallocFreeAllocator.h>
  10 #include <util/AVLTreeBase.h>
  11
  12
  13 // strategies
  14 namespace AVLTreeMapStrategy {
  15         // key orders
  16         template<typename Value> class Ascending;
  17         template<typename Value> class Descending;
  18
  19         //! Automatic node strategy (works like STL containers do)
  20         template <typename Key, typename Value,
  21                           typename KeyOrder = Ascending<Key>,
  22                           template <typename> class Allocator = MallocFreeAllocator>
  23         class Auto;
  24
  25 /*!     NodeStrategy must implement this interface:
  26         typename Node;
  27         inline Node* Allocate(const Key& key, const Value& value)
  28         inline void Free(Node* node)
  29         inline const Key GetKey(const Node* node) const
  30         inline Value& GetValue(Node* node) const
  31         inline AVLTreeNode* GetAVLTreeNode(Node* node) const
  32         inline Node* GetNode(AVLTreeNode* node) const
  33         inline int CompareKeyNode(const Key& a, const Node* b)
  34         inline int CompareNodes(const Node* a, const Node* b)
  35 */
  36 }
  37
  38
  39 // for convenience
  40 #define _AVL_TREE_MAP_TEMPLATE_LIST template<typename Key, typename Value, \
  41         typename NodeStrategy>
  42 #define _AVL_TREE_MAP_CLASS_NAME AVLTreeMap<Key, Value, NodeStrategy>
  43
  44
  45 // AVLTreeMap
  46 template<typename Key, typename Value,
  47                  typename NodeStrategy = AVLTreeMapStrategy::Auto<Key, Value> >
  48 class AVLTreeMap : protected AVLTreeCompare {
  49 private:
  50         typedef typename NodeStrategy::Node     Node;
  51         typedef _AVL_TREE_MAP_CLASS_NAME        Class;
  52
  53 public:
  54         class Iterator;
  55         class ConstIterator;
  56
  57 public:
  58                                                                 AVLTreeMap(const NodeStrategy& strategy
  59                                                                         = NodeStrategy());
  60         virtual                                         ~AVLTreeMap();
  61
  62         inline  int                                     Count() const   { return fTree.Count(); }
  63         inline  bool                            IsEmpty() const { return fTree.IsEmpty(); }
  64         inline  void                            MakeEmpty();
  65
  66                         Node*                           RootNode() const;
  67
  68                         Node*                           Previous(Node* node) const;
  69                         Node*                           Next(Node* node) const;
  70
  71         inline  Iterator                        GetIterator();
  72         inline  ConstIterator           GetIterator() const;
  73
  74         inline  Iterator                        GetIterator(Node* node);
  75         inline  ConstIterator           GetIterator(Node* node) const;
  76
  77                         Iterator                        Find(const Key& key);
  78                         Iterator                        FindClose(const Key& key, bool less);
  79
  80                         status_t                        Insert(const Key& key, const Value& value,
  81                                                                         Iterator* iterator);
  82                         status_t                        Insert(const Key& key, const Value& value,
  83                                                                         Node** _node = NULL);
  84                         status_t                        Remove(const Key& key);
  85                         status_t                        Remove(Node* node);
  86
  87                         const NodeStrategy&     GetNodeStrategy() const { return fStrategy; }
  88
  89 protected:
  90         // AVLTreeCompare
  91         virtual int                                     CompareKeyNode(const void* key,
  92                                                                         const AVLTreeNode* node);
  93         virtual int                                     CompareNodes(const AVLTreeNode* node1,
  94                                                                         const AVLTreeNode* node2);
  95
  96                         void                            _FreeTree(AVLTreeNode* node);
  97
  98         // strategy shortcuts
  99         inline  Node*                           _Allocate(const Key& key, const Value& value);
 100         inline  void                            _Free(Node* node);
 101         inline  Key                                     _GetKey(Node* node) const;
 102         inline  Value&                          _GetValue(Node* node) const;
 103         inline  AVLTreeNode*            _GetAVLTreeNode(const Node* node) const;
 104         inline  Node*                           _GetNode(const AVLTreeNode* node) const;
 105         inline  int                                     _CompareKeyNode(const Key& a, const Node* b);
 106         inline  int                                     _CompareNodes(const Node* a, const Node* b);
 107
 108 protected:
 109                         friend class Iterator;
 110                         friend class ConstIterator;
 111
 112                         AVLTreeBase                     fTree;
 113                         NodeStrategy            fStrategy;
 114
 115 public:
 116         // Iterator
 117         // (need to implement it here, otherwise gcc 2.95.3 chokes)
 118         class Iterator : public ConstIterator {
 119         public:
 120                 inline Iterator()
 121                         : ConstIterator()
 122                 {
 123                 }
 124
 125                 inline Iterator(const Iterator& other)
 126                         : ConstIterator(other)
 127                 {
 128                 }
 129
 130                 inline void Remove()
 131                 {
 132                         if (AVLTreeNode* node = ConstIterator::fTreeIterator.Remove()) {
 133                                 _AVL_TREE_MAP_CLASS_NAME* parent
 134                                         = const_cast<_AVL_TREE_MAP_CLASS_NAME*>(
 135                                                 ConstIterator::fParent);
 136                                 parent->_Free(parent->_GetNode(node));
 137                         }
 138                 }
 139
 140         private:
 141                 inline Iterator(_AVL_TREE_MAP_CLASS_NAME* parent,
 142                         const AVLTreeIterator& treeIterator)
 143                         : ConstIterator(parent, treeIterator)
 144                 {
 145                 }
 146
 147                 friend class _AVL_TREE_MAP_CLASS_NAME;
 148         };
 149 };
 150
 151
 152 // ConstIterator
 153 _AVL_TREE_MAP_TEMPLATE_LIST
 154 class _AVL_TREE_MAP_CLASS_NAME::ConstIterator {
 155 public:
 156         inline ConstIterator()
 157                 : fParent(NULL),
 158                   fTreeIterator()
 159         {
 160         }
 161
 162         inline ConstIterator(const ConstIterator& other)
 163                 : fParent(other.fParent),
 164                   fTreeIterator(other.fTreeIterator)
 165         {
 166         }
 167
 168         inline bool HasCurrent() const
 169         {
 170                 return fTreeIterator.Current();
 171         }
 172
 173         inline Key CurrentKey()
 174         {
 175                 if (AVLTreeNode* node = fTreeIterator.Current())
 176                         return fParent->_GetKey(fParent->_GetNode(node));
 177                 return Key();
 178         }
 179
 180         inline Value Current()
 181         {
 182                 if (AVLTreeNode* node = fTreeIterator.Current())
 183                         return fParent->_GetValue(fParent->_GetNode(node));
 184                 return Value();
 185         }
 186
 187         inline Value* CurrentValuePointer()
 188         {
 189                 if (AVLTreeNode* node = fTreeIterator.Current())
 190                         return &fParent->_GetValue(fParent->_GetNode(node));
 191                 return NULL;
 192         }
 193
 194         inline Node* CurrentNode()
 195         {
 196                 if (AVLTreeNode* node = fTreeIterator.Current())
 197                         return fParent->_GetNode(node);
 198                 return NULL;
 199         }
 200
 201         inline bool HasNext() const
 202         {
 203                 return fTreeIterator.HasNext();
 204         }
 205
 206         inline Value Next()
 207         {
 208                 if (AVLTreeNode* node = fTreeIterator.Next())
 209                         return fParent->_GetValue(fParent->_GetNode(node));
 210                 return Value();
 211         }
 212
 213         inline Value* NextValuePointer()
 214         {
 215                 if (AVLTreeNode* node = fTreeIterator.Next())
 216                         return &fParent->_GetValue(fParent->_GetNode(node));
 217                 return NULL;
 218         }
 219
 220         inline Value Previous()
 221         {
 222                 if (AVLTreeNode* node = fTreeIterator.Previous())
 223                         return fParent->_GetValue(fParent->_GetNode(node));
 224                 return Value();
 225         }
 226
 227         inline ConstIterator& operator=(const ConstIterator& other)
 228         {
 229                 fParent = other.fParent;
 230                 fTreeIterator = other.fTreeIterator;
 231                 return *this;
 232         }
 233
 234 protected:
 235         inline ConstIterator(const _AVL_TREE_MAP_CLASS_NAME* parent,
 236                 const AVLTreeIterator& treeIterator)
 237         {
 238                 fParent = parent;
 239                 fTreeIterator = treeIterator;
 240         }
 241
 242         friend class _AVL_TREE_MAP_CLASS_NAME;
 243
 244         const _AVL_TREE_MAP_CLASS_NAME* fParent;
 245         AVLTreeIterator                                 fTreeIterator;
 246 };
 247
 248
 249 // constructor
 250 _AVL_TREE_MAP_TEMPLATE_LIST
 251 _AVL_TREE_MAP_CLASS_NAME::AVLTreeMap(const NodeStrategy& strategy)
 252         : fTree(this),
 253           fStrategy(strategy)
 254 {
 255 }
 256
 257
 258 // destructor
 259 _AVL_TREE_MAP_TEMPLATE_LIST
 260 _AVL_TREE_MAP_CLASS_NAME::~AVLTreeMap()
 261 {
 262 }
 263
 264
 265 // MakeEmpty
 266 _AVL_TREE_MAP_TEMPLATE_LIST
 267 inline void
 268 _AVL_TREE_MAP_CLASS_NAME::MakeEmpty()
 269 {
 270         AVLTreeNode* root = fTree.Root();
 271         _FreeTree(root);
 272         fTree.MakeEmpty();
 273 }
 274
 275
 276 // RootNode
 277 _AVL_TREE_MAP_TEMPLATE_LIST
 278 inline typename _AVL_TREE_MAP_CLASS_NAME::Node*
 279 _AVL_TREE_MAP_CLASS_NAME::RootNode() const
 280 {
 281         if (AVLTreeNode* root = fTree.Root())
 282                 return _GetNode(root);
 283         return NULL;
 284 }
 285
 286
 287 // Previous
 288 _AVL_TREE_MAP_TEMPLATE_LIST
 289 inline typename _AVL_TREE_MAP_CLASS_NAME::Node*
 290 _AVL_TREE_MAP_CLASS_NAME::Previous(Node* node) const
 291 {
 292         if (node == NULL)
 293                 return NULL;
 294
 295         AVLTreeNode* treeNode = fTree.Previous(_GetAVLTreeNode(node));
 296         return treeNode != NULL ? _GetNode(treeNode) : NULL;
 297 }
 298
 299
 300 // Next
 301 _AVL_TREE_MAP_TEMPLATE_LIST
 302 inline typename _AVL_TREE_MAP_CLASS_NAME::Node*
 303 _AVL_TREE_MAP_CLASS_NAME::Next(Node* node) const
 304 {
 305         if (node == NULL)
 306                 return NULL;
 307
 308         AVLTreeNode* treeNode = fTree.Next(_GetAVLTreeNode(node));
 309         return treeNode != NULL ? _GetNode(treeNode) : NULL;
 310 }
 311
 312
 313 // GetIterator
 314 _AVL_TREE_MAP_TEMPLATE_LIST
 315 inline typename _AVL_TREE_MAP_CLASS_NAME::Iterator
 316 _AVL_TREE_MAP_CLASS_NAME::GetIterator()
 317 {
 318         return Iterator(this, fTree.GetIterator());
 319 }
 320
 321
 322 // GetIterator
 323 _AVL_TREE_MAP_TEMPLATE_LIST
 324 inline typename _AVL_TREE_MAP_CLASS_NAME::ConstIterator
 325 _AVL_TREE_MAP_CLASS_NAME::GetIterator() const
 326 {
 327         return ConstIterator(this, fTree.GetIterator());
 328 }
 329
 330
 331 // GetIterator
 332 _AVL_TREE_MAP_TEMPLATE_LIST
 333 inline typename _AVL_TREE_MAP_CLASS_NAME::Iterator
 334 _AVL_TREE_MAP_CLASS_NAME::GetIterator(Node* node)
 335 {
 336         return Iterator(this, fTree.GetIterator(_GetAVLTreeNode(node)));
 337 }
 338
 339
 340 // GetIterator
 341 _AVL_TREE_MAP_TEMPLATE_LIST
 342 inline typename _AVL_TREE_MAP_CLASS_NAME::ConstIterator
 343 _AVL_TREE_MAP_CLASS_NAME::GetIterator(Node* node) const
 344 {
 345         return ConstIterator(this, fTree.GetIterator(_GetAVLTreeNode(node)));
 346 }
 347
 348
 349 // Find
 350 _AVL_TREE_MAP_TEMPLATE_LIST
 351 typename _AVL_TREE_MAP_CLASS_NAME::Iterator
 352 _AVL_TREE_MAP_CLASS_NAME::Find(const Key& key)
 353 {
 354         if (AVLTreeNode* node = fTree.Find(&key))
 355                 return Iterator(this, fTree.GetIterator(node));
 356         return Iterator();
 357 }
 358
 359
 360 // FindClose
 361 _AVL_TREE_MAP_TEMPLATE_LIST
 362 typename _AVL_TREE_MAP_CLASS_NAME::Iterator
 363 _AVL_TREE_MAP_CLASS_NAME::FindClose(const Key& key, bool less)
 364 {
 365         if (AVLTreeNode* node = fTree.FindClosest(&key, less))
 366                 return Iterator(this, fTree.GetIterator(node));
 367         return Iterator();
 368 }
 369
 370
 371 // Insert
 372 _AVL_TREE_MAP_TEMPLATE_LIST
 373 status_t
 374 _AVL_TREE_MAP_CLASS_NAME::Insert(const Key& key, const Value& value,
 375         Iterator* iterator)
 376 {
 377         // allocate a node
 378         Node* userNode = _Allocate(key, value);
 379         if (!userNode)
 380                 return B_NO_MEMORY;
 381
 382         // insert node
 383         AVLTreeNode* node = _GetAVLTreeNode(userNode);
 384         status_t error = fTree.Insert(node);
 385         if (error != B_OK) {
 386                 _Free(userNode);
 387                 return error;
 388         }
 389
 390         if (iterator)
 391                 *iterator = Iterator(this, fTree.GetIterator(node));
 392
 393         return B_OK;
 394 }
 395
 396
 397 // Insert
 398 _AVL_TREE_MAP_TEMPLATE_LIST
 399 status_t
 400 _AVL_TREE_MAP_CLASS_NAME::Insert(const Key& key, const Value& value,
 401         Node** _node)
 402 {
 403         // allocate a node
 404         Node* userNode = _Allocate(key, value);
 405         if (!userNode)
 406                 return B_NO_MEMORY;
 407
 408         // insert node
 409         AVLTreeNode* node = _GetAVLTreeNode(userNode);
 410         status_t error = fTree.Insert(node);
 411         if (error != B_OK) {
 412                 _Free(userNode);
 413                 return error;
 414         }
 415
 416         if (_node != NULL)
 417                 *_node = userNode;
 418
 419         return B_OK;
 420 }
 421
 422
 423 // Remove
 424 _AVL_TREE_MAP_TEMPLATE_LIST
 425 status_t
 426 _AVL_TREE_MAP_CLASS_NAME::Remove(const Key& key)
 427 {
 428         AVLTreeNode* node = fTree.Remove(&key);
 429         if (!node)
 430                 return B_ENTRY_NOT_FOUND;
 431
 432         _Free(_GetNode(node));
 433         return B_OK;
 434 }
 435
 436
 437 // Remove
 438 _AVL_TREE_MAP_TEMPLATE_LIST
 439 status_t
 440 _AVL_TREE_MAP_CLASS_NAME::Remove(Node* node)
 441 {
 442         if (!fTree.Remove(node))
 443                 return B_ENTRY_NOT_FOUND;
 444
 445         _Free(node);
 446         return B_OK;
 447 }
 448
 449
 450 // CompareKeyNode
 451 _AVL_TREE_MAP_TEMPLATE_LIST
 452 int
 453 _AVL_TREE_MAP_CLASS_NAME::CompareKeyNode(const void* key,
 454         const AVLTreeNode* node)
 455 {
 456         return _CompareKeyNode(*(const Key*)key, _GetNode(node));
 457 }
 458
 459
 460 // CompareNodes
 461 _AVL_TREE_MAP_TEMPLATE_LIST
 462 int
 463 _AVL_TREE_MAP_CLASS_NAME::CompareNodes(const AVLTreeNode* node1,
 464         const AVLTreeNode* node2)
 465 {
 466         return _CompareNodes(_GetNode(node1), _GetNode(node2));
 467 }
 468
 469
 470 // _Allocate
 471 _AVL_TREE_MAP_TEMPLATE_LIST
 472 inline typename _AVL_TREE_MAP_CLASS_NAME::Node*
 473 _AVL_TREE_MAP_CLASS_NAME::_Allocate(const Key& key, const Value& value)
 474 {
 475         return fStrategy.Allocate(key, value);
 476 }
 477
 478
 479 // _Free
 480 _AVL_TREE_MAP_TEMPLATE_LIST
 481 inline void
 482 _AVL_TREE_MAP_CLASS_NAME::_Free(Node* node)
 483 {
 484         fStrategy.Free(node);
 485 }
 486
 487
 488 // _GetKey
 489 _AVL_TREE_MAP_TEMPLATE_LIST
 490 inline Key
 491 _AVL_TREE_MAP_CLASS_NAME::_GetKey(Node* node) const
 492 {
 493         return fStrategy.GetKey(node);
 494 }
 495
 496
 497 // _GetValue
 498 _AVL_TREE_MAP_TEMPLATE_LIST
 499 inline Value&
 500 _AVL_TREE_MAP_CLASS_NAME::_GetValue(Node* node) const
 501 {
 502         return fStrategy.GetValue(node);
 503 }
 504
 505
 506 // _GetAVLTreeNode
 507 _AVL_TREE_MAP_TEMPLATE_LIST
 508 inline AVLTreeNode*
 509 _AVL_TREE_MAP_CLASS_NAME::_GetAVLTreeNode(const Node* node) const
 510 {
 511         return fStrategy.GetAVLTreeNode(const_cast<Node*>(node));
 512 }
 513
 514
 515 // _GetNode
 516 _AVL_TREE_MAP_TEMPLATE_LIST
 517 inline typename _AVL_TREE_MAP_CLASS_NAME::Node*
 518 _AVL_TREE_MAP_CLASS_NAME::_GetNode(const AVLTreeNode* node) const
 519 {
 520         return fStrategy.GetNode(const_cast<AVLTreeNode*>(node));
 521 }
 522
 523
 524 // _CompareKeyNode
 525 _AVL_TREE_MAP_TEMPLATE_LIST
 526 inline int
 527 _AVL_TREE_MAP_CLASS_NAME::_CompareKeyNode(const Key& a, const Node* b)
 528 {
 529         return fStrategy.CompareKeyNode(a, b);
 530 }
 531
 532
 533 // _CompareNodes
 534 _AVL_TREE_MAP_TEMPLATE_LIST
 535 inline int
 536 _AVL_TREE_MAP_CLASS_NAME::_CompareNodes(const Node* a, const Node* b)
 537 {
 538         return fStrategy.CompareNodes(a, b);
 539 }
 540
 541
 542 // _FreeTree
 543 _AVL_TREE_MAP_TEMPLATE_LIST
 544 void
 545 _AVL_TREE_MAP_CLASS_NAME::_FreeTree(AVLTreeNode* node)
 546 {
 547         if (node) {
 548                 _FreeTree(node->left);
 549                 _FreeTree(node->right);
 550                 _Free(_GetNode(node));
 551         }
 552 }
 553
 554
 555 // #pragma mark - strategy parameters
 556
 557 // Ascending
 558 namespace AVLTreeMapStrategy {
 559 template<typename Value>
 560 class Ascending {
 561 public:
 562         inline int operator()(const Value &a, const Value &b) const
 563         {
 564                 if (a < b)
 565                         return -1;
 566                 else if (a > b)
 567                         return 1;
 568                 return 0;
 569         }
 570 };
 571 }
 572
 573
 574 // Descending
 575 namespace AVLTreeMapStrategy {
 576 template<typename Value>
 577 class Descending {
 578 public:
 579         inline int operator()(const Value &a, const Value &b) const
 580         {
 581                 if (a < b)
 582                         return -1;
 583                 else if (a > b)
 584                         return 1;
 585                 return 0;
 586         }
 587 };
 588 }
 589
 590
 591 // #pragma mark - strategies
 592
 593
 594 // Auto
 595 namespace AVLTreeMapStrategy {
 596 template <typename Key, typename Value, typename KeyOrder,
 597                   template <typename> class Allocator>
 598 class Auto {
 599 public:
 600         struct Node : AVLTreeNode {
 601                 Node(const Key &key, const Value &value)
 602                         : AVLTreeNode(),
 603                           key(key),
 604                           value(value)
 605                 {
 606                 }
 607
 608                 Key             key;
 609                 Value   value;
 610         };
 611
 612         inline Node* Allocate(const Key& key, const Value& value)
 613         {
 614                 Node* result = fAllocator.Allocate();
 615                 if (result)
 616                         fAllocator.Construct(result, key, value);
 617                 return result;
 618         }
 619
 620         inline void Free(Node* node)
 621         {
 622                 fAllocator.Destruct(node);
 623                 fAllocator.Deallocate(node);
 624         }
 625
 626         inline const Key& GetKey(const Node* node) const
 627         {
 628                 return node->key;
 629         }
 630
 631         inline Value& GetValue(Node* node) const
 632         {
 633                 return node->value;
 634         }
 635
 636         inline AVLTreeNode* GetAVLTreeNode(Node* node) const
 637         {
 638                 return node;
 639         }
 640
 641         inline Node* GetNode(AVLTreeNode* node) const
 642         {
 643                 return static_cast<Node*>(node);
 644         }
 645
 646         inline int CompareKeyNode(const Key& a, const Node* b) const
 647         {
 648                 return fCompare(a, GetKey(b));
 649         }
 650
 651         inline int CompareNodes(const Node* a, const Node* b) const
 652         {
 653                 return fCompare(GetKey(a), GetKey(b));
 654         }
 655
 656 private:
 657         KeyOrder                fCompare;
 658         Allocator<Node> fAllocator;
 659 };
 660 }
 661
 662 #endif  // _KERNEL_UTIL_AVL_TREE_MAP_H