btree.h

Go to the documentation of this file.

/* -*- C -*- */
/*
 * Copyright (c) 2013-2020 Seagate Technology LLC and/or its Affiliates
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * For any questions about this software or licensing,
 * please email opensource@seagate.com or cortx-questions@seagate.com.
 *
 */

#pragma once
#ifndef __MOTR_BE_BTREE_H__
#define __MOTR_BE_BTREE_H__

#include "be/op.h"              /* m0_be_op */
#include "be/seg.h"
#include "be/seg_xc.h"
#include "format/format.h"      /* m0_format_header */
#include "format/format_xc.h"
#include "lib/buf.h"
#include "lib/cookie.h"         /* m0_cookie */
#include "lib/cookie_xc.h"      /* m0_xcode_type */
#include "fid/fid.h" /* m0_fid */
#include "fid/fid_xc.h" /* m0_fid_xc */

/* export */
struct m0_be_btree;
struct m0_be_btree_kv_ops;

/* import */
struct m0_be_bnode;
struct m0_be_tx;
struct m0_be_tx_credit;

struct m0_be_btree_backlink {
        struct m0_cookie bli_tree;
        uint64_t         bli_type; 
        uint64_t         bli_gen;
        struct m0_fid    bli_fid;
} M0_XCA_RECORD M0_XCA_DOMAIN(be);

struct m0_be_btree {
        /*
         * non-volatile fields
         */
        struct m0_format_header          bb_header;
        uint64_t                         bb_cookie_gen;
        struct m0_be_btree_backlink      bb_backlink;
        struct m0_be_bnode              *bb_root;
        struct m0_format_footer          bb_footer;
        /*
         * volatile-only fields
         */
        struct m0_be_rwlock              bb_lock;
        struct m0_be_seg                *bb_seg;
        const struct m0_be_btree_kv_ops *bb_ops;
} M0_XCA_RECORD M0_XCA_DOMAIN(be);

enum m0_be_btree_format_version {
        M0_BE_BTREE_FORMAT_VERSION_1 = 1,

        /* future versions, uncomment and update M0_BE_BTREE_FORMAT_VERSION */
        /*M0_BE_BTREE_FORMAT_VERSION_2,*/
        /*M0_BE_BTREE_FORMAT_VERSION_3,*/

        M0_BE_BTREE_FORMAT_VERSION = M0_BE_BTREE_FORMAT_VERSION_1
};

struct m0_table;
struct m0_table_ops;

struct m0_be_btree_kv_ops {
        uint64_t      ko_type; 
        m0_bcount_t (*ko_ksize)(const void *key);

        m0_bcount_t (*ko_vsize)(const void *data);

        int         (*ko_compare)(const void *key0, const void *key1);
};

enum m0_be_btree_type {
        M0_BBT_INVALID = 1,
        M0_BBT_BALLOC_GROUP_EXTENTS,
        M0_BBT_BALLOC_GROUP_DESC,
        M0_BBT_EMAP_EM_MAPPING,
        M0_BBT_CAS_CTG,
        M0_BBT_COB_NAMESPACE,
        M0_BBT_COB_OBJECT_INDEX,
        M0_BBT_COB_FILEATTR_BASIC,
        M0_BBT_COB_FILEATTR_EA,
        M0_BBT_COB_FILEATTR_OMG,
        M0_BBT_COB_BYTECOUNT,
        M0_BBT_CONFDB,
        M0_BBT_UT_KV_OPS,
        M0_BBT_NR
} M0_XCA_ENUM;

enum m0_be_btree_op {
        M0_BBO_CREATE,      
        M0_BBO_DESTROY,     
        M0_BBO_INSERT,      
        M0_BBO_DELETE,      
        M0_BBO_UPDATE,      
        M0_BBO_LOOKUP,      
        M0_BBO_MAXKEY,      
        M0_BBO_MINKEY,      
        M0_BBO_CURSOR_GET,  
        M0_BBO_CURSOR_NEXT, 
        M0_BBO_CURSOR_PREV, 
};

M0_EXTERN const struct m0_fid_type m0_btree_fid_type;


/* ------------------------------------------------------------------
 * Btree construction
 * ------------------------------------------------------------------ */

M0_INTERNAL void m0_be_btree_init(struct m0_be_btree *tree,
                                  struct m0_be_seg *seg,
                                  const struct m0_be_btree_kv_ops *ops);

M0_INTERNAL void m0_be_btree_fini(struct m0_be_btree *tree);

M0_INTERNAL void m0_be_btree_create(struct m0_be_btree  *tree,
                                    struct m0_be_tx     *tx,
                                    struct m0_be_op     *op,
                                    const struct m0_fid *btree_fid);

M0_INTERNAL void m0_be_btree_destroy(struct m0_be_btree *tree,
                                     struct m0_be_tx *tx,
                                     struct m0_be_op *op);

M0_INTERNAL void m0_be_btree_truncate(struct m0_be_btree *tree,
                                      struct m0_be_tx    *tx,
                                      struct m0_be_op    *op,
                                      m0_bcount_t         limit);


/* ------------------------------------------------------------------
 * Btree credits
 * ------------------------------------------------------------------ */

M0_INTERNAL void m0_be_btree_create_credit(const struct m0_be_btree *tree,
                                           m0_bcount_t nr,
                                           struct m0_be_tx_credit *accum);

M0_INTERNAL void m0_be_btree_destroy_credit(struct m0_be_btree *tree,
                                            struct m0_be_tx_credit *accum);


M0_INTERNAL void m0_be_btree_clear_credit(struct m0_be_btree     *tree,
                                          struct m0_be_tx_credit *fixed_part,
                                          struct m0_be_tx_credit *single_record,
                                          m0_bcount_t            *records_nr);

M0_INTERNAL void m0_be_btree_insert_credit(const struct m0_be_btree *tree,
                                           m0_bcount_t nr,
                                           m0_bcount_t ksize,
                                           m0_bcount_t vsize,
                                           struct m0_be_tx_credit *accum);

M0_INTERNAL void m0_be_btree_insert_credit2(const struct m0_be_btree *tree,
                                            m0_bcount_t nr,
                                            m0_bcount_t ksize,
                                            m0_bcount_t vsize,
                                            struct m0_be_tx_credit *accum);

M0_INTERNAL void m0_be_btree_delete_credit(const struct m0_be_btree *tree,
                                                 m0_bcount_t nr,
                                                 m0_bcount_t ksize,
                                                 m0_bcount_t vsize,
                                                 struct m0_be_tx_credit *accum);

M0_INTERNAL void m0_be_btree_update_credit(const struct m0_be_btree *tree,
                                                 m0_bcount_t nr,
                                                 m0_bcount_t vsize,
                                                 struct m0_be_tx_credit *accum);

M0_INTERNAL void m0_be_btree_update_credit2(const struct m0_be_btree *tree,
                                            m0_bcount_t               nr,
                                            m0_bcount_t               ksize,
                                            m0_bcount_t               vsize,
                                            struct m0_be_tx_credit   *accum);


/* ------------------------------------------------------------------
 * Btree manipulation
 * ------------------------------------------------------------------ */

M0_INTERNAL void m0_be_btree_insert(struct m0_be_btree *tree,
                                    struct m0_be_tx *tx,
                                    struct m0_be_op *op,
                                    const struct m0_buf *key,
                                    const struct m0_buf *value);

M0_INTERNAL void m0_be_btree_save(struct m0_be_btree  *tree,
                                  struct m0_be_tx     *tx,
                                  struct m0_be_op     *op,
                                  const struct m0_buf *key,
                                  const struct m0_buf *val,
                                  bool                 overwrite);

M0_INTERNAL void m0_be_btree_update(struct m0_be_btree *tree,
                                    struct m0_be_tx *tx,
                                    struct m0_be_op *op,
                                    const struct m0_buf *key,
                                    const struct m0_buf *value);

M0_INTERNAL void m0_be_btree_delete(struct m0_be_btree *tree,
                                    struct m0_be_tx *tx,
                                    struct m0_be_op *op,
                                    const struct m0_buf *key);

M0_INTERNAL void m0_be_btree_lookup(struct m0_be_btree *tree,
                                    struct m0_be_op *op,
                                    const struct m0_buf *key,
                                    struct m0_buf *dest_value);

M0_INTERNAL void m0_be_btree_lookup_slant(struct m0_be_btree *tree,
                                          struct m0_be_op *op,
                                          struct m0_buf *key,
                                          struct m0_buf *value);

M0_INTERNAL void m0_be_btree_maxkey(struct m0_be_btree *tree,
                                    struct m0_be_op *op,
                                    struct m0_buf *out);

M0_INTERNAL void m0_be_btree_minkey(struct m0_be_btree *tree,
                                    struct m0_be_op *op,
                                    struct m0_buf *out);

/* ------------------------------------------------------------------
 * Btree in-place manipulation
 * ------------------------------------------------------------------ */

struct m0_be_btree_anchor {
        struct m0_be_btree *ba_tree;
        struct m0_buf       ba_value;

        bool                ba_write;
};

M0_INTERNAL void m0_be_btree_update_inplace(struct m0_be_btree *tree,
                                            struct m0_be_tx *tx,
                                            struct m0_be_op *op,
                                            const struct m0_buf *key,
                                            struct m0_be_btree_anchor *anchor);

M0_INTERNAL void m0_be_btree_insert_inplace(struct m0_be_btree *tree,
                                            struct m0_be_tx *tx,
                                            struct m0_be_op *op,
                                            const struct m0_buf *key,
                                            struct m0_be_btree_anchor *anchor,
                                            uint64_t zonemask);

M0_INTERNAL void m0_be_btree_save_inplace(struct m0_be_btree        *tree,
                                          struct m0_be_tx           *tx,
                                          struct m0_be_op           *op,
                                          const struct m0_buf       *key,
                                          struct m0_be_btree_anchor *anchor,
                                          bool                       overwrite,
                                          uint64_t                   zonemask);

M0_INTERNAL void m0_be_btree_lookup_inplace(struct m0_be_btree *tree,
                                            struct m0_be_op *op,
                                            const struct m0_buf *key,
                                            struct m0_be_btree_anchor *anchor);

M0_INTERNAL void m0_be_btree_release(struct m0_be_tx           *tx,
                                     struct m0_be_btree_anchor *anchor);

/* ------------------------------------------------------------------
 * Btree cursor
 * ------------------------------------------------------------------ */

struct m0_be_btree_cursor_stack_entry {
        int                 bs_idx;
        struct m0_be_bnode *bs_node;
};

enum {
        BTREE_FAN_OUT    = 128,
        BTREE_HEIGHT_MAX = 5
};

struct m0_be_btree_cursor {
        int                                   bc_pos;
        int                                   bc_stack_pos;
        struct m0_be_btree                   *bc_tree;
        struct m0_be_bnode                   *bc_node;
        struct m0_be_btree_cursor_stack_entry bc_stack[BTREE_HEIGHT_MAX];
        struct m0_be_op                       bc_op; /* XXX DELETEME */
};

M0_INTERNAL void m0_be_btree_cursor_init(struct m0_be_btree_cursor *it,
                                         struct m0_be_btree *tree);

M0_INTERNAL void m0_be_btree_cursor_fini(struct m0_be_btree_cursor *it);

M0_INTERNAL void m0_be_btree_cursor_get(struct m0_be_btree_cursor *it,
                                        const struct m0_buf *key, bool slant);

M0_INTERNAL int m0_be_btree_cursor_get_sync(struct m0_be_btree_cursor *it,
                                            const struct m0_buf *key,
                                            bool slant);

M0_INTERNAL void m0_be_btree_cursor_next(struct m0_be_btree_cursor *it);

M0_INTERNAL int m0_be_btree_cursor_next_sync(struct m0_be_btree_cursor *it);

M0_INTERNAL void m0_be_btree_cursor_prev(struct m0_be_btree_cursor *it);

M0_INTERNAL int m0_be_btree_cursor_prev_sync(struct m0_be_btree_cursor *it);

M0_INTERNAL int m0_be_btree_cursor_first_sync(struct m0_be_btree_cursor *it);

M0_INTERNAL int m0_be_btree_cursor_last_sync(struct m0_be_btree_cursor *it);

M0_INTERNAL void m0_be_btree_cursor_put(struct m0_be_btree_cursor *it);

M0_INTERNAL void m0_be_btree_cursor_kv_get(struct m0_be_btree_cursor *it,
                                           struct m0_buf *key,
                                           struct m0_buf *val);

M0_INTERNAL bool m0_be_btree_is_empty(struct m0_be_btree *tree);

#endif /* __MOTR_BE_BTREE_H__ */

/*
 *  Local variables:
 *  c-indentation-style: "K&R"
 *  c-basic-offset: 8
 *  tab-width: 8
 *  fill-column: 80
 *  scroll-step: 1
 *  End:
 */
/*
 * vim: tabstop=8 shiftwidth=8 noexpandtab textwidth=80 nowrap
 */