master

分支 (1)

管理

管理

master

kvstore
/
bTree.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>

#include <pthread.h>

using namespace std;

#define m 4  //树的阶
#define min ((m+1)/2-1)
#define MAX_KEY_LEN	128
#define MAX_VALUE_LEN	512


typedef struct b_node
{

	char key[m + 1][MAX_KEY_LEN];
	char value[m + 1][MAX_VALUE_LEN];

	struct b_node* child[m + 1];
	struct b_node* parent;
	int key_num;
}bTree_node;

typedef struct tree
{
	bTree_node* root;
	long long key_num;
	pthread_mutex_t lock;
}bTree;

typedef struct
{
	bTree_node* des;
	int index;
	bool tag;
}Result;

void split(bTree_node*& left, int sp_index, bTree_node*& right);
void Restore(bTree& tree, bTree_node*& des);
void InsertBTree(bTree& tree, int key, bTree_node* des, int index);


int search(bTree_node* node, const char* key)
{
	int index = 1;

	while (strcmp(node->key[index], key) < 0 && index <= node->key_num)
	{
		index++;
	}
	return index;
}

void newRoot(bTree& tree, const char* key, const char* value, bTree_node* left, bTree_node* right)
{
	tree.root = (bTree_node*)malloc(sizeof(bTree_node));
	tree.root->parent = NULL;

	strncpy(tree.root->key[1], key, MAX_KEY_LEN);
	strncpy(tree.root->value[1], value, MAX_VALUE_LEN);

	tree.root->key_num = 1;
	tree.root->child[0] = left;
	tree.root->child[1] = right;
	if (left)
	{
		left->parent = tree.root;
	}
	if (right)
	{
		right->parent = tree.root;
	}
}


void Insert(bTree_node*& des, int index, const char* key,const char* value, bTree_node* child)
{
	int n = des->key_num;
	for (int i = n; i >= index; i--)
	{
		strncpy(des->key[i + 1], des->key[i],MAX_KEY_LEN);
		strncpy(des->value[i + 1], des->value[i], MAX_VALUE_LEN);
		des->child[i + 1] = des->child[i];
	}
	strncpy(des->key[index], key, MAX_KEY_LEN);
	strncpy(des->value[index], value, MAX_VALUE_LEN);
	des->child[index] = child;
	if (child)
	{
		child->parent = des;
	}
	des->key_num++;
}

void split(bTree_node*& left, int sp_index, bTree_node*& right)
{
	int n = left->key_num;
	right = (bTree_node*)malloc(sizeof(bTree_node));
	right->child[0] = left->child[sp_index];

	for (int i = 1, j = sp_index + 1; j <= n; j++, i++)
	{
		strncpy(right->key[i], left->key[j], MAX_KEY_LEN);
		strncpy(right->value[i], left->value[j], MAX_VALUE_LEN);

		right->child[i] = left->child[j];
	}
	right->key_num = n - sp_index;
	left->key_num = sp_index - 1;
	right->parent = left->parent;
	for (int i = 0; i <= right->key_num; i++)
	{
		if (right->child[i] != NULL)
		{
			right->child[i]->parent = right;
		}
	}
}


void InsertBTree(bTree& tree, const char* sour_key, const char* sour_value, bTree_node* des, int index)
{
	char key[MAX_KEY_LEN];
	char value[MAX_VALUE_LEN];
	strncpy(key, sour_key, MAX_KEY_LEN);
	strncpy(value, sour_value, MAX_VALUE_LEN);
	if (tree.root == NULL)
	{
		newRoot(tree, key,value, NULL, NULL);
		//pthread_mutex_lock(&tree.lock);
		tree.key_num++;
		//pthread_mutex_unlock(&tree.lock);
		return;
	}

	int split_des;
	int newroot = 0;
	int finish = 0;
	bTree_node* child = NULL;
	while (finish == 0 && newroot == 0)
	{
		Insert(des, index, key,value, child);
		if (des->key_num < m)
		{
			finish = 1;
		}
		else
		{
			split_des = (m + 1) / 2;
			split(des, split_des, child);

			//key = des->key[split_des];
			strncpy(key, des->key[split_des], MAX_KEY_LEN);
			strncpy(value, des->value[split_des], MAX_VALUE_LEN);

			if (des->parent == NULL)
			{
				newroot = 1;
			}
			else
			{
				des = des->parent;
				index = search(des, key);
			}
		}

	}
	if (newroot == 1)
	{
		newRoot(tree, key,value, des, child);
	}

	//pthread_mutex_lock(&tree.lock);
	tree.key_num++;
	//pthread_mutex_unlock(&tree.lock);
}


bTree_node* search_node(bTree tree, const char* key)
{
	int index = 0;
	bool find = false;
	bTree_node* q = tree.root;
	bTree_node* parent = NULL;
	while (q != NULL && find == false)
	{
		index = search(q, key);
		if (strcmp(q->key[index], key) == 0 && index <= q->key_num)
		{
			find = true;
		}
		else
		{
			parent = q;
			q = q->child[index - 1];
		}
	}
	if (find)
	{
		return q;
	}
	else
	{
		return NULL;
	}
}


void SearchNode(bTree tree, const char* key, Result& re)
{
	int index = 0;
	bool find = false;
	bTree_node* q = tree.root;
	bTree_node* parent = NULL;
	while (q != NULL && find == false)
	{
		index = search(q, key);
		if (strcmp(q->key[index],key) == 0 && index <= q->key_num)
		{
			find = true;
		}
		else
		{
			parent = q;
			q = q->child[index - 1];
		}
	}
	if (find)
	{
		re.tag = true;
		re.index = index;
		re.des = q;
	}
	else
	{
		re.tag = false;
		re.index = index;
		re.des = parent;
	}
}

void printfBTree(bTree_node* t, int tab)
{
	if (t == NULL)
	{
		return;
	}
	int i;
	for (i = 1; i <= tab; i++)
	{
		printf("	");
	}
	for (i = 1; i <= t->key_num; i++)
	{
		printf("%s:%s ", t->key[i],t->value[i]);
	}
	printf("\n");
	for (i = 0; i <= t->key_num; i++)
	{
		printfBTree(t->child[i], tab + 1);
	}
}


void insertOperation(bTree& tree)
{
	string key, value;
	Result r;
	int i = 0;
	while (i < 14)
	{
		printf("输入要插入的key:value\n");

		cin >> key >> value;
		cout << key << "  " << value << endl;
		SearchNode(tree, key.c_str(), r);
		if (r.tag == true)
		{
			printf("数据重复\n");
			continue;
		}

		InsertBTree(tree, key.c_str(), value.c_str(), r.des, r.index);
		printf("插入成功");
		printf("----------------------------------\n");
		printfBTree(tree.root, 1);
		printf("----------------------------------\n");
		i++;
	}
}

bTree_node* successor(bTree_node* node, int index)
{
	bTree_node* source = node;
	if (node == NULL) {
		return node;
	}
	node = node->child[index];
	while (node->child[0] != NULL)
	{
		node = node->child[0];
	}
	strncpy(source->key[index], node->key[1], MAX_KEY_LEN);
	strncpy(source->value[index], node->value[1], MAX_VALUE_LEN);


	return node;
}

void Remove(bTree_node*& des, int index)
{
	int n = des->key_num;
	for (int i = index; i < n; i++)
	{
		strncpy(des->key[i], des->key[i + 1], MAX_KEY_LEN);
		strncpy(des->value[i], des->value[i + 1], MAX_VALUE_LEN);
		//des->key[i] = des->key[i + 1];
		des->child[i] = des->child[i + 1];
	}
	des->key_num--;
}

void BorrowFromBro(bTree_node*& p, bTree_node*& lbro, bTree_node*& rbro, bTree_node*& parent, int i)
{
	if (lbro != NULL && lbro->key_num > min)
	{
		for (int i = p->key_num + 1; i > 0; i--)
		{
			if (i > 1)
			{
				strncpy(p->key[i], p->key[i - 1], MAX_KEY_LEN);
				strncpy(p->value[i], p->value[i - 1], MAX_VALUE_LEN);
				//p->key[i] = p->key[i - 1];
			}
			p->child[i] = p->child[i - 1];
		}
		p->child[0] = lbro->child[lbro->key_num];
		if (p->child[0] != NULL)
		{
			p->child[0]->parent = p;
		}
		lbro->child[lbro->key_num] = NULL;
		strncpy(p->key[1], parent->key[i],MAX_KEY_LEN);
		strncpy(p->value[1], parent->value[i], MAX_VALUE_LEN);
		//p->key[1] = parent->key[i];
		strncpy(parent->key[i], lbro->key[lbro->key_num], MAX_KEY_LEN);
		strncpy(parent->value[i], lbro->value[lbro->key_num], MAX_VALUE_LEN);
		//parent->key[i] = lbro->key[lbro->key_num];
		lbro->key_num--;
		p->key_num++;
	}
	else
	{
		p->key_num++;
		strncpy(p->key[p->key_num], parent->key[i + 1], MAX_KEY_LEN);
		strncpy(p->value[p->key_num], parent->value[i + 1], MAX_VALUE_LEN);

		//p->key[p->key_num] = parent->key[i + 1];
		strncpy(parent->key[i + 1], rbro->key[1], MAX_KEY_LEN);
		strncpy(parent->value[i + 1], rbro->value[1] , MAX_VALUE_LEN);
		//parent->key[i + 1] = rbro->key[1];

		p->child[p->key_num] = rbro->child[0];
		if (p->child[p->key_num] != NULL)
		{
			p->child[p->key_num]->parent = p;
		}

		for (int i = 0; i < rbro->key_num; i++)
		{
			if (i > 0)
			{
				strncpy(rbro->key[i], rbro->key[i + 1], MAX_KEY_LEN);
				strncpy(rbro->value[i], rbro->value[i + 1], MAX_VALUE_LEN);

				//rbro->key[i] = rbro->key[i + 1];
			}
			rbro->child[i] = rbro->child[i + 1];
		}
		rbro->child[rbro->key_num] = NULL;
		rbro->key_num--;
	}
}


void mergeBro(bTree_node*& des, bTree_node*& lbro, bTree_node*& parent, int index, bTree& tree)
{
	strncpy(lbro->key[lbro->key_num + 1], parent->key[index], MAX_KEY_LEN);
	strncpy(lbro->value[lbro->key_num + 1], parent->value[index], MAX_VALUE_LEN);
	//lbro->key[lbro->key_num + 1] = parent->key[index];
	lbro->child[lbro->key_num + 1] = des->child[0];
	if (lbro->child[lbro->key_num + 1] != NULL)
	{
		lbro->child[lbro->key_num + 1]->parent = lbro;
	}
	lbro->key_num++;

	for (int i = 1; i <= des->key_num; i++)
	{
		strncpy(lbro->key[lbro->key_num + i], des->key[i], MAX_KEY_LEN);
		strncpy(lbro->value[lbro->key_num + i], des->value[i], MAX_VALUE_LEN);
		//lbro->key[lbro->key_num + i] = des->key[i];
		lbro->child[lbro->key_num + i] = des->child[i];
		if (lbro->child[lbro->key_num + i] != NULL)
		{
			lbro->child[lbro->key_num + i]->parent = lbro;
		}
	}
	lbro->key_num += des->key_num;

	parent->child[index] = NULL;
	free(des);
	des = NULL;

	for (int j = index; j < parent->key_num; j++)
	{
		parent->child[j] = parent->child[j + 1];
		//parent->key[j] = parent->key[j + 1];
		strncpy(parent->key[j], parent->key[j + 1], MAX_KEY_LEN);
		strncpy(parent->value[j], parent->value[j + 1], MAX_VALUE_LEN);
	}
	parent->key_num--;

	if (parent == tree.root)
	{
		if (parent->key_num == 0)
		{
			for (int j = 0; j <= parent->key_num + 1; j++)
			{
				if (parent->child[j] != NULL)
				{
					tree.root = parent->child[j];
					tree.root->parent = NULL;
					break;
				}
			}
		}
	}
	else
	{
		if (parent->key_num < min)
		{
			Restore(tree, parent);
		}
	}
}


void Restore(bTree& tree, bTree_node*& des)
{
	bTree_node* parent = des->parent, * lbro, * rbro;
	int i;
	for (i = 0; i <= parent->key_num; i++)
	{
		if (parent->child[i] == des)
			break;
	}
	if (i > 0)
	{
		lbro = parent->child[i - 1];
	}
	else
	{
		lbro = NULL;
	}
	if (i < parent->key_num)
	{
		rbro = parent->child[i + 1];
	}
	else
	{
		rbro = NULL;
	}
	if ((lbro != NULL && lbro->key_num > min) || (rbro != NULL && rbro->key_num > min))
	{
		BorrowFromBro(des, lbro, rbro, parent, i);
	}
	else
	{
		if (lbro != NULL)
		{
			mergeBro(des, lbro, parent, i, tree);
		}
		else
		{
			i++;
			mergeBro(rbro, des, parent, i, tree);
		}
	}

}


void DeleteBTree(bTree& tree, bTree_node* des, int index)
{
	if (des->child[index] != NULL)
	{
		des = successor(des, index);
		index = 1;
	}

	Remove(des, index);
	if (des->parent == NULL && des->key_num == 0)
	{
		tree.root = NULL;
	}
	if (des->parent != NULL && des->key_num < min)
	{
		Restore(tree, des);
	}
}


void deleteOperation(bTree& tree)
{
	string key, value;
	Result r;
	int i = 0;
	while (i < 14)
	{
		printf("输入要插入的key:value\n");

		cin >> key >> value;
		cout << key << "  " << value << endl;
		SearchNode(tree, key.c_str(), r);
		if (r.tag == false)
		{
			printf("数据不存在\n");
			continue;
		}
		DeleteBTree(tree, r.des, r.index);
		printf("删除成功");
		printf("----------------------------------\n");
		printfBTree(tree.root, 1);
		printf("----------------------------------\n");

		i++;
	}
}


int put_kv_btree(bTree& tree,const char* key,const char* value) {

	if (!key || !value) return -1;

	Result r;
	SearchNode(tree, key,  r);
	//btree_node* node = btree_search(tree, key);
	if (r.tag == true)
	{
		// key exist;
		return 1;
	}
	//if (node != tree->nil) { // key exist;
	//	return 1;
	//}

	InsertBTree(tree, key, value, r.des, r.index);


	return 0;

}

char* get_kv_btree(bTree& tree,const char* key) { //

	if (!tree.root || !key) return NULL;

	Result r;
	SearchNode(tree, key, r);

	if (r.tag == false)
	{
		return NULL;
	}
	else
	{
		return r.des->value[r.index];
	}
}

int count_kv_btree(bTree& tree) {
	return tree.key_num;
}

int exist_kv_btree(bTree& tree, const char* key) {

	if (!tree.root || !key) return -1;

	Result r;
	SearchNode(tree, key, r);
	if (r.tag == true)
	{
		return 1;
	}

	return 0;
}

int delete_kv_btree(bTree& tree, const char* key) {

	if (!tree.root || !key) return -1;

	Result r;
	SearchNode(tree, key, r);
	if (r.tag==false) { // key no exist;
		return 1;
	}

	//pthread_mutex_lock(&tree.lock);

	DeleteBTree(tree, r.des, r.index);
	//pthread_mutex_unlock(&tree.lock);

	return 0;
}

#if 0

int main()
{
	bTree tree;
	tree.root = NULL;
	tree.key_num = 0;

	const char* k1 = "Name";
	const char* v1 = "King";
	int res = put_kv_btree(tree, k1, v1);
	printf("---> traversal\n");
	printfBTree(tree.root, 1);
	printf("<--- traversal\n\n");

	const char* k2 = "Content-Type";
	const char* v2 = "text/html;charset=utf-8";
	res = put_kv_btree(tree, k2, v2);
	printf("---> traversal\n");
	printfBTree(tree.root, 1);
	printf("<--- traversal\n\n");

	const char* k3 = "Server";
	const char* v3 = "Nginx";
	res = put_kv_btree(tree, k3, v3);
	printf("res: %d\n\n", res);

	printf("\n---> traversal\n");
	printfBTree(tree.root, 1);
	printf("<--- traversal\n\n");

	res = put_kv_btree(tree, k1, v1);
	printf("res: %d\n\n", res);

	printf("---> traversal\n");
	printfBTree(tree.root, 1);
	printf("<--- traversal\n\n");
	printf("k4\n");
	const char* k4 = "Connection";
	const char* v4 = "keep-alive";
	res = put_kv_btree(tree, k4, v4);
	printf("res: %d\n\n", res);

	const char* k5 = "Pragma";
	const char* v5 = "no-cache";
	res = put_kv_btree(tree, k5, v5);
	printf("res: %d\n\n", res);

	const char* k6 = "Content-Encoding";
	const char* v6 = "gzip";
	res = put_kv_btree(tree, k6, v6);
	printf("res: %d\n\n", res);

	printf("---> traversal\n");
	printfBTree(tree.root, 1);
	printf("<--- traversal\n\n");

	char* a = get_kv_btree(tree, k6);
	printf(a);
	cout << endl;
	//int i = count_kv_btree(tree);
	//printf("%d",i);

	int i = exist_kv_btree(tree, "aaa");
	printf("%d", i);

	delete_kv_btree(tree, k6);
	printf("---> traversal\n");
	printfBTree(tree.root, 1);
	printf("<--- traversal\n\n");

}

#endif


/*
ni hao
ha ha
ni hao
ha ha
jiu shi
shuo la
nihao ya
nihao ya
zijinlu zjl
dj dj
shen me
shen me
na dao
zhe yang
wen ti
ye jiu
tian cai
ni tian


*/