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

Last change on this file since 625 was 623, checked in by alain, 6 years ago

Introduce three new types of vsegs (KCODE,KDATA,KDEV)
to map the kernel vsegs in the process VSL and GPT.
This now used by both the TSAR and the I86 architectures.
File size: 8.0 KB
Line 
1/*
2 * grdxt.h - Three-levels Generic Radix-tree interface
3 *
4 * Authors  Alain Greiner (2016)
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.