1 | /* onode_index.h
2 | -------------
3 | A casually demented B+Tree designed to stay balanced
4 | and be optimized for access from disk (and in-core cache)
5 | and not to have to write lots of times.
6 |
7 | Some of the ideas for this came from Reiser4 stuff, except
8 | I'm allowing unbalanced stuff to make it to disk if needed.
9 | I'm thinking that if things get really bad, we can run a
10 | tree repacker :)
11 |
12 | $Id: onode_index.h,v 1.9 2003/10/20 07:18:11 stewart Exp $
13 |
14 | (C)2003 Stewart Smith
15 | Distributed under the GNU Public License
16 | */
17 |
18 | #ifndef __ONODE_INDEX_H__
19 | #define __ONODE_INDEX_H__
20 |
21 | #include "testkit/types.h"
22 |
23 | /* In memory representation of onode_index */
24 | struct fcfs_onode_index {
25 | // u64 root_blocknr; /* block run for root of index */
26 | struct fcfs_onode_index_node *root; /* the node */
27 | struct fcfs_disk_block *root_block; /* disk block for node */
28 | struct fcfs_disk *disk; /* disk the index is on */
29 | };
30 |
31 | #define FCFS_ONODE_INDEX_NODE_MAGIC1 0x4f6e4944784e4445ULL /* OnIDxNDE */
32 |
33 | struct fcfs_onode_index_node_item {
34 | u64 key;
35 | u64 node_blocknr;
36 | };
37 |
38 | struct fcfs_onode_index_node {
39 | u64 magic1; /* FCFS_ONODE_INDEX_NODE_MAGIC1 */
40 | u64 id; /*Not necessarily unique, used for locking */
41 | u64 block;
42 | u64 used;
43 | struct fcfs_onode_index_node_item items[1];
44 | };
45 |
46 | #define FCFS_ONODE_INDEX_LEAF_MAGIC1 0x4f6e4944784c6665ULL /* OnIDxLfe */
47 |
48 | struct fcfs_onode_index_leaf_item {
49 | u64 key;
50 | u64 onode_blocknr;
51 | };
52 |
53 | struct fcfs_onode_index_leaf {
54 | u64 magic1; /* FCFS_ONODE_INDEX_LEAF_MAGIC1 */
55 | u64 id; /* Not necessarily unique, used for locking */
56 | u64 block;
57 | u64 used;
58 | struct fcfs_onode_index_leaf_item items[1];
59 | };
60 |
61 | u64 onode_index_new_id(struct fcfs_onode_index *index);
62 | struct fcfs_onode_index* onode_index_read(struct fcfs_disk *disk);
63 | struct fcfs_onode_index* onode_index_new(struct fcfs_disk *disk);
64 | int onode_index_write_leaf(struct fcfs_onode_index *index, struct fcfs_onode_index_leaf *leaf);
65 | struct fcfs_disk_block *onode_index_new_node(struct fcfs_onode_index *index);
66 | struct fcfs_onode_index_leaf *onode_index_leaf_new(struct fcfs_onode_index *index, struct fcfs_onode_index_node *parent, int position);
67 | struct fcfs_onode_index_node* onode_index_read_node(struct fcfs_onode_index *index, u64 blocknr);
68 | int onode_index_free_node(struct fcfs_onode_index *index, struct fcfs_onode_index_node* node);
69 | int onode_index_write_node(struct fcfs_onode_index *index, struct fcfs_onode_index_node* node);
70 |
71 | int onode_index_new_root(struct fcfs_onode_index *index);
72 | int onode_index_leaf_insert(struct fcfs_disk *disk,struct fcfs_onode_index_leaf *leaf, u64 key, u64 value);
73 | struct fcfs_block_run* onode_index_insert(struct fcfs_onode_index *index, struct fcfs_onode1 *onode);
74 | struct fcfs_disk_block *onode_index_lookup(struct fcfs_onode_index *index,struct fcfs_block_run *onode_br, u64 id);
75 | struct fcfs_onode_index* onode_index_delete(struct fcfs_onode_index* index);
76 |
77 | #endif