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