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