aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorcathook <cat.hook31894@gmail.com>2013-12-17 03:12:47 +0800
committercathook <cat.hook31894@gmail.com>2013-12-17 03:18:38 +0800
commit176ecbf10b9d089094ca35e46a3d48f898278aab (patch)
tree0632f7f0ebbce09b2b2e7fe3e8d316fcb7f05a73
parent3e351dcd02c7da9b1c997b470c63cfba60d97278 (diff)
downloadctl-176ecbf10b9d089094ca35e46a3d48f898278aab.tar.gz
ctl-176ecbf10b9d089094ca35e46a3d48f898278aab.tar.zst
ctl-176ecbf10b9d089094ca35e46a3d48f898278aab.zip
init
Diffstat
-rw-r--r--inc/sptree.h47
-rw-r--r--src/sptree.c240
2 files changed, 287 insertions, 0 deletions
diff --git a/inc/sptree.h b/inc/sptree.h
new file mode 100644
index 0000000..dc80d15
--- /dev/null
+++ b/inc/sptree.h
@@ -0,0 +1,47 @@
+#ifndef __SPLAY_TREE__
+#define __SPLAY_TREE__
+
+#include "utility.h"
+
+typedef cmp_func key_cmp;
+
+pvoid ctl_sptree_initX(ppvoid sp, uint k_size, uint v_size, key_cmp f);
+pvoid ctl_sptree_freeX(ppvoid sp);
+
+int ctl_sptree_isEmptyX (ppcvoid sp);
+
+uint ctl_sptree_getKeySizeX(ppcvoid sp);
+uint ctl_sptree_getValSizeX(ppcvoid sp);
+
+pvoid ctl_sptree_findX (ppvoid sp, pcvoid key);
+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_free(A) ctl_sptree_freeX(ppVoid(A))
+
+#define ctl_sptree_isEmpty (A) ctl_sptree_isEmptyX (ppcVoid(A))
+#define ctl_sptree_getKeySize(A) ctl_sptree_getKeySizeX(ppcVoid(A))
+#define ctl_sptree_getValSize(A) ctl_sptree_getValSizeX(ppcVoid(A))
+
+#define ctl_sptree_find (A,B) ctl_sptree_findX (ppVoid(A),pcVoid(B))
+#define ctl_sptree_add (A,B,C) ctl_sptree_addX (ppVoid(A),pcVoid(B),pVoid(C))
+#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_clear(A) ctl_sptree_clearX(ppVoid(A))
+//#define ctl_sptree_copy(A,B) ctl_sptree_copyX (ppVoid(A),ppVoid(B))
+
+#endif /* __SPLAY_TREE__ */
diff --git a/src/sptree.c b/src/sptree.c
new file mode 100644
index 0000000..9401bd4
--- /dev/null
+++ b/src/sptree.c
@@ -0,0 +1,240 @@
+#include "sptree.h"
+
+#include <string.h>
+
+struct StructSplayTree;
+struct StructSplayTreeNode;
+
+struct StructSplayTree{
+ uint key_size;
+ uint val_size;
+ struct StructSplayTreeNode* root;
+ key_cmp func;
+};
+struct StructSpalyTreeNode{
+ struct StructSplayTreeNode* lchd;
+ struct StructSplayTreeNode* rchd;
+ struct StructSplayTreeNode* fath;
+ pcvoid* key;
+ pvoid* val;
+};
+
+typedef struct StructSpalyTree SplayTree;
+typedef struct StructSpalyTreeNode SplayTreeNode;
+
+/******************* static functions *********************/
+static void delete_dfs(SplayTreeNode* nd);
+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(key_cmp f, SplayTreeNode* l, SplayTreeNode* r);
+
+#define getHeader(A) ((SplayTree*)(A))
+#define getSize(A) (sizeof(StructSplayTreeNode)+(A)->key_size+(A)->val_size)
+#define connectL(A,B) \
+ do{\
+ if((A) != NULL) (A)->lchd = (B);\
+ if((B) != NULL) (B)->fath = (A);\
+ }while(0)
+#define connectR(A,B) \
+ do{\
+ if((A) != NULL) (A)->rchd = (B);\
+ if((B) != NULL) (B)->fath = (A);\
+ }while(0)
+#define disconnL(A) \
+ do{\
+ if((A)->lchd != NULL) (A)->lchd->fath = NULL;\
+ (A)->lchd = NULL;\
+ }while(0)
+#define disconnR(A) \
+ do{\
+ if((A)->rchd != NULL) (A)->rchd->fath = NULL;\
+ (A)->rchd = NULL;\
+ }while(0)
+
+/*************** constructure / destructure ***************/
+pvoid ctl_sptree_initX(ppvoid sp, uint k_size, uint v_size, key_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;
+ return pVoid(head);
+}
+pvoid ctl_sptree_freeX(ppvoid sp){
+ SplayTree* head = (SplayTree*)*sp;
+ if(head->root != NULL) delete_dfs(head->root);
+ free(head);
+ *sp = NULL;
+ return NULL;
+}
+
+/****************** get/is ??? method *********************/
+int ctl_sptree_isEmptyX(ppcvoid sp){
+ return (getHeader(*sp)->root == NULL ? 0 : 1);
+}
+uint ctl_sptree_getKeySizeX(ppcvoid sp){
+ return getHeader(*sp)->key_size;
+}
+uint ctl_sptree_getValSizeX(ppcvoid sp){
+ return getHeader(*sp)->val_size;
+}
+
+/******************* splay tree's methods *****************/
+pvoid ctl_sptree_findX(ppvoid sp, pcvoid key){
+ SplayTree* head = getHeader(*sp);
+ SplayTreeNode* nd = access_node(head->root, key, head->func);
+ if(head->root != NULL)
+ while(head->root->fath != NULL)
+ head->root = head->root->fath;
+ if(nd == NULL) return NULL;
+ return getHeader(*sp)->root->val;
+}
+pvoid ctl_sptree_addX(ppvoid sp, pcvoid key, pvoid val){
+ SplayTree* head = getHeader(*sp);
+ SplayTreeNode* lft;
+ SplayTreeNode* rgt;
+ SplayTreeNode* mid = split_node(head->f, 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));
+ memcpy(mid->key, 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);
+ }
+ return mid->val;
+}
+void ctl_sptree_delX(ppvoid sp, pcvoid key){
+ SplayTree* head = getHeader(*sp);
+ SplayTreeNode* left;
+ SplayTreeNode* righ;
+ access_node(head->func, head, 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);
+ free(head->root);
+ head->root = merge_node(left, righ);
+}
+
+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->f, head->root, key, &left, &righ);
+ getHeader(*r)->root = left;
+ getHeader(*l)->root = righ;
+ head->root = NULL;
+ ctl_sptree_freeX(sp);
+}
+pvoid ctl_sptree_mergeX(ppvoid sp1, ppvoid sp2){
+ SplayTree* head1 = getHeader(*sp1);
+ SplayTree* head2 = getHeader(*sp2);
+ head1->root = merge_node(head1->root, head2->root);
+ head2->root = NULL;
+ ctl_sptree_freeX(sp2);
+ *sp1 = NULL;
+ return pVoid(head);
+}
+
+void ctl_sptree_clearX(ppvoid* sp){
+ if(getHeader(*sp)->root != NULL)
+ delete_dfs(getHeader(*sp)->root);
+ getHeader(*sp)->root = NULL;
+}
+
+
+/****************** static functions **********************/
+static void delete_dfs(SplayTreeNode* nd){
+ if(nd->lchd != NULL) delete_dfs(nd->lchd);
+ if(nd->rchd != NULL) delete_dfs(nd->rchd);
+ free(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);
+ 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;
+ connectL(nd, nd->lchd->rchd);
+ connectR(nd->lchd, nd);
+ }
+ return ret;
+ }else{
+ SplayTreeNode* ret = access_node(f, nd->rchd, k);
+ 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;
+ connectR(nd, nd->rchd->lchd);
+ connectL(nd->rchd, nd);
+ }
+ return ret;
+ }
+}
+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;
+ }else{
+ SplayTreeNode* root = nd;
+ while(root->fath != NULL)
+ root = root->fath;
+ if(f(k, root->key) < 0){
+ *l = root->lchd;
+ *r = root;
+ disconnL(root);
+ }else{
+ *l = root;
+ *r = root->rchd;
+ disconnR(root);
+ }
+ return NULL;
+ }
+}
+static SplayTreeNode* access_max(SplayTreeNode *nd){
+ if(nd == NULL) return NULL;
+ if(nd->rchd != NULL){
+ SplayTreeNode* ret = nd->rchd;
+ 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;
+ connectR(nd, nd->rchd->lchd);
+ connectL(nd->rchd, nd);
+ return ret;
+ }else{
+ return nd;
+ }
+}
+static SplayTreeNode* merge_node(key_cmp f,
+ SplayTreeNode* l, SplayTreeNode* r){
+ l = access_max(l);
+ if(l == NULL) return r;
+ connectR(l, r);
+ return l;
+}
generated by cgit (git 2.34.1) at 2025-05-30 10:52:03 +0800