1 /*
2 * %CopyrightBegin%
3 *
4 * Copyright Ericsson AB 1998-2020. All Rights Reserved.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * %CopyrightEnd%
19 */
20
21 #ifndef _DB_TREE_UTIL_H
22 #define _DB_TREE_UTIL_H
23
24 /*
25 ** Internal functions and macros used by both the CA tree and the AVL tree
26 */
27
28
29 #if defined(ARCH_32)
30 /*
31 ** A stack of this size is enough for an AVL tree with more than
32 ** 0xFFFFFFFF elements. May be subject to change if
33 ** the datatype of the element counter is changed to a 64 bit integer.
34 ** The Maximal height of an AVL tree is calculated as:
35 ** h(n) <= 1.4404 * log(n + 2) - 0.328
36 ** Where n denotes the number of nodes, h(n) the height of the tree
37 ** with n nodes and log is the binary logarithm.
38 */
39 #define STACK_NEED 50
40 #elif defined(ARCH_64)
41 /*
42 ** A stack of this size is enough for an AVL tree with more than
43 ** 2^61 elements.
44 ** The Maximal height of an AVL tree is calculated as above.
45 */
46 #define STACK_NEED 90
47 #else
48 #error "Unsported architecture"
49 #endif
50
51
52
53 #define PUSH_NODE(Dtt, Tdt) \
54 ((Dtt)->array[(Dtt)->pos++] = Tdt)
55
56 #define POP_NODE(Dtt) \
57 (((Dtt)->pos) ? \
58 (Dtt)->array[--((Dtt)->pos)] : NULL)
59
60 #define TOP_NODE(Dtt) \
61 ((Dtt->pos) ? \
62 (Dtt)->array[(Dtt)->pos - 1] : NULL)
63
64 #define EMPTY_NODE(Dtt) (TOP_NODE(Dtt) == NULL)
65
66 #define DEC_NITEMS(DB) \
67 erts_flxctr_dec(&(DB)->common.counters, ERTS_DB_TABLE_NITEMS_COUNTER_ID)
68
free_term(DbTable * tb,TreeDbTerm * p)69 static ERTS_INLINE void free_term(DbTable *tb, TreeDbTerm* p)
70 {
71 db_free_term(tb, p, offsetof(TreeDbTerm, dbterm));
72 }
73
74 /*
75 ** Some macros for "direction stacks"
76 */
77 #define DIR_LEFT 0
78 #define DIR_RIGHT 1
79 #define DIR_END 2
80
cmp_key(DbTableCommon * tb,Eterm key,TreeDbTerm * obj)81 static ERTS_INLINE Sint cmp_key(DbTableCommon* tb, Eterm key, TreeDbTerm* obj) {
82 return CMP(key, GETKEY(tb,obj->dbterm.tpl));
83 }
84
85 int tree_balance_left(TreeDbTerm **this);
86 int tree_balance_right(TreeDbTerm **this);
87
88 int db_first_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root,
89 Eterm *ret, DbTableTree *stack_container);
90 int db_next_tree_common(Process *p, DbTable *tbl,
91 TreeDbTerm *root, Eterm key,
92 Eterm *ret, DbTreeStack* stack);
93 int db_last_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root,
94 Eterm *ret, DbTableTree *stack_container);
95 int db_prev_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm key,
96 Eterm *ret, DbTreeStack* stack);
97 int db_put_tree_common(DbTableCommon *tb, TreeDbTerm **root, Eterm obj,
98 int key_clash_fail, DbTableTree *stack_container);
99 int db_get_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm *root, Eterm key,
100 Eterm *ret, DbTableTree *stack_container);
101 int db_get_element_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm *root, Eterm key,
102 int ndex, Eterm *ret, DbTableTree *stack_container);
103 int db_member_tree_common(DbTableCommon *tb, TreeDbTerm *root, Eterm key, Eterm *ret,
104 DbTableTree *stack_container);
105 int db_erase_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm key, Eterm *ret,
106 DbTreeStack *stack /* NULL if no static stack */);
107 int db_erase_object_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm object,
108 Eterm *ret, DbTableTree *stack_container);
109 int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root,
110 Eterm slot_term, Eterm *ret,
111 DbTableTree *stack_container,
112 CATreeRootIterator*);
113 int db_select_chunk_tree_common(Process *p, DbTable *tb,
114 Eterm tid, Eterm pattern, Sint chunk_size,
115 int reverse, Eterm *ret,
116 DbTableTree *stack_container,
117 CATreeRootIterator*);
118 int db_select_tree_common(Process *p, DbTable *tb,
119 Eterm tid, Eterm pattern, int reverse, Eterm *ret,
120 DbTableTree *stack_container,
121 CATreeRootIterator*);
122 int db_select_delete_tree_common(Process *p, DbTable *tbl,
123 Eterm tid, Eterm pattern,
124 Eterm *ret,
125 DbTreeStack* stack,
126 CATreeRootIterator* iter);
127 int db_select_continue_tree_common(Process *p,
128 DbTableCommon *tb,
129 Eterm continuation,
130 Eterm *ret,
131 DbTableTree *stack_container,
132 CATreeRootIterator* iter);
133 int db_select_delete_continue_tree_common(Process *p,
134 DbTable *tbl,
135 Eterm continuation,
136 Eterm *ret,
137 DbTreeStack* stack,
138 CATreeRootIterator* iter);
139 int db_select_count_tree_common(Process *p, DbTable *tb,
140 Eterm tid, Eterm pattern, Eterm *ret,
141 DbTableTree *stack_container,
142 CATreeRootIterator* iter);
143 int db_select_count_continue_tree_common(Process *p,
144 DbTable *tb,
145 Eterm continuation,
146 Eterm *ret,
147 DbTableTree *stack_container,
148 CATreeRootIterator* iter);
149 int db_select_replace_tree_common(Process *p, DbTable*,
150 Eterm tid, Eterm pattern, Eterm *ret,
151 DbTableTree *stack_container,
152 CATreeRootIterator* iter);
153 int db_select_replace_continue_tree_common(Process *p,
154 DbTable*,
155 Eterm continuation,
156 Eterm *ret,
157 DbTableTree *stack_container,
158 CATreeRootIterator* iter);
159 int db_take_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root,
160 Eterm key, Eterm *ret,
161 DbTreeStack *stack /* NULL if no static stack */);
162 void db_print_tree_common(fmtfn_t to, void *to_arg,
163 int show, TreeDbTerm *root, DbTable *tbl);
164 void db_foreach_offheap_tree_common(TreeDbTerm *root,
165 void (*func)(ErlOffHeap *, void *),
166 void * arg);
167 int db_lookup_dbterm_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root,
168 Eterm key, Eterm obj, DbUpdateHandle* handle,
169 DbTableTree *stack_container);
170 void db_finalize_dbterm_tree_common(int cret,
171 DbUpdateHandle *handle,
172 TreeDbTerm **root,
173 DbTableTree *stack_container);
174 void* db_eterm_to_dbterm_tree_common(int compress, int keypos, Eterm obj);
175 void* db_dbterm_list_prepend_tree_common(void* list, void* db_term);
176 void* db_dbterm_list_remove_first_tree_common(void **list);
177 int db_put_dbterm_tree_common(DbTableCommon *tb, TreeDbTerm **root, TreeDbTerm *value_to_insert,
178 int key_clash_fail, DbTableTree *stack_container);
179 void db_free_dbterm_tree_common(int compressed, void* obj);
180 Eterm db_get_dbterm_key_tree_common(DbTable* tb, void* db_term);
181 Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key);
182
183 TreeDbTerm *db_find_tree_node_common(DbTableCommon*, TreeDbTerm *root,
184 Eterm key);
185 Eterm db_binary_info_tree_common(Process*, TreeDbTerm*);
186
187 #endif /* _DB_TREE_UTIL_H */
188