panaLiX: Plik źródłowy src/collection/avltree.hpp

00001 /*
00002  panaLiX, Adrian Panasiuk 2002-5,8
00003  http://panalix.sourceforge.net/
00004  ad.ek336@gmail.com
00005  
00006  small osdev project
00007  provided under GPLv3 license.
00008  */
00009 
00010 
00011 #ifndef __PANALIX_AVLTREE_HPP
00012 #define __PANALIX_AVLTREE_HPP
00013 
00014 #include "src/collection/collection.hpp"
00015 #include "src/collection/option.hpp"
00016 #include "src/ipc/lock.hpp"
00017 
00018 
00019 namespace Collection {
00020 
00021    template <typename T>
00022    int generic_cmp(T a, T b) {
00023       if (a>b) return 1;
00024       if (a<b) return -1;
00025       return 0;
00026    }
00027 
00028    template <typename T>
00029    int pointer_cmp(T *a, T *b) {
00030       return generic_cmp<uint32>( reinterpret_cast<uint32>(a), reinterpret_cast<uint32>(b) );
00031    }
00032 
00033 
00034 //stary kod/*{{{*/
00035 #if 0
00036 
00037    template <typename T, int (*cmp)(T, T)>
00038    class AvlTree {
00039       private:
00040       // wezel
00041          struct AvlNode {
00042             public:
00043                void write() {
00044                   kprintf("(");
00045                   if (left.isNone())
00046                      kprintf("-");
00047                   else
00048                      left.get()->write();
00049 
00050                   kprintf(",");
00051                   
00052                   kprintf("%d", v);
00053 
00054                   kprintf(",");
00055 
00056                   if (right.isNone())
00057                      kprintf("-");
00058                   else
00059                      right.get()->write();
00060 
00061                   kprintf(",%d)", ht);
00062                }
00063                AvlNode (struct Option<struct AvlNode*> left, T v, struct Option<struct AvlNode*> right, uint32 ht ) {
00064                   this->left=left;
00065                   this->right=right;
00066                   this->v=v;
00067                   this->ht=ht;
00068                }
00069 
00070                void  * operator new (size_t s) {
00071                   return static_cast<struct AvlNode*> ( kmalloc(s , "avlnode") );
00072                }
00073 
00074                void operator delete ( void * x ) {
00075                   kfree(x);
00076                }
00077                
00078                struct Option<struct AvlNode*> left, right;
00079                T v;
00080                uint32 ht;
00081 
00082                uint32 getHt(struct Option<struct AvlNode*> x) {
00083                   if (x.isNone())
00084                      return 0;
00085                   return x.get()->ht;
00086                }
00087 
00088                void rotleft() {
00089                   if (right.isNone())
00090                      sysfail("rotleft while right is leaf");
00091 
00092                   struct AvlNode* old_r = right.get();
00093                   T old_v = v;
00094                   struct Option<struct AvlNode*> old_l = left;
00095                   right= old_r->right;
00096                   //^ prawe poddrzewo w ostatecznej formie...
00097                   v = old_r->v;
00098                   left.set(old_r);
00099                   //^ wezel w ostatecznej formie
00100                   left.get()->right = old_r->left;
00101                   left.get()->v = old_v;
00102                   left.get()->left=old_l;
00103                   //^ lewe poddrzewo w ostatecznej formie...
00104                   if (!left.isNone())
00105                      left.get()->ht=1+MAX(getHt(left.get()->left), getHt(left.get()->right));
00106                   if (!right.isNone())
00107                      right.get()->ht=1+MAX(getHt(right.get()->left), getHt(right.get()->right));
00108                   ht=1+MAX(getHt(left), getHt(right));
00109                }
00110 
00111                void rotright() {
00112                   if (left.isNone())
00113                      sysfail("rotright while left is leaf");
00114 
00115                   struct AvlNode* old_l = left.get();
00116                   T old_v = v;
00117                   struct Option<struct AvlNode*> old_r = right;
00118                   left= old_l->left;
00119                   //^ prawe poddrzewo w ostatecznej formie...
00120                   v = old_l->v;
00121                   right.set(old_l);
00122                   //^ wezel w ostatecznej formie
00123                   right.get()->left = old_l->right;
00124                   right.get()->v = old_v;
00125                   right.get()->right=old_r;
00126                   //^ lewe poddrzewo w ostatecznej formie...
00127                   if (!left.isNone())
00128                      left.get()->ht=1+MAX(getHt(left.get()->left), getHt(left.get()->right));
00129                   if (!right.isNone())
00130                      right.get()->ht=1+MAX(getHt(right.get()->left), getHt(right.get()->right));
00131                   ht=1+MAX(getHt(left), getHt(right));
00132                }
00133 
00134                void checkHt() {
00135                   if (!left.isNone())
00136                      left.get()->checkHt();
00137                   if (!right.isNone())
00138                      right.get()->checkHt();
00139                   if (ht!=1+MAX(getHt(left),getHt(right)) || getHt(left) > getHt(right) + 1 || getHt(right) > getHt(left) + 1) {
00140                      kprintf("checkHt: ");
00141                      write();
00142                      kprintf("\n");
00143                    }
00144                }
00145 
00146                bool insert(T v) {
00147                   sint32 c = cmp(this->v,v);
00148                   if (c==0) {
00149                      this->v=v;
00150                      return true;
00151                   }
00152                   if (c > 0) {
00153                      if (left.isNone()) {
00154                            left.set(new AvlNode(Option<struct AvlNode*>(), v, Option<struct AvlNode*>(),1));
00155                            ht++;
00156                            return false;
00157                         }
00158                      left.get()->insert(v);
00159                      if (getHt(left) > getHt(right)+1) {
00160                         if (getHt(left.get()->left) >= getHt(left.get()->right))
00161                            rotright();
00162                         else {
00163                            left.get()->rotleft();
00164                            rotright();
00165                         }
00166                      }
00167                      ht=1+MAX(getHt(left), getHt(right));
00168                      return 0;
00169                   }
00170                   if (c < 0) {
00171                      if (right.isNone()) {
00172                            right.set(new AvlNode(Option<struct AvlNode*>(), v, Option<struct AvlNode*>(),1));
00173                            ht++;
00174                            return false;
00175                         }
00176                     right.get()->insert(v);
00177                     if (getHt(right) > getHt(left)+1) {
00178                         if (getHt(right.get()->right) > getHt(right.get()->left))
00179                            rotleft();
00180                         else {
00181                            right.get()->rotright();
00182                            rotleft();
00183                         }
00184                      }
00185                     ht=1+MAX(getHt(left), getHt(right));
00186                     return 0;
00187                   }
00188                   return false;
00189               }
00190 
00191               T removeMin() {
00192                struct AvlNode* l = left.get();
00193                T ret;
00194                   if (l->left.isNone()) {
00195                      left = l->right;
00196                      ret = l->v;
00197                      delete l;
00198                      ht=1+MAX(getHt(left),getHt(right));
00199                      return ret;
00200                   }
00201                   ret= l->removeMin();
00202                   ht=1+MAX(getHt(left),getHt(right));
00203                   return ret;
00204               }
00205 
00206               bool remove(T v) {
00207                  sint32 c = cmp(this->v, v);
00208                  if (c == 0) {
00209                      if (right.isNone()) {
00210                         struct AvlNode *l= left.get();
00211                            this->v= l->v;
00212                            right= l->right;
00213                            left= l->left;
00214                            delete l;
00215                      } else {
00216                         if (right.get()->left.isNone()) {
00217                            struct AvlNode *r;
00218                               r=right.get();
00219                               this->v = r->v;
00220                               right=r->right;
00221                               delete r;
00222                         } else this->v= right.get()->removeMin();
00223                      }
00224                      ht=1+MAX(getHt(left),getHt(right));
00225                      return true;
00226                  }
00227                 if (c < 0) {
00228                   if (right.isNone())
00229                      return false;
00230                   if (cmp(right.get()->v,v)==0 && right.get()->right.isNone() && right.get()->left.isNone()) {
00231                      delete right.get();
00232                      right.setNone();
00233                      return true;
00234                   }
00235                   bool ret = right.get()->remove(v);
00236                   ht=1+MAX(getHt(left),getHt(right));
00237                   return ret;
00238                 }
00239                 if (c>0) {
00240                   if (left.isNone()) 
00241                      return false;
00242                   if (cmp(left.get()->v,v)==0 && left.get()->right.isNone() && left.get()->left.isNone()) {
00243                      delete left.get();
00244                      left.setNone();
00245                      return true;
00246                   }
00247                   bool ret = left.get()->remove(v);
00248                   ht=1+MAX(getHt(left), getHt(right));
00249                   return ret;
00250               }
00251            return false;
00252            }
00253         }; /* struct AvlNode */
00254 
00255          struct Option<struct AvlNode*> nd;
00256          struct IPC::Lock::lock_t lock;
00257          
00258       public:
00259          void * operator new(size_t s) {
00260             return kmalloc(s, "avltree");
00261          }
00262          AvlTree() : lock(const_cast<char*>("avltree")) {
00263             nd.setNone();
00264 #if 0
00265 #if 0
00266             nd.set(
00267                new AvlNode(
00268                   *new Option<struct AvlNode*> (
00269                      new AvlNode(
00270                         *new struct Option<struct AvlNode*>,
00271                         15,
00272                         *new struct Option<struct AvlNode*>,
00273                         1)
00274                   ),
00275                   10,
00276                   *new Option<struct AvlNode*>(
00277                      new AvlNode(
00278                         *new struct Option<struct AvlNode*>,
00279                         20,
00280                         *new struct Option<struct AvlNode*>,
00281                         1)
00282                      ),
00283                   2)
00284                 );
00285 #endif
00286 
00287             write();
00288             insert(40);
00289             insert(50);
00290             insert(30);
00291             insert(35);
00292             insert(25);
00293             insert(27);
00294             insert(37);
00295             insert(47);
00296             write();
00297             remove(400);
00298             remove(35);
00299             remove(28);
00300             remove(40);
00301             remove(47);
00302             remove(25);
00303             write();
00304 //            nd.get()->rotleft();
00305 //            nd.get()->rotright();
00306             checkHt();
00307 #endif
00308          }
00309 
00310          ~AvlTree() {
00311             if (isEmpty()) {
00312             } else {
00313                debug_dump_call_trace();
00314                notimpl();
00315             }
00316          }
00317 
00318          bool insert(T v) {
00319             lock.lock();
00320             if (nd.isNone()) {
00321                nd.set(new AvlNode(Option<struct AvlNode*>(), v, Option<struct AvlNode*>(),1));
00322                lock.ulock();
00323                return false;
00324             }
00325             bool ret = nd.get()->insert(v);
00326             lock.ulock();
00327             return ret;
00328          }
00329 
00330          bool remove(T v) {
00331             lock.lock();
00332             if (nd.isNone()) {
00333                 lock.ulock();
00334                 return false;
00335             }
00336             if (cmp(v, nd.get()->v) == 0 && nd.get()->left.isNone() && nd.get()->right.isNone()) {
00337                delete nd.get();
00338                nd.setNone();
00339                lock.ulock();
00340                return true;
00341             }
00342             bool ret = nd.get()->remove(v);
00343             lock.ulock();
00344             return ret;
00345          }
00346 
00347          Option<T> findpom(struct AvlNode *it, T v) {
00348             sint32 c = cmp(it->v, v);
00349             if (c == 0)
00350                return it->v;
00351             if (c > 0) {
00352                if (it->left.isNone())
00353                   return Option<T>();
00354                else
00355                   return findpom(it->left.get(), v);
00356             }
00357             if (it->right.isNone())
00358                return Option<T>();
00359             else
00360                return findpom(it->right.get(),v);
00361          }
00362 
00363          Option<T> find(T v) {
00364             lock.lock();
00365             if (nd.isNone()) {
00366                lock.ulock();
00367                return Option<T>();
00368             }
00369             class Option<T> ret= findpom(nd.get(), v);
00370             lock.ulock();
00371             return ret;
00372          }
00373 
00374          Option<T> findMin() {
00375             lock.lock();
00376             if (nd.isNone()) {
00377                lock.ulock();
00378                return Option<T>();
00379             }
00380             struct AvlNode *it;
00381             for (it= nd.get();
00382                   !it->left.isNone();
00383                   it= it->left.get())
00384                ;
00385             class Option<T> ret = it->v;
00386             lock.ulock();
00387             return ret;
00388          }
00389 
00390          bool isEmpty() {
00391             lock.lock();
00392             bool ret = nd.isNone();
00393             lock.ulock();
00394             return ret;
00395          }
00396 
00397          void write() { lock.lock(); if (nd.isNone()) { kprintf("-\n"); lock.ulock(); return ;} nd.get()->write();kprintf("\n"); lock.ulock(); }
00398          void checkHt() { lock.lock(); if (!nd.isNone()) nd.get()->checkHt(); lock.ulock(); }
00399 
00400    };
00401 #endif/*}}}*/
00402       template<typename T,int (*cmp)(T,T)>
00403       struct AvlTree {
00404 
00405          struct AvlNode {
00406             struct AvlNode *l, *r;
00407             T key;
00408             uint32 ht;
00409          };
00410 
00411          struct AvlNode *nd;
00412 
00413          AvlTree () : nd(null) { }
00414 
00415          void  * operator new (size_t s) {
00416             return static_cast<struct AvlNode*> ( Collection::Mem::kmalloc(s , const_cast<char*>("avlnode")) );
00417          }
00418 
00419          void operator delete ( void * x ) {
00421             notimpl();
00422             Collection::Mem::kfree(x);
00423          }
00424 
00425          void rotleft(struct AvlNode *&av) {
00426             testif(av!=null); 
00427             testif(av->r != null);
00428       
00429             struct AvlNode *v;
00430 
00431             v= av->r;
00432             av->r = v->l;
00433             v->l = av;
00434 
00435             av= v;
00436 
00437             setHeight(av->l);
00438             setHeight(av);
00439          }
00440 
00441          void rotright(struct AvlNode *&av) {
00442             testif(av!=null);
00443             testif(av->l!=null);
00444 
00445             struct AvlNode *v;
00446 
00447             v=av->l;
00448             av->l = av->l->r;
00449             v->r = av;
00450 
00451             av= v;
00452 
00453             setHeight(av->r);
00454             setHeight(av);
00455          }
00456 
00457          void setHeight(struct AvlNode *&av) {
00458             uint32 ht=0;
00459             testif(av!=null);
00460             if (av->l)
00461                ht=av->l->ht;
00462             if (av->r)
00463                ht=MAX(ht,av->r->ht);
00464             av->ht= 1+ht;
00465          }
00466 
00467          bool checkHt() { return checkHt(nd); }
00469          bool checkHt(struct AvlNode *&av) {
00470             if (av == null) return false;
00471             uint32 lh=0,rh=0;
00472             if (av->l)
00473                lh= av->l->ht;
00474             if (av->r)
00475                rh= av->r->ht;
00476 
00477             bool ret = checkHt(av->r) || checkHt(av->l);
00478             
00479             if (av->ht != 1+MAX(lh,rh) || lh > rh+1 || rh > lh+1) {
00480                kprintf("checkHt: ");
00481                write(av);
00482                kprintf("\n");
00483                return true;
00484             }
00485             return ret;
00486          }
00487 
00488          uint32 height(struct AvlNode *&av) {
00489             if (av==null)
00490                return 0;
00491             return av->ht;
00492          }
00493 
00494          void bal(struct AvlNode *&av) {
00495             uint32 hl=height(av->l);
00496             uint32 hr=height(av->r);
00497 
00498             if (hl > hr+1) {
00499                if (height(av->l->l) >= height(av->l->r))
00500                   rotright(av);
00501                else {
00502                   rotleft(av->l);
00503                   rotright(av);
00504                }
00505             }
00506             if (hr > hl+1) {
00507                if (height(av->r->r) >= height(av->r->l))
00508                   rotleft(av);
00509                else {
00510                   rotright(av->r);
00511                   rotleft(av);
00512                }
00513             }
00514          }
00515 
00516          bool insert(T v) {
00517             bool ret= insert(nd, v);
00518             return ret;
00519          }
00520 
00521          /* \return true iff an element equivalent to v was already in tree */
00522          bool insert(struct AvlNode *&av, T v) {
00523             if (av==null) {
00524                av= static_cast<struct AvlNode*>(Collection::Mem::kmalloc(sizeof(struct AvlNode),const_cast<char*>("avl node")));
00525                av->l=null;
00526                av->r=null;
00527                av->ht=1;
00528                av->key=v;
00529                return false;
00530             }
00531             int c= cmp(av->key,v);
00532             if (c==0) {
00533                av->key=v;
00534                return true;
00535             }
00536             if (c < 0) {
00537                bool ret=insert(av->r,v);
00538                setHeight(av);
00539                bal(av);
00540                return ret;
00541             }
00542             bool ret= insert(av->l,v);
00543             setHeight(av);
00544             bal(av);
00545 
00546             return ret;
00547          }
00548 
00549 #if 1
00550          T removeMin2(struct AvlNode *&av) {
00551             testif(av!=null);
00552             if (av->l==null) {
00553                T ret= av->key;
00554                struct AvlNode *v=av->r;
00555                //Collection::Mem::kfree(av);
00556                Collection::collection_heapbox.freeFunc2(av,0);
00557                av= v;
00558                return ret;
00559             } else {
00560                T ret = removeMin2(av->l);
00561                setHeight(av);
00562                return ret;
00563             }
00564          }
00565          bool remove2(T v) { return remove2(nd,v); }
00566          bool remove2(struct AvlNode *&av, T v) {
00567             if (av==null) return false;
00568             int c = cmp(av->key,v);
00569             if (c==0) {
00570                if (av->r==null) {
00571                   struct AvlNode *a=av;
00572                   av=av->l;
00573 //                  Collection::Mem::kfree(a);
00574                Collection::collection_heapbox.freeFunc2(a,0);
00575                   return true;
00576                 } else {
00577                   T a = removeMin2(av->r);
00578                   av->key=a;
00579                   setHeight(av);
00580                   bal(av);
00581                   return true;
00582                 }
00583             }
00584             bool ret;
00585             if (c < 0) {
00586                ret = remove2(av->r,v);
00587                setHeight(av);
00588                bal(av);
00589                return ret;
00590             } else {
00591                ret= remove2(av->l,v);
00592                setHeight(av);
00593                bal(av);
00594             }
00595             return ret;
00596          }
00597 #endif
00598 
00599          bool remove(T v) { return remove(nd,v); }
00600          bool remove(struct AvlNode *&av, T v) {
00601             if (av==null) return false;
00602             int c = cmp(av->key,v);
00603             if (c==0) {
00604                if (av->r==null) {
00605                   struct AvlNode *a=av;
00606                   av=av->l;
00607                   Collection::Mem::kfree(a);
00608                   return true;
00609                 } else {
00610                   T a = removeMin(av->r);
00611                   av->key=a;
00612                   setHeight(av);
00613                   bal(av);
00614                   return true;
00615                 }
00616             }
00617             bool ret;
00618             if (c < 0) {
00619                ret = remove(av->r,v);
00620                setHeight(av);
00621                bal(av);
00622                return ret;
00623             } else {
00624                ret= remove(av->l,v);
00625                setHeight(av);
00626                bal(av);
00627             }
00628             return ret;
00629          }
00630 
00631          bool exists(T v) { return exists(nd,v); }
00632          bool exists(struct AvlNode *&av, T v) {
00633             if (av==null) return false;
00634             int c = cmp(av->key,v);
00635             if (c==0) return true;
00636             if (c<0) return exists(av->r,v);
00637             return exists(av->l,v);
00638          }
00639 
00640          Collection::Option<T> find(T v) { return findcmp<cmp>(v); }
00641          template<int(*cmp2)(T,T)>
00642          Collection::Option<T> findcmp(T v) { return findcmp<cmp2>(nd,v); }
00643          template<int(*cmp2)(T,T)>
00644          Collection::Option<T> findcmp(struct AvlNode *&av, T v) {
00645             if (av==null) return Option<T>();
00646             int c = cmp2(av->key,v);
00647             if (c==0) return Option<T>(av->key);
00648             if (c<0) return findcmp<cmp2>(av->r,v);
00649             return findcmp<cmp2>(av->l,v);
00650          }
00651 
00652          T removeMin(struct AvlNode *&av) {
00653             testif(av!=null);
00654             if (av->l==null) {
00655                T ret= av->key;
00656                struct AvlNode *v=av->r;
00657                Collection::Mem::kfree(av);
00658                av= v;
00659                return ret;
00660             } else {
00661                T ret = removeMin(av->l);
00662                setHeight(av);
00663                return ret;
00664             }
00665          }
00666 
00667          Option<T> findMin() { return findMin(nd); }
00668          Option<T> findMin(struct AvlNode *&av) {
00669             if (av==null)
00670                return Option<T> ();
00671             testif(av!=null);
00672             if (av->l == null)
00673                return av->key;
00674             return findMin(av->l);
00675          }
00676 
00677          bool isEmpty() { return isEmpty(nd); }
00678          bool isEmpty(struct AvlNode *&av) {
00679             return av==null;
00680          }
00681 
00682          void write() { write(nd); }
00683          void write(struct AvlNode *&av) {
00684             if (av == null) kprintf("-");
00685             else {
00686                kprintf("(");
00687                write(av->l);
00688                kprintf(",");
00689                kprintf("%d",av->key); //dla typu klucza uint32
00690 //               kprintf("%x%x",*(uint64*)&av->key); //dla typu klucza struct ethernet_address ale i tak takie wypisanie nie dziala
00691                kprintf(",");
00692                write(av->r);
00693                kprintf(",%d",av->ht);
00694                kprintf(")");
00695             }
00696          }
00697       };
00698 
00699 
00700 
00701 
00702 }
00703 
00704 #endif
00705