From d98f46ce647846b0aa30b2e16a30fd4e152a1bf5 Mon Sep 17 00:00:00 2001 From: Carlos Maiolino Date: Thu, 10 Jul 2025 22:55:07 +0200 Subject: Add new code Signed-off-by: Carlos Maiolino --- Algorithms/bplus-tree/.gitignore | 2 + Algorithms/bplus-tree/.uncrustifyrc | 1485 ++++++++++++++++++++++++ Algorithms/bplus-tree/LICENSE | 23 + Algorithms/bplus-tree/Makefile | 22 + Algorithms/bplus-tree/include/bplus_tree.h | 63 + Algorithms/bplus-tree/src/bplus_foreach.c | 39 + Algorithms/bplus-tree/src/bplus_foreach.h | 27 + Algorithms/bplus-tree/src/bplus_insert.c | 58 + Algorithms/bplus-tree/src/bplus_insert.h | 22 + Algorithms/bplus-tree/src/bplus_iterator.c | 161 +++ Algorithms/bplus-tree/src/bplus_iterator.h | 31 + Algorithms/bplus-tree/src/bplus_leaf.c | 71 ++ Algorithms/bplus-tree/src/bplus_leaf.h | 34 + Algorithms/bplus-tree/src/bplus_node.c | 111 ++ Algorithms/bplus-tree/src/bplus_node.h | 55 + Algorithms/bplus-tree/src/bplus_rebalance.c | 279 +++++ Algorithms/bplus-tree/src/bplus_rebalance.h | 24 + Algorithms/bplus-tree/src/bplus_remove.c | 60 + Algorithms/bplus-tree/src/bplus_remove.h | 22 + Algorithms/bplus-tree/src/bplus_search.c | 127 ++ Algorithms/bplus-tree/src/bplus_search.h | 23 + Algorithms/bplus-tree/src/bplus_tree.c | 202 ++++ Algorithms/bplus-tree/src/bplus_tree_private.h | 53 + Algorithms/bplus-tree/test/bplus_tree_all.c | 14 + Algorithms/bplus-tree/test/bplus_tree_test.c | 560 +++++++++ 25 files changed, 3568 insertions(+) create mode 100644 Algorithms/bplus-tree/.gitignore create mode 100644 Algorithms/bplus-tree/.uncrustifyrc create mode 100644 Algorithms/bplus-tree/LICENSE create mode 100644 Algorithms/bplus-tree/Makefile create mode 100644 Algorithms/bplus-tree/include/bplus_tree.h create mode 100644 Algorithms/bplus-tree/src/bplus_foreach.c create mode 100644 Algorithms/bplus-tree/src/bplus_foreach.h create mode 100644 Algorithms/bplus-tree/src/bplus_insert.c create mode 100644 Algorithms/bplus-tree/src/bplus_insert.h create mode 100644 Algorithms/bplus-tree/src/bplus_iterator.c create mode 100644 Algorithms/bplus-tree/src/bplus_iterator.h create mode 100644 Algorithms/bplus-tree/src/bplus_leaf.c create mode 100644 Algorithms/bplus-tree/src/bplus_leaf.h create mode 100644 Algorithms/bplus-tree/src/bplus_node.c create mode 100644 Algorithms/bplus-tree/src/bplus_node.h create mode 100644 Algorithms/bplus-tree/src/bplus_rebalance.c create mode 100644 Algorithms/bplus-tree/src/bplus_rebalance.h create mode 100644 Algorithms/bplus-tree/src/bplus_remove.c create mode 100644 Algorithms/bplus-tree/src/bplus_remove.h create mode 100644 Algorithms/bplus-tree/src/bplus_search.c create mode 100644 Algorithms/bplus-tree/src/bplus_search.h create mode 100644 Algorithms/bplus-tree/src/bplus_tree.c create mode 100644 Algorithms/bplus-tree/src/bplus_tree_private.h create mode 100644 Algorithms/bplus-tree/test/bplus_tree_all.c create mode 100644 Algorithms/bplus-tree/test/bplus_tree_test.c (limited to 'Algorithms/bplus-tree') diff --git a/Algorithms/bplus-tree/.gitignore b/Algorithms/bplus-tree/.gitignore new file mode 100644 index 0000000..6844bf6 --- /dev/null +++ b/Algorithms/bplus-tree/.gitignore @@ -0,0 +1,2 @@ +build/ +coverage/ diff --git a/Algorithms/bplus-tree/.uncrustifyrc b/Algorithms/bplus-tree/.uncrustifyrc new file mode 100644 index 0000000..a53a884 --- /dev/null +++ b/Algorithms/bplus-tree/.uncrustifyrc @@ -0,0 +1,1485 @@ +# Uncrustify 0.59 + +# +# General options +# + +# The type of line endings +newlines = lf # auto/lf/crlf/cr + +# The original size of tabs in the input +input_tab_size = 4 # number + +# The size of tabs in the output (only used if align_with_tabs=true) +# output_tab_size = 8 # number + +# The ASCII value of the string escape char, usually 92 (\) or 94 (^). (Pawn) +# string_escape_char = 92 # number + +# Alternate string escape char for Pawn. Only works right before the quote char. +# string_escape_char2 = 0 # number + +# Allow interpreting '>=' and '>>=' as part of a template in 'void f(list>=val);'. +# If true (default), 'assert(x<0 && y>=3)' will be broken. +# Improvements to template detection may make this option obsolete. +# tok_split_gte = false # false/true + +# Control what to do with the UTF-8 BOM (recommend 'remove') +utf8_bom = remove # ignore/add/remove/force + +# If the file contains bytes with values between 128 and 255, but is not UTF-8, then output as UTF-8 +# utf8_byte = false # false/true + +# Force the output encoding to UTF-8 +utf8_force = true # false/true + +# +# Indenting +# + +# The number of columns to indent per level. +# Usually 2, 3, 4, or 8. +indent_columns = 4 # number + +# The continuation indent. If non-zero, this overrides the indent of '(' and '=' continuation indents. +# For FreeBSD, this is set to 4. Negative value is absolute and not increased for each ( level +# indent_continue = 0 # number + +# How to use tabs when indenting code +# 0=spaces only +# 1=indent with tabs to brace level, align with spaces +# 2=indent and align with tabs, using spaces when not on a tabstop +indent_with_tabs = 0 # number + +# Comments that are not a brace level are indented with tabs on a tabstop. +# Requires indent_with_tabs=2. If false, will use spaces. +# indent_cmt_with_tabs = false # false/true + +# Whether to indent strings broken by '\' so that they line up +indent_align_string = true # false/true + +# The number of spaces to indent multi-line XML strings. +# Requires indent_align_string=True +# indent_xml_string = 0 # number + +# Spaces to indent '{' from level +# indent_brace = 0 # number + +# Whether braces are indented to the body level +# indent_braces = false # false/true + +# Disabled indenting function braces if indent_braces is true +# indent_braces_no_func = false # false/true + +# Disabled indenting class braces if indent_braces is true +# indent_braces_no_class = false # false/true + +# Disabled indenting struct braces if indent_braces is true +# indent_braces_no_struct = false # false/true + +# Indent based on the size of the brace parent, i.e. 'if' => 3 spaces, 'for' => 4 spaces, etc. +# indent_brace_parent = false # false/true + +# Whether the 'namespace' body is indented +indent_namespace = true # false/true + +# The number of spaces to indent a namespace block +indent_namespace_level = 2 # number + +# If the body of the namespace is longer than this number, it won't be indented. +# Requires indent_namespace=true. Default=0 (no limit) +# indent_namespace_limit = 0 # number + +# Whether the 'extern "C"' body is indented +# indent_extern = false # false/true + +# Whether the 'class' body is indented +indent_class = true # false/true + +# Whether to indent the stuff after a leading class colon +indent_class_colon = false # false/true + +# Additional indenting for constructor initializer list +indent_ctor_init = 0 # number + +# False=treat 'else\nif' as 'else if' for indenting purposes +# True=indent the 'if' one level +indent_else_if = true # false/true + +# Amount to indent variable declarations after a open brace. neg=relative, pos=absolute +indent_var_def_blk = 0 # number + +# Indent continued variable declarations instead of aligning. +indent_var_def_cont = false # false/true + +# True: indent continued function call parameters one indent level +# False: align parameters under the open paren +indent_func_call_param = false # false/true + +# Same as indent_func_call_param, but for function defs +indent_func_def_param = false # false/true + +# Same as indent_func_call_param, but for function protos +indent_func_proto_param = false # false/true + +# Same as indent_func_call_param, but for class declarations +indent_func_class_param = false # false/true + +# Same as indent_func_call_param, but for class variable constructors +indent_func_ctor_var_param = false # false/true + +# Same as indent_func_call_param, but for templates +indent_template_param = false # false/true + +# Double the indent for indent_func_xxx_param options +indent_func_param_double = false # false/true + +# Indentation column for standalone 'const' function decl/proto qualifier +indent_func_const = 0 # number + +# Indentation column for standalone 'throw' function decl/proto qualifier +indent_func_throw = 0 # number + +# The number of spaces to indent a continued '->' or '.' +# Usually set to 0, 1, or indent_columns. +indent_member = 0 # number + +# Spaces to indent single line ('//') comments on lines before code +indent_sing_line_comments = 0 # number + +# If set, will indent trailing single line ('//') comments relative +# to the code instead of trying to keep the same absolute column +indent_relative_single_line_comments = false # false/true + +# Spaces to indent 'case' from 'switch' +# Usually 0 or indent_columns. +indent_switch_case = 2 # number + +# Spaces to shift the 'case' line, without affecting any other lines +# Usually 0. +indent_case_shift = 0 # number + +# Spaces to indent '{' from 'case'. +# By default, the brace will appear under the 'c' in case. +# Usually set to 0 or indent_columns. +indent_case_brace = 0 # number + +# Whether to indent comments found in first column +indent_col1_comment = true # false/true + +# How to indent goto labels +# >0 : absolute column where 1 is the leftmost column +# <=0 : subtract from brace indent +indent_label = 1 # number + +# Same as indent_label, but for access specifiers that are followed by a colon +indent_access_spec = 1 # number + +# Indent the code after an access specifier by one level. +# If set, this option forces 'indent_access_spec=0' +indent_access_spec_body = true # false/true + +# If an open paren is followed by a newline, indent the next line so that it lines up after the open paren (not recommended) +indent_paren_nl = false # false/true + +# Controls the indent of a close paren after a newline. +# 0: Indent to body level +# 1: Align under the open paren +# 2: Indent to the brace level +indent_paren_close = 0 # number + +# Controls the indent of a comma when inside a paren.If TRUE, aligns under the open paren +indent_comma_paren = false # false/true + +# Controls the indent of a BOOL operator when inside a paren.If TRUE, aligns under the open paren +indent_bool_paren = false # false/true + +# If 'indent_bool_paren' is true, controls the indent of the first expression. If TRUE, aligns the first expression to the following ones +indent_first_bool_expr = false # false/true + +# If an open square is followed by a newline, indent the next line so that it lines up after the open square (not recommended) +indent_square_nl = false # false/true + +# Don't change the relative indent of ESQL/C 'EXEC SQL' bodies +indent_preserve_sql = false # false/true + +# Align continued statements at the '='. Default=True +# If FALSE or the '=' is followed by a newline, the next line is indent one tab. +indent_align_assign = true # false/true + +# +# Spacing options +# + +# Add or remove space around arithmetic operator '+', '-', '/', '*', etc +sp_arith = force # ignore/add/remove/force + +# Add or remove space around assignment operator '=', '+=', etc +sp_assign = force # ignore/add/remove/force + +# Add or remove space around assignment operator '=' in a prototype +sp_assign_default = remove # ignore/add/remove/force + +# Add or remove space before assignment operator '=', '+=', etc. Overrides sp_assign. +# sp_before_assign = ignore # ignore/add/remove/force + +# Add or remove space after assignment operator '=', '+=', etc. Overrides sp_assign. +# sp_after_assign = ignore # ignore/add/remove/force + +# Add or remove space around assignment '=' in enum +sp_enum_assign = remove # ignore/add/remove/force + +# Add or remove space before assignment '=' in enum. Overrides sp_enum_assign. +# sp_enum_before_assign = ignore # ignore/add/remove/force + +# Add or remove space after assignment '=' in enum. Overrides sp_enum_assign. +# sp_enum_after_assign = ignore # ignore/add/remove/force + +# Add or remove space around preprocessor '##' concatenation operator. Default=Add +sp_pp_concat = force # ignore/add/remove/force + +# Add or remove space after preprocessor '#' stringify operator. Also affects the '#@' charizing operator. Default=Add +sp_pp_stringify = force # ignore/add/remove/force + +# Add or remove space around boolean operators '&&' and '||' +sp_bool = force # ignore/add/remove/force + +# Add or remove space around compare operator '<', '>', '==', etc +sp_compare = force # ignore/add/remove/force + +# Add or remove space inside '(' and ')' +sp_inside_paren = remove # ignore/add/remove/force + +# Add or remove space between nested parens +sp_paren_paren = remove # ignore/add/remove/force + +# Whether to balance spaces inside nested parens +# sp_balance_nested_parens = false # false/true + +# Add or remove space between ')' and '{' +sp_paren_brace = force # ignore/add/remove/force + +# Add or remove space before pointer star '*' +sp_before_ptr_star = remove # ignore/add/remove/force + +# Add or remove space before pointer star '*' that isn't followed by a variable name +# If set to 'ignore', sp_before_ptr_star is used instead. +# sp_before_unnamed_ptr_star = ignore # ignore/add/remove/force + +# Add or remove space between pointer stars '*' +sp_between_ptr_star = remove # ignore/add/remove/force + +# Add or remove space after pointer star '*', if followed by a word. +sp_after_ptr_star = force # ignore/add/remove/force + +# Add or remove space after a pointer star '*', if followed by a func proto/def. +sp_after_ptr_star_func = force # ignore/add/remove/force + +# Add or remove space before a pointer star '*', if followed by a func proto/def. +sp_before_ptr_star_func = remove # ignore/add/remove/force + +# Add or remove space before a reference sign '&' +sp_before_byref = remove # ignore/add/remove/force + +# Add or remove space before a reference sign '&' that isn't followed by a variable name +# If set to 'ignore', sp_before_byref is used instead. +# sp_before_unnamed_byref = ignore # ignore/add/remove/force + +# Add or remove space after reference sign '&', if followed by a word. +sp_after_byref = force # ignore/add/remove/force + +# Add or remove space after a reference sign '&', if followed by a func proto/def. +sp_after_byref_func = force # ignore/add/remove/force + +# Add or remove space before a reference sign '&', if followed by a func proto/def. +sp_before_byref_func = remove # ignore/add/remove/force + +# Add or remove space between type and word. Default=Force +# sp_after_type = force # ignore/add/remove/force + +# Add or remove space before the paren in the D constructs 'template Foo(' and 'class Foo('. +sp_before_template_paren = remove # ignore/add/remove/force + +# Add or remove space in 'template <' vs 'template<'. +# If set to ignore, sp_before_angle is used. +# sp_template_angle = ignore # ignore/add/remove/force + +# Add or remove space before '<>' +sp_before_angle = remove # ignore/add/remove/force + +# Add or remove space inside '<' and '>' +sp_inside_angle = force # ignore/add/remove/force + +# Add or remove space after '<>' +sp_after_angle = force # ignore/add/remove/force + +# Add or remove space between '<>' and '(' as found in 'new List();' +sp_angle_paren = remove # ignore/add/remove/force + +# Add or remove space between '<>' and a word as in 'List m;' +sp_angle_word = force # ignore/add/remove/force + +# Add or remove space between '>' and '>' in '>>' (template stuff C++/C# only). Default=Add +sp_angle_shift = force # ignore/add/remove/force + +# Add or remove space before '(' of 'if', 'for', 'switch', and 'while' +sp_before_sparen = force # ignore/add/remove/force + +# Add or remove space inside if-condition '(' and ')' +sp_inside_sparen = remove # ignore/add/remove/force + +# Add or remove space before if-condition ')'. Overrides sp_inside_sparen. +# sp_inside_sparen_close = ignore # ignore/add/remove/force + +# Add or remove space after ')' of 'if', 'for', 'switch', and 'while' +sp_after_sparen = force # ignore/add/remove/force + +# Add or remove space between ')' and '{' of 'if', 'for', 'switch', and 'while' +sp_sparen_brace = force # ignore/add/remove/force + +# Add or remove space between 'invariant' and '(' in the D language. +sp_invariant_paren = force # ignore/add/remove/force + +# Add or remove space after the ')' in 'invariant (C) c' in the D language. +sp_after_invariant_paren = force # ignore/add/remove/force + +# Add or remove space before empty statement ';' on 'if', 'for' and 'while' +sp_special_semi = remove # ignore/add/remove/force + +# Add or remove space before ';'. Default=Remove +# sp_before_semi = remove # ignore/add/remove/force + +# Add or remove space before ';' in non-empty 'for' statements +sp_before_semi_for = remove # ignore/add/remove/force + +# Add or remove space before a semicolon of an empty part of a for statement. +sp_before_semi_for_empty = remove # ignore/add/remove/force + +# Add or remove space after ';', except when followed by a comment. Default=Add +sp_after_semi = force # ignore/add/remove/force + +# Add or remove space after ';' in non-empty 'for' statements. Default=Force +# sp_after_semi_for = force # ignore/add/remove/force + +# Add or remove space after the final semicolon of an empty part of a for statement: for ( ; ; ). +sp_after_semi_for_empty = remove # ignore/add/remove/force + +# Add or remove space before '[' (except '[]') +sp_before_square = remove # ignore/add/remove/force + +# Add or remove space before '[]' +sp_before_squares = remove # ignore/add/remove/force + +# Add or remove space inside a non-empty '[' and ']' +sp_inside_square = remove # ignore/add/remove/force + +# Add or remove space after ',' +sp_after_comma = force # ignore/add/remove/force + +# Add or remove space before ',' +# sp_before_comma = remove # ignore/add/remove/force + +# Add or remove space between an open paren and comma: '(,' vs '( ,' +sp_paren_comma = remove # ignore/add/remove/force + +# Add or remove space before the variadic '...' when preceded by a non-punctuator +sp_before_ellipsis = force # ignore/add/remove/force + +# Add or remove space after class ':' +sp_after_class_colon = force # ignore/add/remove/force + +# Add or remove space before class ':' +sp_before_class_colon = force # ignore/add/remove/force + +# Add or remove space before case ':'. Default=Remove +# sp_before_case_colon = remove # ignore/add/remove/force + +# Add or remove space between 'operator' and operator sign +sp_after_operator = remove # ignore/add/remove/force + +# Add or remove space between the operator symbol and the open paren, as in 'operator ++(' +sp_after_operator_sym = remove # ignore/add/remove/force + +# Add or remove space after C/D cast, i.e. 'cast(int)a' vs 'cast(int) a' or '(int)a' vs '(int) a' +sp_after_cast = force # ignore/add/remove/force + +# Add or remove spaces inside cast parens +sp_inside_paren_cast = remove # ignore/add/remove/force + +# Add or remove space between the type and open paren in a C++ cast, i.e. 'int(exp)' vs 'int (exp)' +sp_cpp_cast_paren = remove # ignore/add/remove/force + +# Add or remove space between 'sizeof' and '(' +sp_sizeof_paren = remove # ignore/add/remove/force + +# Add or remove space after the tag keyword (Pawn) +sp_after_tag = force # ignore/add/remove/force + +# Add or remove space inside enum '{' and '}' +sp_inside_braces_enum = force # ignore/add/remove/force + +# Add or remove space inside struct/union '{' and '}' +sp_inside_braces_struct = force # ignore/add/remove/force + +# Add or remove space inside '{' and '}' +sp_inside_braces = force # ignore/add/remove/force + +# Add or remove space inside '{}' +sp_inside_braces_empty = remove # ignore/add/remove/force + +# Add or remove space between return type and function name +# A minimum of 1 is forced except for pointer return types. +sp_type_func = force # ignore/add/remove/force + +# Add or remove space between function name and '(' on function declaration +sp_func_proto_paren = remove # ignore/add/remove/force + +# Add or remove space between function name and '(' on function definition +sp_func_def_paren = remove # ignore/add/remove/force + +# Add or remove space inside empty function '()' +sp_inside_fparens = remove # ignore/add/remove/force + +# Add or remove space inside function '(' and ')' +sp_inside_fparen = remove # ignore/add/remove/force + +# Add or remove space between ']' and '(' when part of a function call. +sp_square_fparen = remove # ignore/add/remove/force + +# Add or remove space between ')' and '{' of function +sp_fparen_brace = force # ignore/add/remove/force + +# Add or remove space between function name and '(' on function calls +sp_func_call_paren = remove # ignore/add/remove/force + +# Add or remove space between function name and '()' on function calls without parameters. +# If set to 'ignore' (the default), sp_func_call_paren is used. +# sp_func_call_paren_empty = ignore # ignore/add/remove/force + +# Add or remove space between the user function name and '(' on function calls +# You need to set a keyword to be a user function, like this: 'set func_call_user _' in the config file. +# sp_func_call_user_paren = ignore # ignore/add/remove/force + +# Add or remove space between a constructor/destructor and the open paren +sp_func_class_paren = remove # ignore/add/remove/force + +# Add or remove space between 'return' and '(' +sp_return_paren = force # ignore/add/remove/force + +# Add or remove space between '__attribute__' and '(' +sp_attribute_paren = remove # ignore/add/remove/force + +# Add or remove space between 'defined' and '(' in '#if defined (FOO)' +sp_defined_paren = remove # ignore/add/remove/force + +# Add or remove space between 'throw' and '(' in 'throw (something)' +sp_throw_paren = force # ignore/add/remove/force + +# Add or remove space between 'catch' and '(' in 'catch (something) { }' +# If set to ignore, sp_before_sparen is used. +# sp_catch_paren = ignore # ignore/add/remove/force + +# Add or remove space between 'version' and '(' in 'version (something) { }' (D language) +# If set to ignore, sp_before_sparen is used. +# sp_version_paren = ignore # ignore/add/remove/force + +# Add or remove space between 'scope' and '(' in 'scope (something) { }' (D language) +# If set to ignore, sp_before_sparen is used. +# sp_scope_paren = ignore # ignore/add/remove/force + +# Add or remove space between macro and value +sp_macro = force # ignore/add/remove/force + +# Add or remove space between macro function ')' and value +sp_macro_func = force # ignore/add/remove/force + +# Add or remove space between 'else' and '{' if on the same line +sp_else_brace = force # ignore/add/remove/force + +# Add or remove space between '}' and 'else' if on the same line +sp_brace_else = force # ignore/add/remove/force + +# Add or remove space between '}' and the name of a typedef on the same line +sp_brace_typedef = force # ignore/add/remove/force + +# Add or remove space between 'catch' and '{' if on the same line +sp_catch_brace = force # ignore/add/remove/force + +# Add or remove space between '}' and 'catch' if on the same line +sp_brace_catch = force # ignore/add/remove/force + +# Add or remove space between 'finally' and '{' if on the same line +sp_finally_brace = force # ignore/add/remove/force + +# Add or remove space between '}' and 'finally' if on the same line +sp_brace_finally = force # ignore/add/remove/force + +# Add or remove space between 'try' and '{' if on the same line +sp_try_brace = force # ignore/add/remove/force + +# Add or remove space between get/set and '{' if on the same line +sp_getset_brace = force # ignore/add/remove/force + +# Add or remove space before the '::' operator +sp_before_dc = remove # ignore/add/remove/force + +# Add or remove space after the '::' operator +sp_after_dc = remove # ignore/add/remove/force + +# Add or remove around the D named array initializer ':' operator +sp_d_array_colon = remove # ignore/add/remove/force + +# Add or remove space after the '!' (not) operator. Default=Remove +# sp_not = remove # ignore/add/remove/force + +# Add or remove space after the '~' (invert) operator. Default=Remove +# sp_inv = remove # ignore/add/remove/force + +# Add or remove space after the '&' (address-of) operator. Default=Remove +# This does not affect the spacing after a '&' that is part of a type. +# sp_addr = remove # ignore/add/remove/force + +# Add or remove space around the '.' or '->' operators. Default=Remove +# sp_member = remove # ignore/add/remove/force + +# Add or remove space after the '*' (dereference) operator. Default=Remove +# This does not affect the spacing after a '*' that is part of a type. +# sp_deref = remove # ignore/add/remove/force + +# Add or remove space after '+' or '-', as in 'x = -5' or 'y = +7'. Default=Remove +# sp_sign = remove # ignore/add/remove/force + +# Add or remove space before or after '++' and '--', as in '(--x)' or 'y++;'. Default=Remove +# sp_incdec = remove # ignore/add/remove/force + +# Add or remove space before a backslash-newline at the end of a line. Default=Add +# sp_before_nl_cont = add # ignore/add/remove/force + +# Add or remove space after the scope '+' or '-', as in '-(void) foo;' or '+(int) bar;' +sp_after_oc_scope = remove # ignore/add/remove/force + +# Add or remove space after the colon in message specs +# '-(int) f:(int) x;' vs '-(int) f: (int) x;' +sp_after_oc_colon = force # ignore/add/remove/force + +# Add or remove space before the colon in message specs +# '-(int) f: (int) x;' vs '-(int) f : (int) x;' +sp_before_oc_colon = force # ignore/add/remove/force + +# Add or remove space after the colon in message specs +# '[object setValue:1];' vs '[object setValue: 1];' +sp_after_send_oc_colon = force # ignore/add/remove/force + +# Add or remove space before the colon in message specs +# '[object setValue:1];' vs '[object setValue :1];' +sp_before_send_oc_colon = remove # ignore/add/remove/force + +# Add or remove space after the (type) in message specs +# '-(int)f: (int) x;' vs '-(int)f: (int)x;' +sp_after_oc_type = remove # ignore/add/remove/force + +# Add or remove space after the first (type) in message specs +# '-(int) f:(int)x;' vs '-(int)f:(int)x;' +sp_after_oc_return_type = remove # ignore/add/remove/force + +# Add or remove space between '@selector' and '(' +# '@selector(msgName)' vs '@selector (msgName)' +# Also applies to @protocol() constructs +sp_after_oc_at_sel = remove # ignore/add/remove/force + +# Add or remove space between '@selector(x)' and the following word +# '@selector(foo) a:' vs '@selector(foo)a:' +sp_after_oc_at_sel_parens = force # ignore/add/remove/force + +# Add or remove space inside '@selector' parens +# '@selector(foo)' vs '@selector( foo )' +# Also applies to @protocol() constructs +sp_inside_oc_at_sel_parens = remove # ignore/add/remove/force + +# Add or remove space before a block pointer caret +# '^int (int arg){...}' vs. ' ^int (int arg){...}' +sp_before_oc_block_caret = remove # ignore/add/remove/force + +# Add or remove space after a block pointer caret +# '^int (int arg){...}' vs. '^ int (int arg){...}' +sp_after_oc_block_caret = remove # ignore/add/remove/force + +# Add or remove space around the ':' in 'b ? t : f' +sp_cond_colon = force # ignore/add/remove/force + +# Add or remove space around the '?' in 'b ? t : f' +sp_cond_question = force # ignore/add/remove/force + +# Fix the spacing between 'case' and the label. Only 'ignore' and 'force' make sense here. +sp_case_label = force # ignore/add/remove/force + +# Control the space around the D '..' operator. +sp_range = remove # ignore/add/remove/force + +# Control the space after the opening of a C++ comment '// A' vs '//A' +sp_cmt_cpp_start = force # ignore/add/remove/force + +# Controls the spaces between #else or #endif and a trailing comment +sp_endif_cmt = force # ignore/add/remove/force + +# Controls the spaces after 'new', 'delete', and 'delete[]' +sp_after_new = force # ignore/add/remove/force + +# Controls the spaces before a trailing or embedded comment +sp_before_tr_emb_cmt = force # ignore/add/remove/force + +# Number of spaces before a trailing or embedded comment +# sp_num_before_tr_emb_cmt = 0 # number + +# +# Code alignment (not left column spaces/tabs) +# + +# Whether to keep non-indenting tabs +# align_keep_tabs = false # false/true + +# Whether to use tabs for aligning +# align_with_tabs = false # false/true + +# Whether to bump out to the next tab when aligning +# align_on_tabstop = false # false/true + +# Whether to left-align numbers +align_number_left = false # false/true + +# Align variable definitions in prototypes and functions +align_func_params = true # false/true + +# Align parameters in single-line functions that have the same name. +# The function names must already be aligned with each other. +align_same_func_call_params = false # false/true + +# The span for aligning variable definitions (0=don't align) +align_var_def_span = 1 # number + +# How to align the star in variable definitions. +# 0=Part of the type 'void * foo;' +# 1=Part of the variable 'void *foo;' +# 2=Dangling 'void *foo;' +# align_var_def_star_style = 0 # number + +# How to align the '&' in variable definitions. +# 0=Part of the type +# 1=Part of the variable +# 2=Dangling +# align_var_def_amp_style = 0 # number + +# The threshold for aligning variable definitions (0=no limit) +align_var_def_thresh = 0 # number + +# The gap for aligning variable definitions +align_var_def_gap = 0 # number + +# Whether to align the colon in struct bit fields +align_var_def_colon = true # false/true + +# Whether to align any attribute after the variable name +align_var_def_attribute = true # false/true + +# Whether to align inline struct/enum/union variable definitions +align_var_def_inline = true # false/true + +# The span for aligning on '=' in assignments (0=don't align) +align_assign_span = 1 # number + +# The threshold for aligning on '=' in assignments (0=no limit) +align_assign_thresh = 0 # number + +# The span for aligning on '=' in enums (0=don't align) +align_enum_equ_span = 1 # number + +# The threshold for aligning on '=' in enums (0=no limit) +align_enum_equ_thresh = 0 # number + +# The span for aligning struct/union (0=don't align) +align_var_struct_span = 1 # number + +# The threshold for aligning struct/union member definitions (0=no limit) +align_var_struct_thresh = 0 # number + +# The gap for aligning struct/union member definitions +align_var_struct_gap = 0 # number + +# The span for aligning struct initializer values (0=don't align) +align_struct_init_span = 1 # number + +# The minimum space between the type and the synonym of a typedef +align_typedef_gap = 0 # number + +# The span for aligning single-line typedefs (0=don't align) +align_typedef_span = 1 # number + +# How to align typedef'd functions with other typedefs +# 0: Don't mix them at all +# 1: align the open paren with the types +# 2: align the function type name with the other type names +align_typedef_func = 1 # number + +# Controls the positioning of the '*' in typedefs. Just try it. +# 0: Align on typedef type, ignore '*' +# 1: The '*' is part of type name: typedef int *pint; +# 2: The '*' is part of the type, but dangling: typedef int *pint; +align_typedef_star_style = 0 # number + +# Controls the positioning of the '&' in typedefs. Just try it. +# 0: Align on typedef type, ignore '&' +# 1: The '&' is part of type name: typedef int &pint; +# 2: The '&' is part of the type, but dangling: typedef int &pint; +align_typedef_amp_style = 0 # number + +# The span for aligning comments that end lines (0=don't align) +align_right_cmt_span = 1 # number + +# If aligning comments, mix with comments after '}' and #endif with less than 3 spaces before the comment +align_right_cmt_mix = false # false/true + +# If a trailing comment is more than this number of columns away from the text it follows, +# it will qualify for being aligned. This has to be > 0 to do anything. +align_right_cmt_gap = 0 # number + +# Align trailing comment at or beyond column N; 'pulls in' comments as a bonus side effect (0=ignore) +align_right_cmt_at_col = 1 # number + +# The span for aligning function prototypes (0=don't align) +align_func_proto_span = 1 # number + +# Minimum gap between the return type and the function name. +align_func_proto_gap = 0 # number + +# Align function protos on the 'operator' keyword instead of what follows +align_on_operator = false # false/true + +# Whether to mix aligning prototype and variable declarations. +# If true, align_var_def_XXX options are used instead of align_func_proto_XXX options. +align_mix_var_proto = false # false/true + +# Align single-line functions with function prototypes, uses align_func_proto_span +align_single_line_func = false # false/true + +# Aligning the open brace of single-line functions. +# Requires align_single_line_func=true, uses align_func_proto_span +align_single_line_brace = false # false/true + +# Gap for align_single_line_brace. +align_single_line_brace_gap = 0 # number + +# The span for aligning ObjC msg spec (0=don't align) +align_oc_msg_spec_span = 0 # number + +# Whether to align macros wrapped with a backslash and a newline. +# This will not work right if the macro contains a multi-line comment. +align_nl_cont = true # false/true + +# # Align macro functions and variables together +align_pp_define_together = true # false/true + +# The minimum space between label and value of a preprocessor define +align_pp_define_gap = 1 # number + +# The span for aligning on '#define' bodies (0=don't align) +align_pp_define_span = 1 # number + +# Align lines that start with '<<' with previous '<<'. Default=true +# align_left_shift = true # false/true + +# Span for aligning parameters in an Obj-C message call on the ':' (0=don't align) +# align_oc_msg_colon_span = 0 # number + +# Aligning parameters in an Obj-C '+' or '-' declaration on the ':' +# align_oc_decl_colon = false # false/true + +# +# Newline adding and removing options +# + +# Whether to collapse empty blocks between '{' and '}' +nl_collapse_empty_body = true # false/true + +# Don't split one-line braced assignments - 'foo_t f = { 1, 2 };' +nl_assign_leave_one_liners = true # false/true + +# Don't split one-line braced statements inside a class xx { } body +nl_class_leave_one_liners = true # false/true + +# Don't split one-line enums: 'enum foo { BAR = 15 };' +nl_enum_leave_one_liners = true # false/true + +# Don't split one-line get or set functions +nl_getset_leave_one_liners = true # false/true + +# Don't split one-line function definitions - 'int foo() { return 0; }' +nl_func_leave_one_liners = true # false/true + +# Don't split one-line if/else statements - 'if(a) b++;' +# nl_if_leave_one_liners = false # false/true + +# Add or remove newlines at the start of the file +nl_start_of_file = remove # ignore/add/remove/force + +# The number of newlines at the start of the file (only used if nl_start_of_file is 'add' or 'force' +# nl_start_of_file_min = 0 # number + +# Add or remove newline at the end of the file +nl_end_of_file = force # ignore/add/remove/force + +# The number of newlines at the end of the file (only used if nl_end_of_file is 'add' or 'force') +nl_end_of_file_min = 1 # number + +# Add or remove newline between '=' and '{' +nl_assign_brace = remove # ignore/add/remove/force + +# Add or remove newline between '=' and '[' (D only) +nl_assign_square = remove # ignore/add/remove/force + +# Add or remove newline after '= [' (D only). Will also affect the newline before the ']' +# nl_after_square_assign = ignore # ignore/add/remove/force + +# The number of blank lines after a block of variable definitions at the top of a function body +# 0 = No change (default) +nl_func_var_def_blk = 0 # number + +# The number of newlines before a block of typedefs +# 0 = No change (default) +nl_typedef_blk_start = 1 # number + +# The number of newlines after a block of typedefs +# 0 = No change (default) +nl_typedef_blk_end = 2 # number + +# The maximum consecutive newlines within a block of typedefs +# 0 = No change (default) +nl_typedef_blk_in = 2 # number + +# The number of newlines before a block of variable definitions not at the top of a function body +# 0 = No change (default) +# nl_var_def_blk_start = 0 # number + +# The number of newlines after a block of variable definitions not at the top of a function body +# 0 = No change (default) +# nl_var_def_blk_end = 0 # number + +# The maximum consecutive newlines within a block of variable definitions +# 0 = No change (default) +# nl_var_def_blk_in = 0 # number + +# Add or remove newline between a function call's ')' and '{', as in: +# list_for_each(item, &list) { } +nl_fcall_brace = force # ignore/add/remove/force + +# Add or remove newline between 'enum' and '{' +nl_enum_brace = force # ignore/add/remove/force + +# Add or remove newline between 'struct and '{' +nl_struct_brace = force # ignore/add/remove/force + +# Add or remove newline between 'union' and '{' +nl_union_brace = force # ignore/add/remove/force + +# Add or remove newline between 'if' and '{' +nl_if_brace = force # ignore/add/remove/force + +# Add or remove newline between '}' and 'else' +nl_brace_else = force # ignore/add/remove/force + +# Add or remove newline between 'else if' and '{' +# If set to ignore, nl_if_brace is used instead +nl_elseif_brace = force # ignore/add/remove/force + +# Add or remove newline between 'else' and '{' +nl_else_brace = force # ignore/add/remove/force + +# Add or remove newline between 'else' and 'if' +nl_else_if = remove # ignore/add/remove/force + +# Add or remove newline between '}' and 'finally' +nl_brace_finally = force # ignore/add/remove/force + +# Add or remove newline between 'finally' and '{' +nl_finally_brace = force # ignore/add/remove/force + +# Add or remove newline between 'try' and '{' +nl_try_brace = force # ignore/add/remove/force + +# Add or remove newline between get/set and '{' +nl_getset_brace = force # ignore/add/remove/force + +# Add or remove newline between 'for' and '{' +nl_for_brace = force # ignore/add/remove/force + +# Add or remove newline between 'catch' and '{' +nl_catch_brace = force # ignore/add/remove/force + +# Add or remove newline between '}' and 'catch' +nl_brace_catch = force # ignore/add/remove/force + +# Add or remove newline between 'while' and '{' +nl_while_brace = force # ignore/add/remove/force + +# Add or remove newline between 'scope (x)' and '{' (D) +nl_scope_brace = force # ignore/add/remove/force + +# Add or remove newline between 'unittest' and '{' (D) +nl_unittest_brace = force # ignore/add/remove/force + +# Add or remove newline between 'version (x)' and '{' (D) +nl_version_brace = force # ignore/add/remove/force + +# Add or remove newline between 'using' and '{' +nl_using_brace = force # ignore/add/remove/force + +# Add or remove newline between two open or close braces. +# Due to general newline/brace handling, REMOVE may not work. +nl_brace_brace = force # ignore/add/remove/force + +# Add or remove newline between 'do' and '{' +nl_do_brace = force # ignore/add/remove/force + +# Add or remove newline between '}' and 'while' of 'do' statement +nl_brace_while = force # ignore/add/remove/force + +# Add or remove newline between 'switch' and '{' +nl_switch_brace = force # ignore/add/remove/force + +# Add a newline between ')' and '{' if the ')' is on a different line than the if/for/etc. +# Overrides nl_for_brace, nl_if_brace, nl_switch_brace, nl_while_switch, and nl_catch_brace. +# nl_multi_line_cond = false # false/true + +# Force a newline in a define after the macro name for multi-line defines. +nl_multi_line_define = true # false/true + +# Whether to put a newline before 'case' statement +nl_before_case = true # false/true + +# Add or remove newline between ')' and 'throw' +nl_before_throw = force # ignore/add/remove/force + +# Whether to put a newline after 'case' statement +nl_after_case = true # false/true + +# Add or remove a newline between a case ':' and '{'. Overrides nl_after_case. +nl_case_colon_brace = remove # ignore/add/remove/force + +# Newline between namespace and { +nl_namespace_brace = force # ignore/add/remove/force + +# Add or remove newline between 'template<>' and whatever follows. +# nl_template_class = ignore # ignore/add/remove/force + +# Add or remove newline between 'class' and '{' +nl_class_brace = force # ignore/add/remove/force + +# Add or remove newline after each ',' in the constructor member initialization +nl_class_init_args = force # ignore/add/remove/force + +# Add or remove newline between return type and function name in a function definition +nl_func_type_name = remove # ignore/add/remove/force + +# Add or remove newline between return type and function name inside a class {} +# Uses nl_func_type_name or nl_func_proto_type_name if set to ignore. +nl_func_type_name_class = remove # ignore/add/remove/force + +# Add or remove newline between function scope and name in a definition +# Controls the newline after '::' in 'void A::f() { }' +nl_func_scope_name = remove # ignore/add/remove/force + +# Add or remove newline between return type and function name in a prototype +nl_func_proto_type_name = remove # ignore/add/remove/force + +# Add or remove newline between a function name and the opening '(' +nl_func_paren = remove # ignore/add/remove/force + +# Add or remove newline between a function name and the opening '(' in the definition +nl_func_def_paren = remove # ignore/add/remove/force + +# Add or remove newline after '(' in a function declaration +nl_func_decl_start = remove # ignore/add/remove/force + +# Add or remove newline after '(' in a function definition +nl_func_def_start = remove # ignore/add/remove/force + +# Overrides nl_func_decl_start when there is only one parameter. +# nl_func_decl_start_single = ignore # ignore/add/remove/force + +# Overrides nl_func_def_start when there is only one parameter. +# nl_func_def_start_single = ignore # ignore/add/remove/force + +# Add or remove newline after each ',' in a function declaration +nl_func_decl_args = ignore # ignore/add/remove/force + +# Add or remove newline after each ',' in a function definition +nl_func_def_args = ignore # ignore/add/remove/force + +# Add or remove newline before the ')' in a function declaration +nl_func_decl_end = remove # ignore/add/remove/force + +# Add or remove newline before the ')' in a function definition +nl_func_def_end = remove # ignore/add/remove/force + +# Overrides nl_func_decl_end when there is only one parameter. +# nl_func_decl_end_single = ignore # ignore/add/remove/force + +# Overrides nl_func_def_end when there is only one parameter. +# nl_func_def_end_single = ignore # ignore/add/remove/force + +# Add or remove newline between '()' in a function declaration. +nl_func_decl_empty = remove # ignore/add/remove/force + +# Add or remove newline between '()' in a function definition. +nl_func_def_empty = remove # ignore/add/remove/force + +# Add or remove newline between function signature and '{' +nl_fdef_brace = force # ignore/add/remove/force + +# Add or remove a newline between the return keyword and return expression. +nl_return_expr = remove # ignore/add/remove/force + +# Whether to put a newline after semicolons, except in 'for' statements +nl_after_semicolon = true # false/true + +# Whether to put a newline after brace open. +# This also adds a newline before the matching brace close. +nl_after_brace_open = true # false/true + +# If nl_after_brace_open and nl_after_brace_open_cmt are true, a newline is +# placed between the open brace and a trailing single-line comment. +nl_after_brace_open_cmt = true # false/true + +# Whether to put a newline after a virtual brace open with a non-empty body. +# These occur in un-braced if/while/do/for statement bodies. +nl_after_vbrace_open = true # false/true + +# Whether to put a newline after a virtual brace open with an empty body. +# These occur in un-braced if/while/do/for statement bodies. +nl_after_vbrace_open_empty = true # false/true + +# Whether to put a newline after a brace close. +# Does not apply if followed by a necessary ';'. +nl_after_brace_close = false # false/true + +# Whether to put a newline after a virtual brace close. +# Would add a newline before return in: 'if (foo) a++; return;' +nl_after_vbrace_close = true # false/true + +# Whether to alter newlines in '#define' macros +nl_define_macro = true # false/true + +# Whether to not put blanks after '#ifxx', '#elxx', or before '#endif' +nl_squeeze_ifdef = false # false/true + +# Add or remove blank line before 'if' +nl_before_if = ignore # ignore/add/remove/force + +# Add or remove blank line after 'if' statement +nl_after_if = ignore # ignore/add/remove/force + +# Add or remove blank line before 'for' +nl_before_for = ignore # ignore/add/remove/force + +# Add or remove blank line after 'for' statement +nl_after_for = ignore # ignore/add/remove/force + +# Add or remove blank line before 'while' +nl_before_while = ignore # ignore/add/remove/force + +# Add or remove blank line after 'while' statement +nl_after_while = ignore # ignore/add/remove/force + +# Add or remove blank line before 'switch' +nl_before_switch = ignore # ignore/add/remove/force + +# Add or remove blank line after 'switch' statement +nl_after_switch = ignore # ignore/add/remove/force + +# Add or remove blank line before 'do' +nl_before_do = ignore # ignore/add/remove/force + +# Add or remove blank line after 'do/while' statement +nl_after_do = ignore # ignore/add/remove/force + +# Whether to double-space commented-entries in struct/enum +nl_ds_struct_enum_cmt = true # false/true + +# Whether to double-space before the close brace of a struct/union/enum +# (lower priority than 'eat_blanks_before_close_brace') +nl_ds_struct_enum_close_brace = false # false/true + +# Add or remove a newline around a class colon. +# Related to pos_class_colon, nl_class_init_args, and pos_comma. +nl_class_colon = ignore # ignore/add/remove/force + +# Change simple unbraced if statements into a one-liner +# 'if(b)\n i++;' => 'if(b) i++;' +nl_create_if_one_liner = false # false/true + +# Change simple unbraced for statements into a one-liner +# 'for (i=0;i<5;i++)\n foo(i);' => 'for (i=0;i<5;i++) foo(i);' +nl_create_for_one_liner = false # false/true + +# Change simple unbraced while statements into a one-liner +# 'while (i<5)\n foo(i++);' => 'while (i<5) foo(i++);' +nl_create_while_one_liner = false # false/true + +# +# Positioning options +# + +# The position of arithmetic operators in wrapped expressions +pos_arith = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of assignment in wrapped expressions. +# Do not affect '=' followed by '{' +pos_assign = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of boolean operators in wrapped expressions +pos_bool = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of comparison operators in wrapped expressions +pos_compare = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of conditional (b ? t : f) operators in wrapped expressions +pos_conditional = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of the comma in wrapped expressions +pos_comma = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of the comma in the constructor initialization list +pos_class_comma = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of colons between constructor and member initialization +pos_class_colon = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# +# Line Splitting options +# + +# Try to limit code width to N number of columns +code_width = 0 # number + +# Whether to fully split long 'for' statements at semi-colons +ls_for_split_full = true # false/true + +# Whether to fully split long function protos/calls at commas +ls_func_split_full = true # false/true + +# Whether to split lines as close to code_width as possible and ignore some groupings +ls_code_width = false # false/true + +# +# Blank line options +# + +# The maximum consecutive newlines +nl_max = 2 # number + +# The number of newlines after a function prototype, if followed by another function prototype +nl_after_func_proto = 1 # number + +# The number of newlines after a function prototype, if not followed by another function prototype +nl_after_func_proto_group = 1 # number + +# The number of newlines after '}' of a multi-line function body +nl_after_func_body = 2 # number + +# The number of newlines after '}' of a multi-line function body in a class declaration +nl_after_func_body_class = 2 # number + +# The number of newlines after '}' of a single line function body +nl_after_func_body_one_liner = 2 # number + +# The minimum number of newlines before a multi-line comment. +# Doesn't apply if after a brace open or another multi-line comment. +nl_before_block_comment = 2 # number + +# The minimum number of newlines before a single-line C comment. +# Doesn't apply if after a brace open or other single-line C comments. +nl_before_c_comment = 2 # number + +# The minimum number of newlines before a CPP comment. +# Doesn't apply if after a brace open or other CPP comments. +nl_before_cpp_comment = 2 # number + +# Whether to force a newline after a multi-line comment. +nl_after_multiline_comment = true # false/true + +# The number of newlines after '}' or ';' of a struct/enum/union definition +nl_after_struct = 2 # number + +# The number of newlines after '}' or ';' of a class definition +nl_after_class = 2 # number + +# The number of newlines before a 'private:', 'public:', 'protected:', 'signals:', or 'slots:' label. +# Will not change the newline count if after a brace open. +# 0 = No change. +nl_before_access_spec = 2 # number + +# The number of newlines after a 'private:', 'public:', 'protected:', 'signals:', or 'slots:' label. +# 0 = No change. +nl_after_access_spec = 1 # number + +# The number of newlines between a function def and the function comment. +# 0 = No change. +nl_comment_func_def = 1 # number + +# The number of newlines after a try-catch-finally block that isn't followed by a brace close. +# 0 = No change. +nl_after_try_catch_finally = 2 # number + +# The number of newlines before and after a property, indexer or event decl. +# 0 = No change. +nl_around_cs_property = 1 # number + +# The number of newlines between the get/set/add/remove handlers in C#. +# 0 = No change. +nl_between_get_set = 1 # number + +# Add or remove newline between C# property and the '{' +nl_property_brace = remove # ignore/add/remove/force + +# Whether to remove blank lines after '{' +eat_blanks_after_open_brace = false # false/true + +# Whether to remove blank lines before '}' +eat_blanks_before_close_brace = false # false/true + +# How aggressively to remove extra newlines not in preproc. +# 0: No change +# 1: Remove most newlines not handled by other config +# 2: Remove all newlines and reformat completely by config +nl_remove_extra_newlines = 0 # number + +# Whether to put a blank line before 'return' statements, unless after an open brace. +nl_before_return = true # false/true + +# Whether to put a blank line after 'return' statements, unless followed by a close brace. +nl_after_return = false # false/true + +# +# Code modifying options (non-whitespace) +# + +# Add or remove braces on single-line 'do' statement +mod_full_brace_do = remove # ignore/add/remove/force + +# Add or remove braces on single-line 'for' statement +mod_full_brace_for = remove # ignore/add/remove/force + +# Add or remove braces on single-line function definitions. (Pawn) +mod_full_brace_function = remove # ignore/add/remove/force + +# Add or remove braces on single-line 'if' statement. Will not remove the braces if they contain an 'else'. +mod_full_brace_if = remove # ignore/add/remove/force + +# Make all if/elseif/else statements in a chain be braced or not. Overrides mod_full_brace_if. +# If any must be braced, they are all braced. If all can be unbraced, then the braces are removed. +mod_full_brace_if_chain = true # false/true + +# Don't remove braces around statements that span N newlines +mod_full_brace_nl = 0 # number + +# Add or remove braces on single-line 'while' statement +mod_full_brace_while = remove # ignore/add/remove/force + +# Add or remove braces on single-line 'using ()' statement +mod_full_brace_using = remove # ignore/add/remove/force + +# Add or remove unnecessary paren on 'return' statement +mod_paren_on_return = remove # ignore/add/remove/force + +# Whether to change optional semicolons to real semicolons +mod_pawn_semicolon = true # false/true + +# Add parens on 'while' and 'if' statement around bools +mod_full_paren_if_bool = true # false/true + +# Whether to remove superfluous semicolons +mod_remove_extra_semicolon = true # false/true + +# If a function body exceeds the specified number of newlines and doesn't have a comment after +# the close brace, a comment will be added. +mod_add_long_function_closebrace_comment = 50 # number + +# If a switch body exceeds the specified number of newlines and doesn't have a comment after +# the close brace, a comment will be added. +mod_add_long_switch_closebrace_comment = 50 # number + +# If an #ifdef body exceeds the specified number of newlines and doesn't have a comment after +# the #endif, a comment will be added. +mod_add_long_ifdef_endif_comment = 1 # number + +# If an #ifdef or #else body exceeds the specified number of newlines and doesn't have a comment after +# the #else, a comment will be added. +mod_add_long_ifdef_else_comment = 1 # number + +# If TRUE, will sort consecutive single-line 'import' statements [Java, D] +mod_sort_import = false # false/true + +# If TRUE, will sort consecutive single-line 'using' statements [C#] +mod_sort_using = false # false/true + +# If TRUE, will sort consecutive single-line '#include' statements [C/C++] and '#import' statements [Obj-C] +# This is generally a bad idea, as it may break your code. +mod_sort_include = false # false/true + +# If TRUE, it will move a 'break' that appears after a fully braced 'case' before the close brace. +mod_move_case_break = true # false/true + +# Will add or remove the braces around a fully braced case statement. +# Will only remove the braces if there are no variable declarations in the block. +mod_case_brace = remove # ignore/add/remove/force + +# If TRUE, it will remove a void 'return;' that appears as the last statement in a function. +mod_remove_empty_return = true # false/true + +# +# Comment modifications +# + +# Try to wrap comments at cmt_width columns +cmt_width = 120 # number + +# Set the comment reflow mode (default: 0) +# 0: no reflowing (apart from the line wrapping due to cmt_width) +# 1: no touching at all +# 2: full reflow +cmt_reflow_mode = 1 # number + +# If false, disable all multi-line comment changes, including cmt_width. keyword substitution, and leading chars. +# Default is true. +# cmt_indent_multi = true # false/true + +# Whether to group c-comments that look like they are in a block +cmt_c_group = true # false/true + +# Whether to put an empty '/*' on the first line of the combined c-comment +cmt_c_nl_start = false # false/true + +# Whether to put a newline before the closing '*/' of the combined c-comment +cmt_c_nl_end = true # false/true + +# Whether to group cpp-comments that look like they are in a block +cmt_cpp_group = true # false/true + +# Whether to put an empty '/*' on the first line of the combined cpp-comment +cmt_cpp_nl_start = false # false/true + +# Whether to put a newline before the closing '*/' of the combined cpp-comment +cmt_cpp_nl_end = true # false/true + +# Whether to change cpp-comments into c-comments +cmt_cpp_to_c = false # false/true + +# Whether to put a star on subsequent comment lines +cmt_star_cont = true # false/true + +# The number of spaces to insert at the start of subsequent comment lines +cmt_sp_before_star_cont = 0 # number + +# The number of spaces to insert after the star on subsequent comment lines +cmt_sp_after_star_cont = 0 # number + +# For multi-line comments with a '*' lead, remove leading spaces if the first and last lines of +# the comment are the same length. Default=True +cmt_multi_check_last = false # false/true + +# The filename that contains text to insert at the head of a file if the file doesn't start with a C/C++ comment. +# Will substitute $(filename) with the current file's name. +cmt_insert_file_header = "" # string + +# The filename that contains text to insert at the end of a file if the file doesn't end with a C/C++ comment. +# Will substitute $(filename) with the current file's name. +cmt_insert_file_footer = "" # string + +# The filename that contains text to insert before a function implementation if the function isn't preceded with a C/C++ comment. +# Will substitute $(function) with the function name and $(javaparam) with the javadoc @param and @return stuff. +# Will also substitute $(fclass) with the class name: void CFoo::Bar() { ... } +cmt_insert_func_header = "" # string + +# The filename that contains text to insert before a class if the class isn't preceded with a C/C++ comment. +# Will substitute $(class) with the class name. +cmt_insert_class_header = "" # string + +# The filename that contains text to insert before a Obj-C message specification if the method isn't preceeded with a C/C++ comment. +# Will substitute $(message) with the function name and $(javaparam) with the javadoc @param and @return stuff. +cmt_insert_oc_msg_header = "" # string + +# If a preprocessor is encountered when stepping backwards from a function name, then +# this option decides whether the comment should be inserted. +# Affects cmt_insert_oc_msg_header, cmt_insert_func_header and cmt_insert_class_header. +cmt_insert_before_preproc = false # false/true + +# +# Preprocessor options +# + +# Control indent of preprocessors inside #if blocks at brace level 0 +pp_indent = remove # ignore/add/remove/force + +# Whether to indent #if/#else/#endif at the brace level (true) or from column 1 (false) +pp_indent_at_level = false # false/true + +# If pp_indent_at_level=false, specifies the number of columns to indent per level. Default=1. +pp_indent_count = 1 # number + +# Add or remove space after # based on pp_level of #if blocks +pp_space = force # ignore/add/remove/force + +# Sets the number of spaces added with pp_space +pp_space_count = 1 # number + +# The indent for #region and #endregion in C# and '#pragma region' in C/C++ +pp_indent_region = 0 # number + +# Whether to indent the code between #region and #endregion +pp_region_indent_code = false # false/true + +# If pp_indent_at_level=true, sets the indent for #if, #else, and #endif when not at file-level +pp_indent_if = 0 # number + +# Control whether to indent the code between #if, #else and #endif when not at file-level +pp_if_indent_code = false # false/true + +# Whether to indent '#define' at the brace level (true) or from column 1 (false) +pp_define_at_level = false # false/true + +# You can force a token to be a type with the 'type' option. +# Example: +# type myfoo1 myfoo2 +# +# You can create custom macro-based indentation using macro-open, +# macro-else and macro-close. +# Example: +# macro-open BEGIN_TEMPLATE_MESSAGE_MAP +# macro-open BEGIN_MESSAGE_MAP +# macro-close END_MESSAGE_MAP +# +# You can assign any keyword to any type with the set option. +# set func_call_user _ N_ +# +# The full syntax description of all custom definition config entries +# is shown below: +# +# define custom tokens as: +# - embed whitespace in token using '' escape character, or +# put token in quotes +# - these: ' " and ` are recognized as quote delimiters +# +# type token1 token2 token3 ... +# ^ optionally specify multiple tokens on a single line +# define def_token output_token +# ^ output_token is optional, then NULL is assumed +# macro-open token +# macro-close token +# macro-else token +# set id token1 token2 ... +# ^ optionally specify multiple tokens on a single line +# ^ id is one of the names in token_enum.h sans the CT_ prefix, +# e.g. PP_PRAGMA +# +# all tokens are separated by any mix of ',' commas, '=' equal signs +# and whitespace (space, tab) +# diff --git a/Algorithms/bplus-tree/LICENSE b/Algorithms/bplus-tree/LICENSE new file mode 100644 index 0000000..36b7cd9 --- /dev/null +++ b/Algorithms/bplus-tree/LICENSE @@ -0,0 +1,23 @@ +Boost Software License - Version 1.0 - August 17th, 2003 + +Permission is hereby granted, free of charge, to any person or organization +obtaining a copy of the software and accompanying documentation covered by +this license (the "Software") to use, reproduce, display, distribute, +execute, and transmit the Software, and to prepare derivative works of the +Software, and to permit third-parties to whom the Software is furnished to +do so, all subject to the following: + +The copyright notices in the Software and this entire statement, including +the above license grant, this restriction and the following disclaimer, +must be included in all copies of the Software, in whole or in part, and +all derivative works of the Software, unless such copies or derivative +works are solely in the form of machine-executable object code generated by +a source language processor. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT +SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE +FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, +ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/Algorithms/bplus-tree/Makefile b/Algorithms/bplus-tree/Makefile new file mode 100644 index 0000000..1d4f373 --- /dev/null +++ b/Algorithms/bplus-tree/Makefile @@ -0,0 +1,22 @@ +## +# Distributed under the Boost Software License, Version 1.0. +# See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt +## + +all: build/bplus_tree_test + +build: Makefile + install -d build + +coverage: Makefile + install -d coverage + +test: Makefile build/bplus_tree_test coverage/bplus_tree_test + ./build/bplus_tree_test + cd coverage && ./bplus_tree_test 1>/dev/null 2>/dev/null && lcov --capture --directory . --output bplus_tree_test.info && genhtml bplus_tree_test.info + +coverage/bplus_tree_test: Makefile coverage src/*.[ch] include/*.h test/*.c + cd coverage && gcc -std=c99 -fprofile-arcs -ftest-coverage -o bplus_tree_test ../test/bplus_tree_test.c `pkg-config --cflags --libs glib-2.0` -g -ggdb -I../include/ -I../src/ + +build/bplus_tree_test: Makefile build src/*.[ch] include/*.h test/*.c + cd build && clang -std=c99 -o bplus_tree_test ../test/bplus_tree_test.c `pkg-config --cflags --libs glib-2.0` -g -ggdb -I../include/ -I../src/ diff --git a/Algorithms/bplus-tree/include/bplus_tree.h b/Algorithms/bplus-tree/include/bplus_tree.h new file mode 100644 index 0000000..7bb3e1d --- /dev/null +++ b/Algorithms/bplus-tree/include/bplus_tree.h @@ -0,0 +1,63 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_TREE_H__ +#define __BPLUS_TREE_H__ + +#include +#include + +#include + +#ifdef __cplusplus +extern "C" +{ +#endif /* __cplusplus */ + +typedef uint64_t BplusKey; +typedef void* BplusValue; +typedef struct _BplusItem BplusItem; + +struct _BplusItem +{ + BplusKey key; + BplusValue value; +}; + +typedef struct _BplusTree BplusTree; +typedef struct _BplusIterator BplusIterator; + +typedef void (BplusForeachItemFunc)(BplusTree const* tree, BplusItem* item, void* argument); + +BplusTree* bplus_tree_new(); +BplusTree* bplus_tree_new_full(gboolean allow_duplicate_keys); +void bplus_tree_destroy(BplusTree* tree); +void bplus_tree_destroy_each(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument); + +void bplus_tree_insert(BplusTree* tree, BplusKey const key, BplusValue const value); +BplusValue bplus_tree_remove(BplusTree* tree, BplusKey const key); +BplusValue bplus_tree_remove_first(BplusTree* tree); +void bplus_tree_remove_value(BplusTree* tree, BplusKey const key, BplusValue const value); +BplusValue bplus_tree_get(BplusTree* tree, BplusKey const key); + +BplusValue bplus_tree_get_first(BplusTree const* tree); +BplusValue bplus_tree_get_nth(BplusTree const* tree, size_t position); + +BplusIterator* bplus_iterator_new(BplusTree const* tree); +void bplus_iterator_destroy(BplusIterator* iterator); +gboolean bplus_iterator_next(BplusIterator* iterator); +gboolean bplus_iterator_previous(BplusIterator* iterator); +BplusItem const* bplus_iterator_get_item(BplusIterator const* iterator); +BplusIterator* bplus_tree_first(BplusTree const* tree); +BplusIterator* bplus_iterator_from_key(BplusTree const* tree, BplusKey const key); +BplusIterator* bplus_iterator_to_key(BplusTree const* tree, BplusKey const key); +BplusIterator* bplus_iterator_for_key(BplusTree const* tree, BplusKey const key); +BplusIterator* bplus_iterator_for_key_range(BplusTree const* tree, BplusKey const key_from, BplusKey const key_to); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif // ifndef __BPLUS_TREE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_foreach.c b/Algorithms/bplus-tree/src/bplus_foreach.c new file mode 100644 index 0000000..e9184b7 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_foreach.c @@ -0,0 +1,39 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_foreach.h" + +#include "bplus_node.h" + +void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument) +{ + if (!node->is_leaf) + for (size_t i = 0; i < node->length; ++i) + bplus_foreach_item_in_node(tree, bplus_node_at(node, i), foreach, argument); + + else + for (size_t i = 0; i < node->length; ++i) + foreach(tree, node->items + i, argument); + +} + +void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument) +{ + bplus_foreach_item_in_node(tree, tree->root, foreach, argument); +} + +void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument) +{ + if (!node->is_leaf) + for (size_t i = 0; i < node->length; ++i) + bplus_foreach_node_in_node(tree, bplus_node_at(node, i), foreach, argument); + + foreach(tree, node, argument); +} + +void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument) +{ + bplus_foreach_node_in_node(tree, tree->root, foreach, argument); +} diff --git a/Algorithms/bplus-tree/src/bplus_foreach.h b/Algorithms/bplus-tree/src/bplus_foreach.h new file mode 100644 index 0000000..69849a6 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_foreach.h @@ -0,0 +1,27 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_FOREACH_H__ +#define __BPLUS_FOREACH_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument); +void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument); + +typedef void (BplusForeachNodeFunc)(BplusTree* tree, BplusNode* node, void* argument); +void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument); +void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_FOREACH_H__ diff --git a/Algorithms/bplus-tree/src/bplus_insert.c b/Algorithms/bplus-tree/src/bplus_insert.c new file mode 100644 index 0000000..9cd3ea7 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_insert.c @@ -0,0 +1,58 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_insert.h" + +#include "bplus_node.h" +#include "bplus_search.h" +#include "bplus_rebalance.h" + +#include + +static void bplus_leaf_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, BplusKey const key, BplusValue const value) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index <= node->length); + + bplus_node_move_and_resize_data(tree, node, index + 1, index); + bplus_key_at(node, index) = key; + bplus_value_at(node, index) = value; +} + +void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index <= node->length); + g_return_if_fail(node->length + length <= BPLUS_TREE_ORDER); + + bplus_node_move_and_resize_data(tree, node, index + length, index); + memcpy(node->items + index, items, length * sizeof(BplusItem)); + + if (node->is_leaf) + return; + + for (size_t i = index; i < index + length; ++i) + bplus_node_at(node, i)->parent = node; +} + +void bplus_tree_insert(BplusTree* tree, BplusKey const key, BplusValue const value) +{ + BplusPath path; + bplus_tree_get_path_to_key(tree, key, &path); + + size_t index = path.index[0]; + BplusNode* node = (BplusNode*) path.leaf; + + /* If the node is not empty, we will insert it after the given index */ + if ((index < node->length) && bplus_key_lte(tree, bplus_key_at(node, index), key)) + index++; + + bplus_leaf_insert_at(tree, node, index, key, value); + if (index == 0) + bplus_rebalance_propagate(tree, &path); + + if (bplus_node_overfilled(node)) + bplus_rebalance_overfilled(tree, &path); +} diff --git a/Algorithms/bplus-tree/src/bplus_insert.h b/Algorithms/bplus-tree/src/bplus_insert.h new file mode 100644 index 0000000..e73f963 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_insert.h @@ -0,0 +1,22 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_INSERT_H__ +#define __BPLUS_INSERT_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_INSERT_H__ diff --git a/Algorithms/bplus-tree/src/bplus_iterator.c b/Algorithms/bplus-tree/src/bplus_iterator.c new file mode 100644 index 0000000..8ab796e --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_iterator.c @@ -0,0 +1,161 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_iterator.h" + +#include "bplus_leaf.h" +#include "bplus_search.h" + +static BplusIterator* bplus_iterator_new_full(BplusTree const* tree, + BplusLeaf const* leaf_from, BplusItem const* item_from, + BplusLeaf const* leaf_to, BplusItem const* item_to) +{ + BplusIterator* iterator = g_slice_new(BplusIterator); + + iterator->leaf_from = leaf_from; + iterator->item_from = item_from; + iterator->leaf_to = leaf_to; + iterator->item_to = item_to; + iterator->item = item_from; + iterator->leaf = leaf_from; + + return iterator; +} + +static BplusIterator* bplus_iterator_new_to_last(BplusTree const* tree, BplusLeaf const* leaf_from, BplusItem const* item_from) +{ + return bplus_iterator_new_full(tree, leaf_from, item_from, tree->last, tree->last->node.items + tree->last->node.length); +} + +static BplusIterator* bplus_iterator_new_from_first(BplusTree const* tree, BplusLeaf const* leaf_to, BplusItem const* item_to) +{ + return bplus_iterator_new_full(tree, tree->first, tree->first->node.items, leaf_to, item_to); +} + +BplusIterator* bplus_iterator_new(BplusTree const* tree) +{ + return bplus_iterator_new_to_last(tree, tree->first, tree->first->node.items); +} + +void bplus_iterator_destroy(BplusIterator* iterator) +{ + g_return_if_fail(iterator != NULL); + + g_slice_free(BplusIterator, iterator); +} + +gboolean bplus_iterator_next(BplusIterator* iterator) +{ + g_return_val_if_fail(iterator != NULL, FALSE); + + BplusItem const* const next = iterator->item + 1; + BplusLeaf const* const leaf = iterator->leaf; + if (next == iterator->item_to) + return FALSE; + + if (next - leaf->node.items < leaf->node.length) + { + ++iterator->item; + } + else + { + if (leaf->right == NULL) + return FALSE; + + iterator->leaf = leaf->right; + iterator->item = leaf->right->node.items; + } + + return TRUE; +} + +gboolean bplus_iterator_previous(BplusIterator* iterator) +{ + g_return_val_if_fail(iterator != NULL, FALSE); + + BplusItem const* const item = iterator->item; + BplusLeaf const* const leaf = iterator->leaf; + + if (item == iterator->item_from) + return FALSE; + + if (item - leaf->node.items == 0) + { + if (leaf->left == NULL) + return FALSE; + + iterator->leaf = leaf->left; + iterator->item = leaf->left->node.items + leaf->left->node.length; + } + + --iterator->item; + + return TRUE; +} + +BplusItem const* bplus_iterator_get_item(BplusIterator const* iterator) +{ + g_return_val_if_fail(iterator != NULL, NULL); + + if (iterator->item_from == iterator->item_to) + return NULL; + + return iterator->item; +} + +BplusIterator* bplus_tree_first(BplusTree const* tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + return bplus_iterator_new(tree); +} + +BplusIterator* bplus_iterator_from_key(BplusTree const* tree, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to); + + return bplus_iterator_new_to_last(tree, (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0]); +} + +BplusIterator* bplus_iterator_to_key(BplusTree const* tree, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to); + + return bplus_iterator_new_from_first(tree, (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]); +} + +BplusIterator* bplus_iterator_for_key(BplusTree const* tree, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to); + + return bplus_iterator_new_full(tree, + (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0], + (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]); +} + +BplusIterator* bplus_iterator_for_key_range(BplusTree const* tree, BplusKey const key_from, BplusKey const key_to) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key_from, key_to, &path_from, &path_to); + + return bplus_iterator_new_full(tree, + (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0], + (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]); +} diff --git a/Algorithms/bplus-tree/src/bplus_iterator.h b/Algorithms/bplus-tree/src/bplus_iterator.h new file mode 100644 index 0000000..c7ae9b2 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_iterator.h @@ -0,0 +1,31 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_ITERATOR_H__ +#define __BPLUS_ITERATOR_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +struct _BplusIterator +{ + BplusItem const* item; + BplusLeaf const* leaf; + + BplusLeaf const* leaf_from; + BplusItem const* item_from; + BplusLeaf const* leaf_to; + BplusItem const* item_to; +}; + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_ITERATOR_H__ diff --git a/Algorithms/bplus-tree/src/bplus_leaf.c b/Algorithms/bplus-tree/src/bplus_leaf.c new file mode 100644 index 0000000..a6b6ae5 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_leaf.c @@ -0,0 +1,71 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_leaf.h" + +BplusLeaf* bplus_leaf_new(BplusTree* tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusLeaf* leaf = g_slice_new(BplusLeaf); + + bplus_node_init(&leaf->node, TRUE); + leaf->left = NULL; + leaf->right = NULL; + +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count++; + tree->leaf_count++; + tree->underflow_count++; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + return leaf; +} + +BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left) +{ + g_return_val_if_fail(tree != NULL, NULL); + g_return_val_if_fail(leaf_left != NULL, NULL); + + BplusLeaf* leaf_right = bplus_leaf_new(tree); + + leaf_right->left = leaf_left; + leaf_right->right = leaf_left->right; + leaf_left->right = leaf_right; + + if (leaf_right->right != NULL) + leaf_right->right->left = leaf_right; + + if (tree->last == leaf_left) + tree->last = leaf_right; + + return leaf_right; +} + +void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(leaf != NULL); + + if (leaf->left != NULL) + leaf->left->right = leaf->right; + + if (leaf->right != NULL) + leaf->right->left = leaf->left; + + if (tree->first == leaf) + tree->first = leaf->right; + + if (tree->last == leaf) + tree->last = leaf->left; + +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count--; + tree->leaf_count--; + tree->underflow_count--; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + g_slice_free(BplusLeaf, leaf); +} diff --git a/Algorithms/bplus-tree/src/bplus_leaf.h b/Algorithms/bplus-tree/src/bplus_leaf.h new file mode 100644 index 0000000..482a933 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_leaf.h @@ -0,0 +1,34 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_LEAF_H__ +#define __BPLUS_LEAF_H__ + +#include "bplus_tree_private.h" + +#include "bplus_node.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +struct _BplusLeaf +{ + BplusNode node; + + BplusLeaf* left; + BplusLeaf* right; +}; + +BplusLeaf* bplus_leaf_new(BplusTree* tree); +BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left); +void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_LEAF_H__ diff --git a/Algorithms/bplus-tree/src/bplus_node.c b/Algorithms/bplus-tree/src/bplus_node.c new file mode 100644 index 0000000..6637367 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_node.c @@ -0,0 +1,111 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_node.h" + +#include "bplus_leaf.h" + +#include + +BplusNode* bplus_node_new(BplusTree* tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusNode* node = g_slice_new(BplusNode); + + bplus_node_init(node, FALSE); + +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count++; + tree->underflow_count++; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + return node; +} + +BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left) +{ + g_return_val_if_fail(tree != NULL, NULL); + g_return_val_if_fail(node_left != NULL, NULL); + + BplusNode* node_right; + + if (node_left->is_leaf) + node_right = (BplusNode*) bplus_leaf_new_right(tree, (BplusLeaf*) node_left); + else + node_right = bplus_node_new(tree); + + node_right->parent = node_left->parent; + + return node_right; +} + +void bplus_node_init(BplusNode* node, gboolean is_leaf) +{ + g_return_if_fail(node != NULL); + + node->parent = NULL; + node->is_leaf = is_leaf; + + node->length = 0; +} + +void bplus_node_destroy(BplusTree* tree, BplusNode* node) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(node != NULL); + + if (node->is_leaf) + { + bplus_leaf_destroy(tree, (BplusLeaf*) node); + } + else + { +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count--; + tree->underflow_count--; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + g_slice_free(BplusNode, node); + } +} + +void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index_from <= node->length); + +#ifdef BPLUS_TREE_GATHER_STATS + int was_underfilled = bplus_node_underfilled(node); + int was_overfilled = bplus_node_overfilled(node); +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + int64_t const resize_length = index_to - index_from; + if (resize_length == 0) + return; + + int64_t const move_length = node->length - index_from; + if (move_length > 0) + memmove(node->items + index_to, node->items + index_from, move_length * sizeof(BplusItem)); + + if (resize_length > 0) + node->length += resize_length; + + else if (resize_length < 0) + node->length -= -resize_length; + +#ifdef BPLUS_TREE_GATHER_STATS + if (!bplus_node_underfilled(node) && was_underfilled) + tree->underflow_count--; + else if (bplus_node_underfilled(node) && !was_underfilled) + tree->underflow_count++; + + if (bplus_node_overfilled(node) && !was_overfilled) + tree->overflow_count++; + else if (!bplus_node_overfilled(node) && was_overfilled) + tree->overflow_count--; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + +} diff --git a/Algorithms/bplus-tree/src/bplus_node.h b/Algorithms/bplus-tree/src/bplus_node.h new file mode 100644 index 0000000..83a4d9a --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_node.h @@ -0,0 +1,55 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_NODE_H__ +#define __BPLUS_NODE_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +struct _BplusNode +{ + size_t length; + BplusItem items[BPLUS_TREE_ORDER]; + + uint8_t is_leaf; + BplusNode* parent; +}; + +#define bplus_key_gt(bplus_tree_m, k1, k2) ((k1) > (k2)) +#define bplus_key_gte(bplus_tree_m, k1, k2) ((k1) >= (k2)) +#define bplus_key_lt(bplus_tree_m, k1, k2) ((k1) < (k2)) +#define bplus_key_lte(bplus_tree_m, k1, k2) ((k1) <= (k2)) +#define bplus_key_eq(bplus_tree_m, k1, k2) ((k1) == (k2)) +#define bplus_key_neq(bplus_tree_m, k1, k2) ((k1) != (k2)) + +#define bplus_key_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].key) +#define bplus_key_first(node_m) bplus_key_at(node_m, 0) +#define bplus_key_last(node_m) bplus_key_at(node_m, (node_m)->length - 1) +#define bplus_value_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].value) +#define bplus_value_first(node_m) bplus_value_at(node_m, 0) +#define bplus_value_last(node_m) bplus_value_at(node_m, (node_m)->length - 1) +#define bplus_node_at(node_m, index_m) ((BplusNode*) bplus_value_at(node_m, index_m)) +#define bplus_node_first(node_m) ((BplusNode*) bplus_value_first(node_m)) +#define bplus_node_last(node_m) ((BplusNode*) bplus_value_last(node_m)) + +#define bplus_node_overfilled(node_m) ((node_m)->length > (BPLUS_TREE_ORDER - 1)) +#define bplus_node_underfilled(node_m) ((node_m)->length <= 1) + +BplusNode* bplus_node_new(BplusTree* tree); +BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left); +void bplus_node_destroy(BplusTree* tree, BplusNode* node); +void bplus_node_init(BplusNode* node, gboolean is_leaf); +void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_NODE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.c b/Algorithms/bplus-tree/src/bplus_rebalance.c new file mode 100644 index 0000000..a3cf401 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_rebalance.c @@ -0,0 +1,279 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_rebalance.h" + +#include "bplus_node.h" +#include "bplus_search.h" +#include "bplus_insert.h" +#include "bplus_remove.h" + +void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(path != NULL); + + BplusNode* node = path->leaf; + for (size_t i = 1; i < path->length; ++i) + { + size_t const index = path->index[i]; + BplusKey const key = bplus_key_first(node); + + if (bplus_key_gt(tree, bplus_key_at(node->parent, index), key)) + bplus_key_at(node->parent, index) = key; + else + break; + + node = node->parent; + } +} + +static int64_t bplus_node_get_rebalance_amount(BplusTree const* tree, BplusNode const* node_left, BplusNode const* node_right) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node_left != NULL, 0); + g_return_val_if_fail(node_right != NULL, 0); + + size_t const total = node_left->length + node_right->length; + + /* If the nodes can be merged without overfilling */ + if (total <= (BPLUS_TREE_ORDER / 3)) + return -node_right->length; + + /* If the data can be balanced over the two without overfilling */ + else if (total < (BPLUS_TREE_ORDER * 5 / 3)) + return node_left->length - (total + 1) / 2; + + return 0; +} + +static gboolean bplus_node_find_merge_candidate(BplusTree const* tree, size_t const index, BplusNode* node, + BplusNode** node_left, BplusNode** node_right) +{ + g_return_val_if_fail(tree != NULL, FALSE); + g_return_val_if_fail(node != NULL, FALSE); + + *node_left = node; + *node_right = node; + if ((node->parent == NULL) || (node->parent->length <= 1)) + return FALSE; + + if (index == 0) + { + *node_right = bplus_node_at(node->parent, index + 1); + if (bplus_node_get_rebalance_amount(tree, node, *node_right) == 0) + *node_right = node; + + } + else if (index == node->parent->length - 1) + { + *node_left = bplus_node_at(node->parent, index - 1); + if (bplus_node_get_rebalance_amount(tree, *node_left, node) == 0) + *node_left = node; + + } + else + { + *node_left = bplus_node_at(node->parent, index - 1); + *node_right = bplus_node_at(node->parent, index + 1); + + int64_t const merge_amount_right = bplus_node_get_rebalance_amount(tree, node, *node_right); + int64_t const merge_amount_left = bplus_node_get_rebalance_amount(tree, *node_left, node); + + if (merge_amount_left < 0) + { + /* Merge with left copies data to the left. + * Prefer a merge with right only if it copies less data from the right. + */ + if (merge_amount_right >= 0) + *node_right = node; + else if (merge_amount_right < merge_amount_left) + *node_right = node; + else + *node_left = node; + } + else if (merge_amount_left > 0) + { + /* Merge with left copies data from the left. + * Prefer a merge with right if it copies less data to the right or data from right. + */ + if (merge_amount_right == 0) + *node_right = node; + else if (merge_amount_right > merge_amount_left) + *node_right = node; + else + *node_left = node; + } + else if (merge_amount_right != 0) + { + /* Merge with left is impossible. + * Prefer a merge with right. + */ + *node_left = node; + } + else + { + *node_left = node; + *node_right = node; + } + } + + return *node_left != *node_right; +} /* bplus_node_find_merge_candidate */ + +static size_t bplus_rebalance_data(BplusTree const* tree, BplusNode* node_left, BplusNode* node_right) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node_left != NULL, 0); + g_return_val_if_fail(node_right != NULL, 0); + + int64_t const amount = bplus_node_get_rebalance_amount(tree, node_left, node_right); + g_return_val_if_fail(amount <= 0 || amount < node_left->length, 0); + g_return_val_if_fail(amount >= 0 || -amount <= node_right->length, 0); + + if (amount > 0) + { + size_t const index = node_left->length - amount; + BplusItem const* items = node_left->items + index; + + bplus_node_insert_at(tree, node_right, 0, amount, items); + bplus_node_remove_at(tree, node_left, index, amount); + + } + else if (amount < 0) + { + size_t const index = node_left->length; + BplusItem const* items = node_right->items; + + bplus_node_insert_at(tree, node_left, index, -amount, items); + bplus_node_remove_at(tree, node_right, 0, -amount); + } + + return 0; +} /* bplus_rebalance_data */ + +static void bplus_rebalance_split_node(BplusTree* tree, BplusNode* node_left, size_t const index) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(node_left != NULL); + + BplusNode* const node_right = bplus_node_new_right(tree, node_left); + bplus_rebalance_data(tree, node_left, node_right); + + BplusItem const item = { .key = bplus_key_first(node_right), .value = node_right }; + bplus_node_insert_at(tree, node_left->parent, index + 1, 1, &item); +} + +static void bplus_rebalance_new_root(BplusTree* tree) +{ + g_return_if_fail(tree != NULL); + + BplusNode* const node = tree->root; + BplusNode* const root = bplus_node_new(tree); + bplus_key_first(root) = bplus_key_first(node); + bplus_value_first(root) = node; + root->length = 1; + node->parent = root; + tree->root = root; + tree->height++; +} + +static int bplus_rebalance_try_merge(BplusTree* tree, BplusNode* node, size_t const index) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node != NULL, 0); + + BplusNode* node_left; + BplusNode* node_right; + if (!bplus_node_find_merge_candidate(tree, index, node, &node_left, &node_right)) + return 0; + + size_t const index_right = (node == node_left) ? index + 1 : index; + bplus_rebalance_data(tree, node_left, node_right); + + if (node_right->length == 0) + { + bplus_node_remove_at(tree, node->parent, index_right, 1); + bplus_node_destroy(tree, node_right); + } + else + { + bplus_key_at(node->parent, index_right) = bplus_key_first(node_right); + } + + return 1; +} + +void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(path != NULL); + + BplusNode* node = (BplusNode*) path->leaf; + for (size_t i = 1; i < path->length; ++i) + { + if (!bplus_node_overfilled(node)) + break; + + size_t const index = path->index[i]; + if (!bplus_rebalance_try_merge(tree, node, index)) + bplus_rebalance_split_node(tree, node, index); + + node = node->parent; + } + + if (bplus_node_overfilled(node)) + { + bplus_rebalance_new_root(tree); + bplus_rebalance_split_node(tree, node, 0); + } +} + +static void bplus_rebalance_shrink_tree(BplusTree* tree) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(tree->root != NULL); + + size_t i = 0; + for (; i < tree->height; ++i) + { + if (tree->root->length != 1) + break; + if (tree->root->is_leaf) + break; + + BplusNode* node = tree->root; + tree->root = bplus_node_first(tree->root); + tree->root->parent = NULL; + node->length = 0; + bplus_node_destroy(tree, node); + } + + tree->height -= i; +} + +void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(path != NULL); + + BplusNode* node = (BplusNode*) path->leaf; + for (size_t i = 1; i < path->length; ++i) + { + if (!bplus_node_underfilled(node)) + break; + + size_t const index = path->index[i]; + if (!bplus_rebalance_try_merge(tree, node, index) && (node->length == 0)) + { + bplus_node_remove_at(tree, node->parent, index, 1); + bplus_node_destroy(tree, node); + } + + node = node->parent; + } + + bplus_rebalance_shrink_tree(tree); +} diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.h b/Algorithms/bplus-tree/src/bplus_rebalance.h new file mode 100644 index 0000000..3872f4d --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_rebalance.h @@ -0,0 +1,24 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_REBALANCE_H__ +#define __BPLUS_REBALANCE_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path); +void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path); +void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_REBALANCE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_remove.c b/Algorithms/bplus-tree/src/bplus_remove.c new file mode 100644 index 0000000..9265ce1 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_remove.c @@ -0,0 +1,60 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_remove.h" + +#include "bplus_node.h" +#include "bplus_search.h" +#include "bplus_rebalance.h" + +void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index < node->length); + g_return_if_fail(index + length <= node->length); + + bplus_node_move_and_resize_data(tree, node, index, index + length); +} + +BplusValue bplus_tree_remove_first(BplusTree* tree) +{ + BplusPath path = { .leaf = (BplusNode*) tree->first }; + BplusNode* node = (BplusNode*) path.leaf; + size_t const index = path.index[0]; + + BplusValue value = bplus_value_at(node, 0); + bplus_node_remove_at(tree, node, index, 1); + if (index == 0) + bplus_rebalance_propagate(tree, &path); + + if (bplus_node_underfilled(node)) + bplus_rebalance_underfilled(tree, &path); + + return value; +} + +BplusValue bplus_tree_remove(BplusTree* tree, BplusKey const key) +{ + BplusPath path; + bplus_tree_get_path_to_key(tree, key, &path); + + size_t const index = path.index[0]; + BplusNode* node = (BplusNode*) path.leaf; + + if (bplus_key_eq(tree, bplus_key_at(node, index), key)) + { + BplusValue value = bplus_value_at(node, index); + bplus_node_remove_at(tree, node, index, 1); + if (index == 0) + bplus_rebalance_propagate(tree, &path); + + if (bplus_node_underfilled(node)) + bplus_rebalance_underfilled(tree, &path); + + return value; + } + + return NULL; +} diff --git a/Algorithms/bplus-tree/src/bplus_remove.h b/Algorithms/bplus-tree/src/bplus_remove.h new file mode 100644 index 0000000..81b94d3 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_remove.h @@ -0,0 +1,22 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_REMOVE_H__ +#define __BPLUS_REMOVE_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_REMOVE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_search.c b/Algorithms/bplus-tree/src/bplus_search.c new file mode 100644 index 0000000..a1e7c3b --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_search.c @@ -0,0 +1,127 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_search.h" + +#include "bplus_node.h" +#include "bplus_leaf.h" + +#define bplus_node_get_key_index_op(operator_m, tree_m, node_m, key_m) \ + do \ + { \ + size_t index = 1; \ + while (index < (node_m)->length) \ + { \ + if (operator_m((tree_m), bplus_key_at(node_m, index), (key_m))) \ + break; \ + ++index; \ + } \ + \ + return --index; \ + } \ + while (0) + +static size_t bplus_node_get_key_index(BplusTree const* tree, BplusNode const* node, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node != NULL, 0); + + bplus_node_get_key_index_op(bplus_key_gt, tree, node, key); +} + +static size_t bplus_node_get_key_index_before(BplusTree const* tree, BplusNode const* node, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node != NULL, 0); + + bplus_node_get_key_index_op(bplus_key_gte, tree, node, key); +} + +#define bplus_tree_get_path_to_key_op(operator_m, tree_m, key_m, path_m) \ + do \ + { \ + if (__builtin_expect(((tree_m)->root->length == 0), 0)) \ + { \ + (path_m)->length = 1; \ + (path_m)->index[0] = 0; \ + (path_m)->leaf = tree->root; \ + return; \ + } \ + \ + BplusNode const* node = (tree_m)->root; \ + size_t const length = (tree_m)->height; \ + for (size_t i = length; i > 0; --i) \ + { \ + for (int i = 0; i < BPLUS_TREE_ORDER * sizeof(*node->items) / 64; ++i) \ + { \ + __builtin_prefetch(node->items + i * 64 / sizeof(*node->items)); \ + } \ + \ + size_t const index = operator_m((tree_m), node, (key_m)); \ + (path_m)->index[i - 1] = index; \ + \ + if (i == 1) \ + break; \ + \ + node = bplus_node_at(node, index); \ + } \ + \ + (path_m)->length = length; \ + (path_m)->leaf = (BplusNode*) node; \ + } \ + while (0) + +void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path) +{ + g_return_if_fail(tree != NULL); + g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index)); + + bplus_tree_get_path_to_key_op(bplus_node_get_key_index, tree, key, path); +} + +static void bplus_tree_get_path_to_key_before(BplusTree const* tree, BplusKey const key, BplusPath* path) +{ + g_return_if_fail(tree != NULL); + g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index)); + + bplus_tree_get_path_to_key_op(bplus_node_get_key_index_before, tree, key, path); +} + +void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to) +{ + g_return_if_fail(tree != NULL); + g_assert(tree->height < sizeof((path_from)->index) / sizeof(*(path_from)->index)); + g_assert(tree->height < sizeof((path_to)->index) / sizeof(*(path_to)->index)); + + if (bplus_key_gt(tree, key_from, key_to)) + { + BplusKey tmp = key_to; + key_to = key_from; + key_from = tmp; + } + + bplus_tree_get_path_to_key(tree, key_to, path_to); + if (!bplus_key_gt(tree, bplus_key_at(path_to->leaf, path_to->index[0]), key_to)) + path_to->index[0]++; + + bplus_tree_get_path_to_key_before(tree, key_from, path_from); + if (!bplus_key_gte(tree, bplus_key_at(path_from->leaf, path_from->index[0]), key_from)) + path_from->index[0]++; + + BplusLeaf const* const leaf = (BplusLeaf*) path_from->leaf; + if (path_from->index[0] == leaf->node.length) + { + if (leaf->right == NULL) + { + path_from->leaf = path_to->leaf; + path_from->index[0] = path_to->index[0]; + } + else + { + path_from->leaf = (BplusNode*) leaf->right; + path_from->index[0] = 0; + } + } +} diff --git a/Algorithms/bplus-tree/src/bplus_search.h b/Algorithms/bplus-tree/src/bplus_search.h new file mode 100644 index 0000000..3e76a39 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_search.h @@ -0,0 +1,23 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_SEARCH_H__ +#define __BPLUS_SEARCH_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path); +void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_SEARCH_H__ diff --git a/Algorithms/bplus-tree/src/bplus_tree.c b/Algorithms/bplus-tree/src/bplus_tree.c new file mode 100644 index 0000000..fc8bb8e --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_tree.c @@ -0,0 +1,202 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_tree_private.h" + +#include "bplus_leaf.h" +#include "bplus_search.h" +#include "bplus_iterator.h" +#include "bplus_foreach.h" + +#include +#include +#include +#include +#include + +int bplus_tree_print(BplusTree const* const tree, char const* format, ...) __attribute__((format(printf, 2, 3))); + +BplusTree* bplus_tree_new() +{ + return bplus_tree_new_full(1); +} + +BplusTree* bplus_tree_new_full(gboolean allow_duplicate_keys) +{ + BplusTree* tree = malloc(sizeof(BplusTree)); + + tree->first = bplus_leaf_new(tree); + tree->last = tree->first; + tree->root = (BplusNode*) tree->first; + + tree->height = 1; + tree->allow_duplicate_keys = allow_duplicate_keys; + + return tree; +} + +void bplus_tree_print_stats(BplusTree* tree); + +static void bplus_foreach_node_destroy(BplusTree* tree, BplusNode* node, void* argument) +{ + bplus_node_destroy(tree, node); +} + +void bplus_tree_destroy(BplusTree* tree) +{ + g_return_if_fail(tree != NULL); + +#ifdef BPLUS_TREE_GATHER_STATS + bplus_tree_print_stats(tree); +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + bplus_foreach_node_in_tree(tree, &bplus_foreach_node_destroy, NULL); + free(tree); +} + +void bplus_tree_destroy_each(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument) +{ + bplus_foreach_item_in_tree(tree, foreach, argument); + bplus_tree_destroy(tree); +} + +#ifdef BPLUS_TREE_GATHER_STATS + +void bplus_tree_print_stats(BplusTree* tree) +{ + printf("tree height: %zu\n", tree->height); + printf("node count: %zu\n", tree->node_count); + printf("leaf count: %zu\n", tree->leaf_count); + printf("underflow count: %zu\n", tree->underflow_count); + printf("overflow count: %zu\n", tree->overflow_count); +} + +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + +BplusValue bplus_tree_get(BplusTree* tree, BplusKey key) +{ + BplusPath path; + bplus_tree_get_path_to_key(tree, key, &path); + + size_t const index = path.index[0]; + BplusNode const* node = path.leaf; + BplusValue value = NULL; + + if ((index < node->length) && bplus_key_eq(tree, bplus_key_at(node, index), key)) + value = bplus_value_at(node, index); + + return value; +} + +BplusValue bplus_tree_get_first(BplusTree const* tree) +{ + if (tree->first->node.length == 0) + return NULL; + + return tree->first->node.items[0].value; +} + +BplusValue bplus_tree_get_nth(BplusTree const* tree, size_t position) +{ + BplusLeaf* leaf = tree->first; + if (leaf->node.length == 0) + return NULL; + + while (leaf != NULL && position >= leaf->node.length) + { + position -= leaf->node.length; + leaf = leaf->right; + } + + if (leaf != NULL) + return leaf->node.items[position].value; + + return NULL; +} + +void bplus_value_print(BplusNode* node, size_t const index, BplusKey key, BplusValue value, int depth) +{ + static char const* indent = " "; + + fprintf(stderr, "%*.s n%p_%zu[label=\"%lu\",fontcolor=\"#000099\"];", 0, indent, node, index, key); + fprintf(stderr, "%*.s n%p->n%p_%zu;", 0, indent, node, node, index); +} + +void bplus_node_print(BplusNode* parent, BplusKey key, BplusNode* node, int depth) +{ + static char const* indent = " "; + + fprintf(stderr, "%*.s n%p[label=\"%lu\"];", 0, indent, node, key); + fprintf(stderr, "%*.s n%p->n%p;", 0, indent, parent, node); + + if (node->is_leaf) + { + if (((BplusLeaf*) node)->right != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right); + if (((BplusLeaf*) node)->left != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left); + } + + for (size_t i = 0; i < node->length; ++i) + { + if (node->is_leaf) + bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2); + else + bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), depth + 2); + + } +} + +int bplus_tree_print(BplusTree const* const tree, char const* format, ...) +{ + static int count = 0; + + fprintf(stderr, "echo 'digraph {"); + fprintf(stderr, "graph[ordering=\"out\"];\n"); + fprintf(stderr, "node[width=0.2,height=0.2,fixedsize=true,fontsize=6,fontcolor=\"#990000\",shape=plaintext];"); + fprintf(stderr, "edge[arrowsize=0.1,fontsize=6];"); + + BplusNode* node = tree->root; + fprintf(stderr, "n%p[label=\"0\"];", node); + if (node->is_leaf) + { + if (((BplusLeaf*) node)->right != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right); + if (((BplusLeaf*) node)->left != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left); + } + + for (size_t i = 0; i < node->length; ++i) + { + if (node->is_leaf) + bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2); + else + bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), 2); + + } + + va_list vargs; + va_start(vargs, format); + vfprintf(stderr, format, vargs); + va_end(vargs); + + fprintf(stderr, "}'| dot -T png -o tree-%d.png\n", count); + count++; + return 0; +} + +int bplus_iterator_print(BplusTree const* tree, BplusIterator const* iterator) +{ + bplus_tree_print(tree, + "label=\"iterator\"; i[fontcolor=\"#009900\",label=\"i\"];" + "n%p_%zu->i[label=\"from\"];" + "n%p_%zu->i[color=\"#009900\"];" + "n%p_%zu->i[label=\"to\"];", + iterator->leaf_from, iterator->item_from - iterator->leaf_from->node.items, + iterator->leaf, iterator->item - iterator->leaf->node.items, + iterator->leaf_to, iterator->item_to - iterator->leaf_to->node.items - 1); + + return 0; +} diff --git a/Algorithms/bplus-tree/src/bplus_tree_private.h b/Algorithms/bplus-tree/src/bplus_tree_private.h new file mode 100644 index 0000000..97b873f --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_tree_private.h @@ -0,0 +1,53 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_TREE_PRIVATE_H__ +#define __BPLUS_TREE_PRIVATE_H__ + +#include "bplus_tree.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +#ifndef BPLUS_TREE_ORDER +# define BPLUS_TREE_ORDER 32 +#endif /* ifndef BPLUS_TREE_ORDER */ + +typedef struct _BplusNode BplusNode; +typedef struct _BplusLeaf BplusLeaf; +typedef struct _BplusPath BplusPath; + +struct _BplusPath +{ + size_t length; + size_t index[16]; + BplusNode* leaf; +}; + +struct _BplusTree +{ + BplusNode* root; + + BplusLeaf* first; + BplusLeaf* last; + + size_t height; + gboolean allow_duplicate_keys; + +#ifdef BPLUS_TREE_GATHER_STATS + size_t node_count; + size_t leaf_count; + size_t underflow_count; + size_t overflow_count; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ +}; + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_TREE_PRIVATE_H__ diff --git a/Algorithms/bplus-tree/test/bplus_tree_all.c b/Algorithms/bplus-tree/test/bplus_tree_all.c new file mode 100644 index 0000000..1186dc8 --- /dev/null +++ b/Algorithms/bplus-tree/test/bplus_tree_all.c @@ -0,0 +1,14 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_tree.c" +#include "bplus_search.c" +#include "bplus_remove.c" +#include "bplus_rebalance.c" +#include "bplus_node.c" +#include "bplus_leaf.c" +#include "bplus_iterator.c" +#include "bplus_insert.c" +#include "bplus_foreach.c" diff --git a/Algorithms/bplus-tree/test/bplus_tree_test.c b/Algorithms/bplus-tree/test/bplus_tree_test.c new file mode 100644 index 0000000..5ddd69f --- /dev/null +++ b/Algorithms/bplus-tree/test/bplus_tree_test.c @@ -0,0 +1,560 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef BPLUS_TREE_ORDER +# define BPLUS_TREE_ORDER 4 +#endif /* ifndef BPLUS_TREE_ORDER */ + +#include "bplus_tree_all.c" + +void test_search_key_index(void) +{ + BplusTree tree; + BplusNode node; + + node.length = 0; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0); + + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0); + + bplus_key_at(&node, 0) = 1; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 1); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + bplus_key_at(&node, 2) = 2; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 2); + g_assert(bplus_node_get_key_index(&tree, &node, 3) == 2); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 2); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + bplus_key_at(&node, 2) = 3; + bplus_key_at(&node, 3) = 3; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 3) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 4) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 3); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + bplus_key_at(&node, 2) = 1; + bplus_key_at(&node, 3) = 1; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 3) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 4) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 3); + + // bplus_key_at(&node, 0) = 1; + // bplus_key_at(&node, 1) = 2; + // bplus_key_at(&node, 2) = 3; + // bplus_key_at(&node, 3) = 4; + // bplus_key_at(&node, 4) = 4; + // bplus_key_at(&node, 5) = 4; + // bplus_key_at(&node, 6) = 6; + // bplus_key_at(&node, 7) = 6; + // bplus_key_at(&node, 8) = 9; + // node.length = 9; + // g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + // g_assert(bplus_node_get_key_index(&tree, &node, 1) == 0); + // g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1); + // g_assert(bplus_node_get_key_index(&tree, &node, 3) == 2); + // g_assert(bplus_node_get_key_index(&tree, &node, 4) == 5); + // g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 8); +} /* test_search_key_index */ + +void test_search_bplus_tree_new(void) +{ + BplusTree* tree = bplus_tree_new(); + + g_assert(tree != NULL); + g_assert(tree->root != NULL); + g_assert((void*) tree->root == (void*) tree->first); + g_assert((void*) tree->root == (void*) tree->last); + + g_assert(tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 0); + + g_assert(tree->first->left == NULL); + g_assert(tree->first->right == NULL); + + bplus_tree_destroy(tree); +} + +void test_search_bplus_node_insert_at(void) +{ + // BplusTree* tree = bplus_tree_new(); + + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 1); + + // g_assert(tree->root->is_leaf); + // g_assert(tree->root->parent == NULL); + // g_assert(tree->root->length == 1); + + // g_assert(bplus_key_first(tree->root) == 0); + // g_assert(bplus_value_first(tree->root) == (void*) 1); + + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 2); + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 3); + + // g_assert(bplus_value_first(tree->root) == (void*) 3); + // g_assert(bplus_value_at(tree->root, 1) == (void*) 2); + // g_assert(bplus_value_at(tree->root, 2) == (void*) 1); + + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 4); + + // /* We should have splitted here */ + // g_assert(!tree->root->is_leaf); + // g_assert(tree->root->parent == NULL); + // g_assert(tree->root->length == 2); + + // g_assert(bplus_key_first(tree->root) == 0); + // BplusNode* left = (BplusNode*) bplus_value_first(tree->root); + // g_assert(left != NULL); + + // g_assert(bplus_key_at(tree->root, 1) == 0); + // BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1); + // g_assert(right != NULL); + + // g_assert(left->is_leaf); + // g_assert(left->parent == tree->root); + // g_assert(left->length == 2); + // g_assert(bplus_key_first(left) == 0); + // g_assert(bplus_value_first(left) == (void*) 4); + // g_assert(bplus_key_at(left, 1) == 0); + // g_assert(bplus_value_at(left, 1) == (void*) 3); + + // g_assert(right->is_leaf); + // g_assert(right->parent == tree->root); + // g_assert(right->length == 2); + // g_assert(bplus_key_first(right) == 0); + // g_assert(bplus_value_first(right) == (void*) 2); + // g_assert(bplus_key_at(right, 1) == 0); + // g_assert(bplus_value_at(right, 1) == (void*) 1); + + // bplus_node_insert_at(tree, left, 2, 0, (void*) 1); + // bplus_node_insert_at(tree, left, 2, 0, (void*) 2); + + // g_assert(tree->root->length == 3); + + // g_assert(bplus_key_at(tree->root, 1) == 0); + // BplusNode* middle = (BplusNode*) bplus_value_at(tree->root, 1); + // g_assert(middle != NULL); + // g_assert(middle != left); + // g_assert(middle != right); + + // g_assert(bplus_key_first(tree->root) == 0); + // g_assert(bplus_value_first(tree->root) == left); + // g_assert(bplus_key_at(tree->root, 1) == 0); + // g_assert(bplus_value_at(tree->root, 1) == middle); + // g_assert(bplus_key_at(tree->root, 2) == 0); + // g_assert(bplus_value_at(tree->root, 2) == right); + + // g_assert(middle->is_leaf); + // g_assert(middle->parent == tree->root); + // g_assert(middle->length == 2); + // g_assert(bplus_key_first(middle) == 0); + // g_assert(bplus_value_first(middle) == (void*) 2); + // g_assert(bplus_key_at(middle, 1) == 0); + // g_assert(bplus_value_at(middle, 1) == (void*) 1); + + // g_assert(tree->first == (BplusLeaf*) left); + // g_assert(tree->last == (BplusLeaf*) right); + // g_assert(((BplusLeaf*) left)->right == (BplusLeaf*) middle); + // g_assert(((BplusLeaf*) right)->left == (BplusLeaf*) middle); + // g_assert(((BplusLeaf*) left)->left == NULL); + // g_assert(((BplusLeaf*) right)->right == NULL); + // g_assert(((BplusLeaf*) middle)->left == (BplusLeaf*) left); + // g_assert(((BplusLeaf*) middle)->right == (BplusLeaf*) right); + + // bplus_tree_destroy(tree); +} /* test_search_bplus_node_insert_at */ + +void test_search_bplus_tree_insert_k0(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 0, (void*) 1); + + g_assert(tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 1); + + g_assert(bplus_key_first(tree->root) == 0); + g_assert(bplus_value_first(tree->root) == (void*) 1); + + bplus_tree_insert(tree, 0, (void*) 2); + bplus_tree_insert(tree, 0, (void*) 3); + + g_assert(bplus_value_first(tree->root) == (void*) 1); + g_assert(bplus_value_at(tree->root, 1) == (void*) 2); + g_assert(bplus_value_at(tree->root, 2) == (void*) 3); + + bplus_tree_insert(tree, 0, (void*) 4); + + /* We should have splitted here */ + g_assert(!tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 2); + + g_assert(bplus_key_first(tree->root) == 0); + BplusNode* left = (BplusNode*) bplus_value_first(tree->root); + g_assert(left != NULL); + + g_assert(bplus_key_at(tree->root, 1) == 0); + BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1); + g_assert(right != NULL); + + g_assert(left->is_leaf); + g_assert(left->parent == tree->root); + g_assert(left->length == 2); + g_assert(bplus_key_first(left) == 0); + g_assert(bplus_value_first(left) == (void*) 1); + g_assert(bplus_key_at(left, 1) == 0); + g_assert(bplus_value_at(left, 1) == (void*) 2); + + g_assert(right->is_leaf); + g_assert(right->parent == tree->root); + g_assert(right->length == 2); + g_assert(bplus_key_first(right) == 0); + g_assert(bplus_value_first(right) == (void*) 3); + g_assert(bplus_key_at(right, 1) == 0); + g_assert(bplus_value_at(right, 1) == (void*) 4); + + bplus_tree_insert(tree, 0, (void*) 5); + bplus_tree_insert(tree, 0, (void*) 6); + + g_assert(tree->root->length == 3); + + g_assert(bplus_key_at(tree->root, 2) == 0); + BplusNode* middle = right; + right = (BplusNode*) bplus_value_at(tree->root, 2); + g_assert(middle != NULL); + g_assert(middle != left); + g_assert(middle != right); + + g_assert(bplus_key_first(tree->root) == 0); + g_assert(bplus_value_first(tree->root) == left); + g_assert(bplus_key_at(tree->root, 1) == 0); + g_assert(bplus_value_at(tree->root, 1) == middle); + g_assert(bplus_key_at(tree->root, 2) == 0); + g_assert(bplus_value_at(tree->root, 2) == right); + + g_assert(right->is_leaf); + g_assert(right->parent == tree->root); + g_assert(right->length == 2); + g_assert(bplus_key_first(right) == 0); + g_assert(bplus_value_first(right) == (void*) 5); + g_assert(bplus_key_at(right, 1) == 0); + g_assert(bplus_value_at(right, 1) == (void*) 6); + + g_assert(tree->first == (BplusLeaf*) left); + g_assert(tree->last == (BplusLeaf*) right); + g_assert(((BplusLeaf*) left)->right == (BplusLeaf*) middle); + g_assert(((BplusLeaf*) right)->left == (BplusLeaf*) middle); + g_assert(((BplusLeaf*) left)->left == NULL); + g_assert(((BplusLeaf*) right)->right == NULL); + g_assert(((BplusLeaf*) middle)->left == (BplusLeaf*) left); + g_assert(((BplusLeaf*) middle)->right == (BplusLeaf*) right); + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_insert_k0 */ + +void test_search_bplus_tree_insert_k(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 3, (void*) 1); + + g_assert(tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 1); + + g_assert(bplus_key_first(tree->root) == 3); + g_assert(bplus_value_first(tree->root) == (void*) 1); + + bplus_tree_insert(tree, 1, (void*) 2); + g_assert(bplus_value_first(tree->root) == (void*) 2); + g_assert(bplus_value_at(tree->root, 1) == (void*) 1); + + bplus_tree_insert(tree, 2, (void*) 3); + + g_assert(bplus_value_first(tree->root) == (void*) 2); + g_assert(bplus_value_at(tree->root, 1) == (void*) 3); + g_assert(bplus_value_at(tree->root, 2) == (void*) 1); + + bplus_tree_insert(tree, 2, (void*) 4); + + /* We should have splitted here */ + g_assert(!tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 2); + + g_assert(bplus_key_first(tree->root) == 1); + BplusNode* left = (BplusNode*) bplus_value_first(tree->root); + g_assert(left != NULL); + + g_assert(bplus_key_at(tree->root, 1) == 2); + BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1); + g_assert(right != NULL); + + g_assert(left->is_leaf); + g_assert(left->parent == tree->root); + g_assert(left->length == 2); + g_assert(bplus_key_first(left) == 1); + g_assert(bplus_value_first(left) == (void*) 2); + g_assert(bplus_key_at(left, 1) == 2); + g_assert(bplus_value_at(left, 1) == (void*) 3); + + g_assert(right->is_leaf); + g_assert(right->parent == tree->root); + g_assert(right->length == 2); + g_assert(bplus_key_first(right) == 2); + g_assert(bplus_value_first(right) == (void*) 4); + g_assert(bplus_key_at(right, 1) == 3); + g_assert(bplus_value_at(right, 1) == (void*) 1); + + g_assert(bplus_key_first(tree->root) == 1); + g_assert(bplus_key_at(tree->root, 1) == 2); + + bplus_tree_insert(tree, 3, (void*) 5); + bplus_tree_insert(tree, 3, (void*) 6); + g_assert(tree->root->length == 3); + + /* Should not have splitted */ + g_assert(bplus_value_first(tree->root) == (void*) left); + g_assert(bplus_value_at(tree->root, 1) == (void*) right); + + bplus_tree_insert(tree, 2, (void*) 7); + g_assert(tree->root->length == 3); + g_assert(bplus_key_first(tree->root) == 1); + g_assert(bplus_key_at(tree->root, 1) == 2); + g_assert(bplus_key_at(tree->root, 2) == 3); + + // /* Should split root again */ + // bplus_tree_insert(tree, 4, (void*) 8); + // g_assert(tree->root->length == 3); + // g_assert(bplus_value_first(tree->root) != (void*) left); + // g_assert(bplus_value_at(tree->root, 1) != (void*) right); + + // g_assert(bplus_key_first(tree->root) == 1); + // g_assert(bplus_key_at(tree->root, 1) == 3); + + /* This should propagate 0 up to root */ + bplus_tree_insert(tree, 0, (void*) 9); + g_assert((bplus_key_first(tree->root) == 0)); + + // for (int i = 0; i < 10000; ++i) { + // bplus_tree_insert(tree, random(), (void*) i + 1); + // } + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_insert_k */ + +void test_search_bplus_tree_remove_k(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 3, (void*) 1); + bplus_tree_insert(tree, 1, (void*) 2); + bplus_tree_insert(tree, 2, (void*) 3); + bplus_tree_insert(tree, 2, (void*) 4); + bplus_tree_insert(tree, 3, (void*) 5); + bplus_tree_insert(tree, 3, (void*) 6); + bplus_tree_insert(tree, 2, (void*) 7); + bplus_tree_insert(tree, 4, (void*) 8); + bplus_tree_insert(tree, 0, (void*) 9); + + // bplus_tree_print(tree, "label=\"remove(0)\";"); + bplus_tree_remove(tree, 0); + + // bplus_tree_print(tree, "label=\"remove(1)\";"); + bplus_tree_remove(tree, 1); + + // bplus_tree_print(tree, "label=\"remove(4)\";"); + bplus_tree_remove(tree, 4); + + // bplus_tree_print(tree, "label=\"remove(3)\";"); + bplus_tree_remove(tree, 3); + + // bplus_tree_print(tree, "label=\"remove(2)\";"); + bplus_tree_remove(tree, 2); + + // bplus_tree_print(tree, "label=\"remove(3)\";"); + bplus_tree_remove(tree, 3); + + // bplus_tree_print(tree, "label=\"remove(3)\";"); + bplus_tree_remove(tree, 3); + + // bplus_tree_print(tree, "label=\"remove(2)\";"); + bplus_tree_remove(tree, 2); + + // bplus_tree_print(tree, "label=\"remove(2)\";"); + bplus_tree_remove(tree, 2); + + // bplus_tree_print(tree, ""); + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_insert_k */ + +void test_search_bplus_tree_iterator(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 3, (void*) 1); + bplus_tree_insert(tree, 1, (void*) 2); + bplus_tree_insert(tree, 2, (void*) 3); + bplus_tree_insert(tree, 2, (void*) 4); + bplus_tree_insert(tree, 3, (void*) 5); + bplus_tree_insert(tree, 3, (void*) 6); + bplus_tree_insert(tree, 2, (void*) 7); + bplus_tree_insert(tree, 4, (void*) 8); + bplus_tree_insert(tree, 0, (void*) 9); + + BplusKey keys[] = { 0, 1, 2, 2, 2, 3, 3, 3, 4 }; + BplusValue values[] = { (BplusValue*) 9, (BplusValue*) 2, (BplusValue*) 3, (BplusValue*) 4, (BplusValue*) 7, (BplusValue*) 1, (BplusValue*) 5, (BplusValue*) 6, (BplusValue*) 8 }; + + BplusIterator* iterator = bplus_tree_first(tree); + for (int i = 0; i < 9; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i]); + g_assert(item->value == values[i]); + if (i < 8) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_to_key(tree, 2); + for (int i = 0; i < 5; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i]); + g_assert(item->value == values[i]); + if (i < 4) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + for (int i = 4; i >= 0; --i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i]); + g_assert(item->value == values[i]); + if (i > 0) + bplus_iterator_previous(iterator); + } + g_assert(!bplus_iterator_previous(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key(tree, 2); + for (int i = 0; i < 3; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 2) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_from_key(tree, 2); + for (int i = 0; i < 7; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 6) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 2, 3); + for (int i = 0; i < 6; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 5) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 3, 2); + for (int i = 0; i < 6; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 5) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 4, 5); + for (int i = 0; i < 1; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 8]); + g_assert(item->value == values[i + 8]); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 5, 5); + g_assert(bplus_iterator_get_item(iterator) == NULL); + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 5, 6); + g_assert(bplus_iterator_get_item(iterator) == NULL); + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_iterator */ + +int main(int argc, char** argv) +{ + g_test_init(&argc, &argv, NULL); + + g_test_add_func("/tree/search_key_index", test_search_key_index); + g_test_add_func("/tree/new", test_search_bplus_tree_new); + g_test_add_func("/tree/insert_at", test_search_bplus_node_insert_at); + g_test_add_func("/tree/insert_k0", test_search_bplus_tree_insert_k0); + g_test_add_func("/tree/insert_k", test_search_bplus_tree_insert_k); + g_test_add_func("/tree/remove_k", test_search_bplus_tree_remove_k); + g_test_add_func("/tree/iterator", test_search_bplus_tree_iterator); + + g_test_run(); + return 0; +} -- cgit v1.2.3