mapping.c

#include <stdio.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>

#define PAGE_SIZE       ((size_t) 4096)
#define PAGE_COUNT      50000
#define KEY_SPACE       16
#define MAX_KEY_SIZE    (KEY_SPACE - (sizeof char))
#define FACTOR          60

typedef struct page page_t;

struct page {
    char leaf;
    page_t *next;
    char count;
    union {
        page_t *children[FACTOR * 2];
        size_t values[FACTOR * 2 - 1];
    } data;
    char keys[1];
};

struct mapping {
    int fd, page_k;
    size_t len;
    void *addr;
    char *break_addr;
};

struct b_tree {
    struct mapping map;
    page_t *root;
};

struct page *new_page(struct mapping *m);
void split_child(struct b_tree *t, page_t *x, int i);
void open_mapping(struct mapping *map);
void close_mapping(struct mapping *map);
void init_tree(struct b_tree *t);
void free_tree(struct b_tree *t);
void insert_key(struct b_tree *t, char *key, size_t len, size_t value);
void split_child(struct b_tree *t, page_t *x, int i);
void move_keys(page_t *dst, page_t *src,
    int dst_i, int src_i, int count);
void insert_nf(struct b_tree *t, page_t *x,
    char *key, size_t len, size_t value);
int find_index(page_t *x, char *key, size_t len);
int compare_keys(char *a, int a_len, char *b);


struct page *new_page(struct mapping *m)
{
    page_t *ret = (page_t *) m->break_addr;
    m->break_addr += PAGE_SIZE;
    m->page_k++;
    //printf("\r%d", m->page_k);
    
    ret->leaf = 1;
    ret->next = NULL;
    ret->count = 0;
    
    return ret;
}

void open_mapping(struct mapping *map)
{
    map->fd = open("tree.dat", O_RDWR | O_CREAT, 0666);
    map->page_k = 0;
    map->len = PAGE_COUNT * PAGE_SIZE;
    lseek(map->fd, map->len - 1, SEEK_SET);
    write(map->fd, "", 1);
    lseek(map->fd, 0, SEEK_SET);
    map->addr = mmap(NULL, map->len, 
        PROT_READ | PROT_WRITE, MAP_PRIVATE, map->fd, 0);
    map->break_addr = (char *) map->addr;
}

void close_mapping(struct mapping *map)
{
    //msync(map->addr, map->len, MS_SYNC);
    munmap(map->addr, map->len);
    close(map->fd);
}

void init_tree(struct b_tree *t)
{
    open_mapping(&t->map);
    t->root = new_page(&t->map);
}

void free_tree(struct b_tree *t)
{
    close_mapping(&t->map);
}

void insert_key(struct b_tree *t, char *key, size_t len, size_t value)
{
    page_t *s;
    
    if (t->root->count == 2 * FACTOR - 1) {
        s = new_page(&t->map);
        s->leaf = 0;
        s->data.children[0] = t->root;

        t->root = s;
        split_child(t, s, 0);
        
        insert_nf(t, s, key, len, value);
    } else {
        insert_nf(t, t->root, key, len, value);
    }
}

void split_child(struct b_tree *t, page_t *x, int i)
{
    page_t *y, *z;
    
    z = new_page(&t->map);
    y = x->data.children[i];
    
    z->leaf = y->leaf;
    z->count = FACTOR + z->leaf - 1;
    z->next = y->next;
    y->next = z;

    move_keys(z, y, 0, FACTOR - z->leaf, FACTOR + z->leaf - 1);
    /* Children/values should be differentiated */
    memcpy(
        z->data.children,
        &y->data.children[FACTOR - z->leaf],
        FACTOR * sizeof(page_t *)
    );
    
    y->count = FACTOR - 1;
    
    memmove(
        &x->data.children[i+2],
        &x->data.children[i+1],
        (x->count - i) * sizeof(page_t *)
    );
    x->data.children[i+1] = z;
    
    move_keys(x, x, i + 1, i, x->count - i);
    move_keys(x, y, i, FACTOR - 1, 1);
    x->count++;
}

void move_keys(page_t *dst, page_t *src,
    int dst_i, int src_i, int count)
{
    memmove(
        dst->keys + dst_i * KEY_SPACE,
        src->keys + src_i * KEY_SPACE,
        count * KEY_SPACE
    );
}

void insert_nf(struct b_tree *t, page_t *x,
    char *key, size_t len, size_t value)
{
    int i = find_index(x, key, len);
    if (x->leaf) {
        move_keys(x, x, i + 1, i, x->count - i);
        memmove(
            &x->data.children[i+1],
            &x->data.children[i],
            (x->count - i) * sizeof(page_t *)
        );
        
        *(x->keys + i * KEY_SPACE) = len;
        memcpy(x->keys + i * KEY_SPACE + 1, key, len);
        x->data.values[i] = value;
        x->count++;
    } else {
        if (x->data.children[i]->count == 2 * FACTOR - 1) {
            split_child(t, x, i);
            if (compare_keys(key, len, x->keys + i * KEY_SPACE) > 0)
                i++;
        }
        insert_nf(t, x->data.children[i], key, len, value);
    }
}

int find_index(page_t *x, char *key, size_t len)
{
    int i = x->count - 1;
    while (i >= 0 && compare_keys(key, len, x->keys + KEY_SPACE * i) < 0)
        i--;
    return i + 1;
}

int compare_keys(char *a, int a_len, char *b)
{
    int b_len = *b++, i = 0;
    while (i < a_len && i < b_len) {
        if (a[i] != b[i])
            return a[i] - b[i];
        i++;
    }
    if (i == a_len && i == b_len)
        return 0;
    else if (i == a_len)
        return -1;
    else
        return 1;
}

void iterate_entries(struct b_tree *t)
{
    int i, v;
    char k[256], *ks;
    page_t *p = t->root;
    
    while (!p->leaf)
        p = p->data.children[0];
    
    while (p) {
        for (i = 0; i < p->count; i++) {
            ks = p->keys + i * KEY_SPACE;
            memcpy(k, ks + 1, *ks);
            k[*ks] = '\0';
            //printf("\r%s %zd", k, p->data.values[i]);
        }
        p = p->next;
    }
}

int main()
{
    struct b_tree t;
    int i, j, n;    
    char k[256];
    
    init_tree(&t);
    
    puts("Insert");
    for (i = 0; i < 2000000; i++) {
        n = 11;
        for (j = 0; j < n; j++)
            k[j] = rand() % 26 + 'A';
        k[n] = 0;
        //printf("\r%s %d\n", k, i);
        
        insert_key(&t, k, n, i);
    }
    
    puts("Iterate");
    iterate_entries(&t);
    free_tree(&t);
    
    return 0;
}