begeekmyfriend / bplustree Goto Github PK

/*
 * Copyright (C) 2015, Leo Ma <[email protected]>
 */

#ifndef _BPLUS_TREE_H
#define _BPLUS_TREE_H

#define BPLUS_MIN_ORDER     3
#define BPLUS_MAX_ORDER     64
#define BPLUS_MAX_ENTRIES   64
#define BPLUS_MAX_LEVEL     10

typedef int key_t;

struct list_head {
        struct list_head *prev, *next;
};

static inline void list_init(struct list_head *link)
{
        link->prev = link;
        link->next = link;
}

static inline void
__list_add(struct list_head *link, struct list_head *prev, struct list_head *next)
{
        link->next = next;
        link->prev = prev;
        next->prev = link;
        prev->next = link;
}

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
        prev->next = next;
        next->prev = prev;
}

static inline void list_add(struct list_head *link, struct list_head *prev)
{
        __list_add(link, prev, prev->next);
}

static inline void list_add_tail(struct list_head *link, struct list_head *head)
{
	__list_add(link, head->prev, head);
}

static inline void list_del(struct list_head *link)
{
        __list_del(link->prev, link->next);
        list_init(link);
}

static inline int list_is_first(struct list_head *link, struct list_head *head)
{
	return link->prev == head;
}

static inline int list_is_last(struct list_head *link, struct list_head *head)
{
	return link->next == head;
}

#define list_entry(ptr, type, member) \
        ((type *)((char *)(ptr) - (size_t)(&((type *)0)->member)))

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_prev_entry(pos, member) \
	list_entry((pos)->member.prev, typeof(*(pos)), member)

#define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)
/**
 * b plus tree basic node
 * 
 * 
 */ 
struct bplus_node {
/**  type indicates leaf node or not
 *     BPLUS_TREE_LEAF is 0 and  BPLUS_TREE_NON_LEAF is 1
 */
        int type;
/**     parent_key_idx: index of parent node */
        int parent_key_idx;
/** piointer to parent node */
        struct bplus_non_leaf *parent;
/** pointer to first node(head) in leaf linked list */
        struct list_head link;
/** */
        int count;
};
/**  b plus tree non-leaf(internal)  node 
 * non-leaf node need to carry children node information
 * node contains only keys not key-value-pairs
 
*/
struct bplus_non_leaf {
/**  type indicates leaf node or not
 *     BPLUS_TREE_LEAF is 0 and  BPLUS_TREE_NON_LEAF is 1
 */
        int type;
/**     parent_key_idx: index of parent node */
        int parent_key_idx;
/** piointer to parent node */
        struct bplus_non_leaf *parent;
/** pointer to first node(head) in leaf linked list 
*/
        struct list_head link;
/**  number of child node */
        int children;
/**  key array */
        int key[BPLUS_MAX_ORDER - 1];
/** pointers to child node */
        struct bplus_node *sub_ptr[BPLUS_MAX_ORDER];
};
/**  b plus tree leaf node 
 * leaf node need to carry key-value-pairs
 
*/
struct bplus_leaf {
/**  type indicates leaf node or not
 *     BPLUS_TREE_LEAF is 0 and  BPLUS_TREE_NON_LEAF is 1
 */
        int type;
/**     parent_key_idx: index of parent node */
        int parent_key_idx;
/** piointer to parent node */
        struct bplus_non_leaf *parent;
/** pointer to first node(head) in leaf linked list 
*/
        struct list_head link;
/** number of actual key-value pairs in leaf node */
        int entries;
/**  key array */
        int key[BPLUS_MAX_ENTRIES];
/**  val array */
        int data[BPLUS_MAX_ENTRIES];

};
/** b plus tree structure */
struct bplus_tree {
/**  The actual number of children for a node, referred to here as order */
        int order;
/** number of actual key-value pairs in tree */
        int entries;
/** height of the tree */
        int level;
        struct bplus_node *root;
/** double linked list to search leaf node */
        struct list_head list[BPLUS_MAX_LEVEL];
};
 /** print the whole tree for debugging
   *  
   * @param tree pointer to bplus tree
   */
void bplus_tree_dump(struct bplus_tree *tree);
 /** return value acordding to key
   *  
   * @param tree pointer to bplus tree
   * @param key  key in key-value pair
   */
int bplus_tree_get(struct bplus_tree *tree, key_t key);
 /** insert key-value pair to tree
   *  
   * @param tree pointer to bplus tree
   * @param key  key in key-value pair
   * @param data value in key-value pair
   
   */
int bplus_tree_put(struct bplus_tree *tree, key_t key, int data);

 /** return data between [key1,key2]
   *  
   * @param tree pointer to bplus tree
   * @param key1  key in key-value pair
   * @param key2 value in key-value pair
   
*/
int bplus_tree_get_range(struct bplus_tree *tree, key_t key1, key_t key2);

 /** init b plus tree 
  * @return a pointer to tree
   *  
   * @param order  The actual number of children for a node, referred to here as order 
   * @param key1  key in key-value pair
   * @param key2  key in key-value pair
   
*/
struct bplus_tree *bplus_tree_init(int order, int entries);
 /** destory the tree safely
  * @return a pointer to tree
   * @param order  The actual number of children for a node, referred to here as order 
   * @param entries   number of actual key-value pairs in tree 
   
   
*/
void bplus_tree_deinit(struct bplus_tree *tree);

#endif  /* _BPLUS_TREE_H */

    /* split = [m/2] */
    int split = (_max_order + 1) / 2;

    /* split as right sibling */
    right_node_add(tree, node, right);

    /* split key is key[split - 1] */
    key_t split_key = key(node)[split - 1];

    /* calculate split nodes' children (sum as (order + 1))*/
    int pivot = 0;
    node->children = split;
    right->children = _max_order - split + 1;

    /* insert new key and sub-nodes */
    key(right)[0] = key;
    sub_node_update(tree, right, pivot, l_ch);
    sub_node_update(tree, right, pivot + 1, r_ch);

    /* sum = right->children = 2 + (right->children - 2) */
    /* replicate from key[split] to key[_max_order - 2] */
    memmove(&key(right)[pivot + 1], &key(node)[split], (right->children - 2) * sizeof(key_t));
    memmove(&sub(right)[pivot + 2], &sub(node)[split + 1], (right->children - 2) * sizeof(off_t));

/home/yxy/桌面/bplustree/tests/bplustree_demo.c: In function ‘bplus_tree_setting’:
/home/yxy/桌面/bplustree/tests/bplustree_demo.c:29:25: error: this statement may fall through [-Werror=implicit-fallthrough=]
                         printf("\n");
                         ^~~~~~~~~~~~
/home/yxy/桌面/bplustree/tests/bplustree_demo.c:30:17: note: here
                 case 'q':
                 ^~~~
/home/yxy/桌面/bplustree/tests/bplustree_demo.c:54:25: error: this statement may fall through [-Werror=implicit-fallthrough=]
                         printf("\n");
                         ^~~~~~~~~~~~
/home/yxy/桌面/bplustree/tests/bplustree_demo.c:55:17: note: here
                 case 'q':
                 ^~~~
/home/yxy/桌面/bplustree/tests/bplustree_demo.c: In function ‘command_process’:
/home/yxy/桌面/bplustree/tests/bplustree_demo.c:196:28: error: this statement may fall through [-Werror=implicit-fallthrough=]
                         if (number_process(tree, c) < 0) {
                            ^
/home/yxy/桌面/bplustree/tests/bplustree_demo.c:199:17: note: here
                 case '\n':
                 ^~~~
cc1: all warnings being treated as errors

Please wait about 10 seconds for test case generation...
CMake Deprecation Warning at CMakeLists.txt:1 (cmake_minimum_required):
  Compatibility with CMake < 2.8.12 will be removed from a future version of
  CMake.

  Update the VERSION argument <min> value or use a ...<max> suffix to tell
  CMake that the project does not need compatibility with older versions.
-- The C compiler identification is AppleClang 13.0.0.13000029
-- The CXX compiler identification is AppleClang 13.0.0.13000029
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
CMake Error at cmake/CodeCoverage.cmake:127 (MESSAGE):
  lcov not found! Aborting...
Call Stack (most recent call first):
  tests/CMakeLists.txt:16 (setup_target_for_coverage)

static key_t non_leaf_split_right2(struct bplus_tree *tree, struct bplus_node *node,
                        	   struct bplus_node *right, struct bplus_node *l_ch,
                        	   struct bplus_node *r_ch, key_t key, int insert)
{
        int i;

        /* split = [m/2] */
        int split = (_max_order + 1) / 2;

        /* split as right sibling */
        right_node_add(tree, node, right);

        /* split key is key[split] */
        key_t split_key = key(node)[split];  // it's here, split_key = key(node)[split - 1] maybe better?

        /* calculate split nodes' children (sum as (order + 1))*/
        int pivot = insert - split - 1;
        node->children = split + 1;
        right->children = _max_order - split;

        /* sum = right->children = pivot + 2 + (_max_order - insert - 1) */
        /* replicate from key[split + 1] to key[insert] */
        memmove(&key(right)[0], &key(node)[split + 1], pivot * sizeof(key_t));
        memmove(&sub(right)[0], &sub(node)[split + 1], pivot * sizeof(off_t));

        /* insert new key and sub-node */
        key(right)[pivot] = key;
        sub_node_update(tree, right, pivot, l_ch);
        sub_node_update(tree, right, pivot + 1, r_ch);

        /* replicate from key[insert] to key[order - 1] */
        memmove(&key(right)[pivot + 1], &key(node)[insert], (_max_order - insert - 1) * sizeof(key_t));
        memmove(&sub(right)[pivot + 2], &sub(node)[insert + 1], (_max_order - insert - 1) * sizeof(off_t));

        /* flush sub-nodes of the new splitted right node */
        for (i = 0; i < right->children; i++) {
                if (i != pivot && i != pivot + 1) {
                        sub_node_flush(tree, right, sub(right)[i]);
                }
        }

        return split_key;
}