xref: /6.6.0/couchstore/src/couch_btree.h (revision aa2f4cf2)
1#ifndef COUCH_BTREE_H
2#define COUCH_BTREE_H
3#include <libcouchstore/couch_common.h>
4#include "internal.h"
5#include "arena.h"
6
7// B+tree KV (leaf) node size limit.
8#define DB_KV_CHUNK_THRESHOLD 1279
9// B+tree KP (intermediate) node size limit.
10#define DB_KP_CHUNK_THRESHOLD 1279
11#define MAX_REDUCTION_SIZE ((1 << 16) - 1)
12
13    typedef int (*compare_callback)(const sized_buf *k1, const sized_buf *k2);
14
15    typedef struct compare_info {
16        /* Compare function */
17        compare_callback compare;
18    } compare_info;
19
20
21    /* Lookup */
22
23    struct couchfile_lookup_request {
24        couchfile_lookup_request()
25            : cmp({nullptr}),
26              file(nullptr),
27              num_keys(0),
28              fold(0),
29              in_fold(0),
30              tolerate_corruption(0),
31              keys(nullptr),
32              callback_ctx(nullptr),
33              fetch_callback(nullptr),
34              node_callback(nullptr) {
35        }
36
37        compare_info cmp;
38        tree_file *file;
39        int num_keys;
40        /**
41         * If nonzero, calls fetch_callback for all keys between and
42         * including key 0 and key 1 in the keys array, or all keys after
43         * key 0 if it contains only one key.
44         * GIVE KEYS SORTED.
45         */
46        int fold;
47        //  v-- Flag used during lookup, do not set.
48        int in_fold;
49        // If nonzero, continue to traverse tree skipping corrupted node.
50        int tolerate_corruption;
51        sized_buf **keys;
52        void *callback_ctx;
53        couchstore_error_t (*fetch_callback) (
54                struct couchfile_lookup_request *rq,
55                const sized_buf *k,
56                const sized_buf *v);
57        couchstore_error_t (*node_callback) (
58                struct couchfile_lookup_request *rq,
59                uint64_t subtreeSize,
60                const sized_buf *reduce_value);
61    } ;
62
63    couchstore_error_t btree_lookup(couchfile_lookup_request *rq,
64                                    uint64_t root_pointer);
65
66    /* Modify */
67    typedef struct nodelist {
68        sized_buf data;
69        sized_buf key;
70        node_pointer *pointer;
71        struct nodelist *next;
72    } nodelist;
73
74    /* Reduce function gets items and places reduce value in dst buffer */
75    typedef couchstore_error_t (*reduce_fn)(char *dst,
76                                            size_t *size_r,
77                                            const nodelist *itmlist,
78                                            int count,
79                                            void *ctx);
80
81    typedef couchstore_error_t (*make_docinfo_callback)(DocInfo** pInfo,
82                                                        const sized_buf* k,
83                                                        const sized_buf* v);
84
85#define ACTION_FETCH  0
86#define ACTION_REMOVE 1
87#define ACTION_INSERT 2
88#define ACTION_FETCH_INSERT 3
89
90    typedef struct couchfile_modify_action {
91        int type;
92        sized_buf *key;
93        sized_buf* data;
94        sized_buf* seq;
95    } couchfile_modify_action;
96
97    /* Guided purge related constants */
98#define PURGE_ITEM    0
99#define PURGE_STOP    1
100#define PURGE_KEEP    2
101#define PURGE_PARTIAL 3
102
103    /* Returns purge action or error code */
104    typedef int (*purge_kp_fn)(const node_pointer *nptr, void *ctx);
105    typedef int (*purge_kv_fn)(const sized_buf *key, const sized_buf *val, void *ctx);
106
107    typedef struct couchfile_modify_request {
108        couchfile_modify_request()
109            : file(nullptr),
110              num_actions(0),
111              actions(nullptr),
112              fetch_callback(nullptr),
113              reduce(nullptr),
114              rereduce(nullptr),
115              user_reduce_ctx(nullptr),
116              purge_kp(nullptr),
117              purge_kv(nullptr),
118              enable_purging(0),
119              guided_purge_ctx(nullptr),
120              compacting(0),
121              kv_chunk_threshold(0),
122              kp_chunk_threshold(0),
123              save_callback(nullptr),
124              save_callback_ctx(nullptr),
125              docinfo_callback(nullptr) {
126        }
127        compare_info cmp;
128        tree_file *file;
129        int num_actions;
130        couchfile_modify_action *actions;
131        void (*fetch_callback) (struct couchfile_modify_request *rq, sized_buf *k, sized_buf *v, void *arg);
132        void* fetch_callback_ctx;
133        reduce_fn reduce;
134        reduce_fn rereduce;
135        void *user_reduce_ctx;
136        /* For guided btree purge */
137        purge_kp_fn purge_kp;
138        purge_kv_fn purge_kv;
139        int enable_purging;
140        void *guided_purge_ctx;
141        /*  We're in the compactor */
142        int compacting;
143        int kv_chunk_threshold;
144        int kp_chunk_threshold;
145        save_callback_fn save_callback;
146        void* save_callback_ctx;
147        make_docinfo_callback docinfo_callback;
148    } couchfile_modify_request;
149
150#define KP_NODE 0
151#define KV_NODE 1
152
153    /* Used to build and chunk modified nodes */
154    typedef struct couchfile_modify_result {
155        couchfile_modify_request *rq;
156        struct arena *arena;
157        /* If this is set, prefer to put items that can be thrown away after a flush in this arena */
158        struct arena *arena_transient;
159        nodelist *values;
160        nodelist *values_end;
161
162        long node_len;
163        int count;
164
165        nodelist *pointers;
166        nodelist *pointers_end;
167        /* If we run over a node and never set this, it can be left as-is on disk. */
168        int modified;
169        /* 1 - leaf, 0 - ptr */
170        int node_type;
171        int error_state;
172    } couchfile_modify_result;
173
174    node_pointer *modify_btree(couchfile_modify_request *rq,
175                               node_pointer *root,
176                               couchstore_error_t *errcode);
177
178    couchstore_error_t mr_push_item(sized_buf *k, sized_buf *v, couchfile_modify_result *dst);
179
180    couchfile_modify_result* new_btree_modres(arena* a, arena* transient_arena, tree_file *file,
181                                              compare_info* cmp, reduce_fn reduce,
182                                              reduce_fn rereduce, void *user_reduce_ctx,
183                                              int kv_chunk_threshold,
184                                              int kp_chunk_threshold);
185
186    node_pointer* complete_new_btree(couchfile_modify_result* mr, couchstore_error_t *errcode);
187
188    node_pointer *guided_purge_btree(couchfile_modify_request *rq,
189                                                node_pointer *root,
190                                                couchstore_error_t *errcode);
191
192    node_pointer* copy_node_pointer(node_pointer* ptr);
193
194    node_pointer *read_pointer(arena* a, sized_buf *key, char *buf);
195
196    node_pointer *finish_root(couchfile_modify_request *rq,
197                              couchfile_modify_result *root_result,
198                              couchstore_error_t *errcode);
199
200    couchfile_modify_result *make_modres(arena* a, couchfile_modify_request *rq);
201
202#endif
203