A better btree library Code
A small, sane btree lib, derived from the old berkeley db 1.85 code
Brought to you by:
hardyfalk
Menu
▾
▴
Tree [f2a6c0] master / History
Hardy
Read Me
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
