Merge branch 'feature-splay_tree' into develop

3 files changed, 220 insertions, 151 deletions

diff --git a/inc/sptree.h b/inc/sptree.h
index 5ca63dd..baec7e5 100644
--- a/inc/sptree.h
+++ b/inc/sptree.h
@@ -3,9 +3,9 @@
 
 #include "utility.h"
 
-typedef cmp_func key_cmp;
+typedef ctl_cmp_func ctl_spt_cmp;
 
-pvoid ctl_sptree_initX(ppvoid sp, uint k_size, uint v_size, key_cmp f);
+pvoid ctl_sptree_initX(ppvoid sp, uint k_size, uint v_size, ctl_spt_cmp f);
 pvoid ctl_sptree_freeX(ppvoid sp);
 
 int  ctl_sptree_isEmptyX   (ppcvoid sp); 
@@ -18,14 +18,13 @@ pvoid ctl_sptree_addX   (ppvoid sp, pcvoid key, pvoid val);
 void  ctl_sptree_delX   (ppvoid sp, pcvoid key);
 pvoid ctl_sptree_updateX(ppvoid sp, pcvoid key, pvoid val);
 
-
 void  ctl_sptree_splitX(ppvoid sp, pcvoid key, ppvoid r, ppvoid l);
 pvoid ctl_sptree_mergeX(ppvoid sp1, ppvoid sp2);
 
 void ctl_sptree_clearX(ppvoid sp);
 //void ctl_sptree_copyX (ppvoid sp, ppvoid sp2);
 
-#define ctl_sptree_init(A,B,C,D) ctl_sptree_initX(ppVoid(A),B,C,(key_cmp)D)
+#define ctl_sptree_init(A,B,C,D) ctl_sptree_initX(ppVoid(A),B,C,(ctl_spt_cmp)D)
 #define ctl_sptree_free(A)       ctl_sptree_freeX(ppVoid(A))
 
 #define ctl_sptree_isEmpty(A)    ctl_sptree_isEmptyX   (ppcVoid(A))
@@ -37,9 +36,9 @@ void ctl_sptree_clearX(ppvoid sp);
 #define ctl_sptree_del(A,B)      ctl_sptree_delX   (ppVoid(A),pcVoid(B))
 #define ctl_sptree_update(A,B,C) ctl_sptree_updateX(ppVoid(A),pcVoid(B),pvoid(C))
 
-#define ctl_sptree_split(A,B,C,D) ctl_sptree_split(ppVoid(A),pcVoid(B),\
-                                                   ppVoid(C),pcVoid(D))
-#define ctl_sptree_merge(A,B)     ctl_sptree_merge(ppVoid(A),ppVoid(B))
+#define ctl_sptree_split(A,B,C,D) ctl_sptree_splitX(ppVoid(A),pcVoid(B),\
+                                                    ppVoid(C),pcVoid(D))
+#define ctl_sptree_merge(A,B)     ctl_sptree_mergeX(ppVoid(A),ppVoid(B))
 
 #define ctl_sptree_clear(A)  ctl_sptree_clearX(ppVoid(A))
 //#define ctl_sptree_copy(A,B) ctl_sptree_copyX (ppVoid(A),ppVoid(B))
diff --git a/inc/utility.h b/inc/utility.h
index 638c989..ccfd6fa 100644
--- a/inc/utility.h
+++ b/inc/utility.h
@@ -104,7 +104,9 @@ typedef       pcuchar* ppcuchar;
 #define ppcuChar(X) ((ppcuchar)(X))
 
 //
-typedef int (*cmp_func)(pcvoid,pcvoid);
+typedef int (*ctl_cmp_func)(pcvoid,pcvoid);
+
+#define ctl_priv static inline 
 
 
 pvoid ctl_malloc (size_t size);
diff --git a/src/sptree.c b/src/sptree.c
index 0952a4d..378f216 100644
--- a/src/sptree.c
+++ b/src/sptree.c
@@ -3,6 +3,8 @@
 
 #include <string.h>
 
+
+/********************** #Structures ***********************/
 struct StructSplayTree;
 struct StructSplayTreeNode;
 
@@ -10,7 +12,7 @@ struct StructSplayTree{
     uint                        key_size;
     uint                        val_size;
     struct StructSplayTreeNode* root;
-    key_cmp                     func;
+    ctl_spt_cmp                 func;
 };
 struct StructSplayTreeNode{
     struct StructSplayTreeNode* lchd;
@@ -19,23 +21,35 @@ struct StructSplayTreeNode{
     pcvoid                      key;
     pvoid                       val;
 };
-
 typedef struct StructSplayTree     SplayTree;
 typedef struct StructSplayTreeNode SplayTreeNode;
 
-/******************* static functions *********************/
-static void            delete_dfs(SplayTreeNode* nd);
-static inline void connectL(SplayTreeNode* fath, SplayTreeNode* righ);
-static inline void connectR(SplayTreeNode* fath, SplayTreeNode* righ);
+/******************* #Private functions *******************/
+ctl_priv void connectL  (SplayTreeNode* fath, SplayTreeNode* lchd);
+ctl_priv void connectR  (SplayTreeNode* fath, SplayTreeNode* righ);
+ctl_priv void delete_dfs(SplayTreeNode* nd);
+
+ctl_priv SplayTreeNode* acces(ctl_spt_cmp f,SplayTreeNode*nd,pcvoid k,int*t);
+ctl_priv SplayTreeNode* split(ctl_spt_cmp f,SplayTreeNode*nd,pcvoid k,
+                              SplayTreeNode** l, SplayTreeNode** r);
+ctl_priv SplayTreeNode* merge(SplayTreeNode* l, SplayTreeNode* r);
+ctl_priv SplayTreeNode* splay(SplayTreeNode* nd);
+
+ctl_priv void splay_root(SplayTreeNode* m, SplayTreeNode* f);
+ctl_priv void splay_l   (SplayTreeNode* m, SplayTreeNode* f, SplayTreeNode* g);
+ctl_priv void splay_r   (SplayTreeNode* m, SplayTreeNode* f, SplayTreeNode* g);
 
-static SplayTreeNode* access_node(key_cmp f, SplayTreeNode* nd, pcvoid k);
-static SplayTreeNode* split_node (key_cmp f, SplayTreeNode* nd, pcvoid k,
-                                  SplayTreeNode** l, SplayTreeNode** r);
-static SplayTreeNode* access_max(SplayTreeNode *nd);
-static SplayTreeNode* merge_node(SplayTreeNode* l, SplayTreeNode* r);
+ctl_priv void dump_node(SplayTreeNode* now);
 
+/************************* #Macros ************************/
 #define getHeader(A) ((SplayTree*)(A))
-#define getSize(A)   (sizeof(SplayTreeNode)+(A)->key_size+(A)->val_size)
+#define getSize(A)   (sizeof(SplayTreeNode) + \
+		              (A)->key_size+ (A)->val_size)
+#define getKey(A)     pVoid(pChar(A) + \
+			                sizeof(SplayTreeNode))
+#define getValue(A,X) pVoid(pChar(A) + \
+			                sizeof(SplayTreeNode) + \
+			                (X))
 #define disconnL(A) \
     do{\
         if((A)->lchd != NULL) (A)->lchd->fath = NULL;\
@@ -47,41 +61,33 @@ static SplayTreeNode* merge_node(SplayTreeNode* l, SplayTreeNode* r);
         (A)->rchd = NULL;\
     }while(0)
 
-/*
-static void dump_node(SplayTreeNode* now){
-    if(now == NULL) return ;
-    printf("now = (%5.1f, %2d)    ", *(double*)now->key, *(int*)now->val);
-    if(now->lchd == NULL) printf("lchd = (     NULL) ");
-    else                  printf("lchd = (%5.1f, %2d) ", *(double*)now->lchd->key, *(int*)now->lchd->val);
-    if(now->rchd == NULL) printf("rchd = (     NULL) ");
-    else                  printf("rchd = (%5.1f, %2d) ", *(double*)now->rchd->key, *(int*)now->rchd->val);
-    if(now->fath == NULL) printf("fath = (     NULL) ");
-    else                  printf("fath = (%5.1f, %2d) ", *(double*)now->fath->key, *(int*)now->fath->val);
-    printf("\n");
-    dump_node(now->lchd);
-    dump_node(now->rchd);
-}
-// */
-/*************** constructure / destructure ***************/
-pvoid ctl_sptree_initX(ppvoid sp, uint k_size, uint v_size, key_cmp f){
+/**********************************************************/
+/*                #constructure / destructure             */
+/**********************************************************/
+pvoid ctl_sptree_initX(ppvoid sp, uint k_size, uint v_size, ctl_spt_cmp f){
     SplayTree* head = (SplayTree*)ctl_malloc(sizeof(SplayTree));
     head->key_size = k_size;
     head->val_size = v_size;
     head->root = NULL;
     head->func = f;
+    if(*sp != NULL)
+        *sp = pVoid(head);
     return pVoid(head);
 }
 pvoid ctl_sptree_freeX(ppvoid sp){
     SplayTree* head = (SplayTree*)*sp;
-    if(head->root != NULL) delete_dfs(head->root);
+    if(head->root != NULL)
+		delete_dfs(head->root);
     ctl_free(pVoid(head));
     *sp = NULL;
     return NULL;
 }
 
-/****************** get/is ??? method *********************/
+/**********************************************************/
+/*                   #get/is ??? method                   */
+/**********************************************************/
 int ctl_sptree_isEmptyX(ppcvoid sp){
-    return (getHeader(*sp)->root == NULL ? 0 : 1);
+    return (getHeader(*sp)->root == NULL ? 1 : 0);
 }
 uint ctl_sptree_getKeySizeX(ppcvoid sp){
     return getHeader(*sp)->key_size;
@@ -90,75 +96,100 @@ uint ctl_sptree_getValSizeX(ppcvoid sp){
     return getHeader(*sp)->val_size;
 }
 
-/******************* splay tree's methods *****************/
+/**********************************************************/
+/*           #splay tree's method  --  FIND               */
+/**********************************************************/
 pvoid ctl_sptree_findX(ppvoid sp, pcvoid key){
     SplayTree* head = getHeader(*sp);
-    SplayTreeNode* nd = access_node(head->func, head->root, key);
-    if(head->root != NULL)
-        while(head->root->fath != NULL)
-            head->root = head->root->fath;
-    if(nd == NULL) return NULL;
-    return getHeader(*sp)->root->val;
+	int t = 1;
+	if(head->root != NULL){
+		head->root = acces(head->func, head->root, key, &t);
+    }
+	if(t == 0)
+		return head->root->val;
+	else
+		return NULL;
 }
+
+/**********************************************************/
+/*        #splay tree's method  --  ADD (key, value)      */
+/**********************************************************/
 pvoid ctl_sptree_addX(ppvoid sp, pcvoid key, pvoid val){
     SplayTree* head = getHeader(*sp);
-    SplayTreeNode* lft;
-    SplayTreeNode* rgh;
-    SplayTreeNode* mid = split_node(head->func, head->root, key, &lft, &rgh);
-    if(mid != NULL){
-        memcpy(mid->val, val, head->val_size);
-        head->root = merge_node(lft, rgh);
-    }else{
-        mid = (SplayTreeNode*)ctl_malloc(getSize(head));
-        mid->key = pcVoid(pChar(mid) + sizeof(SplayTreeNode));
-        mid->val =  pVoid(pChar(mid) + sizeof(SplayTreeNode) + head->key_size);
-        memcpy(pChar(mid) + sizeof(SplayTreeNode), key, head->key_size);
-        memcpy(mid->val, val, head->val_size);
-        mid->fath = NULL;
-        mid->lchd = NULL;
-        mid->rchd = NULL;
-        head->root = merge_node(merge_node(lft, mid), rgh);
-    }
+	SplayTreeNode* lft = NULL;
+	SplayTreeNode* rgh = NULL;
+	SplayTreeNode* mid = NULL;
+	if(head->root != NULL)
+		mid = split(head->func, head->root, key, &lft, &rgh);
+	if(mid != NULL){
+		memcpy(mid->val, val, head->val_size);
+		head->root = merge(lft, rgh);
+	}else{
+		mid = (SplayTreeNode*)ctl_malloc(getSize(head));
+		mid->key = pcVoid(getKey  (mid                ));
+		mid->val =        getValue(mid, head->key_size) ;
+		memcpy(getKey  (mid                ), key, head->key_size);
+		memcpy(getValue(mid, head->key_size), val, head->val_size);
+		mid->fath = NULL;
+		mid->lchd = NULL;
+		mid->rchd = NULL;
+		head->root = merge(merge(lft, mid), rgh);
+	}
     return mid->val;
 }
+
+/**********************************************************/
+/*        #splay tree's method  --  Delete by key         */
+/**********************************************************/
 void ctl_sptree_delX(ppvoid sp, pcvoid key){
     SplayTree* head = getHeader(*sp);
     SplayTreeNode* left;
     SplayTreeNode* righ;
-    access_node(head->func, head->root, key);
-    if(head->root != NULL)
-        while(head->root->fath != NULL)
-            head->root = head->root->fath;
-    left = head->root->lchd;
-    righ = head->root->rchd;
-    disconnL(head->root);
-    disconnR(head->root);
-    ctl_free(pVoid(head->root));
-    head->root = merge_node(left, righ);
+	int x;
+    head->root = acces(head->func, head->root, key, &x);
+	if(x == 0){
+		left = head->root->lchd;
+		righ = head->root->rchd;
+		disconnL(head->root);
+		disconnR(head->root);
+		ctl_free(pVoid(head->root));
+		head->root = merge(left, righ);
+	}
 }
 
+/**********************************************************/
+/*         #splay tree's method  --  Split by key         */
+/**********************************************************/
 void ctl_sptree_splitX(ppvoid sp , pcvoid key, ppvoid l, ppvoid r){
     SplayTree* head = getHeader(*sp);
     ctl_sptree_initX(l, head->key_size, head->val_size, head->func);
     ctl_sptree_initX(r, head->key_size, head->val_size, head->func);
     SplayTreeNode* left;
     SplayTreeNode* righ;
-    split_node(head->func, head->root, key, &left, &righ);
-    getHeader(*r)->root = left;
-    getHeader(*l)->root = righ;
-    head->root = NULL;
+	if(head->root != NULL){
+		split(head->func, head->root, key, &left, &righ);
+		getHeader(*l)->root = left;
+		getHeader(*r)->root = righ;
+		head->root = NULL;
+	}
     ctl_sptree_freeX(sp);
 }
+/**********************************************************/
+/*      #splay tree's method  --  Big + small = merge     */
+/**********************************************************/
 pvoid ctl_sptree_mergeX(ppvoid sp1, ppvoid sp2){
     SplayTree* head1 = getHeader(*sp1);
     SplayTree* head2 = getHeader(*sp2);
-    head1->root = merge_node(head1->root, head2->root);
+    head1->root = merge(head1->root, head2->root);
     head2->root = NULL;
     ctl_sptree_freeX(sp2);
     *sp1 = NULL;
     return pVoid(head1);
 }
     
+/**********************************************************/
+/*           #splay tree's method  --  clean up           */
+/**********************************************************/
 void ctl_sptree_clearX(ppvoid sp){
     if(getHeader(*sp)->root != NULL)
         delete_dfs(getHeader(*sp)->root);
@@ -166,96 +197,133 @@ void ctl_sptree_clearX(ppvoid sp){
 }
 
 
-/****************** static functions **********************/
-static inline void connectL(SplayTreeNode* fath, SplayTreeNode* lchd){
+/***************** # safe connect two nodes ***************/
+ctl_priv void connectL(SplayTreeNode* fath, SplayTreeNode* lchd){
     if(fath != NULL) fath->lchd = lchd;
     if(lchd != NULL) lchd->fath = fath;
 }
-static inline void connectR(SplayTreeNode* fath, SplayTreeNode* righ){
+ctl_priv void connectR(SplayTreeNode* fath, SplayTreeNode* righ){
     if(fath != NULL) fath->rchd = righ;
     if(righ != NULL) righ->fath = fath;
 }
-static void delete_dfs(SplayTreeNode* nd){
+
+/************* # for destruct the whole tree **************/
+ctl_priv void delete_dfs(SplayTreeNode* nd){
     if(nd->lchd != NULL) delete_dfs(nd->lchd);
     if(nd->rchd != NULL) delete_dfs(nd->rchd);
     ctl_free(pVoid(nd));
 }
-static SplayTreeNode* access_node(key_cmp f, SplayTreeNode* nd, pcvoid k){
-    if(nd == NULL) return NULL;
-    if(f(k, nd->key) == 0) return nd;
-    if(f(k, nd->key)  < 0){
-        SplayTreeNode* ret = access_node(f, nd->lchd, k), *tmp;
-        if(nd->lchd != NULL){
-            if(nd->fath != NULL)
-                if(nd->fath->lchd == nd) connectL(nd->fath, nd->lchd);
-                else                     connectR(nd->fath, nd->lchd);
-            else
-                nd->lchd->fath = NULL;
-            tmp = nd->lchd;
-            connectL(nd, tmp->rchd);
-            connectR(tmp, nd);
-        }
-        return ret;
-    }else{
-        SplayTreeNode* ret = access_node(f, nd->rchd, k), *tmp;
-        if(nd->rchd != NULL){
-            if(nd->fath != NULL)
-                if(nd->fath->lchd == nd) connectL(nd->fath, nd->rchd);
-                else                     connectR(nd->fath, nd->rchd);
-            else
-                nd->rchd->fath = NULL;
-            tmp = nd->rchd;
-            connectR(nd, tmp->lchd);
-            connectL(tmp, nd);
-        }
-        return ret;
+
+/************* # access the node by some key **************/
+ctl_priv SplayTreeNode* acces(ctl_spt_cmp f,SplayTreeNode*nd,pcvoid k,int*t){
+    while(1){
+		*t = f(k, nd->key);
+		if     (*t < 0 && nd->lchd != NULL) nd = nd->lchd;
+		else if(*t > 0 && nd->rchd != NULL) nd = nd->rchd;
+		else                                break;
     }
+    return (nd->fath == NULL ? nd : splay(nd));
 }
-static SplayTreeNode* split_node(key_cmp f, SplayTreeNode*  nd, pcvoid k,
-                                 SplayTreeNode** l, SplayTreeNode** r){
-    if(nd == NULL) return (*l = *r = NULL);
-    SplayTreeNode* mid = access_node(f, nd, k);
-    if(mid != NULL){
-        *l = mid;
-        *r = mid->rchd;
-        disconnR(mid);
-        return mid;
+
+/******************* # split & merge **********************/
+ctl_priv SplayTreeNode* split(ctl_spt_cmp f, SplayTreeNode* nd, pcvoid k,
+                              SplayTreeNode** l, SplayTreeNode** r){
+	int ret;
+    nd = acces(f, nd, k, &ret);
+	if(ret >= 0){
+        *l = nd;
+        *r = nd->rchd;
+        disconnR(nd);
     }else{
-        SplayTreeNode* root = nd;
-        while(root->fath != NULL)
-            root = root->fath;
-        if(f(k, root->key) < 0){
-            *l = root->lchd;
-            *r = root;
-            disconnL(root);
+        *l = nd->lchd;
+        *r = nd;
+        disconnL(nd);
+    }
+	return (ret == 0 ? *l : NULL);
+}
+ctl_priv SplayTreeNode* merge(SplayTreeNode* l, SplayTreeNode* r){
+	if(l == NULL) return r;
+	while(l->rchd != NULL) l = l->rchd;
+    if(l->fath != NULL) l = splay(l);
+    connectR(l, r);
+    return l;
+}
+
+/************* #'Splay' the node to the root **************/
+ctl_priv SplayTreeNode* splay(SplayTreeNode* nd){
+    while(nd->fath != NULL){
+        if(nd->fath->fath == NULL){
+            splay_root(nd, nd->fath);
+            nd->fath = NULL;
         }else{
-            *l = root;
-            *r = root->rchd;
-            disconnR(root);
+            SplayTreeNode* f = nd->fath;
+            SplayTreeNode* g = nd->fath->fath;
+            SplayTreeNode* a = nd->fath->fath->fath;
+            if(a != NULL)
+                if(a->lchd == g) connectL(a, nd);
+                else             connectR(a, nd);
+            else                 nd->fath = NULL;
+            if(nd == f->lchd) splay_l(nd, f, g);
+            else              splay_r(nd, f, g);
         }
-        return NULL;
     }
+    return nd;
 }
-static SplayTreeNode* access_max(SplayTreeNode *nd){
-    if(nd == NULL) return NULL;
-    if(nd->rchd != NULL){
-        SplayTreeNode* ret = nd->rchd, *tmp;
-        if(nd->fath != NULL)
-            if(nd->fath->lchd == nd) connectL(nd->fath, nd->rchd);
-            else                     connectR(nd->fath, nd->rchd);
-        else
-            nd->rchd->fath = NULL;
-        tmp = nd->rchd;
-        connectR(nd, tmp->lchd);
-        connectL(tmp, nd);
-        return ret;
+/**** #It's included the case of now->father == root ******/
+ctl_priv void splay_root(SplayTreeNode* m, SplayTreeNode* f){
+    if(f->lchd == m){
+        connectL(f, m->rchd);
+        connectR(m, f      );
     }else{
-        return nd;
+        connectR(f, m->lchd);
+        connectL(m, f      );
     }
 }
-static SplayTreeNode* merge_node(SplayTreeNode* l, SplayTreeNode* r){
-    l = access_max(l);
-    if(l == NULL) return r;
-    connectR(l, r);
-    return l;
+
+/************ #It's include the case of LL, LR ************/
+ctl_priv void splay_l(SplayTreeNode* m, SplayTreeNode* f, SplayTreeNode* g){
+    if(f == g->lchd){
+        connectL(g, f ->rchd);
+        connectL(f, m->rchd);
+        connectR(f, g);
+        connectR(m, f);
+    }else{
+        connectR(g, m->lchd);
+        connectL(f, m->rchd);
+        connectL(m, g);
+        connectR(m, f);
+    }
+}
+
+/************ #It's include the case of RR, RL ************/
+ctl_priv void splay_r(SplayTreeNode* m, SplayTreeNode* f, SplayTreeNode* g){
+    if(f == g->rchd){
+        connectR(g, f->lchd);
+        connectR(f, m->lchd);
+        connectL(f, g);
+        connectL(m, f);
+    }else{
+        connectL(g, m->rchd);
+        connectR(f, m->lchd);
+        connectR(m, g);
+        connectL(m, f);
+    }
+}
+
+/********************* # for debug ************************/
+#include <stdio.h>
+#include <unistd.h>
+ctl_priv void dump_node(SplayTreeNode* now){
+    if(now == NULL) return ;
+    printf("now = (%5.1f, %2d) %lld ", *(double*)now->key, *(int*)now->val, now);
+    if(now->lchd == NULL) printf("lchd = (     NULL) ");
+    else                  printf("lchd = (%5.1f, %2d) ", *(double*)now->lchd->key, *(int*)now->lchd->val);
+    if(now->rchd == NULL) printf("rchd = (     NULL) ");
+    else                  printf("rchd = (%5.1f, %2d) ", *(double*)now->rchd->key, *(int*)now->rchd->val);
+    if(now->fath == NULL) printf("fath = (     NULL) ");
+    else                  printf("fath = (%5.1f, %2d) ", *(double*)now->fath->key, *(int*)now->fath->val);
+    printf("\n");
+    dump_node(now->lchd);
+    dump_node(now->rchd);
+    fflush(stdout);
 }