cppUtility/BPlusTree.hpp at main · 20190511/cppUtility · 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// FOR JH_SQL Project (since 24.02.21 ~) __ Junhyeong(0511)
// B+ Tree Delete Flag -> Projection
#ifndef BPLUSTREE_HPP
#define BPLUSTREE_HPP
#define DEFAULT_NSIZE   5
// key, ptr underflow 기준
#define MINCNT_PTR(_N)  (_N/2 + (_N%2 ? 1 : 0))
#define MINCNT_KEY(_N)  (_N/2 + (_N%2 ? 1 : 0) - 1)


#include <iostream>
#include <cstring>
#include <deque>
using namespace std;


class Bnode {
private:
    friend class BpTree; //Bnode 관리체

    Bnode *parent;   // 부모
    Bnode *prev;     // 왼쪽 형제
    Bnode *next;     // 오른쪽 형제
    deque<Bnode*> ptr;
    deque<string> key;

public:
    Bnode();
    int getPtrSize();
    int getKeySize();
};


class BpTree{
private:
    Bnode* root;
    int nodeCnt;
    int indexCnt;
    int n_size;

//Initalizer
public:
    BpTree();
    BpTree(int nSize);


//in-System Func
private:
    bool    preempt(Bnode* a); // a <-- b 재분배

//Utility
public:
    int     getNodeCnt();
    int     getIndexCnt();
    bool    append(string key);
    void    printAll();
};
/** ---- Implementation ---- **/

// Initializer
Bnode::Bnode() : parent(NULL), prev(NULL), next(NULL) {}
BpTree::BpTree() : nodeCnt(0), indexCnt(0), n_size(DEFAULT_NSIZE) {
    this->root = new Bnode;
}
BpTree::BpTree(int nSize) : nodeCnt(0), indexCnt(0), n_size(nSize) {
    this->root = new Bnode;
}

bool BpTree::preempt(Bnode* a)
{
    //왼쪽 형제 판단
    Bnode* bro = a->prev, *parent = a->parent;
    if (bro && MINCNT_KEY(n_size) < bro->getKeySize()) {
    }

    bro = a->next;
    if (bro && MINCNT_KEY(n_size) < bro->getKeySize()) {

    }
    return false;
}


//Utility Function __
int BpTree::getNodeCnt() { return this->nodeCnt; }
int BpTree::getIndexCnt() { return this->indexCnt; }
int Bnode::getPtrSize() { return (int)this->key.size(); }
int Bnode::getKeySize() { return (int)this->ptr.size(); }

bool BpTree::append(string key) {
    //find curPos
    Bnode* curNode = root;
    int k_idx = 0, p_idx = 0;
    while(k_idx < curNode->getKeySize()) {
        for (k_idx = 0 ; k_idx < (int)curNode->key.size() ; k_idx++) {
            if (curNode->key[k_idx].compare(key) < 0)
                break;
        }

        p_idx = k_idx;
        if (curNode->getPtrSize() < p_idx || !curNode->ptr[p_idx])
            break;
        curNode = curNode->ptr[p_idx];
        k_idx = p_idx = 0;
    }

    cout<<k_idx<<endl;
    curNode->key.insert(curNode->key.begin() + k_idx, key);
    this->nodeCnt++;
    return true;
}
void BpTree::printAll() {

}
/*
bool Bnode::preempt(pair<deque<int>, deque<Bnode*>> keyAndPtr)
{
    deque<int> keys = keyAndPtr.first;
    deque<Bnode*> ptrs = keyAndPtr.second;
    this->__curPtrPos = this->__curKeyPos = 0 ;
    memset(this->ptr, 0, sizeof(this->ptr));
    memset(this->key, 0, sizeof(this->key));

    for (this->__curKeyPos = 0 ; !keys.empty() ; this->__curKeyPos++) {
        this->key[__curKeyPos] = keys.front();
        keys.pop_front();
    }

    for (this->__curPtrPos = 0 ; !ptrs.empty() ; this->__curPtrPos++) {
        this->ptr[__curPtrPos] = ptrs.front();
        ptrs.pop_front();
    }
}
*/
#endif