summaryrefslogtreecommitdiff
path: root/sw/source/core/bastyp/bplustree.cxx
blob: 93ecf1fc383d45ca5655147df7757ef558ffab04 (plain)
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
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
 * This file is part of the LibreOffice project.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#include <bplustree.hxx>

#include <cassert>

/** B+ tree node implementation.

It has to be able to act as an internal node, as well as the leaf node.
*/
template < class Key, class Value >
struct BPlusTreeNode
{
    /// The tree node order
    static const int sOrder = 7; /// TODO find out the optimal value here :-)

    /// The number of children / data entries.
    int m_nUsed;

    /// The B+ tree has the data only in leaves, so we have to distinguish between internal nodes and leaves.
    bool m_bIsInternal : 1;

    /// Keys for this node (meaning intervals in case of internal nodes, real keys otherwise)
    Key m_pKeys[ sOrder ];

    union {
        /// Internal node, contains only pointers to other nodes
        BPlusTreeNode m_pChildren[ sOrder ];

        /// Leaf node, contains data.
        Value m_pValues[ sOrder ];
    };

    /// Pointer to the next node (valid only for the leaf nodes).
    BPlusTreeNode *m_pNext;

    BPlusTreeNode() : m_nUsed( 0 ), m_pNext( NULL ) {}
};

template < class Key, class Value >
BPlusTree< Key, Value >::BPlusTree()
    : m_pRoot( new BPlusTreeNode< Key, Value > )
{
}

template < class Key, class Value >
BPlusTree< Key, Value >::~BPlusTree()
{
    // TODO
}

template < class Key, class Value >
Key BPlusTree< Key, Value >::Count() const
{
    // TODO
}

template < class Key, class Value >
void BPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
{
    // TODO
}

template < class Key, class Value >
void BPlusTree< Key, Value >::Remove( Key nPos, Key nNumber )
{
    // TODO
}

template < class Key, class Value >
void BPlusTree< Key, Value >::Move( Key nFrom, Key nTo )
{
    // TODO
}

template < class Key, class Value >
void BPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
{
    // TODO
}

template < class Key, class Value >
const Value& BPlusTree< Key, Value >::operator[]( Key nPos ) const
{
    assert( m_pRoot->m_nUsed > 0 );

    BPlusTreeNode< Key, Value > *pNode = m_pRoot;

    // recursion is nice for the alg. description, but for implementation, we
    // want to unwind it
    while ( pNode->m_bIsInternal )
    {
        for ( int i = 0; i < pNode->m_nUsed - 1 ; ++i )
        {
            if ( nPos < pNode->m_pKeys[ i ] )
            {
                pNode = pNode->m_pChildren[ i ];
                break;
            }
        }
        pNode = pNode->m_pChildren[ pNode->m_nUsed - 1 ];
    }

    // now we have the leaf node
    for ( int i = 0; i < pNode->m_nUsed; ++i )
    {
        if ( nPos == pNode->m_pKeys[ i ] )
            return pNode->m_pValues[ i ];
    }

    // we do not allow not finding a value so far
    assert( false );
}

template < class Key, class Value >
void BPlusTree< Key, Value >::ForEach( FnForEach fn, void* pArgs )
{
    // TODO
}

template < class Key, class Value >
void BPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs )
{
    // TODO
}

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */