btree.c File Reference

#include <linux/btree.h>
#include <linux/cache.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/module.h>

Go to the source code of this file.

Data Structures
struct	btree_geo

Macros
#define	MAX(a, b)   ((a) > (b) ? (a) : (b))
#define	NODESIZE   MAX(L1_CACHE_BYTES, 128)
#define	LONG_PER_U64   (64 / BITS_PER_LONG)

Functions
	EXPORT_SYMBOL_GPL (btree_geo32)
	EXPORT_SYMBOL_GPL (btree_geo64)
	EXPORT_SYMBOL_GPL (btree_geo128)
void *	btree_alloc (gfp_t gfp_mask, void *pool_data)
	EXPORT_SYMBOL_GPL (btree_alloc)
void	btree_free (void *element, void *pool_data)
	EXPORT_SYMBOL_GPL (btree_free)
void	btree_init_mempool (struct btree_head *head, mempool_t *mempool)
	EXPORT_SYMBOL_GPL (btree_init_mempool)
int	btree_init (struct btree_head *head)
	EXPORT_SYMBOL_GPL (btree_init)
void	btree_destroy (struct btree_head *head)
	EXPORT_SYMBOL_GPL (btree_destroy)
void *	btree_last (struct btree_head *head, struct btree_geo *geo, unsigned long *key)
	EXPORT_SYMBOL_GPL (btree_last)
void *	btree_lookup (struct btree_head *head, struct btree_geo *geo, unsigned long *key)
	EXPORT_SYMBOL_GPL (btree_lookup)
int	btree_update (struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val)
	EXPORT_SYMBOL_GPL (btree_update)
void *	btree_get_prev (struct btree_head *head, struct btree_geo *geo, unsigned long *__key)
	EXPORT_SYMBOL_GPL (btree_get_prev)
int	btree_insert (struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, gfp_t gfp)
	EXPORT_SYMBOL_GPL (btree_insert)
void *	btree_remove (struct btree_head *head, struct btree_geo *geo, unsigned long *key)
	EXPORT_SYMBOL_GPL (btree_remove)
int	btree_merge (struct btree_head *target, struct btree_head *victim, struct btree_geo *geo, gfp_t gfp)
	EXPORT_SYMBOL_GPL (btree_merge)
void	visitorl (void *elem, unsigned long opaque, unsigned long *key, size_t index, void *__func)
	EXPORT_SYMBOL_GPL (visitorl)
void	visitor32 (void *elem, unsigned long opaque, unsigned long *__key, size_t index, void *__func)
	EXPORT_SYMBOL_GPL (visitor32)
void	visitor64 (void *elem, unsigned long opaque, unsigned long *__key, size_t index, void *__func)
	EXPORT_SYMBOL_GPL (visitor64)
void	visitor128 (void *elem, unsigned long opaque, unsigned long *__key, size_t index, void *__func)
	EXPORT_SYMBOL_GPL (visitor128)
size_t	btree_visitor (struct btree_head *head, struct btree_geo *geo, unsigned long opaque, void(*func)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2), void *func2)
	EXPORT_SYMBOL_GPL (btree_visitor)
size_t	btree_grim_visitor (struct btree_head *head, struct btree_geo *geo, unsigned long opaque, void(*func)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2), void *func2)
	EXPORT_SYMBOL_GPL (btree_grim_visitor)
	module_init (btree_module_init)
	module_exit (btree_module_exit)
	MODULE_AUTHOR ("Joern Engel <[email protected]>")
	MODULE_AUTHOR ("Johannes Berg <[email protected]>")
	MODULE_LICENSE ("GPL")

Variables
struct btree_geo	btree_geo32
struct btree_geo	btree_geo64
struct btree_geo	btree_geo128

Macro Definition Documentation

#define LONG_PER_U64   (64 / BITS_PER_LONG)

Definition at line 64 of file btree.c.

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

Definition at line 48 of file btree.c.

#define NODESIZE   MAX(L1_CACHE_BYTES, 128)

Definition at line 49 of file btree.c.

Function Documentation

void* btree_alloc	(	gfp_t	gfp_mask,
		void *	pool_data
	)

btree_alloc - allocate function for the mempool : gfp mask for the allocation : unused

Definition at line 81 of file btree.c.

void btree_destroy

(

struct btree_head *

head

)

btree_destroy - destroy mempool

: the btree head to destroy

This function destroys the internal memory pool, use only when using btree_init(), not with btree_init_mempool().

Definition at line 199 of file btree.c.

void btree_free	(	void *	element,
		void *	pool_data
	)

btree_free - free function for the mempool : the element to free : unused

Definition at line 87 of file btree.c.

void* btree_get_prev	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long *	key
	)

btree_get_prev - get previous entry

: btree head : btree geometry : pointer to key

The function returns the next item right before the value pointed to by , and updates with its key, or returns NULL when there is no entry with a key smaller than the given key.

Definition at line 310 of file btree.c.

size_t btree_grim_visitor	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long	opaque,
		void(*)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2)	func,
		void *	func2
	)

Definition at line 763 of file btree.c.

int btree_init

(

struct btree_head *

head

)

btree_init - initialise a btree

: the btree head to initialise

This function allocates the memory pool that the btree needs. Returns zero or a negative error code (-ENOMEM) when memory allocation fails.

Definition at line 189 of file btree.c.

void btree_init_mempool	(	struct btree_head *	head,
		mempool_t *	mempool
	)

btree_init_mempool - initialise a btree with given mempool

: the btree head to initialise : the mempool to use

When this function is used, there is no need to destroy the mempool.

Definition at line 182 of file btree.c.

int btree_insert	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long *	key,
		void *	val,
		gfp_t	gfp
	)

btree_insert - insert an entry into the btree

: the btree to add to : the btree geometry : the key to add (must not already be present) : the value to add (must not be NULL) : allocation flags for node allocations

This function returns 0 if the item could be added, or an error code if it failed (may fail due to memory pressure).

Definition at line 509 of file btree.c.

void* btree_last	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long *	key
	)

btree_last - get last entry in btree

: btree head : btree geometry : last key

Returns the last entry in the btree, and sets to the key of that entry; returns NULL if the tree is empty, in that case key is not changed.

Definition at line 206 of file btree.c.

void* btree_lookup	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long *	key
	)

btree_lookup - look up a key in the btree

: the btree to look in : the btree geometry : the key to look up

This function returns the value for the given key, or NULL.

Definition at line 240 of file btree.c.

int btree_merge	(	struct btree_head *	target,
		struct btree_head *	victim,
		struct btree_geo *	geo,
		gfp_t	gfp
	)

btree_merge - merge two btrees

: the tree that gets all the entries : the tree that gets merged into : the btree geometry : allocation flags

The two trees and may not contain the same keys, that is a bug and triggers a BUG(). This function returns zero if the trees were merged successfully, and may return a failure when memory allocation fails, in which case both trees might have been partially merged, i.e. some entries have been moved from to .

Definition at line 638 of file btree.c.

void* btree_remove	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long *	key
	)

btree_remove - remove an entry from the btree

: the btree to update : the btree geometry : the key to remove

This function returns the removed entry, or NULL if the key could not be found.

Definition at line 628 of file btree.c.

int btree_update	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long *	key,
		void *	val
	)

btree_update - update an entry in the btree

: the btree to update : the btree geometry : the key to update : the value to change it to (must not be NULL)

This function returns 0 if the update was successful, or -ENOENT if the key could not be found.

Definition at line 270 of file btree.c.

size_t btree_visitor	(	struct btree_head *	head,
		struct btree_geo *	geo,
		unsigned long	opaque,
		void(*)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2)	func,
		void *	func2
	)

Definition at line 745 of file btree.c.

EXPORT_SYMBOL_GPL

(

btree_geo32

)

EXPORT_SYMBOL_GPL

(

btree_geo64

)

EXPORT_SYMBOL_GPL

(

btree_geo128

)

EXPORT_SYMBOL_GPL

(

btree_alloc

)

EXPORT_SYMBOL_GPL

(

btree_free

)

EXPORT_SYMBOL_GPL

(

btree_init_mempool

)

EXPORT_SYMBOL_GPL

(

btree_init

)

EXPORT_SYMBOL_GPL

(

btree_destroy

)

EXPORT_SYMBOL_GPL

(

btree_last

)

EXPORT_SYMBOL_GPL

(

btree_lookup

)

EXPORT_SYMBOL_GPL

(

btree_update

)

EXPORT_SYMBOL_GPL

(

btree_get_prev

)

EXPORT_SYMBOL_GPL

(

btree_insert

)

EXPORT_SYMBOL_GPL

(

btree_remove

)

EXPORT_SYMBOL_GPL

(

btree_merge

)

EXPORT_SYMBOL_GPL

(

visitorl

)

EXPORT_SYMBOL_GPL

(

visitor32

)

EXPORT_SYMBOL_GPL

(

visitor64

)

EXPORT_SYMBOL_GPL

(

visitor128

)

EXPORT_SYMBOL_GPL

(

btree_visitor

)

EXPORT_SYMBOL_GPL

(

btree_grim_visitor

)

MODULE_AUTHOR

(

"Joern Engel <[email protected]>"

)

MODULE_AUTHOR

(

"Johannes Berg <[email protected]>"

)

module_exit

(

btree_module_exit

)

module_init

(

btree_module_init

)

MODULE_LICENSE

(

"GPL"

)

void visitor128	(	void *	elem,
		unsigned long	opaque,
		unsigned long *	__key,
		size_t	index,
		void *	__func
	)

Definition at line 735 of file btree.c.

void visitor32	(	void *	elem,
		unsigned long	opaque,
		unsigned long *	__key,
		size_t	index,
		void *	__func
	)

Definition at line 715 of file btree.c.

void visitor64	(	void *	elem,
		unsigned long	opaque,
		unsigned long *	__key,
		size_t	index,
		void *	__func
	)

Definition at line 725 of file btree.c.

void visitorl	(	void *	elem,
		unsigned long	opaque,
		unsigned long *	key,
		size_t	index,
		void *	__func
	)

Definition at line 706 of file btree.c.

Variable Documentation

struct btree_geo btree_geo128

Initial value:

= {
    .keylen = 2 * LONG_PER_U64,
    .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
    .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
}

Definition at line 72 of file btree.c.

struct btree_geo btree_geo32

Initial value:

= {
    .keylen = 1,
    .no_pairs = NODESIZE / sizeof(long) / 2,
    .no_longs = NODESIZE / sizeof(long) / 2,
}

Definition at line 57 of file btree.c.

struct btree_geo btree_geo64

Initial value:

= {
    .keylen = LONG_PER_U64,
    .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
    .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
}

Definition at line 65 of file btree.c.