/* * grdxt.h - Three-levels Generic Radix-tree definition. * * Authors Alain Greiner (2016,2017,2018,2019,2019) * * Copyright UPMC Sorbonne Universites * * This file is part of ALMOS-MKH. * * ALMOS-MKH is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-MKH is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-MKH; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef _GRDXT_H_ #define _GRDXT_H_ #include /******************************************************************************************* * This structure defines a three levels radix-tree descriptor. * The key is split in three fields : ix1 (MSB) / ix2 / ix3 (LSB) to index the first, * second and third level arrays respectively. * The pointers on the registered items are stored in the third level arrays. * The number or bits for each field are parameters for the grdxt_init() function. * Memory for the first level array is allocated by the grdxt_init() function. * Memory for the second and third levels arrays is dynamically allocated by the * grdxt_insert() function and is only released by grdxt_destroy(). * This structure is entirely contained in one single cluster, but to allow any thread * to access it, two sets of access functions are defined: * - local threads can use access function using local pointers. * - remote threads must use the access functions using extended pointers. ****************************************************************************************** * When it is used by the mapper implementing the file cache: * - the key is the page index in file. * - the registered value is a local pointer on the page descriptor. ******************************************************************************************/ typedef struct grdxt_s { void ** root; /*! pointer on first level array of pointers */ uint32_t ix1_width; /*! number of bits for first level array index */ uint32_t ix2_width; /*! number of bits for second level array index */ uint32_t ix3_width; /*! number of bits for third level array index */ } grdxt_t; //////////////////////////////////////////////////////////////////////////////////////////// // Local access functions //////////////////////////////////////////////////////////////////////////////////////////// /******************************************************************************************* * This function initialises the radix-tree descriptor, * and allocates memory for the first level array of pointers. * It must be called by a local thread. ******************************************************************************************* * @ rt : pointer on the radix-tree descriptor. * @ ix1_width : number of bits in ix1 field * @ ix2_width : number of bits in ix2 field * @ ix3_width : number of bits in ix3 field * @ returns 0 if success / returns ENOMEM if no more memory. ******************************************************************************************/ error_t grdxt_init( grdxt_t * rt, uint32_t ix1_width, uint32_t ix2_width, uint32_t ix3_width ); /******************************************************************************************* * This function releases all memory allocated to the radix-tree infrastructure. * A warning message is printed on the kernel TXT0 if the radix tree is not empty. * It must be called by a local thread. ******************************************************************************************* * @ rt : pointer on the radix-tree descriptor. ******************************************************************************************/ void grdxt_destroy( grdxt_t * rt ); /******************************************************************************************* * This function insert a new item in the radix-tree. * It dynamically allocates memory for new second and third level arrays if required. * It must be called by a local thread. ******************************************************************************************* * @ rt : pointer on the radix-tree descriptor. * @ key : key value. * @ value : pointer on item to be registered in radix-tree. * @ returns 0 if success / returns -1 if no memory, or illegal key. ******************************************************************************************/ error_t grdxt_insert( grdxt_t * rt, uint32_t key, void * value ); /******************************************************************************************* * This function removes an item identified by its key from the radix tree, * and returns a pointer on the removed item. No memory is released. * It must be called by a local thread. ******************************************************************************************* * @ rt : pointer on the radix-tree descriptor. * @ key : key value. * @ returns pointer on removed item if success / returns NULL if failure. ******************************************************************************************/ void * grdxt_remove( grdxt_t * rt, uint32_t key ); /******************************************************************************************* * This function returns to a local client, a local pointer on the item identified * It must be called by a local thread. * by the argument, from the radix tree identified by the local pointer. ******************************************************************************************* * @ rt : local pointer on the radix-tree descriptor. * @ key : key value. * @ returns a local pointer on found item if success / returns NULL if failure. ******************************************************************************************/ void * grdxt_lookup( grdxt_t * rt, uint32_t key ); /******************************************************************************************* * This function scan all radix-tree entries in increasing key order, starting from * the key defined by the argument. It returns a pointer on the first valid * registered item, and returns in the buffer the found item key value. * It must be called by a local thread. ******************************************************************************************* * @ rt : pointer on the radix-tree descriptor. * @ start_key : key starting value for the scan. * @ found_key : [out] buffer for found key value. * @ return pointer on first valid item if found / return NULL if no item found. ******************************************************************************************/ void * grdxt_get_first( grdxt_t * rt, uint32_t start_key, uint32_t * found_key ); //////////////////////////////////////////////////////////////////////////////////////////// // Remote access functions //////////////////////////////////////////////////////////////////////////////////////////// /******************************************************************************************* * This function initialises the radix-tree descriptor, * and allocates memory for the first level array of pointers. * It can be called by any thread running in any cluster ******************************************************************************************* * @ rt_xp : extended pointer on the radix-tree descriptor. * @ ix1_width : number of bits in ix1 field * @ ix2_width : number of bits in ix2 field * @ ix3_width : number of bits in ix3 field * @ returns 0 if success / returns ENOMEM if no more memory. ******************************************************************************************/ error_t grdxt_remote_init( xptr_t rt_xp, uint32_t ix1_width, uint32_t ix2_width, uint32_t ix3_width ); /******************************************************************************************* * This function releases all memory allocated to the radix-tree infrastructure. * A warning message is printed on the kernel TXT0 if the radix tree is not empty. * It can be called by any thread running in any cluster ******************************************************************************************* * @ rt_xp : extended pointer on the radix-tree descriptor. ******************************************************************************************/ void grdxt_remote_destroy( xptr_t rt_xp ); /******************************************************************************************* * This function insert a new item in a - possibly remote - radix tree. * It dynamically allocates memory for new second and third level arrays if required. * It can be called by any thread running in any cluster ******************************************************************************************* * @ rt_xp : extended pointer on the radix-tree descriptor. * @ key : key value. * @ value : pointer on item to be registered in radix-tree. * @ returns 0 if success / returns -1 if no memory, or illegal key. ******************************************************************************************/ error_t grdxt_remote_insert( xptr_t rt_xp, uint32_t key, void * value ); /******************************************************************************************* * This function removes an item identified by its key from a - possibly remote - radix * tree, and returns a local pointer on the removed item. No memory is released. * It can be called by a thread running in any cluster ******************************************************************************************* * @ rt_xp : pointer on the radix-tree descriptor. * @ key : key value. * @ returns extended pointer on removed item if success / returns XPTR_NULL if failure. ******************************************************************************************/ xptr_t grdxt_remote_remove( xptr_t rt_xp, uint32_t key ); /******************************************************************************************* * This function returns to a - possibly remote - client, an extended pointer * on the item identified by the argument, from the radix tree identified by * the remote pointer. * It can be called by a thread running in any cluster ******************************************************************************************* * @ rt_xp : extended pointer on the radix-tree descriptor. * @ key : key value. * @ returns extended pointer on found item if success / returns XPTR_NULL if not found. ******************************************************************************************/ xptr_t grdxt_remote_lookup( xptr_t rt_xp, uint32_t key ); /******************************************************************************************* * This function scan all radix-tree entries of a - possibly remote - radix tree , * in increasing key order, starting from the key defined by the argument. * It returns an extended pointer on the first valid registered item, and returns in the * buffer the found item key value. * It can be called by a thread running in any cluster ******************************************************************************************* * @ rt_xp : extended pointer on the radix-tree descriptor. * @ start_key : key starting value for the scan. * @ found_key : [out] buffer for found key value. * @ return xptr on first valid item if found / return XPTR_NULL if no item found. ******************************************************************************************/ xptr_t grdxt_remote_get_first( xptr_t rt_xp, uint32_t start_key, uint32_t * found_key ); /******************************************************************************************* * This function displays the current content of a possibly remote radix_tree. * It can be called by a thread running in any cluster ******************************************************************************************* * @ rt : extended pointer on the radix-tree descriptor. * @ string : radix tree identifier. ******************************************************************************************/ void grdxt_remote_display( xptr_t rt_xp, char * string ); #endif /* _GRDXT_H_ */