[1] | 1 | /* |
---|
[626] | 2 | * grdxt.h - Three-levels Generic Radix-tree definition. |
---|
[1] | 3 | * |
---|
[657] | 4 | * Authors Alain Greiner (2016,2017,2018,2019,2019) |
---|
[1] | 5 | * |
---|
| 6 | * Copyright UPMC Sorbonne Universites |
---|
| 7 | * |
---|
| 8 | * This file is part of ALMOS-MKH. |
---|
| 9 | * |
---|
| 10 | * ALMOS-MKH is free software; you can redistribute it and/or modify it |
---|
| 11 | * under the terms of the GNU General Public License as published by |
---|
| 12 | * the Free Software Foundation; version 2.0 of the License. |
---|
| 13 | * |
---|
| 14 | * ALMOS-MKH is distributed in the hope that it will be useful, but |
---|
| 15 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
| 17 | * General Public License for more details. |
---|
| 18 | * |
---|
| 19 | * You should have received a copy of the GNU General Public License |
---|
| 20 | * along with ALMOS-MKH; if not, write to the Free Software Foundation, |
---|
| 21 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
---|
| 22 | */ |
---|
| 23 | |
---|
| 24 | #ifndef _GRDXT_H_ |
---|
| 25 | #define _GRDXT_H_ |
---|
| 26 | |
---|
[457] | 27 | #include <hal_kernel_types.h> |
---|
[1] | 28 | |
---|
| 29 | /******************************************************************************************* |
---|
| 30 | * This structure defines a three levels radix-tree descriptor. |
---|
| 31 | * The key is split in three fields : ix1 (MSB) / ix2 / ix3 (LSB) to index the first, |
---|
| 32 | * second and third level arrays respectively. |
---|
| 33 | * The pointers on the registered items are stored in the third level arrays. |
---|
| 34 | * The number or bits for each field are parameters for the grdxt_init() function. |
---|
| 35 | * Memory for the first level array is allocated by the grdxt_init() function. |
---|
| 36 | * Memory for the second and third levels arrays is dynamically allocated by the |
---|
| 37 | * grdxt_insert() function and is only released by grdxt_destroy(). |
---|
[635] | 38 | * This structure is entirely contained in one single cluster, but to allow any thread |
---|
| 39 | * to access it, two sets of access functions are defined: |
---|
| 40 | * - local threads can use access function using local pointers. |
---|
| 41 | * - remote threads must use the access functions using extended pointers. |
---|
[603] | 42 | ****************************************************************************************** |
---|
[610] | 43 | * When it is used by the mapper implementing the file cache: |
---|
[603] | 44 | * - the key is the page index in file. |
---|
| 45 | * - the registered value is a local pointer on the page descriptor. |
---|
[1] | 46 | ******************************************************************************************/ |
---|
| 47 | |
---|
| 48 | typedef struct grdxt_s |
---|
| 49 | { |
---|
| 50 | void ** root; /*! pointer on first level array of pointers */ |
---|
| 51 | uint32_t ix1_width; /*! number of bits for first level array index */ |
---|
| 52 | uint32_t ix2_width; /*! number of bits for second level array index */ |
---|
| 53 | uint32_t ix3_width; /*! number of bits for third level array index */ |
---|
| 54 | } |
---|
| 55 | grdxt_t; |
---|
| 56 | |
---|
[635] | 57 | //////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 58 | // Local access functions |
---|
| 59 | //////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 60 | |
---|
[1] | 61 | /******************************************************************************************* |
---|
| 62 | * This function initialises the radix-tree descriptor, |
---|
[656] | 63 | * and allocates memory for the first level array of pointers. |
---|
[635] | 64 | * It must be called by a local thread. |
---|
[1] | 65 | ******************************************************************************************* |
---|
| 66 | * @ rt : pointer on the radix-tree descriptor. |
---|
| 67 | * @ ix1_width : number of bits in ix1 field |
---|
| 68 | * @ ix2_width : number of bits in ix2 field |
---|
| 69 | * @ ix3_width : number of bits in ix3 field |
---|
| 70 | * @ returns 0 if success / returns ENOMEM if no more memory. |
---|
| 71 | ******************************************************************************************/ |
---|
| 72 | error_t grdxt_init( grdxt_t * rt, |
---|
| 73 | uint32_t ix1_width, |
---|
| 74 | uint32_t ix2_width, |
---|
| 75 | uint32_t ix3_width ); |
---|
| 76 | |
---|
| 77 | /******************************************************************************************* |
---|
| 78 | * This function releases all memory allocated to the radix-tree infrastructure. |
---|
[656] | 79 | * A warning message is printed on the kernel TXT0 if the radix tree is not empty. |
---|
[635] | 80 | * It must be called by a local thread. |
---|
[1] | 81 | ******************************************************************************************* |
---|
| 82 | * @ rt : pointer on the radix-tree descriptor. |
---|
| 83 | ******************************************************************************************/ |
---|
| 84 | void grdxt_destroy( grdxt_t * rt ); |
---|
| 85 | |
---|
| 86 | /******************************************************************************************* |
---|
| 87 | * This function insert a new item in the radix-tree. |
---|
[656] | 88 | * It dynamically allocates memory for new second and third level arrays if required. |
---|
[635] | 89 | * It must be called by a local thread. |
---|
[1] | 90 | ******************************************************************************************* |
---|
| 91 | * @ rt : pointer on the radix-tree descriptor. |
---|
| 92 | * @ key : key value. |
---|
| 93 | * @ value : pointer on item to be registered in radix-tree. |
---|
[635] | 94 | * @ returns 0 if success / returns -1 if no memory, or illegal key. |
---|
[1] | 95 | ******************************************************************************************/ |
---|
| 96 | error_t grdxt_insert( grdxt_t * rt, |
---|
| 97 | uint32_t key, |
---|
| 98 | void * value ); |
---|
| 99 | |
---|
| 100 | /******************************************************************************************* |
---|
[635] | 101 | * This function removes an item identified by its key from the radix tree, |
---|
[656] | 102 | * and returns a pointer on the removed item. No memory is released. |
---|
[635] | 103 | * It must be called by a local thread. |
---|
[1] | 104 | ******************************************************************************************* |
---|
| 105 | * @ rt : pointer on the radix-tree descriptor. |
---|
| 106 | * @ key : key value. |
---|
| 107 | * @ returns pointer on removed item if success / returns NULL if failure. |
---|
| 108 | ******************************************************************************************/ |
---|
| 109 | void * grdxt_remove( grdxt_t * rt, |
---|
| 110 | uint32_t key ); |
---|
| 111 | |
---|
| 112 | /******************************************************************************************* |
---|
[603] | 113 | * This function returns to a local client, a local pointer on the item identified |
---|
[635] | 114 | * It must be called by a local thread. |
---|
[603] | 115 | * by the <key> argument, from the radix tree identified by the <rt> local pointer. |
---|
[1] | 116 | ******************************************************************************************* |
---|
[603] | 117 | * @ rt : local pointer on the radix-tree descriptor. |
---|
[1] | 118 | * @ key : key value. |
---|
[603] | 119 | * @ returns a local pointer on found item if success / returns NULL if failure. |
---|
[1] | 120 | ******************************************************************************************/ |
---|
| 121 | void * grdxt_lookup( grdxt_t * rt, |
---|
| 122 | uint32_t key ); |
---|
| 123 | |
---|
| 124 | /******************************************************************************************* |
---|
| 125 | * This function scan all radix-tree entries in increasing key order, starting from |
---|
[657] | 126 | * the key defined by the <start_key> argument. It returns a pointer on the first valid |
---|
| 127 | * registered item, and returns in the <found_key> buffer the found item key value. |
---|
[635] | 128 | * It must be called by a local thread. |
---|
[1] | 129 | ******************************************************************************************* |
---|
| 130 | * @ rt : pointer on the radix-tree descriptor. |
---|
| 131 | * @ start_key : key starting value for the scan. |
---|
| 132 | * @ found_key : [out] buffer for found key value. |
---|
[656] | 133 | * @ return pointer on first valid item if found / return NULL if no item found. |
---|
[1] | 134 | ******************************************************************************************/ |
---|
| 135 | void * grdxt_get_first( grdxt_t * rt, |
---|
| 136 | uint32_t start_key, |
---|
| 137 | uint32_t * found_key ); |
---|
| 138 | |
---|
[635] | 139 | //////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 140 | // Remote access functions |
---|
| 141 | //////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 142 | |
---|
[1] | 143 | /******************************************************************************************* |
---|
[657] | 144 | * This function initialises the radix-tree descriptor, |
---|
| 145 | * and allocates memory for the first level array of pointers. |
---|
| 146 | * It can be called by any thread running in any cluster |
---|
| 147 | ******************************************************************************************* |
---|
| 148 | * @ rt_xp : extended pointer on the radix-tree descriptor. |
---|
| 149 | * @ ix1_width : number of bits in ix1 field |
---|
| 150 | * @ ix2_width : number of bits in ix2 field |
---|
| 151 | * @ ix3_width : number of bits in ix3 field |
---|
| 152 | * @ returns 0 if success / returns ENOMEM if no more memory. |
---|
| 153 | ******************************************************************************************/ |
---|
| 154 | error_t grdxt_remote_init( xptr_t rt_xp, |
---|
| 155 | uint32_t ix1_width, |
---|
| 156 | uint32_t ix2_width, |
---|
| 157 | uint32_t ix3_width ); |
---|
| 158 | |
---|
| 159 | /******************************************************************************************* |
---|
| 160 | * This function releases all memory allocated to the radix-tree infrastructure. |
---|
| 161 | * A warning message is printed on the kernel TXT0 if the radix tree is not empty. |
---|
| 162 | * It can be called by any thread running in any cluster |
---|
| 163 | ******************************************************************************************* |
---|
| 164 | * @ rt_xp : extended pointer on the radix-tree descriptor. |
---|
| 165 | ******************************************************************************************/ |
---|
| 166 | void grdxt_remote_destroy( xptr_t rt_xp ); |
---|
| 167 | |
---|
| 168 | /******************************************************************************************* |
---|
[635] | 169 | * This function insert a new item in a - possibly remote - radix tree. |
---|
| 170 | * It dynamically allocates memory for new second and third level arrays if required. |
---|
[657] | 171 | * It can be called by any thread running in any cluster |
---|
[635] | 172 | ******************************************************************************************* |
---|
| 173 | * @ rt_xp : extended pointer on the radix-tree descriptor. |
---|
| 174 | * @ key : key value. |
---|
| 175 | * @ value : pointer on item to be registered in radix-tree. |
---|
| 176 | * @ returns 0 if success / returns -1 if no memory, or illegal key. |
---|
| 177 | ******************************************************************************************/ |
---|
| 178 | error_t grdxt_remote_insert( xptr_t rt_xp, |
---|
| 179 | uint32_t key, |
---|
| 180 | void * value ); |
---|
| 181 | |
---|
| 182 | /******************************************************************************************* |
---|
| 183 | * This function removes an item identified by its key from a - possibly remote - radix |
---|
| 184 | * tree, and returns a local pointer on the removed item. No memory is released. |
---|
[657] | 185 | * It can be called by a thread running in any cluster |
---|
[635] | 186 | ******************************************************************************************* |
---|
| 187 | * @ rt_xp : pointer on the radix-tree descriptor. |
---|
| 188 | * @ key : key value. |
---|
[657] | 189 | * @ returns extended pointer on removed item if success / returns XPTR_NULL if failure. |
---|
[635] | 190 | ******************************************************************************************/ |
---|
[657] | 191 | xptr_t grdxt_remote_remove( xptr_t rt_xp, |
---|
[635] | 192 | uint32_t key ); |
---|
| 193 | |
---|
| 194 | /******************************************************************************************* |
---|
| 195 | * This function returns to a - possibly remote - client, an extended pointer |
---|
| 196 | * on the item identified by the <key> argument, from the radix tree identified by |
---|
| 197 | * the <rt_xp> remote pointer. |
---|
[657] | 198 | * It can be called by a thread running in any cluster |
---|
[635] | 199 | ******************************************************************************************* |
---|
| 200 | * @ rt_xp : extended pointer on the radix-tree descriptor. |
---|
| 201 | * @ key : key value. |
---|
[657] | 202 | * @ returns extended pointer on found item if success / returns XPTR_NULL if not found. |
---|
[635] | 203 | ******************************************************************************************/ |
---|
| 204 | xptr_t grdxt_remote_lookup( xptr_t rt_xp, |
---|
| 205 | uint32_t key ); |
---|
| 206 | |
---|
| 207 | /******************************************************************************************* |
---|
[657] | 208 | * This function scan all radix-tree entries of a - possibly remote - radix tree <rt_xp>, |
---|
| 209 | * in increasing key order, starting from the key defined by the <start_key> argument. |
---|
| 210 | * It returns an extended pointer on the first valid registered item, and returns in the |
---|
| 211 | * <found_key> buffer the found item key value. |
---|
| 212 | * It can be called by a thread running in any cluster |
---|
| 213 | ******************************************************************************************* |
---|
| 214 | * @ rt_xp : extended pointer on the radix-tree descriptor. |
---|
| 215 | * @ start_key : key starting value for the scan. |
---|
| 216 | * @ found_key : [out] buffer for found key value. |
---|
| 217 | * @ return xptr on first valid item if found / return XPTR_NULL if no item found. |
---|
| 218 | ******************************************************************************************/ |
---|
| 219 | xptr_t grdxt_remote_get_first( xptr_t rt_xp, |
---|
| 220 | uint32_t start_key, |
---|
| 221 | uint32_t * found_key ); |
---|
| 222 | |
---|
| 223 | /******************************************************************************************* |
---|
[603] | 224 | * This function displays the current content of a possibly remote radix_tree. |
---|
[657] | 225 | * It can be called by a thread running in any cluster |
---|
[1] | 226 | ******************************************************************************************* |
---|
[603] | 227 | * @ rt : extended pointer on the radix-tree descriptor. |
---|
[406] | 228 | * @ string : radix tree identifier. |
---|
[1] | 229 | ******************************************************************************************/ |
---|
[635] | 230 | void grdxt_remote_display( xptr_t rt_xp, |
---|
| 231 | char * string ); |
---|
[1] | 232 | |
---|
| 233 | #endif /* _GRDXT_H_ */ |
---|
| 234 | |
---|