Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tree: 740253274e
Fetching contributors…

Cannot retrieve contributors at this time

963 lines (751 sloc) 21.721 kB
/*
Borodin - Object Storage System
Memory-Mapped Binary-Trees
Copyright (C) 2011/2012 Angel Ortega <angel@triptico.com>
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
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
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.
http://triptico.com
*/
#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#ifdef CONFOPT_SYS_MMAN_H
#include <sys/mman.h>
#endif
#include "borodin_tree.h"
/* on-disk format (increment on changes) */
#define BRTR_FORMAT 3
/** code **/
off_t brtr_get_root(brtr_t *b)
{
off_t r;
if (b->fdes == -1)
r = b->root;
else
r = ((struct brtr_header *)b->data)->root;
return r;
}
void brtr_set_root(brtr_t *b, off_t root)
{
if (root) {
if (b->fdes == -1)
b->root = root;
else
((struct brtr_header *)b->data)->root = root;
}
}
struct brtr_node *brtr_node(brtr_t *b, off_t id)
{
return id ? (struct brtr_node *)(b->data + id) : NULL;
}
/**
* brtr_node_key - Returns the key of a Borodin Tree node.
* @n: the node
*
* Returns the key of a Borotree node as a character string.
* [API]
*/
char *brtr_node_key(struct brtr_node *n)
{
char *ptr = (char *)n;
ptr += sizeof(*n);
return ptr;
}
/**
* brtr_node_value - Returns the value of a Borodin Tree node.
* @n: the node
*
* Returns the value of a Borotree node.
* [API]
*/
void *brtr_node_value(struct brtr_node *n)
{
char *ptr;
ptr = brtr_node_key(n);
ptr += strlen(ptr) + 1;
return ptr;
}
int brtr_node_stree(brtr_t *b, off_t id, off_t *stree)
{
int r = 0;
struct brtr_node *n;
if ((n = brtr_node(b, id)) != NULL && n->f & BRTR_FLAG_STREE) {
if (stree != NULL)
memcpy(stree, brtr_node_value(n), sizeof(off_t));
r = 1;
}
return r;
}
off_t brtr_count(brtr_t *b, off_t id)
{
off_t c = 0;
struct brtr_node *n;
if ((n = brtr_node(b, id)) != NULL)
c = n->c;
return c;
}
#define UPDATE_COUNT(b, n) n->c = brtr_count(b, n->left) + brtr_count(b, n->right) + 1
static void do_mmap(brtr_t *b)
{
/* calculate optimal mmap size */
b->msize = ((b->size / BRTR_MMAP_STEP) + 1) * BRTR_MMAP_STEP;
/* do the mmapping */
if ((b->data = mmap(NULL, b->msize, PROT_READ | PROT_WRITE,
MAP_SHARED, b->fdes, 0)) == MAP_FAILED) {
printf("do_mmap(): MAP_FAILED (msize %lx)\n", (unsigned long)b->msize);
abort();
}
}
int brtr_open(brtr_t *b, char *filename)
{
int r = 1;
/* clear the structure */
memset(b, '\0', sizeof(*b));
if (filename != NULL) {
struct brtr_header h;
long s;
/* create the signature */
s = BRTR_SIGNATURE |
(BRTR_FORMAT +
(sizeof(off_t) == 8 ? 'A' : 'a')
) << 24;
if ((b->fdes = open(filename, O_RDWR)) != -1) {
/* file exists */
if (read(b->fdes, &h, sizeof(h)) == sizeof(h)) {
/* correct signature? file is valid */
if (h.sig == s) {
struct stat buf;
fstat(b->fdes, &buf);
b->size = buf.st_size;
}
else
r = 0;
}
}
else
if ((b->fdes = open(filename, O_RDWR | O_CREAT, 0644)) != -1) {
/* new file */
b->size = sizeof(h);
/* write a header */
h.sig = s;
h.del = 0;
h.root = 0;
write(b->fdes, &h, sizeof(h));
}
if (b->size)
do_mmap(b);
else
r = 0;
}
else {
/* in-memory tree: nothing more to do */
b->fdes = -1;
}
/* no key generated yet */
b->lk = 0;
/* initialize read/write locking engine */
pthread_mutex_init(&b->mutex, NULL);
sem_init(&b->sem, 0, BRTR_MAX_THREADS);
return r;
}
void brtr_close(brtr_t *b)
{
if (b->fdes == -1) {
/* destroy the root tree */
brtr_destroy(b, brtr_get_root(b));
}
else {
munmap(b->data, b->msize);
close(b->fdes);
}
}
static off_t set_left(brtr_t *b, off_t id, off_t ptr)
/* sets the pointer to the left node with optional rotation */
{
struct brtr_node *n, *m;
/* nodes are assumed to exist */
n = brtr_node(b, id);
m = brtr_node(b, ptr);
if (m && m->c > (n->c / 2) + 1) {
/* do the rotation */
n->left = m->right;
m->right = id;
id = ptr;
UPDATE_COUNT(b, n);
n = m;
}
else
n->left = ptr;
UPDATE_COUNT(b, n);
return id;
}
static off_t set_right(brtr_t *b, off_t id, off_t ptr)
/* sets the pointer to the left node with optional rotation */
{
struct brtr_node *n, *m;
/* nodes are assumed to exist */
n = brtr_node(b, id);
m = brtr_node(b, ptr);
if (m && m->c > (n->c / 2) + 1) {
/* do the rotation */
n->right = m->left;
m->left = id;
id = ptr;
UPDATE_COUNT(b, n);
n = m;
}
else
n->right = ptr;
UPDATE_COUNT(b, n);
return id;
}
static off_t merge_nodes(brtr_t *b, off_t left, off_t right)
{
off_t id = 0;
struct brtr_node *l;
if ((l = brtr_node(b, left)) != NULL) {
struct brtr_node *r;
if ((r = brtr_node(b, right)) != NULL) {
if (l->c > r->c)
id = set_right(b, left, merge_nodes(b, l->right, right));
else
id = set_left(b, right, merge_nodes(b, left, r->left));
}
else
id = left;
}
else
id = right;
return id;
}
static off_t del_pull(brtr_t *b, off_t r, int size, off_t *id)
/* pulls a node with the specified size from the delete queue */
{
struct brtr_node *n;
if ((n = brtr_node(b, r)) != NULL) {
int c;
c = size - n->size;
if (c < 0)
r = set_left(b, r, del_pull(b, n->left, size, id));
else
if (c > 0)
r = set_right(b, r, del_pull(b, n->right, size, id));
else {
/* equal: return this node */
*id = r;
r = merge_nodes(b, n->left, n->right);
}
}
return r;
}
off_t brtr_alloc(brtr_t *b, char *k, void *v, int vs,
off_t l, off_t r,
off_t c, int32_t flags)
{
struct brtr_node *n = NULL;
int size;
off_t id;
id = 0;
if (vs == -1) {
/* assume value is a string and calculate its length */
vs = strlen((char *) v);
}
/* size of the new node */
size = sizeof(*n) + strlen(k) + 1 + vs;
if (b->fdes != -1) {
struct brtr_header *h;
/* use a minimum size */
if (size < BRTR_MIN_NODE_SIZE)
size = BRTR_MIN_NODE_SIZE;
else
/* align next node to pointer */
if (size % sizeof(char *))
size += (size % sizeof(char *));
/* get header */
h = (struct brtr_header *)b->data;
/* pull a node from the deleted tree */
h->del = del_pull(b, h->del, size, &id);
if ((n = brtr_node(b, id)) == NULL) {
/* new node will live at the end */
id = b->size;
/* increase tree size */
b->size += size;
/* alloc space in the file */
ftruncate(b->fdes, b->size);
if (b->size > b->msize) {
/* is size bigger than current mmap? */
munmap(b->data, b->msize);
do_mmap(b);
}
/* store node size inside the node */
n = brtr_node(b, id);
n->size = size;
}
}
else {
/* in-memory */
n = malloc(size);
id = (off_t) n;
}
/* fill data */
n->c = c;
n->f = flags & BRTR_NODE_FLAGS;
n->left = l;
n->right = r;
n->vsize = vs;
strcpy(brtr_node_key(n), k);
memcpy(brtr_node_value(n), v, vs);
return id;
}
static off_t del_push(brtr_t *b, off_t r, int size, off_t id)
/* puts a node in the delete tree */
{
struct brtr_node *n;
struct brtr_node *m;
if ((m = brtr_node(b, r)) != NULL) {
int c;
c = size - m->size;
if (c < 0)
id = set_left(b, r, del_push(b, m->left, size, id));
else
if (c > 0)
id = set_right(b, r, del_push(b, m->right, size, id));
else {
n = brtr_node(b, id);
/* equal to this node: insert */
n->left = m->left;
n->right = r;
m->left = 0;
UPDATE_COUNT(b, m);
UPDATE_COUNT(b, n);
}
}
else {
n = brtr_node(b, id);
n->left = n->right = 0;
n->c = 1;
}
return id;
}
void brtr_free(brtr_t *b, off_t id)
{
off_t d;
/* if this node stores a subtree, destroy it */
if (brtr_node_stree(b, id, &d))
brtr_destroy(b, d);
if (b->fdes != -1) {
struct brtr_header *h;
struct brtr_node *n;
/* get header */
h = (struct brtr_header *)b->data;
/* get node */
n = brtr_node(b, id);
/* add to the deleted tree */
h->del = del_push(b, h->del, n->size, id);
}
else
free((void *)id);
}
/** inter-thread locking **/
/**
* brtr_read_lock - Locks a Borodin Tree for reading.
* @b: the borotree handler
*
* Locks the current thread until @b is free for doing a
* set of reading operations.
*
* [API]
* [Locks]
*/
void brtr_read_lock(brtr_t *b)
{
sem_wait(&b->sem);
}
/**
* brtr_read_unlock - Unlocks a reading lock.
* @b: the borotree handler
*
* Unlocks @b from a reading lock, made by brtr_read_lock().
*
* [API]
* [Locks]
*/
void brtr_read_unlock(brtr_t *b)
{
sem_post(&b->sem);
}
/**
* brtr_write_lock - Locks a Borodin Tree for writing.
* @b: the borotree handler
*
* Locks the current thread until @b is free for doing a
* set of writing operations.
*
* [API]
* [Locks]
*/
void brtr_write_lock(brtr_t *b)
{
int n;
pthread_mutex_lock(&b->mutex);
for (n = 0; n < BRTR_MAX_THREADS; n++)
sem_wait(&b->sem);
pthread_mutex_unlock(&b->mutex);
}
/**
* brtr_write_unlock - Unlocks a writing lock.
* @b: the borotree handler
*
* Unlocks @b from a writing lock, made by brtr_write_lock().
*
* [API]
* [Locks]
*/
void brtr_write_unlock(brtr_t *b)
{
int n;
for (n = 0; n < BRTR_MAX_THREADS; n++)
sem_post(&b->sem);
}
/** operations **/
off_t brtr_foreach(brtr_t *b, off_t id, void *p,
off_t (*f)(brtr_t *b, off_t id, void *p))
{
struct brtr_node *n;
off_t r = 0;
if ((n = brtr_node(b, id)) != NULL) {
if (!(r = brtr_foreach(b, n->left, p, f)))
if (!(r = f(b, id, p)))
r = brtr_foreach(b, n->right, p, f);
}
return r;
}
/**
* brtr_set - Sets a node in a Borodin Tree by key
* @b: the borotree handler
* @r: the root of the tree
* @k: the key
* @v: the value
* @vs: value size in bytes
* @f: flags
*
* Inserts or updates a node in a Borodin Tree. The node is described
* by the @k key, and is replaced if it exists and inserted if it doesn't
* (but see the description of the @flags argument). The @r value is the
* identifier of the root node of the tree, the @v value a pointer to
* the value and @vs the value size in bytes.
*
* The value returned is the identifier of the new root of the tree, or 0
* if the node couldn't be set (see below for possible causes).
*
* The @flags argument is an OR combination of the constants explained
* below. There are node flags and brtr_set() ("behavioural") flags.
* The node flags are the following:
*
* BRTR_FLAG_STREE: the value to be inserted is itself an identifier of
* the root of a subtree, so it's a pointer to an off_t value. The value
* size should be set to sizeof(off_t).
*
* BRTR_FLAG_ARRAY: to be always used in combination of BRTR_FLAG_STREE.
* It hints that the subtree stored in this node is to be treated as an
* array instead of a set of value/key pairs (for example, its output
* will be between square brackets when dumping it in JSON format).
*
* Behavioural flags:
*
* BRTR_SET_INSERT: Commands brtr_set() to fail if the key already
* exists (insert-only mode).
*
* BRTR_SET_UPDATE: The opposite of BRTR_SET_INSERT, fail if the
* key does not exist (update-only mode).
*
* BRTR_SET_KSTREE: To be used in combination of BRTR_FLAG_STREE. It
* instructs brtr_set() that the subtree to be stored is the same as (or
* is an update of) the subtree currently stored in the node (it basically
* means the stored subtree is not destroyed when replaced).
*
* [API]
*/
off_t brtr_set(brtr_t *b, off_t r, char *k, void *v, int vs, int32_t f)
{
struct brtr_node *n;
off_t nr;
if ((n = brtr_node(b, r)) != NULL) {
int c;
c = strcmp(k, brtr_node_key(n));
if (c < 0)
nr = set_left(b, r, brtr_set(b, n->left, k, v, vs, f));
else
if (c > 0)
nr = set_right(b, r, brtr_set(b, n->right, k, v, vs, f));
else {
/* key exists */
if (f & BRTR_SET_INSERT) {
/* if insert-only mode, fail */
nr = 0;
}
else {
/* create new node cloning current one as possible */
nr = brtr_alloc(b, k, v, vs, n->left, n->right, n->c, f);
/* keep stored stree? */
if (f & BRTR_SET_KSTREE)
n->f &= ~(BRTR_FLAG_STREE);
/* destroy current node */
brtr_free(b, r);
}
}
}
else {
/* key does not exist */
if (f & BRTR_SET_UPDATE) {
/* if update-only mode, fail */
nr = 0;
}
else {
/* insert */
nr = brtr_alloc(b, k, v, vs, 0, 0, 1, f);
}
}
return nr;
}
off_t brtr_get(brtr_t *b, off_t r, char *k)
{
struct brtr_node *n = NULL;
if ((n = brtr_node(b, r)) != NULL) {
int c = strcmp(k, brtr_node_key(n));
if (c < 0)
r = brtr_get(b, n->left, k);
else
if (c > 0)
r = brtr_get(b, n->right, k);
}
return r;
}
off_t brtr_delete(brtr_t *b, off_t r, char *k)
{
struct brtr_node *n;
if ((n = brtr_node(b, r)) != NULL) {
int c;
c = strcmp(k, brtr_node_key(n));
if (c < 0)
r = set_left(b, r, brtr_delete(b, n->left, k));
else
if (c > 0)
r = set_right(b, r, brtr_delete(b, n->right, k));
else {
off_t nr;
nr = merge_nodes(b, n->left, n->right);
brtr_free(b, r);
r = nr;
}
}
return r;
}
void brtr_destroy(brtr_t *b, off_t r)
{
struct brtr_node *n;
if ((n = brtr_node(b, r)) != NULL) {
brtr_destroy(b, n->left);
brtr_destroy(b, n->right);
brtr_free(b, r);
}
}
off_t brtr_force_count(brtr_t *b, off_t r)
{
off_t ret = 0;
struct brtr_node *n;
if ((n = brtr_node(b, r)) != NULL) {
ret++;
ret += brtr_force_count(b, n->left);
ret += brtr_force_count(b, n->right);
}
return ret;
}
/**
* brtr_fsck - Checks the integrity of a Borodin Tree.
* @b: the brtr handler
* @root: the root node of the index
*
* Checks the integrity of a Borodin Tree, writing on stdin all problems
* found. The file is not modified and should be locked for reading.
*/
int brtr_fsck(brtr_t *b, off_t root)
{
struct brtr_node *n;
struct brtr_node *l;
struct brtr_node *r;
int i, c;
c = 0;
if ((n = brtr_node(b, root)) != NULL) {
off_t id;
off_t cnt;
cnt = brtr_force_count(b, root);
if (n->c != cnt) {
printf("brtr_fsck(): node c and real count mismatch (%ld, %ld)\n", n->c, cnt);
c++;
}
cnt = brtr_count(b, n->left) + brtr_count(b, n->right) + 1;
if (n->c != cnt) {
printf("brtr_fsck(): node c and recount mismatch (%ld, %ld)\n", n->c, cnt);
c++;
}
if ((l = brtr_node(b, n->left)) != NULL) {
i = strcmp(brtr_node_key(n), brtr_node_key(l));
if (i < 0) {
printf("brtr_fsck(): key (%s) < left->key (%s) [%ld,%ld]\n",
brtr_node_key(n), brtr_node_key(l), root, n->left);
c++;
}
}
else {
if (n->left != 0) {
printf("brtr_fsck(): fail to load left node %ld\n", n->left);
c++;
}
}
if ((r = brtr_node(b, n->right)) != NULL) {
i = strcmp(brtr_node_key(n), brtr_node_key(r));
if (i >= 0) {
printf("brtr_fsck(): key (%s) >= right->key (%s) [%ld,%ld]\n",
brtr_node_key(n), brtr_node_key(r), root, n->right);
c++;
}
}
else {
if (n->right != 0) {
printf("brtr_fsck(): fail to load right node %ld\n", n->left);
c++;
}
}
if (l && r) {
i = strcmp(brtr_node_key(l), brtr_node_key(r));
if (i >= 0) {
printf("brtr_fsck(): left->key (%s) >= right->key (%s) [%ld,%ld,%ld]\n",
brtr_node_key(n), brtr_node_key(r), root, n->left, n->right);
c++;
}
}
/* fsck the stree, if there is one */
if (brtr_node_stree(b, root, &id))
c += brtr_fsck(b, id);
/* check branches */
c += brtr_fsck(b, n->left);
c += brtr_fsck(b, n->right);
}
else {
if (root != 0) {
printf("brtr_fsck(): fail to load node %ld\n", root);
c++;
}
}
return c;
}
/** autokeys **/
static char ak_set[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvxyz";
#define SS (sizeof(ak_set) - 1)
#define KS 9
char *brtr_autokey(brtr_t *b, char *str)
{
struct timeval tv;
int n = 0;
unsigned long long i;
gettimeofday(&tv, NULL);
i = (((unsigned long long)
(tv.tv_sec - 1330435678) * 1000000)) + tv.tv_usec;
i *= 32;
/* if this is same key as the last time (fast computer or
low-res timer) change the key to make it different */
if (b->lk >= i)
i = b->lk + 1;
b->lk = i;
for (n = 0; n < KS; n++) {
str[KS - 1 - n] = ak_set[i % SS];
i /= SS;
}
str[n] = '\0';
// printf("[%s]\n", str);
return str;
}
/** arrays **/
off_t brtr_get_n(brtr_t *b, off_t r, off_t i)
{
off_t id = 0;
struct brtr_node *n;
if ((n = brtr_node(b, r)) != NULL) {
if (i < n->c) {
off_t c = brtr_count(b, n->left);
if (i < c)
id = brtr_get_n(b, n->left, i);
else
if (i > c)
id = brtr_get_n(b, n->right, i - c - 1);
else
id = r;
}
}
return id;
}
/**
* brtr_set_n - Sets a node in a Borodin Tree by subscript
* @b: the borotree handler
* @r: the root of the tree
* @i: the subscript
* @v: the value
* @vs: value size in bytes
* @f: flags
*
* Updates a node in a Borodin Tree. The node is described by the @i
* subscript (so the tree is treated as an array), and it's replaced
* if it already exists (no insertion is possible). The @r value is
* the identifier of the root node of the tree, the @v value a pointer
* to the value and @vs the value size in bytes.
*
* The value returned is the identifier of the new root of the tree, or 0
* if the node couldn't be set because there is no #i node in the tree.
*
* For an explanation of @flags, please see brtr_set() documentation
* (but take note that flags implying insertion do not apply).
*
* [API]
*/
off_t brtr_set_n(brtr_t *b, off_t r, off_t i, void *v, int vs, int32_t f)
{
struct brtr_node *n;
off_t nr = 0;
if ((n = brtr_node(b, r)) != NULL) {
if (i < n->c) {
off_t c = brtr_count(b, n->left);
if (i < c)
nr = set_left(b, r, brtr_set_n(b, n->left, i, v, vs, f));
else
if (i > c)
nr = set_right(b, r, brtr_set_n(b, n->right, i - c - 1, v, vs, f));
else {
/* replace */
nr = brtr_alloc(b, brtr_node_key(n), v, vs,
n->left, n->right, n->c, f);
/* keep stored stree? */
if (f & BRTR_SET_KSTREE)
n->f &= ~(BRTR_FLAG_STREE);
brtr_free(b, r);
}
}
}
return nr;
}
Jump to Line
Something went wrong with that request. Please try again.