## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# csutil/redblacktree.h

Go to the documentation of this file.

    00001 /*
    00002     Copyright (C) 2005 by Jorrit Tyberghein
    00003               (C) 2005 by Frank Richter
    00004
    00005     This library is free software; you can redistribute it and/or
    00006     modify it under the terms of the GNU Library General Public
    00007     License as published by the Free Software Foundation; either
    00008     version 2 of the License, or (at your option) any later version.
    00009
    00010     This library is distributed in the hope that it will be useful,
    00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
    00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00013     Library General Public License for more details.
    00014
    00015     You should have received a copy of the GNU Library General Public
    00016     License along with this library; if not, write to the Free
    00017     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
    00018 */
    00019
    00020 #ifndef __CS_UTIL_REDBLACKTREE_H__
    00021 #define __CS_UTIL_REDBLACKTREE_H__
    00022
    00023 #include "csutil/blockallocator.h"
    00024 #include "csutil/comparator.h"
    00025
    00040 template <typename K>
    00041 class csRedBlackTree
    00042 {
    00043 protected:
    00044   enum NodeColor { Black = 0, Red = 1 };
    00046   struct Node
    00047   {
    00048   private:
    00050     Node* parent;
    00051   public:
    00052     Node* left;
    00053     Node* right;
    00054     uint8 key[sizeof(K)];
    00055
    00056     Node() : parent(0) {}
    00057     ~Node() { ((K*)&key)->~K(); }
    00058     inline Node* GetParent() const
    00059     { return (Node*)((uintptr_t)parent & (uintptr_t)~1); }
    00060     void SetParent(Node* p)
    00061     { parent = (Node*)(((uintptr_t)p & (uintptr_t)~1) | (uint)GetColor()); }
    00062     NodeColor GetColor() const
    00063     { // Expression split over two statements to pacify some broken gcc's which
    00064       // barf saying "can't convert Node* to NodeColor".
    00065       uintptr_t const v = ((uintptr_t)parent & 1);
    00066       return (NodeColor)v;
    00067     }
    00068     void SetColor (NodeColor color)
    00069     { parent = (Node*)(((uintptr_t)parent & (uintptr_t)~1) | (uint)color); }
    00070   };
    00071   csBlockAllocator<Node, csBlockAllocatorAlignPolicy<2> > nodeAlloc;
    00072
    00073   Node* root;
    00074
    00076   Node* RecursiveInsert (Node* parent, Node*& node, const K& key)
    00077   {
    00078     if (node == 0)
    00079     {
    00080       node = nodeAlloc.Alloc();
    00081       node->SetParent (parent);
    00082       node->left = node->right = 0;
    00083       new ((K*)&node->key) K (key);
    00084       node->SetColor (Red);
    00085       return node;
    00086     }
    00087     else
    00088     {
    00089       int r = csComparator<K, K>::Compare (key, *((K*)&node->key));
    00090       if (r == 0)
    00091         return 0;
    00092       else if (r < 0)
    00093         return RecursiveInsert (node, node->left, key);
    00094       else
    00095         return RecursiveInsert (node, node->right, key);
    00096     }
    00097   }
    00099   void RotateLeft (Node* pivot)
    00100   {
    00101     Node* pivotReplace = pivot->right;
    00102     pivot->right = pivotReplace->left;
    00103     if (pivotReplace->left != 0) pivotReplace->left->SetParent (pivot);
    00104     pivotReplace->SetParent (pivot->GetParent());
    00105     if (pivot->GetParent() == 0)
    00106       root = pivotReplace;
    00107     else
    00108     {
    00109       if (pivot == pivot->GetParent()->left)
    00110         pivot->GetParent()->left = pivotReplace;
    00111       else
    00112         pivot->GetParent()->right = pivotReplace;
    00113     }
    00114     pivotReplace->left = pivot;
    00115     pivot->SetParent (pivotReplace);
    00116   }
    00118   void RotateRight (Node* pivot)
    00119   {
    00120     Node* pivotReplace = pivot->left;
    00121     pivot->left = pivotReplace->right;
    00122     pivotReplace->right->SetParent (pivot);
    00123     pivotReplace->SetParent (pivot->GetParent());
    00124     if (pivot->GetParent() == 0)
    00125       root = pivotReplace;
    00126     else
    00127     {
    00128       if (pivot == pivot->GetParent()->left)
    00129         pivot->GetParent()->left = pivotReplace;
    00130       else
    00131         pivot->GetParent()->right = pivotReplace;
    00132     }
    00133     pivotReplace->right = pivot;
    00134     pivot->SetParent (pivotReplace);
    00135   }
    00137   bool IsBlack (Node* node) const
    00138   { return (node == 0) || (node->GetColor() == Black); }
    00140   bool IsRed (Node* node) const
    00141   { return (node != 0) && (node->GetColor() == Red); }
    00143   void InsertFixup (Node* node)
    00144   {
    00145     Node* p;
    00146     while (((p = node->GetParent()) != 0) && IsRed (p))
    00147     {
    00148       Node* pp = p->GetParent();
    00149       if (pp == 0) break;
    00150       if (p == pp->left)
    00151       {
    00152         Node* y = pp->right;
    00153         if (IsRed (y))
    00154         {
    00155           // Uncle of 'node' is red
    00156           p->SetColor (Black);
    00157           y->SetColor (Black);
    00158           pp->SetColor (Red);
    00159           node = pp;
    00160         }
    00161         else
    00162         {
    00163           if (node == p->right)
    00164           {
    00165             // Uncle of 'node' is black, node is right child
    00166             node = p;
    00167             RotateLeft (node);
    00168           }
    00169           // Uncle of 'node' is black, node is left child
    00170           p->SetColor (Black);
    00171           pp->SetColor (Red);
    00172           RotateRight (pp);
    00173         }
    00174       }
    00175       else
    00176       {
    00177         Node* y = pp->left;
    00178         if (IsRed (y))
    00179         {
    00180           // Uncle of 'node' is red
    00181           p->SetColor (Black);
    00182           y->SetColor (Black);
    00183           pp->SetColor (Red);
    00184           node = pp;
    00185         }
    00186         else
    00187         {
    00188           if (node == p->left)
    00189           {
    00190             // Uncle of 'node' is black, node is left child
    00191             node = p;
    00192             RotateRight (node);
    00193           }
    00194           // Uncle of 'node' is black, node is right child
    00195           p->SetColor (Black);
    00196           pp->SetColor (Red);
    00197           RotateLeft (pp);
    00198         }
    00199       }
    00200     }
    00201     root->SetColor (Black);
    00202   }
    00204   void DeleteNode (Node* node)
    00205   {
    00206     Node* y; // Node we will replace 'node' with
    00207     if ((node->left == 0) || (node->right == 0))
    00208       y = node;
    00209     else
    00210       y = Successor (node);
    00211     Node* x;
    00212     if (y->left != 0)
    00213       x = y->left;
    00214     else
    00215       x = y->right;
    00216     if (x != 0) x->SetParent (y->GetParent());
    00217     if (y->GetParent() == 0)
    00218       root = x;
    00219     else
    00220     {
    00221       if (y == y->GetParent()->left)
    00222         y->GetParent()->left = x;
    00223       else
    00224         y->GetParent()->right = x;
    00225     }
    00226     if (y != node)
    00227     {
    00228       // Copy key
    00229       ((K*)&node->key)->~K();
    00230       new ((K*)&node->key) K (*((K*)&y->key));
    00231     }
    00232     if (y->GetColor() == Black)
    00233       DeleteFixup (node);
    00234     nodeAlloc.Free (y);
    00235   }
    00237   void DeleteFixup (Node* node)
    00238   {
    00239     while ((node != root) && IsBlack (node))
    00240     {
    00241       Node* p = node->GetParent();
    00242       if (node == p->left)
    00243       {
    00244         Node* w = p->right;
    00245         if (IsRed (w))
    00246         {
    00247           w->SetColor (Black);
    00248           p->SetColor (Red);
    00249           RotateLeft (p);
    00250           w = p->right;
    00251         }
    00252         if (IsBlack (w->left) && IsBlack (w->right))
    00253         {
    00254           w->SetColor (Red);
    00255           node = p;
    00256         }
    00257         else
    00258         {
    00259           if (IsBlack (w->right))
    00260           {
    00261             w->left->SetColor (Red);
    00262             w->SetColor (Red);
    00263             RotateRight (w);
    00264             w = p->right;
    00265           }
    00266           w->SetColor (p->GetColor ());
    00267           p->SetColor (Black);
    00268           w->right->SetColor (Black);
    00269           RotateLeft (p);
    00270           node = root;
    00271         }
    00272       }
    00273       else
    00274       {
    00275         Node* w = p->left;
    00276         if (IsRed (w))
    00277         {
    00278           w->SetColor (Black);
    00279           p->SetColor (Red);
    00280           RotateRight (p);
    00281           w = p->left;
    00282         }
    00283         if (IsBlack (w->left) && IsBlack (w->right))
    00284         {
    00285           w->SetColor (Red);
    00286           node = p;
    00287         }
    00288         else
    00289         {
    00290           if (IsBlack (w->left))
    00291           {
    00292             w->right->SetColor (Red);
    00293             w->SetColor (Red);
    00294             RotateLeft (w);
    00295             w = p->left;
    00296           }
    00297           w->SetColor (p->GetColor ());
    00298           p->SetColor (Black);
    00299           w->left->SetColor (Black);
    00300           RotateRight (p);
    00301           node = root;
    00302         }
    00303       }
    00304     }
    00305     node->SetColor (Black);
    00306   }
    00308   Node* LocateNode (Node* node, const K& key) const
    00309   {
    00310     if (node == 0) return 0;
    00311
    00312     int r = csComparator<K, K>::Compare (key, node->key);
    00313     if (r == 0)
    00314       return node;
    00315     else if (r < 0)
    00316       return LocateNode (node->left, key);
    00317     else
    00318       return LocateNode (node->right, key);
    00319   }
    00321   Node* Successor (Node* node) const
    00322   {
    00323     Node* succ;
    00324     if (node->right != 0)
    00325     {
    00326       succ = node->right;
    00327       while (succ->left != 0) succ = succ->left;
    00328       return succ;
    00329     }
    00330     Node* y = node->GetParent();
    00331     while ((y != 0) && (node == y->right))
    00332     {
    00333       node = y;
    00334       y = y->GetParent();
    00335     }
    00336     return y;
    00337   }
    00339
    00340   template<typename K2>
    00341   const K* RecursiveFind (Node* node, const K2& other) const
    00342   {
    00343     if (node == 0) return 0;
    00344     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
    00345     if (r == 0)
    00346       return ((K*)&node->key);
    00347     else if (r < 0)
    00348       return RecursiveFind (node->left, other);
    00349     else
    00350       return RecursiveFind (node->right, other);
    00351   }
    00352   template<typename K2>
    00353   K* RecursiveFind (Node* node, const K2& other)
    00354   {
    00355     if (node == 0) return 0;
    00356     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
    00357     if (r == 0)
    00358       return ((K*)&node->key);
    00359     else if (r < 0)
    00360       return RecursiveFind (node->left, other);
    00361     else
    00362       return RecursiveFind (node->right, other);
    00363   }
    00364   template<typename K2>
    00365   const K& RecursiveFind (Node* node, const K2& other, const K& fallback) const
    00366   {
    00367     if (node == 0) return fallback;
    00368     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
    00369     if (r == 0)
    00370       return *((K*)&node->key);
    00371     else if (r < 0)
    00372       return RecursiveFind (node->left, other);
    00373     else
    00374       return RecursiveFind (node->right, other);
    00375   }
    00376   template<typename K2>
    00377   K& RecursiveFind (Node* node, const K2& other, K& fallback)
    00378   {
    00379     if (node == 0) return fallback;
    00380     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
    00381     if (r == 0)
    00382       return *((K*)&node->key);
    00383     else if (r < 0)
    00384       return RecursiveFind (node->left, other);
    00385     else
    00386       return RecursiveFind (node->right, other);
    00387   }
    00389
    00390   template <typename CB>
    00391   void RecursiveTraverseInOrder (Node* node, CB& callback) const
    00392   {
    00393     if (node->left != 0) RecursiveTraverseInOrder (node->left, callback);
    00394     callback.Process (*((K*)&node->key));
    00395     if (node->right != 0) RecursiveTraverseInOrder (node->right, callback);
    00396   }
    00397
    00399
    00400   template<typename K2>
    00401   K* Find (const K2& other)
    00402   {
    00403     return RecursiveFind (root, other);
    00404   }
    00405   template<typename K2>
    00406   K& Find (const K2& other, K& fallback)
    00407   {
    00408     return RecursiveFind (root, other, fallback);
    00409   }
    00411
    00413   void RecursiveCopy (Node*& to, Node* parent, const Node* from)
    00414   {
    00415     if (from == 0)
    00416     {
    00417       to = 0;
    00418       return;
    00419     }
    00420     to = nodeAlloc.Alloc();
    00421     to->SetParent (parent);
    00422     to->SetColor (from->GetColor());
    00423     new ((K*)&to->key) K (*((K*)&from->key));
    00424     RecursiveCopy (to->left, to, from->left);
    00425     RecursiveCopy (to->right, to, from->right);
    00426   }
    00427 public:
    00433   csRedBlackTree (size_t allocatorBlockSize = 4096) :
    00434     nodeAlloc (allocatorBlockSize / sizeof(Node)), root(0) { }
    00435   csRedBlackTree (const csRedBlackTree& other) :
    00436     nodeAlloc (other.nodeAlloc.GetBlockElements())
    00437   {
    00438     RecursiveCopy (root, 0, other.root);
    00439   }
    00440
    00446   const K* Insert (const K& key)
    00447   {
    00448     Node* n = RecursiveInsert (0, root, key);
    00449     if (n == 0) return 0;
    00450     InsertFixup (n);
    00451     return (K*)&n->key;
    00452   }
    00458   bool Delete (const K& key)
    00459   {
    00460     Node* n = LocateNode (root, key);
    00461     if (n == 0) return false;
    00462     DeleteNode (n);
    00463     return true;
    00464   }
    00466   bool In (const K& key) const
    00467   {
    00468     return (LocateNode (root, key) != 0);
    00469   }
    00475   bool Contains (const K& key) const { return In (key); }
    00476
    00478
    00479   template<typename K2>
    00480   const K* Find (const K2& other) const
    00481   {
    00482     return RecursiveFind (root, other);
    00483   }
    00484   template<typename K2>
    00485   const K& Find (const K2& other, const K& fallback) const
    00486   {
    00487     return RecursiveFind (root, other, fallback);
    00488   }
    00490
    00492   void DeleteAll()
    00493   {
    00494     nodeAlloc.Empty();
    00495     root = 0;
    00496   }
    00498   void Empty() { DeleteAll(); }
    00500   bool IsEmpty() const { return (root == 0); }
    00501
    00503
    00504   template <typename CB>
    00505   void TraverseInOrder (CB& callback) const
    00506   {
    00507     if (root != 0) RecursiveTraverseInOrder (root, callback);
    00508   }
    00510 };
    00511
    00516 template <typename K, typename T>
    00517 class csRedBlackTreePayload
    00518 {
    00519   K key;
    00520   T value;
    00521 public:
    00522   csRedBlackTreePayload (const K& k, const T& v) : key(k), value(v) {}
    00523   csRedBlackTreePayload (const csRedBlackTreePayload& other) :
    00524     key(other.key), value(other.value) {}
    00525
    00526   const K& GetKey() const { return key; }
    00527   const T& GetValue() const { return value; }
    00528   T& GetValue() { return value; }
    00529   bool operator < (const csRedBlackTreePayload& other) const
    00530   {
    00531     return (csComparator<K, K>::Compare (key, other.key) < 0);
    00532   }
    00533   bool operator < (const K& other) const
    00534   {
    00535     return (csComparator<K, K>::Compare (key, other) < 0);
    00536   }
    00537   friend bool operator < (const K& k1, const csRedBlackTreePayload& k2)
    00538   {
    00539     return (csComparator<K, K>::Compare (k1, k2.key) < 0);
    00540   }
    00541   operator const T&() const { return value; }
    00542   operator T&() { return value; }
    00543 };
    00544
    00549 template <typename K, typename T>
    00550 class csRedBlackTreeMap : protected csRedBlackTree<csRedBlackTreePayload<K, T> >
    00551 {
    00552   typedef csRedBlackTree<csRedBlackTreePayload<K, T> > supahclass;
    00553
    00554   template<typename CB>
    00555   class TraverseCB
    00556   {
    00557     CB callback;
    00558   public:
    00559     TraverseCB (const CB& callback) : callback(callback) {}
    00560     void Process (csRedBlackTreePayload<K, T>& value)
    00561     {
    00562       callback.Process (value.GetKey(), value.GetValue());
    00563     }
    00564   };
    00565 public:
    00571   T* Put (const K& key, const T &value)
    00572   {
    00573     csRedBlackTreePayload<K, T>* payload = (csRedBlackTreePayload<K, T>*)
    00574       Insert (csRedBlackTreePayload<K, T>(key, value));
    00575     return (payload != 0) ? &payload->GetValue() :  0;
    00576   }
    00582   bool Delete (const K& key)
    00583   {
    00584     csRedBlackTreePayload<K, T>* payload = Find (key);
    00585     if (payload == 0) return false;
    00586     return supahclass::Delete (*payload);
    00587   }
    00589
    00593   const T* GetElementPointer (const K& key) const
    00594   {
    00595     csRedBlackTreePayload<K, T>* payload = Find (key);
    00596     if (payload == 0) return 0;
    00597     return &payload->GetValue();
    00598   }
    00599   T* GetElementPointer (const K& key)
    00600   {
    00601     csRedBlackTreePayload<K, T>* payload = Find (key);
    00602     if (payload == 0) return 0;
    00603     return &payload->GetValue();
    00604   }
    00606
    00608
    00611   const T& Get (const K& key, const T& fallback) const
    00612   {
    00613     csRedBlackTreePayload<K, T>* payload = Find (key);
    00614     if (payload == 0) return fallback;
    00615     return payload->GetValue();
    00616   }
    00617   T& Get (const K& key, T& fallback)
    00618   {
    00619     csRedBlackTreePayload<K, T>* payload = Find (key);
    00620     if (payload == 0) return fallback;
    00621     return payload->GetValue();
    00622   }
    00624
    00625   void DeleteAll() { supahclass::Empty(); }
    00627   void Empty() { DeleteAll(); }
    00629   bool IsEmpty() const { return supahclass::IsEmpty(); }
    00630
    00632
    00633   template <typename CB>
    00634   void TraverseInOrder (CB& callback) const
    00635   {
    00636     TraverseCB<CB> traverser (callback);
    00637     supahclass::TraverseInOrder (traverser);
    00638   }
    00640 };
    00641
    00644 #endif // __CS_UTIL_REDBLACKTREE_H__