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