API tools faq
paste
Guest User

avl.c

a guest
Aug 2nd, 2019
390
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.65 KB | None | 0 0
raw download clone embed print report
  1. // avl.c
  2. #include "avl.h"
  3.  
  4. #include <stdlib.h>
  5. #define AVL_MEM_ALLOC(size) malloc(size)
  6. #define AVL_MEM_FREE(p)     free(p)
  7.  
  8. enum {  avl_max_height=40 };
  9. // 40--> min 267914295 nodes (3Gb) (MH ~ 1.440*ln2(N)-0.328)
  10. // S(0)=0
  11. // S(1)=1
  12. // S(n)=1+S(n-1)+S(n-2)
  13. //...
  14. // S(19)=10945
  15. // S(24)=121392
  16. // S(40)=267914295
  17. // S(41)=433494436
  18. // S(64)=27777890035287
  19. // S(86)=1100087778366101930
  20. // S(193)=25299086886458645685589389182743678652929
  21. //...
  22. // 16bit->19, 24bit->24, 32bit->41, 48bit->64, 64bit->86, 128bit->193
  23.  
  24. #define AVL_ITEM(n)         (void*)( (char*)avl->items + avl->item_size*(n) )
  25. #define AVL_CMP1(item,n)    avl->cmp(avl->cmp_ctx,item       ,AVL_ITEM(n))
  26. #define AVL_CMP2(a,b)       avl->cmp(avl->cmp_ctx,AVL_ITEM(a),AVL_ITEM(b))
  27. #define AVL_LEFT(n)         (avl->LR[2*(n)]>>2)
  28. #define AVL_RIGHT(n)        (avl->LR[2*(n)+1])
  29. #define AVL_FLG(n)          (avl->LR[2*(n)]&3)
  30. #define AVL_SET_LEFT(n,v)   (avl->LR[2*(n)]=(avl->LR[2*(n)]&3)|((v)<<2))
  31. #define AVL_SET_RIGHT(n,v)  (avl->LR[2*(n)+1]=(v))
  32. #define AVL_SET_CHILD(n,dir,v) \
  33.     {if (dir) avl->LR[2*(n)+1]=(v); \
  34.     else avl->LR[2*(n)]=(avl->LR[2*(n)]&3)|((v)<<2);}
  35. #define AVL_SET_FLG(n,v)    (avl->LR[2*(n)]=(avl->LR[2*(n)]&~3)|(v))
  36. #define AVL_MARK_ERASED(n)  (avl->LR[2*(n)]=avl_none)
  37. #define AVL_SET_NOCHILD(n)  \
  38.     {avl->LR[2*(n)]=(avl_none<<2)+1; avl->LR[2*(n)+1]=avl_none;}
  39. #define AVL_COPY(n,item)    {avl->copy(avl->copy_ctx,AVL_ITEM(n),item);}
  40. #define AVL_COPY_CHILDREN(d,s) \
  41.     {avl->LR[2*(d)]=avl->LR[2*(s)]; avl->LR[2*(d)+1]=avl->LR[2*(s)+1];}
  42.  
  43. int  avl_clear(avl_t *avl) {
  44.     avl->count=0;
  45.     avl->size=0;
  46.     avl->root=avl_none;
  47.     avl->tail=avl_none;
  48. }
  49. int avl_init(avl_t *avl,int limit) {
  50.     avl->LR=(int*)AVL_MEM_ALLOC(limit*2*sizeof(int));
  51.     avl->items=AVL_MEM_ALLOC(limit*avl->item_size);
  52.     avl->limit=limit;
  53.     avl_clear(avl);
  54. }
  55. void avl_done(avl_t *avl) {
  56.     AVL_MEM_FREE(avl->items); avl->items=0;
  57.     AVL_MEM_FREE(avl->LR);    avl->LR=0;
  58.     avl->limit=0;
  59.     avl_clear(avl);
  60. }
  61. static int avl_alloc(avl_t *avl) {
  62.     int r;
  63.     if (avl->count==0) {
  64.         if (avl->limit==0) return avl_none;
  65.         avl->count=1;
  66.         avl->size=1;
  67.         avl->tail=avl_none;
  68.         r=0;
  69.     } else {
  70.         r=avl->tail;
  71.         if (r!=avl_none) {
  72.             avl->tail=AVL_RIGHT(avl->tail);
  73.         } else {
  74.             if (avl->size>=avl->limit) {
  75.                 if (avl->ovf) avl->ovf(avl->ovf_ctx,avl);
  76.                 if (avl->size>=avl->limit) {
  77.                     return avl_none;
  78.                 }
  79.             }
  80.             r=avl->size++;
  81.         }
  82.         avl->count++;
  83.     }
  84.     AVL_SET_NOCHILD(r);
  85.     return r;
  86. }
  87. static void avl_free(avl_t *avl,int n) {
  88.     AVL_MARK_ERASED(n);
  89.     AVL_SET_RIGHT(n,avl->tail);
  90.     avl->tail=n;
  91.     avl->count--;
  92. }
  93. int avl_find(avl_t *avl,void *item) {
  94.     int r=avl->root;
  95.     while(r!=avl_none) {
  96.         int c=AVL_CMP1(item,r); if (c==0) return r;
  97.         if (c<0) r=AVL_LEFT(r); else r=AVL_RIGHT(r);
  98.     }
  99.     return avl_none;
  100. }
  101. static int avl_sl(avl_t *avl,int A) {
  102.     int B,b;
  103.     //            h+3                   h+2
  104.     //             |                     |
  105.     //            A:-2                  B:0
  106.     //           /   \                 /   \
  107.     //         B:-1   g:h    ==>    a:h+1  A:0
  108.     //        /   \                       /   \
  109.     //     a:h+1   b:h                  b:h   g:h
  110.     B=AVL_LEFT(A);     b=AVL_RIGHT(B);
  111.     AVL_SET_LEFT(A,b); AVL_SET_RIGHT(B,A);
  112.     AVL_SET_FLG(B,1);  AVL_SET_FLG(A,1);
  113.     return B;
  114. }
  115. static int avl_sr(avl_t *avl,int A) {
  116.     int B,b;
  117.     //            h+3                   h+2
  118.     //             |                     |
  119.     //            A:+2                  B:0
  120.     //           /   \                 /   \
  121.     //         a:h   B:+1    ==>     A:0   g:h+1
  122.     //              /   \           /   \
  123.     //           b:h   g:h+1      a:h   b:h
  124.     B=AVL_RIGHT(A);     b=AVL_LEFT(B);
  125.     AVL_SET_RIGHT(A,b); AVL_SET_LEFT(B,A);
  126.     AVL_SET_FLG(B,1);   AVL_SET_FLG(A,1);
  127.     return B;
  128. }
  129. static int avl_lr(avl_t *avl,int A) {
  130.     int B,C,b,g;
  131.     //        h+3                     h+2
  132.     //         |                       |
  133.     //        A:-2                    C:0           x= 0 if C.f=0,-1
  134.     //       /   \                  /     \         x=-1 if C.f=+1
  135.     //     B:+1  d:h     ==>      B:x     A:y       y= 0 if C.f=0,+1
  136.     //    /   \                  /   \   /   \      y=+1 if C.f=-1
  137.     //  a:h   C:f              a:h b<=h g<=h d:h
  138.     //       /   \
  139.     //     [b     g]:h
  140.     B=AVL_LEFT(A); C=AVL_RIGHT(B);
  141.     b=AVL_LEFT(C); g=AVL_RIGHT(C);
  142.     AVL_SET_RIGHT(B,b);
  143.     AVL_SET_LEFT(A,g);
  144.     AVL_SET_LEFT(C,B);
  145.     AVL_SET_RIGHT(C,A);
  146.     AVL_SET_FLG(B,AVL_FLG(C)==2?0:1);
  147.     AVL_SET_FLG(A,AVL_FLG(C)==0?2:1);
  148.     AVL_SET_FLG(C,1);
  149.     return C;
  150. }        
  151. static int avl_rl(avl_t *avl,int A) {
  152.     int B,C,b,g;
  153.     //        h+3                     h+2
  154.     //         |                       |
  155.     //        A:+2                    C:0            x= 0 if C.f=0,-1
  156.     //       /   \                  /     \          x=-1 if C.f=+1
  157.     //     a:h   B:-1      ==>    A:x     B:y        y= 0 if C.f=0,+1
  158.     //          /   \            /   \   /   \       y=+1 if C.f=-1
  159.     //        C:f   d:h        a:h b<=h g<=h d:h
  160.     //       /   \
  161.     //     [b     g]:h
  162.     B=AVL_RIGHT(A); C=AVL_LEFT(B);
  163.     b=AVL_LEFT(C);  g=AVL_RIGHT(C);
  164.     AVL_SET_RIGHT(A,b);
  165.     AVL_SET_LEFT(B,g);
  166.     AVL_SET_LEFT(C,A);
  167.     AVL_SET_RIGHT(C,B);
  168.     AVL_SET_FLG(A,AVL_FLG(C)==2?0:1);
  169.     AVL_SET_FLG(B,AVL_FLG(C)==0?2:1);
  170.     AVL_SET_FLG(C,1);
  171.     return C;
  172. }    
  173. static int avl_sl0(avl_t *avl,int A) {
  174.     int B,b;
  175.     //            h+3                   h+3
  176.     //             |                     |
  177.     //            A:-2                  B:+1
  178.     //           /   \                 /   \
  179.     //         B:0    g:h    ==>    a:h+1  A:-1
  180.     //        /   \                       /   \
  181.     //     a:h+1  b:h+1                b:h+1  g:h
  182.     B=AVL_LEFT(A);      b=AVL_RIGHT(B);
  183.     AVL_SET_LEFT(A,b);  AVL_SET_RIGHT(B,A);
  184.     AVL_SET_FLG(B,2);   AVL_SET_FLG(A,0);
  185.     return B;
  186. }
  187. static int avl_sr0(avl_t *avl,int A) {
  188.     int B,b;
  189.     //            h+3                   h+3
  190.     //             |                     |
  191.     //            A:+2                  B:-1
  192.     //           /   \                 /   \
  193.     //         a:h   B:0     ==>     A:1   g:h+1
  194.     //              /   \           /   \
  195.     //           b:h+1 g:h+1      a:h   b:h+1
  196.     B=AVL_RIGHT(A);     b=AVL_LEFT(B);
  197.     AVL_SET_RIGHT(A,b); AVL_SET_LEFT(B,A);
  198.     AVL_SET_FLG(B,0);   AVL_SET_FLG(A,2);
  199.     return B;
  200. }
  201. int avl_insert(avl_t *avl,void *item) {
  202.     int flg,pp,tt,t,r;
  203.     int path[avl_max_height];
  204.    
  205.     if (!item) return avl_none;
  206.     r=avl->root;
  207.     if (r==avl_none) { // trivial case
  208.         r=avl_alloc(avl);
  209.         avl->root=r;
  210.         if (r!=avl_none) AVL_COPY(r,item);
  211.         return r;
  212.     }
  213.     pp=-1;
  214.     // 1. find node
  215.     do {
  216.         int v=r<<1, c=AVL_CMP1(item,r);
  217.         if (c<0) { r=AVL_LEFT(r); } else
  218.         if (c>0) { r=AVL_RIGHT(r); v++; } else return r;
  219.         path[++pp]=v;
  220.     } while(r!=avl_none);
  221.     // 2. create new node
  222.     r=avl_alloc(avl); if (r==avl_none) return r; // overflow. no room
  223.     AVL_COPY(r,item);
  224.     AVL_SET_CHILD(path[pp]>>1,path[pp]&1,r);
  225.     // 3. walk back and rebalance tree
  226.     for(;pp>=0;pp--) {
  227.         t=path[pp]>>1; flg=AVL_FLG(t);
  228.         if (path[pp]&1) { // right
  229.             if (flg==0) { AVL_SET_FLG(t,1); break;    }
  230.             if (flg==1) { AVL_SET_FLG(t,2); continue; }
  231.             tt=AVL_RIGHT(t); // Skew=+2
  232.             flg=AVL_FLG(tt);
  233.             if (flg==2) t=avl_sr(avl,t); else if (flg==0) t=avl_rl(avl,t);
  234.         } else { // left
  235.             if (flg==2) { AVL_SET_FLG(t,1); break;    }
  236.             if (flg==1) { AVL_SET_FLG(t,0); continue; }
  237.             tt=AVL_LEFT(t); // Skew=-2
  238.             flg=AVL_FLG(tt);
  239.             if (flg==0) t=avl_sl(avl,t); else if (flg==2) t=avl_lr(avl,t);
  240.         }
  241.         if (pp>0) { AVL_SET_CHILD(path[pp-1]>>1,path[pp-1]&1,t); }
  242.         else avl->root=t;
  243.         break;
  244.     }
  245.     return r;
  246. }
  247. int avl_remove(avl_t *avl,void *item) {  // O(ln(n))
  248.     int mp,pp,r,thd;
  249.     int path[avl_max_height];
  250.  
  251.     if (!item) return avl_none;
  252.     pp=0; r=avl->root;
  253.     // 1. find  node to erase
  254.     for(;r!=avl_none;pp++) {
  255.         int v=r<<1, c=AVL_CMP1(item,r);
  256.         if (c<0) { r=AVL_LEFT(r); } else
  257.         if (c>0) { r=AVL_RIGHT(r); v++; } else
  258.         { path[pp]=v; break; } // find node to erase
  259.         path[pp]=v;
  260.     }
  261.     if (r==avl_none) return r; // no node found
  262.     // 2. look around. check childs
  263.     if (AVL_LEFT(r)==avl_none) { // right child or none
  264.         int rn=AVL_RIGHT(r);
  265.         if (pp>0) { AVL_SET_CHILD(path[pp-1]>>1,path[pp-1]&1,rn); }
  266.         else avl->root=rn;
  267.     } else if (AVL_RIGHT(r)==avl_none) { // only left child
  268.         int ln=AVL_LEFT(r);
  269.         if (pp>0) { AVL_SET_CHILD(path[pp-1]>>1,path[pp-1]&1,ln); }
  270.         else avl->root=ln;
  271.     } else { // we've got both childs
  272.         int w,mn,ri,z=AVL_RIGHT(r);
  273.         mp=pp; path[pp]|=1; path[++pp]=z<<1;
  274.         // find sub tree min node
  275.         for(w=AVL_LEFT(z);w!=avl_none;w=AVL_LEFT(w)) {
  276.             path[pp]&=~1; path[++pp]=w<<1;
  277.         }
  278.         mn=path[pp]>>1; ri=AVL_RIGHT(mn);
  279.         AVL_SET_CHILD(path[pp-1]>>1,path[pp-1]&1,ri);
  280.         if (mp>0) { AVL_SET_CHILD(path[mp-1]>>1,path[mp-1]&1,mn); }
  281.         else avl->root=mn;
  282.         AVL_COPY_CHILDREN(mn,r); path[mp]=(mn<<1)|(path[mp]&1);
  283.     }
  284.     avl_free(avl,r); pp--;
  285.     // 3. walk back and rebalance tree
  286.     for(thd=1;pp>=0;pp--) {
  287.         int t=path[pp]>>1, flg=AVL_FLG(t), tl,tr;
  288.         if (path[pp]&1) { // from right
  289.             if (flg==2) { AVL_SET_FLG(t,1); continue; }
  290.             if (flg==1) { AVL_SET_FLG(t,0); break;    }
  291.             tl=AVL_LEFT(t); // skew=-2
  292.             flg=AVL_FLG(tl);
  293.             if (flg==0) t=avl_sl(avl,t); else if (flg==2) t=avl_lr(avl,t);
  294.             else { thd=0; t=avl_sl0(avl,t); }
  295.         } else { // from left
  296.             if (flg==0) { AVL_SET_FLG(t,1); continue; }
  297.             if (flg==1) { AVL_SET_FLG(t,2); break;    }
  298.             tr=AVL_RIGHT(t); // skew=+2
  299.             flg=AVL_FLG(tr);
  300.             if (flg==2) t=avl_sr(avl,t); else if (flg==0) t=avl_rl(avl,t);
  301.             else { thd=0; t=avl_sr0(avl,t); }      
  302.         }
  303.         if (pp>0) { AVL_SET_CHILD(path[pp-1]>>1,path[pp-1]&1,t); }
  304.         else avl->root=t;
  305.         if (!thd) break;
  306.     }
  307.     return r;
  308. }
  309. int  avl_get(avl_t *avl,int n,void *item) {
  310.     if (n<0 || n>=avl->limit) return avl_none; // out of bounds
  311.     if (AVL_FLG(n)==3) return avl_none;        // erased item
  312.     if (item) avl->copy(avl->copy_ctx,item,AVL_ITEM(n));
  313.     return n;
  314. }
  315. int  avl_min(avl_t *avl,void *item) {
  316.     int t,r=avl->root; if (r==avl_none) return avl_none;
  317.     for(;;r=t) {
  318.         t=AVL_LEFT(r);
  319.         if (t==avl_none) break;
  320.     }
  321.     return avl_get(avl,r,item);
  322. }
  323. int  avl_max(avl_t *avl,void *item) {
  324.     int t,r=avl->root; if (r==avl_none) return avl_none;
  325.     for(;;r=t) {
  326.         t=AVL_RIGHT(r);
  327.         if (t==avl_none) break;
  328.     }
  329.     return avl_get(avl,r,item);
  330. }
  331. int  avl_next(avl_t *avl,void *item) {
  332.     int pp,r,rr,c;
  333.     int path[avl_max_height];
  334.    
  335.     r=avl->root; if (r==avl_none || !item) return r; // trivial case
  336.     pp=-1;
  337.     // 1. find node
  338.     do {
  339.         int v=r<<1; c=AVL_CMP1(item,r);
  340.         if (c<0) { r=AVL_LEFT(r); } else
  341.         if (c>0) { r=AVL_RIGHT(r); v++; }
  342.         path[++pp]=v;
  343.         if (c==0) break;
  344.     } while(r!=avl_none);
  345.     if (c>0) r=path[pp]>>1;
  346.     if (r!=avl_none) { // c=0 found item
  347.         r=AVL_RIGHT(r);
  348.         if (r==avl_none) {
  349.             while(pp>0 && path[pp-1]&1) --pp;
  350.             rr=pp>0 ? path[pp-1]>>1 : avl_none;
  351.         } else {
  352.             do { rr=r; r=AVL_LEFT(r); } while(r!=avl_none);
  353.         }
  354.     } else { // no iten found & c<0
  355.         rr=path[pp]>>1;
  356.     }
  357.     if (rr!=avl_none) avl->copy(avl->copy_ctx,item,AVL_ITEM(rr));
  358.     return rr;
  359. }
  360. int  avl_prev(avl_t *avl,void *item) {
  361.     int pp,r,rr,c;
  362.     int path[avl_max_height];
  363.    
  364.     r=avl->root; if (r==avl_none || !item) return r; // trivial case
  365.     pp=-1;
  366.     // 1. find node
  367.     do {
  368.         int v=r<<1; c=AVL_CMP1(item,r);
  369.         if (c<0) { r=AVL_LEFT(r); } else
  370.         if (c>0) { r=AVL_RIGHT(r); v++; }
  371.         path[++pp]=v;
  372.         if (c==0) break;
  373.     } while(r!=avl_none);
  374.     if (c<0) r=path[pp]>>1;
  375.     if (r!=avl_none) { // c=0 found item
  376.         r=AVL_LEFT(r);
  377.         if (r==avl_none) {
  378.             while(pp>0 && ((path[pp-1]&1)==0)) --pp;
  379.             rr=pp>0 ? path[pp-1]>>1 : avl_none;
  380.         } else {
  381.             do { rr=r; r=AVL_RIGHT(r); } while(r!=avl_none);
  382.         }
  383.     } else { // no iten found & c<0
  384.         rr=path[pp]>>1;
  385.     }
  386.     if (rr!=avl_none) avl->copy(avl->copy_ctx,item,AVL_ITEM(rr));
  387.     return rr;
  388. }
  389. int  avl_available(avl_t *avl) {
  390.     return avl->limit-avl->count;
  391. }
  392. int  avl_count(avl_t *avl) {
  393.     return avl->count;
  394. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!