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

Last change on this file since 674 was 671, checked in by alain, 4 years ago

Cosmetic.
File size: 13.0 KB
Line 
1/*
2 * grdxt.h - Three-levels Generic Radix-tree definition.
3 *
4 * Authors  Alain Greiner (2016,2017,2018,2019,2019,2020)
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, 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.
42 ******************************************************************************************
43 * When it is used by the mapper implementing the file cache:
44 * - the key is the page index in file.
45 * - the registered value is a local pointer on the page descriptor.
46 ******************************************************************************************/
47
48typedef 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}
55grdxt_t;
56
57////////////////////////////////////////////////////////////////////////////////////////////
58//                       Local access functions
59////////////////////////////////////////////////////////////////////////////////////////////
60
61/*******************************************************************************************
62 * This function initialises the radix-tree descriptor,
63 * and allocates memory for the first level array of pointers.
64 * It must be called by a local thread.
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 ******************************************************************************************/
72error_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.
79 * A warning message is printed on the kernel TXT0 if the radix tree is not empty.
80 * It must be called by a local thread.
81 *******************************************************************************************
82 * @ rt      : pointer on the radix-tree descriptor.
83 ******************************************************************************************/
84void grdxt_destroy( grdxt_t * rt );
85
86/*******************************************************************************************
87 * This function insert a new item in the radix-tree.
88 * It dynamically allocates memory for new second and third level arrays if required.
89 * It must be called by a local thread.
90 *******************************************************************************************
91 * @ rt      : pointer on the radix-tree descriptor.
92 * @ key     : key value.
93 * @ value   : pointer on item to be registered in radix-tree.
94 * @ returns 0 if success / returns -1 if no memory, or illegal key.
95 ******************************************************************************************/
96error_t grdxt_insert( grdxt_t  * rt,
97                      uint32_t   key,
98                      void     * value );
99
100/*******************************************************************************************
101 * This function removes an item identified by its key from the radix tree,
102 * and returns a pointer on the removed item. No memory is released.
103 * It must be called by a local thread.
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 ******************************************************************************************/
109void * grdxt_remove( grdxt_t  * rt,
110                     uint32_t   key );
111
112/*******************************************************************************************
113 * This function returns to a local client, a local pointer on the item identified
114 * It must be called by a local thread.
115 * by the <key> argument, from the radix tree identified by the <rt> local pointer.
116 *******************************************************************************************
117 * @ rt      : local pointer on the radix-tree descriptor.
118 * @ key     : key value.
119 * @ returns a local pointer on found item if success / returns NULL if failure.
120 ******************************************************************************************/
121void * 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
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.
128 * It must be called by a local thread.
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.
133 * @ return pointer on first valid item if found / return NULL if no item found.
134 ******************************************************************************************/
135void * grdxt_get_first( grdxt_t  * rt,
136                        uint32_t   start_key,
137                        uint32_t * found_key );
138
139////////////////////////////////////////////////////////////////////////////////////////////
140//                       Remote access functions
141////////////////////////////////////////////////////////////////////////////////////////////
142
143/*******************************************************************************************
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 ******************************************************************************************/
154error_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 ******************************************************************************************/
166void grdxt_remote_destroy( xptr_t  rt_xp );
167
168/*******************************************************************************************
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.
171 * It can be called by any thread running in any cluster
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 ******************************************************************************************/
178error_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.
185 * It can be called by a thread running in any cluster
186 *******************************************************************************************
187 * @ rt_xp   : pointer on the radix-tree descriptor.
188 * @ key     : key value.
189 * @ returns extended pointer on removed item if success / returns XPTR_NULL if failure.
190 ******************************************************************************************/
191xptr_t grdxt_remote_remove( xptr_t    rt_xp,
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.
198 * It can be called by a thread running in any cluster
199 *******************************************************************************************
200 * @ rt_xp   : extended pointer on the radix-tree descriptor.
201 * @ key     : key value.
202 * @ returns extended pointer on found item if success / returns XPTR_NULL if not found.
203 ******************************************************************************************/
204xptr_t grdxt_remote_lookup( xptr_t     rt_xp, 
205                            uint32_t   key );
206
207/*******************************************************************************************
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 ******************************************************************************************/
219xptr_t grdxt_remote_get_first( xptr_t     rt_xp,
220                               uint32_t   start_key,
221                               uint32_t * found_key );
222
223/*******************************************************************************************
224 * This function displays the current content of a possibly remote radix_tree.
225 * It can be called by a thread running in any cluster
226 *******************************************************************************************
227 * @ rt      : extended pointer on the radix-tree descriptor.
228 * @ string  : radix tree identifier.
229 ******************************************************************************************/
230void grdxt_remote_display( xptr_t    rt_xp,
231                           char    * string );
232
233#endif  /* _GRDXT_H_ */
234
Note: See TracBrowser for help on using the repository browser.