Skip to content


Subversion checkout URL

You can clone with
Download ZIP
Tree: a8edd9a2e6
Fetching contributors…

Cannot retrieve contributors at this time

151 lines (106 sloc) 4.18 KB
Borodin - Object Storage System
Memory-Mapped Binary-Trees
Copyright (C) 2011/2012 Angel Ortega <>
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
#ifdef __cplusplus
extern "C" {
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
/** definitions **/
#define BRTR_SIGNATURE 0x00584942
#define BRTR_MMAP_STEP (1024 * 1024)
#define BRTR_MAX_THREADS 256
/** flags **/
/* node flags (stored on disk) */
#define BRTR_FLAG_STREE 0x00000001 /* value is an stree */
#define BRTR_FLAG_ARRAY 0x00000002 /* stree is an array */
/* brtr_set() "behavioural" flags (not stored on disk) */
#define BRTR_SET_INSERT 0x80000000 /* insert only; do not update */
#define BRTR_SET_UPDATE 0x40000000 /* update only; do not insert */
#define BRTR_SET_KSTREE 0x20000000 /* do not destroy stree in set */
/* node flags (stored on disk) */
/** node **/
struct brtr_node {
size_t size; /* size of node */
off_t c; /* # of nodes in subtree (including this) */
int32_t f; /* flags */
off_t left; /* pointer to left or next free node */
off_t right; /* pointer to right node */
size_t vsize; /* size of value */
/* key + '\0' + value + '\0' follows in the memory block */
/* on-disk tree header */
struct brtr_header {
int32_t sig; /* signature */
off_t del; /* deleted node */
off_t root; /* root node */
/* handler */
struct brtr {
int fdes; /* file descriptor (-1: in-memory) */
off_t root; /* root node (only in-memory) */
size_t size; /* tree size in bytes */
size_t msize; /* mmap size */
unsigned char *data; /* mmapped data */
unsigned long long lk; /* last autokey */
pthread_mutex_t mutex; /* read-write mutex */
sem_t sem; /* read-write semaphore */
typedef struct brtr brtr_t;
/** API **/
int brtr_open(brtr_t *b, char *filename);
void brtr_close(brtr_t *b);
off_t brtr_get_root(brtr_t *b);
void brtr_set_root(brtr_t *b, off_t root);
struct brtr_node *brtr_node(brtr_t *b, off_t id);
char *brtr_node_key(struct brtr_node *n);
void *brtr_node_value(struct brtr_node *n);
int brtr_node_stree(brtr_t *b, off_t id, off_t *stree);
off_t brtr_count(brtr_t *b, off_t r);
off_t brtr_alloc(brtr_t *b, char *k, void *v, int vs, off_t l, off_t r, off_t p, int32_t flags);
void brtr_free(brtr_t *b, off_t id);
void brtr_read_lock(brtr_t *b);
void brtr_read_unlock(brtr_t *b);
void brtr_write_lock(brtr_t *b);
void brtr_write_unlock(brtr_t *b);
off_t brtr_foreach(brtr_t *b, off_t id, void *p, off_t (*f)(brtr_t *b, off_t id, void *p));
off_t brtr_set(brtr_t *b, off_t r, char *k, void *v, int vs, int32_t f);
off_t brtr_get(brtr_t *b, off_t r, char *k);
off_t brtr_delete(brtr_t *b, off_t r, char *k);
void brtr_destroy(brtr_t *b, off_t r);
off_t brtr_force_count(brtr_t *b, off_t r);
int brtr_fsck(brtr_t *b, off_t root);
char *brtr_autokey(brtr_t *b, char *str);
off_t brtr_get_n(brtr_t *b, off_t r, off_t i);
off_t brtr_set_n(brtr_t *b, off_t r, off_t i, void *v, int vs, int32_t f);
#ifdef __cplusplus
#endif /* BORODIN_TREE_H */
Jump to Line
Something went wrong with that request. Please try again.