Binary Search Tree, self-balancing.

main.c

/*
 * Copyright (c) 2016 Simon Schmidt
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"

static struct bintree_node* newelem(){
	struct bintree_node* res;
	res = malloc(sizeof(struct bintree_node));
	if(!res)return 0;
	memset(res,0,sizeof(struct bintree_node));
	return res;
}
void bt_clear(struct bintree_node* n){
	n->left = 0;
	n->right = 0;
}

static void btwrite_node(FILE* f, struct bintree_node* src, const char* nam, struct bintree_node* n){
	fprintf(f,"N%p [label=\"%p\"];\n",n,n->K);
	if(src) fprintf(f,"N%p -> N%p [label=%s];\n",src,n,nam);
	if(n->left) btwrite_node(f,n,"left" ,n->left);
	if(n->right)btwrite_node(f,n,"right",n->right);
}
static void btwrite_graph(FILE* f, struct bintree_node* n){
	fprintf(f,"digraph G%p{\n",n);
	if(n)btwrite_node(f,0,"",n);
	fprintf(f,"}\n");
}


int main(){
	FILE * dot;
	int i,j;
	uintptr_t P;
	struct bintree_node* tree = 0;
	struct bintree_node* elem = 0;
	struct bintree_node** res;
	
	for(i=0;i<100;++i){
		if(!elem){
			//printf("newelem\n");
			elem = newelem();
		}
		elem->K = random();//i;
		//elem->K = i;
		//printf("begin bt_insert\n");
		bt_insert(&tree,&elem);
		//printf("end bt_insert\n");
		//if(elem)free(elem);
	}
	if(elem)free(elem);
	elem = 0;
	
	for(j=0;j<10;++j){
		P = random();
		res = bt_ceiling(&tree,P);
		if(res)if(*res) {
			printf("found %d -> %d\n",P,(*res)->K);
		}
		if(!res){
			printf("not found %d\n",P);
		}
	}
	/*
	for(j=0;j<10000;++j){
		elem = 0;
		//printf("Tree %p\n",tree);
		bt_remove(&tree,&elem);
		//printf("Elem %p\n",elem);
		if(elem){
			bt_clear(elem);
			bt_insert(&tree,&elem);
		}
	}//*/
	
	/*
	if(dot = fopen("dump","w")) {
		btwrite_graph(dot,tree);
		fclose(dot);
	}// */
	
	//printf("rand = %d\n",random());
	return 0;
}

tree.c

/*
 * Copyright (c) 2016 Simon Schmidt
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#include "tree.h"

#define m64(i) ((i)&63)

static uint32_t bt_max(uint32_t a,uint32_t b){
	return a>b?a:b;
}

static uint32_t bt_depth(struct bintree_node *node){
	if(node)return node->depth;
	return 0;
}

static uint32_t bt_calcdepth(struct bintree_node *node){
	if(!node) return;
	node->depth = bt_max(bt_depth(node->left),bt_depth(node->right))+1;
}

static void bt_rotleft(struct bintree_node **node){
	struct bintree_node * h = *node;
	struct bintree_node * x = h->right;
	h->right = x->left;
	x->left  = h;
	bt_calcdepth(h);
	bt_calcdepth(x);
	*node    = x;
}

static void bt_rotright(struct bintree_node **node){
	struct bintree_node * h = *node;
	struct bintree_node * x = h->left;
	h->left  = x->right;
	x->right = h;
	bt_calcdepth(h);
	bt_calcdepth(x);
	*node    = x;
}

/* balance a node, and calculate it's depth. */
static void bt_balance(struct bintree_node **node){
	struct bintree_node * h = *node;
	if(!h)return;
	uint32_t l,r;
	l = bt_depth(h->left);
	r = bt_depth(h->right);
	if(l>r && ((l-r)>1))      bt_rotright(node);
	else if(r>l && ((r-l)>1)) bt_rotleft (node);
	else bt_calcdepth(h);
}

void bt_insert(struct bintree_node **node,struct bintree_node **it){
	struct bintree_node *n;
	uintptr_t K = (*it)->K;
	uintptr_t N;
	struct bintree_node **narr[64];
	int i;
	for(i=0;i<64;++i)narr[i]=0;
	narr[m64(i)]=node;
	
	for(;;){
		n = *node;
		if(!n){
			*node = *it;
			*it = 0;
			break;
		}
		N = n->K;
		if(K<N){
			node = &(n->left);
			narr[m64(++i)]=node;
			continue;
		}
		if(N<K){
			node = &(n->right);
			narr[m64(++i)]=node;
			continue;
		}
		n->V = (*it)->V;
		break;
	}
	/* Backtracking. */
	for(;narr[m64(i)];--i){
		bt_balance(narr[m64(i)]);
		narr[m64(i)] = 0;
	}
}

void bt_remove(struct bintree_node **node,struct bintree_node **it){
	uint32_t l,r;
	struct bintree_node *n;
	struct bintree_node **narr[64];
	int i;
	for(i=0;i<64;++i)narr[i]=0;
	narr[m64(i)]=node;
	
	for(;;){
		n = *node;
		if(!n) break;
		if(!(n->left)){
			*it = n;
			*node = n->right;
			break;
		}
		if(!(n->right)){
			*it = n;
			*node = n->left;
			break;
		}
		l = bt_depth(n->left );
		r = bt_depth(n->right);
		if(l<=r){
			bt_rotleft (node);
			node = &((*node)->left);
			narr[m64(++i)]=node;
		}else{
			bt_rotright(node);
			node = &((*node)->right);
			narr[m64(++i)]=node;
		}
	}
	
	for(;narr[m64(i)];--i){
		if(*narr[m64(i)])bt_balance(narr[m64(i)]);
		narr[m64(i)] = 0;
	}
}

struct bintree_node** bt_lookup(struct bintree_node **node,uintptr_t K){
	struct bintree_node* n;
	uintptr_t N;
	for(;;){
		n = *node;
		if(!n)return 0;
		N = n->K;
		if(K<N){
			node = &(n->left);
			continue;
		}
		if(N<K){
			node = &(n->right);
			continue;
		}
		return node;
	}
	return 0;
}

struct bintree_node** bt_floor(struct bintree_node **node,uintptr_t K){
	struct bintree_node* n;
	struct bintree_node** lowermost = 0;
	uintptr_t N;
	for(;;){
		n = *node;
		if(!n)return lowermost;
		N = n->K;
		if(K<N){
			node = &(n->left);
			continue;
		}
		if(N<K){
			lowermost = node;
			node = &(n->right);
			continue;
		}
		return node;
	}
	return lowermost;
}

struct bintree_node** bt_ceiling(struct bintree_node **node,uintptr_t K){
	struct bintree_node* n;
	struct bintree_node** uppermost = 0;
	uintptr_t N;
	for(;;){
		n = *node;
		if(!n)return uppermost;
		N = n->K;
		if(K<N){
			uppermost = node;
			node = &(n->left);
			continue;
		}
		if(N<K){
			node = &(n->right);
			continue;
		}
		return node;
	}
	return uppermost;
}

tree.h

/*
 * Copyright (c) 2016 Simon Schmidt
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#pragma once
#include <stdint.h>

struct bintree_node  {
	uintptr_t K;
	void*     V;
	struct bintree_node* left ;
	struct bintree_node* right;
	uint32_t  depth;
};

void bt_insert(struct bintree_node **node,struct bintree_node **it);
void bt_remove(struct bintree_node **node,struct bintree_node **it);
struct bintree_node** bt_lookup(struct bintree_node **node,uintptr_t K);
struct bintree_node** bt_floor(struct bintree_node **node,uintptr_t K);
struct bintree_node** bt_ceiling(struct bintree_node **node,uintptr_t K);

z-addenda.txt

/* fancy rotleft */
static void bt_balleft(struct bintree_node **node){
	struct bintree_node * h = *node;
	struct bintree_node * x = h->right;
	if(bt_depth(x->left) > bt_depth(x->right))
		bt_rotright(&h->right);
	bt_rotleft(node);
}

/* fancy rotright */
static void bt_balright(struct bintree_node **node){
	struct bintree_node * h = *node;
	struct bintree_node * x = h->left;
	if(bt_depth(x->right) > bt_depth(x->left))
		bt_rotleft(&h->right);
	bt_rotright(node);
}