blob: 510a9e81d35a32d0e115b40222102decd49acd62 (
plain) (
blame)
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
|
/*
* %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 */
#ifdef ERTS_ENABLE_LOCK_CHECK
DbRouteKey lc_key;
#endif
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;
} DbTableCATree;
typedef struct {
DbTableCATree* tb;
Eterm next_route_key;
DbTableCATreeBaseNode* locked_bnode;
int read_only;
} 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);
TreeDbTerm** catree_find_next_root(CATreeRootIterator*);
TreeDbTerm** catree_find_prev_root(CATreeRootIterator*);
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
#endif /* _DB_CATREE_H */
|