LockFreeBtree/treeAlgorithm.h at master · sanastas/LockFreeBtree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#ifndef _TREE_ALGORITHM_H_FILE
#define _TREE_ALGORITHM_H_FILE


#include "entry.h"
#include "chunk.h"
#include "globals.h"
#include "chunkAlgorithm.h"


/*****************************************************************************
	searching
*****************************************************************************/
Chunk* findLeaf(Btree* btree, ThreadGlobals* tg, int key);
Chunk* findParent(Btree* btree, ThreadGlobals* tg, int key, Chunk* sonChunk,
	Entry** parentEnt, Entry** neighborEnt);
/*****************************************************************************
	enslave
*****************************************************************************/
Chunk* findMergeSlave(Btree* btree, ThreadGlobals* tg, Chunk* master);
Bool setSlave(Btree* btree, ThreadGlobals* tg, Chunk* master, Chunk* slave, int masterKey, int slaveKey);
/*****************************************************************************
	balancing
*****************************************************************************/
void split(Btree* btree, ThreadGlobals* tg, int sepKey, Chunk* chunk);
void merge(Btree* btree, ThreadGlobals* tg, Chunk* master);
void borrow(Btree* btree, ThreadGlobals* tg, Chunk* master, int sepKey);
void splitRoot(Btree* btree, ThreadGlobals* tg, Chunk* root, int sepKey);
void mergeRoot(Btree* btree, ThreadGlobals* tg, Chunk* root, Chunk* possibleNewRoot, int key, Data data, Chunk* master);
/*****************************************************************************
	synchronizing main structure
*****************************************************************************/
void callForUpdate(Btree* btree, ThreadGlobals* tg, RecoveryType recovType, Chunk* chunk, int sepKey);
void helpInfant(Btree* btree, ThreadGlobals* tg, Chunk* chunk);
void addRootSons(Btree* btree, Chunk* newRoot, int sepKey1, Chunk* newLow, int sepKey2, Chunk* newHigh);
/*****************************************************************************
	debug and test
*****************************************************************************/
void printTree(Btree* btree);
void printTree1(Btree* btree, Chunk* head, const char* tabs);
int TreeSize(Btree* btree);


#endif //_TREE_ALGORITHM_H_FILE