1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */ 2 /* 3 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana 4 * University Research and Technology 5 * Corporation. All rights reserved. 6 * Copyright (c) 2004-2005 The University of Tennessee and The University 7 * of Tennessee Research Foundation. All rights 8 * reserved. 9 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, 10 * University of Stuttgart. All rights reserved. 11 * Copyright (c) 2004-2005 The Regents of the University of California. 12 * All rights reserved. 13 * Copyright (c) 2015-2018 Los Alamos National Security, LLC. All rights 14 * reserved. 15 * $COPYRIGHT$ 16 * 17 * Additional copyrights may follow 18 * 19 * $HEADER$ 20 * 21 */ 22 23 /** @file 24 * 25 * A thread-safe interval tree derived from opal_rb_tree_t 26 */ 27 28 #ifndef OPAL_INTERVAL_TREE_H 29 #define OPAL_INTERVAL_TREE_H 30 31 #include "opal_config.h" 32 #include <stdlib.h> 33 #include "opal/constants.h" 34 #include "opal/class/opal_object.h" 35 #include "opal/class/opal_free_list.h" 36 37 BEGIN_C_DECLS 38 /* 39 * Data structures and datatypes 40 */ 41 42 /** 43 * red and black enum 44 */ 45 typedef enum {OPAL_INTERVAL_TREE_COLOR_RED, OPAL_INTERVAL_TREE_COLOR_BLACK} opal_interval_tree_nodecolor_t; 46 47 /** 48 * node data structure 49 */ 50 struct opal_interval_tree_node_t 51 { 52 opal_free_list_item_t super; /**< the parent class */ 53 opal_interval_tree_nodecolor_t color; /**< the node color */ 54 struct opal_interval_tree_node_t *parent;/**< the parent node, can be NULL */ 55 struct opal_interval_tree_node_t *left; /**< the left child - can be nill */ 56 struct opal_interval_tree_node_t *right; /**< the right child - can be nill */ 57 /** edit epoch associated with this node */ 58 uint32_t epoch; 59 /** data for this interval */ 60 void *data; 61 /** low value of this interval */ 62 uint64_t low; 63 /** high value of this interval */ 64 uint64_t high; 65 /** maximum value of all intervals in tree rooted at this node */ 66 uint64_t max; 67 }; 68 typedef struct opal_interval_tree_node_t opal_interval_tree_node_t; 69 70 /** maximum number of simultaneous readers */ 71 #define OPAL_INTERVAL_TREE_MAX_READERS 128 72 73 /** 74 * the data structure that holds all the needed information about the tree. 75 */ 76 struct opal_interval_tree_t { 77 opal_object_t super; /**< the parent class */ 78 /* this root pointer doesn't actually point to the root of the tree. 79 * rather, it points to a sentinal node who's left branch is the real 80 * root of the tree. This is done to eliminate special cases */ 81 opal_interval_tree_node_t root; /**< a pointer to the root of the tree */ 82 opal_interval_tree_node_t nill; /**< the nill sentinal node */ 83 opal_free_list_t free_list; /**< the free list to get the memory from */ 84 opal_list_t gc_list; /**< list of nodes that need to be released */ 85 uint32_t epoch; /**< current update epoch */ 86 volatile size_t tree_size; /**< the current size of the tree */ 87 volatile int32_t lock; /**< update lock */ 88 volatile int32_t reader_count; /**< current highest reader slot to check */ 89 volatile uint32_t reader_id; /**< next reader slot to check */ 90 volatile uint32_t reader_epochs[OPAL_INTERVAL_TREE_MAX_READERS]; 91 }; 92 typedef struct opal_interval_tree_t opal_interval_tree_t; 93 94 /** declare the tree node as a class */ 95 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_interval_tree_node_t); 96 /** declare the tree as a class */ 97 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_interval_tree_t); 98 99 /* Function pointers for map traversal function */ 100 /** 101 * this function is used for the opal_interval_tree_traverse function. 102 * it is passed a pointer to the value for each node and, if it returns 103 * a one, the action function is called on that node. Otherwise, the node is ignored. 104 */ 105 typedef int (*opal_interval_tree_condition_fn_t)(void *); 106 /** 107 * this function is used for the user to perform any action on the passed 108 * values. The first argument is the key and the second is the value. 109 * note that this function SHOULD NOT modify the keys, as that would 110 * mess up the tree. 111 */ 112 typedef int (*opal_interval_tree_action_fn_t)(uint64_t low, uint64_t high, void *data, void *ctx); 113 114 /* 115 * Public function protoypes 116 */ 117 118 /** 119 * the function creates a new tree 120 * 121 * @param tree a pointer to an allocated area of memory for the main 122 * tree data structure. 123 * @param comp a pointer to the function to use for comaparing 2 nodes 124 * 125 * @retval OPAL_SUCCESS if it is successful 126 * @retval OPAL_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful 127 */ 128 OPAL_DECLSPEC int opal_interval_tree_init(opal_interval_tree_t * tree); 129 130 131 /** 132 * inserts a node into the tree 133 * 134 * @param tree a pointer to the tree data structure 135 * @param key the key for the node 136 * @param value the value for the node 137 * 138 * @retval OPAL_SUCCESS 139 * @retval OPAL_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful 140 */ 141 OPAL_DECLSPEC int opal_interval_tree_insert(opal_interval_tree_t *tree, void *value, uint64_t low, uint64_t high); 142 143 /** 144 * finds a value in the tree based on the passed key using passed 145 * compare function 146 * 147 * @param tree a pointer to the tree data structure 148 * @param key a pointer to the key 149 * @param compare function 150 * 151 * @retval pointer to the value if found 152 * @retval NULL if not found 153 */ 154 OPAL_DECLSPEC void *opal_interval_tree_find_overlapping (opal_interval_tree_t *tree, uint64_t low, uint64_t high); 155 156 /** 157 * deletes a node based on its interval 158 * 159 * @param tree a pointer to the tree data structure 160 * @param low low value of interval 161 * @param high high value of interval 162 * @param data data to match (NULL for any) 163 * 164 * @retval OPAL_SUCCESS if the node is found and deleted 165 * @retval OPAL_ERR_NOT_FOUND if the node is not found 166 * 167 * This function finds and deletes an interval from the tree that exactly matches 168 * the given range. 169 */ 170 OPAL_DECLSPEC int opal_interval_tree_delete(opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data); 171 172 /** 173 * frees all the nodes on the tree 174 * 175 * @param tree a pointer to the tree data structure 176 * 177 * @retval OPAL_SUCCESS 178 */ 179 OPAL_DECLSPEC int opal_interval_tree_destroy(opal_interval_tree_t *tree); 180 181 /** 182 * traverses the entire tree, performing the cond function on each of the 183 * values and if it returns one it performs the action function on the values 184 * 185 * @param tree a pointer to the tree 186 * @param low low value of interval 187 * @param high high value of interval 188 * @param partial_ok traverse nodes that parially overlap the given range 189 * @param action a pointer to the action function 190 * @param ctx context to pass to action function 191 * 192 * @retval OPAL_SUCCESS 193 * @retval OPAL_ERROR if there is an error 194 */ 195 OPAL_DECLSPEC int opal_interval_tree_traverse (opal_interval_tree_t *tree, uint64_t low, uint64_t high, 196 bool complete, opal_interval_tree_action_fn_t action, void *ctx); 197 198 /** 199 * returns the size of the tree 200 * 201 * @param tree a pointer to the tree data structure 202 * 203 * @retval int the nuber of items on the tree 204 */ 205 OPAL_DECLSPEC size_t opal_interval_tree_size (opal_interval_tree_t *tree); 206 207 /** 208 * Diagnostic function to get the max depth of an interval tree. 209 * 210 * @param[in] tree opal interval tree pointer 211 * 212 * This is an expensive function that walks the entire tree to find the 213 * maximum depth. For a valid interval tree this depth will always be 214 * O(log(n)) where n is the number of intervals in the tree. 215 */ 216 OPAL_DECLSPEC size_t opal_interval_tree_depth (opal_interval_tree_t *tree); 217 218 /** 219 * Diagnostic function that can be used to verify that an interval tree 220 * is valid. 221 * 222 * @param[in] tree opal interval tree pointer 223 * 224 * @returns true if the tree is a valid interval tree 225 * @returns false otherwise 226 */ 227 OPAL_DECLSPEC bool opal_interval_tree_verify (opal_interval_tree_t *tree); 228 229 /** 230 * Dump a DOT representation of the interval tree 231 * 232 * @param[in] tree opal interval tree pointer 233 * @param[in] path output file path 234 * 235 * This function dumps the tree and includes: color, data value, interval, and sub-tree 236 * min and max. 237 */ 238 OPAL_DECLSPEC int opal_interval_tree_dump (opal_interval_tree_t *tree, const char *path); 239 240 END_C_DECLS 241 #endif /* OPAL_INTERVAL_TREE_H */ 242