linux-imx

/*

 * linux/fs/befs/btree.c

 *

 * Copyright (C) 2001-2002 Will Dyson <will_dyson@pobox.com>

 *

 * Licensed under the GNU GPL. See the file COPYING for details.

 *

 * 2002-02-05: Sergey S. Kostyliov added binary search within

 *      btree nodes.

 *

 * Many thanks to:

 *

 * Dominic Giampaolo, author of "Practical File System

 * Design with the Be File System", for such a helpful book.

 *

 * Marcus J. Ranum, author of the b+tree package in

 * comp.sources.misc volume 10. This code is not copied from that

 * work, but it is partially based on it.

 *

 * Makoto Kato, author of the original BeFS for linux filesystem

 * driver.

 */

​

#include <linux/kernel.h>

#include <linux/string.h>

#include <linux/slab.h>

#include <linux/mm.h>

#include <linux/buffer_head.h>

​

#include "befs.h"

#include "btree.h"

#include "datastream.h"

​

/*

 * The btree functions in this file are built on top of the

 * datastream.c interface, which is in turn built on top of the

 * io.c interface.

 */

​

/* Befs B+tree structure:

 *

 * The first thing in the tree is the tree superblock. It tells you

 * all kinds of useful things about the tree, like where the rootnode

 * is located, and the size of the nodes (always 1024 with current version

 * of BeOS).

 *

 * The rest of the tree consists of a series of nodes. Nodes contain a header

 * (struct befs_btree_nodehead), the packed key data, an array of shorts

 * containing the ending offsets for each of the keys, and an array of

 * befs_off_t values. In interior nodes, the keys are the ending keys for

 * the childnode they point to, and the values are offsets into the

 * datastream containing the tree.

 */

​

/* Note:

 *

 * The book states 2 confusing things about befs b+trees. First,

 * it states that the overflow field of node headers is used by internal nodes

 * to point to another node that "effectively continues this one". Here is what

 * I believe that means. Each key in internal nodes points to another node that

 * contains key values less than itself. Inspection reveals that the last key

 * in the internal node is not the last key in the index. Keys that are

 * greater than the last key in the internal node go into the overflow node.