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 /*
22  * Description: Implementation of ETS ordered_set table type with
23  *              fine-grained synchronization.
24  *
25  * Author: 	Kjell Winblad
26  *
27  * "erl_db_catree.c" contains more details about the implementation.
28  *
29  */
30 
31 #ifndef _DB_CATREE_H
32 #define _DB_CATREE_H
33 
34 struct DbTableCATreeNode;
35 
36 typedef struct {
37     Eterm term;
38     struct erl_off_heap_header* oh;
39     Uint size;
40     Eterm heap[1];
41 } DbRouteKey;
42 
43 typedef struct {
44     erts_rwmtx_t lock; /* The lock for this base node */
45     erts_atomic_t lock_statistics;
46     int is_valid; /* If this base node is still valid */
47     TreeDbTerm *root; /* The root of the sequential tree */
48     ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */
49 
50     char end_of_struct__;
51 } DbTableCATreeBaseNode;
52 
53 typedef struct {
54 #ifdef ERTS_ENABLE_LOCK_CHECK
55     Sint lc_order;
56 #endif
57     ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */
58     erts_mtx_t lock; /* Used when joining route nodes */
59     int is_valid; /* If this route node is still valid */
60     erts_atomic_t left;
61     erts_atomic_t right;
62     DbRouteKey key;
63 } DbTableCATreeRouteNode;
64 
65 typedef struct DbTableCATreeNode {
66     int is_base_node;
67     union {
68         DbTableCATreeRouteNode route;
69         DbTableCATreeBaseNode base;
70     } u;
71 } DbTableCATreeNode;
72 
73 typedef struct {
74     Uint pos;          /* Current position on stack */
75     Uint size;         /* The size of the stack array */
76     DbTableCATreeNode** array; /* The stack */
77 } CATreeNodeStack;
78 
79 typedef struct db_table_catree {
80     DbTableCommon common;
81 
82     /* CA Tree-specific fields */
83     erts_atomic_t root;         /* The tree root (DbTableCATreeNode*) */
84     Uint deletion;		/* Being deleted */
85     int is_routing_nodes_freed;
86     /* The fields below are used by delete_all_objects and
87        select_delete(DeleteAll)*/
88     Uint nr_of_deleted_items;
89     Binary* nr_of_deleted_items_wb;
90 } DbTableCATree;
91 
92 typedef struct {
93     DbTableCATree* tb;
94     Eterm next_route_key;
95     DbTableCATreeNode* locked_bnode;
96     DbTableCATreeNode* bnode_parent;
97     int bnode_level;
98     int read_only;
99     DbRouteKey* search_key;
100 } CATreeRootIterator;
101 
102 
103 void db_initialize_catree(void);
104 
105 int db_create_catree(Process *p, DbTable *tbl);
106 
107 TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator*);
108 
109 TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, CATreeRootIterator*);
110 TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, CATreeRootIterator*);
111 TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator*, int next, Eterm* keyp);
112 TreeDbTerm** catree_find_next_root(CATreeRootIterator*, Eterm* keyp);
113 TreeDbTerm** catree_find_prev_root(CATreeRootIterator*, Eterm* keyp);
114 TreeDbTerm** catree_find_first_root(CATreeRootIterator*);
115 TreeDbTerm** catree_find_last_root(CATreeRootIterator*);
116 
117 
118 #ifdef ERTS_ENABLE_LOCK_COUNT
119 void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable);
120 #endif
121 
122 void db_catree_force_split(DbTableCATree*, int on);
123 void db_catree_debug_random_split_join(DbTableCATree*, int on);
124 
125 typedef struct {
126     Uint route_nodes;
127     Uint base_nodes;
128     Uint max_depth;
129 } DbCATreeStats;
130 void db_calc_stats_catree(DbTableCATree*, DbCATreeStats*);
131 void
132 erts_db_foreach_thr_prgr_offheap_catree(void (*func)(ErlOffHeap *, void *),
133                                         void *arg);
134 
135 
136 #endif /* _DB_CATREE_H */
137