96 lines
2.6 KiB
C
96 lines
2.6 KiB
C
#ifndef INDEX_H
|
|
#define INDEX_H
|
|
|
|
#include "io.h"
|
|
#include "record.h"
|
|
#include "tape.h"
|
|
#include <inttypes.h>
|
|
#include <stdbool.h>
|
|
|
|
#define SIZEOF_ENTRIES(n) (sizeof(btree_node_header_t) + (sizeof(btree_entry_t) - sizeof(page_t))*(n) + ((n) > 0 ? 1 : 0) * sizeof(page_t))
|
|
#define NODE_SIZE(node) SIZEOF_ENTRIES(node->header.entries)
|
|
#define NODE_SIZE_MAX (PAGE_SIZE - sizeof(btree_node_header_t))
|
|
#define NODE_ENTRY_OFFSET(n) (sizeof(btree_entry_t) - sizeof(page_t))*(n)
|
|
|
|
#define NODE_ENTRY(buffer, n) ((btree_entry_t*)((char*)buffer + NODE_ENTRY_OFFSET(n)))
|
|
#define ENTRY_INDEX(buffer, entry) (((char*)buffer - (char*)entry) / (sizeof(btree_entry_t) - sizeof(page_t)))
|
|
|
|
#define NODE_IS_ROOT 1
|
|
#define NODE_IS_LEAF 2
|
|
|
|
#define BTREE_ERR_CANNOT_OPEN_FILE -1
|
|
#define BTREE_ERR_PAGE_SIZE_DIFFERENT -2
|
|
|
|
#define BTREE_OPTIMIZE_RECORDS_MIN 1000
|
|
#define BTREE_OPTIMIZE_THRESHOLD 0.1
|
|
|
|
typedef struct {
|
|
size_t d; /* 8 bytes long */
|
|
size_t page_size; /* 8 bytes long */
|
|
page_t root; /* 8 bytes long */
|
|
char main[256]; /* 256 bytes long */
|
|
size_t records; /* 8 bytes long */
|
|
size_t changes; /* 8 bytes long */
|
|
} btree_header_t; /* 296 bytes long */
|
|
|
|
typedef struct {
|
|
uint16_t flags;
|
|
uint16_t entries;
|
|
} btree_node_header_t;
|
|
|
|
typedef struct {
|
|
btree_node_header_t header;
|
|
char entries[NODE_SIZE_MAX];
|
|
page_t page;
|
|
} btree_node_t;
|
|
|
|
typedef struct {
|
|
page_t left;
|
|
record_key_t key;
|
|
offset_t location;
|
|
page_t right;
|
|
} btree_entry_t;
|
|
|
|
typedef struct {
|
|
btree_node_t node;
|
|
btree_entry_t *entry;
|
|
unsigned position;
|
|
} btree_stack_elem_t;
|
|
|
|
typedef struct {
|
|
file_t *file;
|
|
tape_t *main;
|
|
btree_header_t header;
|
|
struct {
|
|
btree_stack_elem_t *current;
|
|
btree_stack_elem_t stack[100];
|
|
} trace;
|
|
} btree_t;
|
|
|
|
typedef struct {
|
|
page_t left;
|
|
page_t right;
|
|
|
|
btree_entry_t *left_entry;
|
|
btree_entry_t *right_entry;
|
|
} btree_siblings_t;
|
|
|
|
int btree_init(btree_t *tree, char* filename, size_t d);
|
|
int btree_open(btree_t *tree, char* filename);
|
|
|
|
void btree_optimize(btree_t *tree);
|
|
|
|
page_t btree_insert(btree_t *tree, record_t record);
|
|
page_t btree_remove(btree_t *tree, record_key_t key);
|
|
bool btree_update(btree_t *tree, record_key_t key, record_t record);
|
|
page_t btree_find(btree_t *tree, record_key_t key, btree_entry_t *entry, btree_node_t *node, unsigned *index);
|
|
|
|
page_t btree_read_record(btree_t *tree, record_key_t key, record_t *record);
|
|
|
|
btree_entry_t *btree_get_entry(btree_node_t* node, unsigned n);
|
|
|
|
void btree_flush(btree_t* tree);
|
|
void btree_close(btree_t* tree);
|
|
|
|
#endif /* INDEX_H */
|