Subversion Repositories HelenOS-historic

Rev

Rev 1221 | Rev 1702 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1221 Rev 1248
Line 24... Line 24...
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
27
 */
28
 
28
 
29
/*
29
/**
-
 
30
 * @file    btree.c
-
 
31
 * @brief   B+tree implementation.
-
 
32
 *
-
 
33
 * This file implements B+tree type and operations.
-
 
34
 *
30
 * This B-tree has the following properties:
35
 * The B+tree has the following properties:
31
 * - it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
36
 * @li it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
32
 * - values (i.e. pointers to values) are stored only in leaves
37
 * @li values (i.e. pointers to values) are stored only in leaves
33
 * - leaves are linked in a list
38
 * @li leaves are linked in a list
34
 * - technically, it is a B+tree (because of the previous properties)
-
 
35
 *
39
 *
36
 * Be carefull when using these trees. They need to allocate
40
 * Be carefull when using these trees. They need to allocate
37
 * and deallocate memory for their index nodes and as such
41
 * and deallocate memory for their index nodes and as such
38
 * can sleep.
42
 * can sleep.
39
 */
43
 */