/* * %CopyrightBegin% * * Copyright Ericsson AB 1998-2016. All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * %CopyrightEnd% */ #ifndef _DB_TREE_UTIL_H #define _DB_TREE_UTIL_H /* ** Internal functions and macros used by both the CA tree and the AVL tree */ #if defined(ARCH_32) /* ** A stack of this size is enough for an AVL tree with more than ** 0xFFFFFFFF elements. May be subject to change if ** the datatype of the element counter is changed to a 64 bit integer. ** The Maximal height of an AVL tree is calculated as: ** h(n) <= 1.4404 * log(n + 2) - 0.328 ** Where n denotes the number of nodes, h(n) the height of the tree ** with n nodes and log is the binary logarithm. */ #define STACK_NEED 50 #elif defined(ARCH_64) /* ** A stack of this size is enough for an AVL tree with more than ** 2^61 elements. ** The Maximal height of an AVL tree is calculated as above. */ #define STACK_NEED 90 #else #error "Unsported architecture" #endif #define PUSH_NODE(Dtt, Tdt) \ ((Dtt)->array[(Dtt)->pos++] = Tdt) #define POP_NODE(Dtt) \ (((Dtt)->pos) ? \ (Dtt)->array[--((Dtt)->pos)] : NULL) #define TOP_NODE(Dtt) \ ((Dtt->pos) ? \ (Dtt)->array[(Dtt)->pos - 1] : NULL) #define EMPTY_NODE(Dtt) (TOP_NODE(Dtt) == NULL) #define DEC_NITEMS(DB) \ erts_flxctr_dec(&(DB)->common.counters, ERTS_DB_TABLE_NITEMS_COUNTER_ID) static ERTS_INLINE void free_term(DbTable *tb, TreeDbTerm* p) { db_free_term(tb, p, offsetof(TreeDbTerm, dbterm)); } /* ** Some macros for "direction stacks" */ #define DIR_LEFT 0 #define DIR_RIGHT 1 #define DIR_END 2 static ERTS_INLINE Sint cmp_key(DbTableCommon* tb, Eterm key, TreeDbTerm* obj) { return CMP(key, GETKEY(tb,obj->dbterm.tpl)); } int tree_balance_left(TreeDbTerm **this); int tree_balance_right(TreeDbTerm **this); int db_first_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm *ret, DbTableTree *stack_container); int db_next_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm key, Eterm *ret, DbTreeStack* stack); int db_last_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm *ret, DbTableTree *stack_container); int db_prev_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm key, Eterm *ret, DbTreeStack* stack); int db_put_tree_common(DbTableCommon *tb, TreeDbTerm **root, Eterm obj, int key_clash_fail, DbTableTree *stack_container); int db_get_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm *root, Eterm key, Eterm *ret, DbTableTree *stack_container); int db_get_element_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm *root, Eterm key, int ndex, Eterm *ret, DbTableTree *stack_container); int db_member_tree_common(DbTableCommon *tb, TreeDbTerm *root, Eterm key, Eterm *ret, DbTableTree *stack_container); int db_erase_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm key, Eterm *ret, DbTreeStack *stack /* NULL if no static stack */); int db_erase_object_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm object, Eterm *ret, DbTableTree *stack_container); int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm slot_term, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator*); int db_select_chunk_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Sint chunk_size, int reverse, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator*); int db_select_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, int reverse, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator*); int db_select_delete_tree_common(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret, DbTreeStack* stack, CATreeRootIterator* iter); int db_select_continue_tree_common(Process *p, DbTableCommon *tb, Eterm continuation, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator* iter); int db_select_delete_continue_tree_common(Process *p, DbTable *tbl, Eterm continuation, Eterm *ret, DbTreeStack* stack, CATreeRootIterator* iter); int db_select_count_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator* iter); int db_select_count_continue_tree_common(Process *p, DbTable *tb, Eterm continuation, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator* iter); int db_select_replace_tree_common(Process *p, DbTable*, Eterm tid, Eterm pattern, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator* iter); int db_select_replace_continue_tree_common(Process *p, DbTable*, Eterm continuation, Eterm *ret, DbTableTree *stack_container, CATreeRootIterator* iter); int db_take_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root, Eterm key, Eterm *ret, DbTreeStack *stack /* NULL if no static stack */); void db_print_tree_common(fmtfn_t to, void *to_arg, int show, TreeDbTerm *root, DbTable *tbl); void db_foreach_offheap_tree_common(TreeDbTerm *root, void (*func)(ErlOffHeap *, void *), void * arg); int db_lookup_dbterm_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root, Eterm key, Eterm obj, DbUpdateHandle* handle, DbTableTree *stack_container); void db_finalize_dbterm_tree_common(int cret, DbUpdateHandle *handle, DbTableTree *stack_container); Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key); #endif /* _DB_TREE_UTIL_H */