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
Count()62 inline int Count() const { return fTree.Count(); }
IsEmpty()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
GetNodeStrategy()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:
Iterator()120 inline Iterator()
121 : ConstIterator()
122 {
123 }
124
Iterator(const Iterator & other)125 inline Iterator(const Iterator& other)
126 : ConstIterator(other)
127 {
128 }
129
Remove()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:
Iterator(_AVL_TREE_MAP_CLASS_NAME * parent,const AVLTreeIterator & treeIterator)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:
ConstIterator()156 inline ConstIterator()
157 : fParent(NULL),
158 fTreeIterator()
159 {
160 }
161
ConstIterator(const ConstIterator & other)162 inline ConstIterator(const ConstIterator& other)
163 : fParent(other.fParent),
164 fTreeIterator(other.fTreeIterator)
165 {
166 }
167
HasCurrent()168 inline bool HasCurrent() const
169 {
170 return fTreeIterator.Current();
171 }
172
CurrentKey()173 inline Key CurrentKey()
174 {
175 if (AVLTreeNode* node = fTreeIterator.Current())
176 return fParent->_GetKey(fParent->_GetNode(node));
177 return Key();
178 }
179
Current()180 inline Value Current()
181 {
182 if (AVLTreeNode* node = fTreeIterator.Current())
183 return fParent->_GetValue(fParent->_GetNode(node));
184 return Value();
185 }
186
CurrentValuePointer()187 inline Value* CurrentValuePointer()
188 {
189 if (AVLTreeNode* node = fTreeIterator.Current())
190 return &fParent->_GetValue(fParent->_GetNode(node));
191 return NULL;
192 }
193
CurrentNode()194 inline Node* CurrentNode()
195 {
196 if (AVLTreeNode* node = fTreeIterator.Current())
197 return fParent->_GetNode(node);
198 return NULL;
199 }
200
HasNext()201 inline bool HasNext() const
202 {
203 return fTreeIterator.HasNext();
204 }
205
Next()206 inline Value Next()
207 {
208 if (AVLTreeNode* node = fTreeIterator.Next())
209 return fParent->_GetValue(fParent->_GetNode(node));
210 return Value();
211 }
212
NextValuePointer()213 inline Value* NextValuePointer()
214 {
215 if (AVLTreeNode* node = fTreeIterator.Next())
216 return &fParent->_GetValue(fParent->_GetNode(node));
217 return NULL;
218 }
219
Previous()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:
ConstIterator(const _AVL_TREE_MAP_CLASS_NAME * parent,const AVLTreeIterator & treeIterator)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
AVLTreeMap(const NodeStrategy & strategy)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
~AVLTreeMap()260 _AVL_TREE_MAP_CLASS_NAME::~AVLTreeMap()
261 {
262 }
263
264
265 // MakeEmpty
266 _AVL_TREE_MAP_TEMPLATE_LIST
267 inline void
MakeEmpty()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*
RootNode()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*
Previous(Node * 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*
Next(Node * 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
GetIterator()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
GetIterator()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
GetIterator(Node * node)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
GetIterator(Node * node)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
Find(const Key & key)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
FindClose(const Key & key,bool less)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
Insert(const Key & key,const Value & value,Iterator * iterator)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
Insert(const Key & key,const Value & value,Node ** _node)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
Remove(const Key & key)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
Remove(Node * node)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
CompareKeyNode(const void * key,const AVLTreeNode * node)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
CompareNodes(const AVLTreeNode * node1,const AVLTreeNode * node2)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*
_Allocate(const Key & key,const Value & value)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
_Free(Node * node)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
_GetKey(Node * node)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&
_GetValue(Node * node)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*
_GetAVLTreeNode(const Node * node)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*
_GetNode(const AVLTreeNode * 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
_CompareKeyNode(const Key & a,const Node * b)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
_CompareNodes(const Node * a,const Node * b)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
_FreeTree(AVLTreeNode * node)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:
operator()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:
operator()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 {
NodeNode601 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
Allocate(const Key & key,const Value & value)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
Free(Node * node)620 inline void Free(Node* node)
621 {
622 fAllocator.Destruct(node);
623 fAllocator.Deallocate(node);
624 }
625
GetKey(const Node * node)626 inline const Key& GetKey(const Node* node) const
627 {
628 return node->key;
629 }
630
GetValue(Node * node)631 inline Value& GetValue(Node* node) const
632 {
633 return node->value;
634 }
635
GetAVLTreeNode(Node * node)636 inline AVLTreeNode* GetAVLTreeNode(Node* node) const
637 {
638 return node;
639 }
640
GetNode(AVLTreeNode * node)641 inline Node* GetNode(AVLTreeNode* node) const
642 {
643 return static_cast<Node*>(node);
644 }
645
CompareKeyNode(const Key & a,const Node * b)646 inline int CompareKeyNode(const Key& a, const Node* b) const
647 {
648 return fCompare(a, GetKey(b));
649 }
650
CompareNodes(const Node * a,const Node * b)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
663