linux-imx

/*

 * lib/btree.c  - Simple In-memory B+Tree

 *

 * As should be obvious for Linux kernel code, license is GPLv2

 *

 * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>

 * Bits and pieces stolen from Peter Zijlstra's code, which is

 * Copyright 2007, Red Hat Inc. Peter Zijlstra

 * GPLv2

 *

 * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch

 *

 * A relatively simple B+Tree implementation.  I have written it as a learning

 * exercise to understand how B+Trees work.  Turned out to be useful as well.

 *

 * B+Trees can be used similar to Linux radix trees (which don't have anything

 * in common with textbook radix trees, beware).  Prerequisite for them working

 * well is that access to a random tree node is much faster than a large number

 * of operations within each node.

 *

 * Disks have fulfilled the prerequisite for a long time.  More recently DRAM

 * has gained similar properties, as memory access times, when measured in cpu

 * cycles, have increased.  Cacheline sizes have increased as well, which also

 * helps B+Trees.

 *

 * Compared to radix trees, B+Trees are more efficient when dealing with a

 * sparsely populated address space.  Between 25% and 50% of the memory is

 * occupied with valid pointers.  When densely populated, radix trees contain

 * ~98% pointers - hard to beat.  Very sparse radix trees contain only ~2%

 * pointers.

 *

 * This particular implementation stores pointers identified by a long value.

 * Storing NULL pointers is illegal, lookup will return NULL when no entry

 * was found.

 *

 * A tricks was used that is not commonly found in textbooks.  The lowest

 * values are to the right, not to the left.  All used slots within a node

 * are on the left, all unused slots contain NUL values.  Most operations

 * simply loop once over all slots and terminate on the first NUL.

 */

​

#include <linux/btree.h>

#include <linux/cache.h>

#include <linux/kernel.h>

#include <linux/slab.h>

#include <linux/module.h>

​

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define NODESIZE MAX(L1_CACHE_BYTES, 128)

​

struct btree_geo {

    int keylen;

    int no_pairs;

    int no_longs;

};

​

struct btree_geo btree_geo32 = {

    .keylen = 1,

    .no_pairs = NODESIZE / sizeof(long) / 2,

    .no_longs = NODESIZE / sizeof(long) / 2,

};

EXPORT_SYMBOL_GPL(btree_geo32);

​