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

Last change on this file since 633 was 626, checked in by alain, 6 years ago

This version has been tested on the sort multithreaded application
for TSAR_IOB architectures ranging from 1 to 8 clusters.
It fixes three bigs bugs:
1) the dev_ioc device API has been modified: the dev_ioc_sync_read()
and dev_ioc_sync_write() function use now extended pointers on the
kernel buffer to access a mapper stored in any cluster.
2) the hal_uspace API has been modified: the hal_copy_to_uspace()
and hal_copy_from_uspace() functions use now a (cxy,ptr) couple
to identify the target buffer (equivalent to an extended pointer.
3) an implementation bug has been fixed in the assembly code contained
in the hal_copy_to_uspace() and hal_copy_from_uspace() functions.
File size: 8.0 KB
Line 
1/*
2 * grdxt.h - Three-levels Generic Radix-tree definition.
3 *
4 * Authors  Alain Greiner (2016,2017,2018,2019)
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
27#include <hal_kernel_types.h>
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().
38 * - This structure is entirely contained in one single cluster.
39 * - All modifications (insert / remove) must be done by a thread running in local cluster.
40 * - Lookup can be done by a thread running in any cluster (local or remote).
41 ******************************************************************************************
42 * When it is used by the mapper implementing the file cache:
43 * - the key is the page index in file.
44 * - the registered value is a local pointer on the page descriptor.
45 ******************************************************************************************/
46
47typedef struct grdxt_s
48{
49        void          ** root;           /*! pointer on first level array of pointers         */
50        uint32_t         ix1_width;      /*! number of bits for first level array index       */
51        uint32_t         ix2_width;      /*! number of bits for second level array index      */
52    uint32_t         ix3_width;      /*! number of bits for third level array index       */
53}
54grdxt_t;
55
56/*******************************************************************************************
57 * This function initialises the radix-tree descriptor,
58 * and allocates memory for the first level array of pointers.
59 *******************************************************************************************
60 * @ rt        : pointer on the radix-tree descriptor.
61 * @ ix1_width : number of bits in ix1 field
62 * @ ix2_width : number of bits in ix2 field
63 * @ ix3_width : number of bits in ix3 field
64 * @ returns 0 if success / returns ENOMEM if no more memory.     
65 ******************************************************************************************/
66error_t grdxt_init( grdxt_t  * rt,
67                    uint32_t   ix1_width,
68                    uint32_t   ix2_width,
69                    uint32_t   ix3_width );
70
71/*******************************************************************************************
72 * This function releases all memory allocated to the radix-tree infrastructure.
73 * The radix-tree is supposed to be empty, but this is NOT checked by this function.
74 *******************************************************************************************
75 * @ rt      : pointer on the radix-tree descriptor.
76 ******************************************************************************************/
77void grdxt_destroy( grdxt_t * rt );
78
79/*******************************************************************************************
80 * This function insert a new item in the radix-tree.
81 * It dynamically allocates memory for new second and third level arrays if required.
82 *******************************************************************************************
83 * @ rt      : pointer on the radix-tree descriptor.
84 * @ key     : key value.
85 * @ value   : pointer on item to be registered in radix-tree.
86 * @ returns 0 if success / returns ENOMEM if no memory, or EINVAL if illegal key.
87 ******************************************************************************************/
88error_t grdxt_insert( grdxt_t  * rt,
89                      uint32_t   key,
90                      void     * value );
91
92/*******************************************************************************************
93 * This function removes an item identified by its key, and returns a pointer
94 * on the removed item. No memory is released.
95 *******************************************************************************************
96 * @ rt      : pointer on the radix-tree descriptor.
97 * @ key     : key value.
98 * @ returns pointer on removed item if success / returns NULL if failure.
99 ******************************************************************************************/
100void * grdxt_remove( grdxt_t  * rt,
101                     uint32_t   key );
102
103/*******************************************************************************************
104 * This function returns to a local client, a local pointer on the item identified
105 * by the <key> argument, from the radix tree identified by the <rt> local pointer.
106 *******************************************************************************************
107 * @ rt      : local pointer on the radix-tree descriptor.
108 * @ key     : key value.
109 * @ returns a local pointer on found item if success / returns NULL if failure.
110 ******************************************************************************************/
111void * grdxt_lookup( grdxt_t  * rt, 
112                     uint32_t   key );
113
114/*******************************************************************************************
115 * This function returns to a - possibly remote - remote client, an extended pointer
116 * on the item identified by the <key> argument, from the radix tree identified by
117 * the <rt_xp> remote pointer.
118 *******************************************************************************************
119 * @ rt_xp   : extended pointer on the radix-tree descriptor.
120 * @ key     : key value.
121 * @ returns an extended pointer on found item if success / returns XPTR_NULL if failure.
122 ******************************************************************************************/
123xptr_t grdxt_remote_lookup( xptr_t     rt_xp, 
124                            uint32_t   key );
125
126/*******************************************************************************************
127 * This function scan all radix-tree entries in increasing key order, starting from
128 * the value defined by the <key> argument, and return a pointer on the first valid
129 * registered item, and the found item key value.
130 *******************************************************************************************
131 * @ rt         : pointer on the radix-tree descriptor.
132 * @ start_key  : key starting value for the scan.
133 * @ found_key  : [out] buffer for found key value.
134 * @ return pointer on first valid item if found / return NULL if not found.
135 ******************************************************************************************/
136void * grdxt_get_first( grdxt_t  * rt,
137                        uint32_t   start_key,
138                        uint32_t * found_key );
139
140/*******************************************************************************************
141 * This function displays the current content of a possibly remote radix_tree.
142 *******************************************************************************************
143 * @ rt      : extended pointer on the radix-tree descriptor.
144 * @ string  : radix tree identifier.
145 ******************************************************************************************/
146void grdxt_display( xptr_t    rt_xp,
147                    char    * string );
148
149
150#endif  /* _GRDXT_H_ */
151
Note: See TracBrowser for help on using the repository browser.