Download Latest Version bt.tgz (37.6 kB)
Email in envelope

Get an email when there's a new version of A better btree library

Home
Name Modified Size InfoDownloads / Week
bt.tgz 2014-07-12 37.6 kB
README 2014-07-12 4.8 kB
Totals: 2 Items   42.5 kB 0
This is not a release yet.
Any feedback or comments on the api are welcome.

// Header file btree.h :


#ifndef BT_H_INCLUDED
#define	BT_H_INCLUDED 

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

#include <stdio.h>	
#include <stdint.h>	

typedef struct BT BT ; 
typedef struct BTINFO BTINFO ; 

typedef struct 
{
	void	*data;		
	uint32_t size;	
} DBT ; 

struct BTINFO 
{
	int    (*cmp)( const DBT *k1 , const DBT *k2 ) ; /* must not be null */
	int    (*pfx)( const DBT *k1 , const DBT *k2 ) ; /* may be null */
	char   magic[10+1] ;/* application magic */
	int    pagesize ;	/* 0 defaults to struct stat.st_blksize, 256 to 65536*/
	int    cachesize ;	/* KBytes , 0 defaults to 9 pages */
} ;

#define BTDECL(const) \
	const int fd ; \
	/* don't close this or any other fd referring to this file! */ \
	const uint32_t pagesize;/* actual pagesize */ \
	const uint32_t npages ; /* actual number of pages in the tree */ \
	const uint32_t ncache ; /* number of currently cached paged */ \
	const uint32_t ndirty ; /* number of dirty pages */ \
	const uint32_t nfree  ; /* number of reusable free pages in the file */ \
	const  int32_t nflush ; /* number of cache flush calls */ \
	const  int32_t nio    ; /* number of i/o operations,circular counter */ \

#ifndef BT_INTERFACE_PRIVATE
struct BT
{
	BTDECL(const) ;
} ;  
#endif

BT  *bt_open( const char *filename, int mode, int mask, const BTINFO *info );
/* mask is the file creation mask for open() 
 * O_CREAT|O_EXCL|O_NOATIME|O_NOFOLLOW are passed to open()
 * O_TRUNC,O_APPEND and O_WRONLY lead to EINVAL 
 * O_CLOEXEC is always set.
 * info.subtype may omit the trailing '\0', but it's not recommended.
 * info.cmp must not be NULL, you may use bt_dflt_cmp 
 * info.pfx may be NULL, you may use bt_dflt_pfx 
 */

int  bt_error( const BT * ) ; 
/*  0 on success
 *  1 if lowspace condition encountered or BT* is NULL
 * -1 on a more serious error
 */ 

int  bt_sync( BT *) ; 
int  bt_close(BT *) ; /* bt_close(NULL) returns success */


int  bt_writep(BT *t)  ; /* test for a queued writer */
int  bt_detach(BT *t ) ; 
int  bt_attach(BT *t ) ; 


int  bt_get( BT *, const DBT *key, DBT *data ) ; 
int  bt_put( BT *, const DBT *key, const DBT *data, int nooverwrite ) ; 
int  bt_del( BT *, const DBT *key ) ; /* bt_del(t,NULL) in scans */

int  bt_first( BT *, DBT *key, DBT *data ) ; 
int  bt_seek( BT *, DBT *key, DBT *data ) ; 
int  bt_last( BT *, DBT *key, DBT *data ) ; 
int  bt_next( BT *, DBT *key, DBT *data ) ; 
int  bt_prev( BT *, DBT *key, DBT *data ) ; 
int  bt_cursor( BT *, DBT *key, DBT *data ) ; /* return cursor key/data */


/* nur in der Testsuite mit key != 0 */
/* im keyscan mit big data kann bt_getcur(t,NULL,&d) 
 * marginal nützlich sein */

void bt_dump( BT *bt, FILE *f ) ; 


DBT bt_dbtdup( DBT *dbt ) ;
/* allocate a copy of DBT on the heap
** if k.size == 0 or k.data == NULL return { NULL, 0 } 
*/ 
DBT bt_dbtcpy( DBT *mem , DBT *dbt ) ;
/*  copy to a growable buffer.
**  returned data == mem->data, 
**  mem->size grows if necessary
**  returns { mem->data, dbt->size }
*/

int bt_dflt_cmp( const DBT *a, const DBT *b ) ; 
/* compare lexically with memcmp */
int bt_dflt_pfx( const DBT *a, const DBT *b ) ; 
/* prefix compression compatible with bt_dflt_cmp */





typedef struct 
{
	int pageget ; 	
	int pagenew ;	/* get + new */
	int pagefree ;  /* pages returned to the free list */
	int cachehit ;  /* pageget fulfilled from the page cache */
	int pageread ;  /* pread() */
	int pagewrite ; /* pwrite() */
	int pageflush ; /* pages written from cache miss/pageread */
	int pagesplit ; /* Anzahl der Split-Operationen im BT */
	int sortsplit ; /* asymmetrische Splits */
	int pfxsaved  ; /* bytes saved by prefix compression */
	int ref_plus  ; /* reference counting for overflow keys */
	int ref_minus ; /* reference counting for overflow keys */
	int stkacq    ; /* stack acqusition for bt_del() */
	int    n_critical ;/* number of passes through critical section */
	double t_critical ;  /* Im kritischen Abschnitt verbrachte Zeit [s] */
} BTSTAT ;


const BTSTAT *bt_statistics( const BT * ) ; 
/* returns NULL if compiled witrhout -DSTATISTICS */

int  bt_salvage( BT *t , DBT *k, DBT *d ) ;
/* recover key/data pairs from a possibly damaged btree file.
** leaf pages are scanned in file order.
** BT *t ; 
** DBT k,d ; 
** t = bt_open(...) ; ...
** while ( 0 == bt_salvage(t,&k,&d) ) { ... } 
*/


/* improvements
 *
 * safe caching: user code may exit or crash 
 * without damaging the file structure. 
 * signals are blocked during cache flushes.
 * cache flushing is suppressed if the file system is 
 * almost full.
 *
 * large key pages are reference counted.
 * large items that fit on a single page are not copied.
 * 
 */


#if defined(__cplusplus) || defined(c_plusplus)
	}
#endif

#endif

Source: README, updated 2014-07-12