source: trunk/kernel/libk/grdxt.h @ 636

/*
 * grdxt.h - Three-levels Generic Radix-tree definition.
 * 
 * Authors  Alain Greiner (2016,2017,2018,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 <hal_kernel_types.h>

/*******************************************************************************************
 * 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,
 * It must be called by a local thread.
 * and allocates memory for the first level array of pointers.
 *******************************************************************************************
 * @ 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.
 * It must be called by a local thread.
 * A warning message is printed on the kernel TXT0 if the radix tree is not empty.
 *******************************************************************************************
 * @ rt      : pointer on the radix-tree descriptor.
 ******************************************************************************************/
void grdxt_destroy( grdxt_t * rt );

/*******************************************************************************************
 * This function insert a new item in the radix-tree.
 * It must be called by a local thread.
 * It dynamically allocates memory for new second and third level arrays if required.
 *******************************************************************************************
 * @ 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,
 * It must be called by a local thread.
 * and returns a pointer on the removed item. No memory is released.
 *******************************************************************************************
 * @ 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 <key> argument, from the radix tree identified by the <rt> 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
 * It must be called by a local thread.
 * the value defined by the <key> argument, and return a pointer on the first valid
 * registered item, and the found item key value.
 *******************************************************************************************
 * @ 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 not found.
 ******************************************************************************************/
void * grdxt_get_first( grdxt_t  * rt,
                        uint32_t   start_key,
                        uint32_t * found_key );

////////////////////////////////////////////////////////////////////////////////////////////
//                       Remote access functions
////////////////////////////////////////////////////////////////////////////////////////////

/*******************************************************************************************
 * 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.
 *******************************************************************************************
 * @ 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.
 *******************************************************************************************
 * @ rt_xp   : pointer on the radix-tree descriptor.
 * @ key     : key value.
 * @ returns local pointer on removed item if success / returns NULL if failure.
 ******************************************************************************************/
void * 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 <key> argument, from the radix tree identified by
 * the <rt_xp> remote pointer.
 *******************************************************************************************
 * @ rt_xp   : extended pointer on the radix-tree descriptor.
 * @ key     : key value.
 * @ returns an extended pointer on found item if success / returns XPTR_NULL if failure.
 ******************************************************************************************/
xptr_t grdxt_remote_lookup( xptr_t     rt_xp, 
                            uint32_t   key );

/*******************************************************************************************
 * This function displays the current content of a possibly remote radix_tree.
 *******************************************************************************************
 * @ 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_ */