source: trunk/kernel/libk/grdxt.c @ 608

Last change on this file since 608 was 603, checked in by alain, 6 years ago

Improve the FAT32 file system to support cat, rm, cp commands.

File size: 11.2 KB
Line 
1/*
2 * grdxt.c - Three-levels Generic Radix-tree implementation
3 *
4 * authors  Alain Greiner (2016)
5 *
6 * Copyright (c)  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#include <hal_kernel_types.h>
25#include <hal_special.h>
26#include <hal_remote.h>
27#include <errno.h>
28#include <printk.h>
29#include <kmem.h>
30#include <grdxt.h>
31
32/////////////////////////////////
33error_t grdxt_init( grdxt_t * rt,
34                    uint32_t  ix1_width,
35                    uint32_t  ix2_width,
36                    uint32_t  ix3_width )
37{
38    void      ** root;
39        kmem_req_t   req;
40 
41        rt->ix1_width = ix1_width;
42        rt->ix2_width = ix2_width;
43        rt->ix3_width = ix3_width;
44
45    // allocates first level array
46        req.type  = KMEM_GENERIC;
47        req.size  = sizeof(void *) << ix1_width;
48        req.flags = AF_KERNEL | AF_ZERO;
49        root = kmem_alloc( &req );
50        if( root == NULL ) return ENOMEM;
51 
52        rt->root = root;
53
54        return 0;
55
56}  // end grdxt_init()
57
58//////////////////////////////////
59void grdxt_destroy( grdxt_t * rt )
60{
61        kmem_req_t req;
62
63    uint32_t   w1 = rt->ix1_width;
64    uint32_t   w2 = rt->ix2_width;
65    uint32_t   w3 = rt->ix3_width;
66
67    void    ** ptr1 = rt->root;
68    void    ** ptr2;
69    void    ** ptr3;
70
71        uint32_t   ix1;
72        uint32_t   ix2;
73
74// check rt
75assert( (rt != NULL) , "pointer on radix tree is NULL\n" );
76
77        req.type = KMEM_GENERIC;
78
79        for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ )
80        {
81        ptr2 = ptr1[ix1];
82
83                if( ptr2 == NULL ) continue;
84
85        for( ix2=0 ; ix2 < (uint32_t)(1 << w2) ; ix2++ )
86        {
87            ptr3 = ptr2[ix2];
88
89                    if( ptr3 == NULL ) continue;
90
91            // release level 3 array
92                    req.ptr  = ptr3;
93            req.type = KMEM_GENERIC;
94            req.size = sizeof(void *) * (1 << w3);
95                    kmem_free( &req );
96        }
97
98        // release level 2 array
99                req.ptr  = ptr2;
100        req.type = KMEM_GENERIC;
101        req.size = sizeof(void *) * (1 << w2);
102                kmem_free( &req );
103    }
104
105    // release level 1 array
106        req.ptr  = ptr1;
107    req.type = KMEM_GENERIC;
108    req.size = sizeof(void *) * (1 << w1);
109        kmem_free( &req );
110
111}  // end grdxt_destroy()
112
113////////////////////////////////////
114void grdxt_display( xptr_t    rt_xp,
115                    char    * name )
116{
117        uint32_t       ix1; 
118        uint32_t       ix2;
119        uint32_t       ix3;
120
121// check rt_xp
122assert( (rt_xp != XPTR_NULL) , "pointer on radix tree is NULL\n" );
123
124    // get cluster and local pointer on remote rt descriptor
125    grdxt_t      * rt_ptr = GET_PTR( rt_xp );
126    cxy_t          rt_cxy = GET_CXY( rt_xp );
127
128    // get widths
129    uint32_t       w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
130    uint32_t       w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
131    uint32_t       w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
132
133    void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
134
135        printk("\n***** Generic Radix Tree for <%s> : %d / %d / %d\n", 
136    name, 1<<w1 , 1<<w2 , 1<<w3 );
137
138        for( ix1=0 ; ix1 < (uint32_t)(1<<w1) ; ix1++ )
139        {
140            void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
141        if( ptr2 == NULL )  continue;
142   
143        for( ix2=0 ; ix2 < (uint32_t)(1<<w2) ; ix2++ )
144        {
145                void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
146            if( ptr3 == NULL ) continue;
147
148            for( ix3=0 ; ix3 < (uint32_t)(1<<w3) ; ix3++ )
149            {
150                void * value = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );
151                if( value == NULL )  continue;
152
153                uint32_t key = (ix1<<(w2+w3)) + (ix2<<w3) + ix3;
154                printk(" - key = %x / value = %x\n", key , (intptr_t)value );
155            }
156        }
157        }
158
159} // end grdxt_display()
160
161////////////////////////////////////
162error_t grdxt_insert( grdxt_t  * rt,
163                      uint32_t   key,
164                      void     * value )
165{
166        kmem_req_t      req;
167
168    uint32_t        w1 = rt->ix1_width;
169    uint32_t        w2 = rt->ix2_width;
170    uint32_t        w3 = rt->ix3_width;
171
172// Check key value
173assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
174
175    // compute indexes
176    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
177        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
178        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
179
180    void         ** ptr1 = rt->root;                     // pointer on level 1 array
181        void         ** ptr2;                                // pointer on level 2 array
182        void         ** ptr3;                                // pointer on level 3 array
183
184    // If required, we must allocate memory for the selected level 2 array,
185    // and update the level 1 array.
186        if( ptr1[ix1] == NULL )
187        {
188        // allocate memory for level 2 array
189        req.type = KMEM_GENERIC;
190        req.size = sizeof(void *) << w2;
191        req.flags = AF_KERNEL | AF_ZERO;
192        ptr2 = kmem_alloc( &req );
193        if( ptr2 == NULL) return ENOMEM;
194
195        // update level 1 array
196        ptr1[ix1] = ptr2;
197        }
198    else    // get pointer on selected level 2 array.
199    {
200            ptr2 = ptr1[ix1];
201    }
202
203    // If required, we must allocate memory for the selected level 3 array,
204    // and update the level 2 array.
205        if( ptr2[ix2] == NULL )
206        {
207        // allocate memory for level 3 array
208        req.type = KMEM_GENERIC;
209        req.size = sizeof(void *) << w3;
210        req.flags = AF_KERNEL | AF_ZERO;
211        ptr3 = kmem_alloc( &req );
212        if( ptr3 == NULL) return ENOMEM;
213
214        //  update level 3 array
215                ptr2[ix2] = ptr3;
216        }
217    else    // get pointer on selected level 3 array.
218    {
219            ptr3 = ptr2[ix2];
220    }
221
222    // selected slot in level 3 array must be empty
223        if( ptr3[ix3] != NULL ) return EEXIST;
224
225    // register the value
226        ptr3[ix3] = value;
227        hal_fence();
228
229        return 0;
230
231}  // end grdxt_insert()
232
233///////////////////////////////////
234void * grdxt_remove( grdxt_t  * rt,
235                     uint32_t   key )
236{
237    uint32_t        w1 = rt->ix1_width;
238    uint32_t        w2 = rt->ix2_width;
239    uint32_t        w3 = rt->ix3_width;
240
241// Check key value
242assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
243
244    // compute indexes
245    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
246        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
247        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
248
249    void         ** ptr1 = rt->root;                     // pointer on level 1 array
250        void         ** ptr2;                                // pointer on level 2 array
251        void         ** ptr3;                                // pointer on level 3 array
252
253    // get ptr2
254        ptr2 = ptr1[ix1];
255        if( ptr2 == NULL ) return NULL;
256
257    // get ptr3
258        ptr3 = ptr2[ix2];
259        if( ptr3 == NULL ) return NULL;
260
261    // get value
262        void * value = ptr3[ix3];
263
264    // reset selected slot
265        ptr3[ix3] = NULL;
266        hal_fence();
267
268        return value;
269
270}  // end grdxt_remove()
271
272///////////////////////////////////
273void * grdxt_lookup( grdxt_t  * rt,
274                     uint32_t   key )
275{
276    uint32_t        w1 = rt->ix1_width;
277    uint32_t        w2 = rt->ix2_width;
278    uint32_t        w3 = rt->ix3_width;
279
280// Check key value
281assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
282
283    void         ** ptr1 = rt->root;
284    void         ** ptr2;
285    void         ** ptr3;
286
287    // compute indexes
288    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
289        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
290        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
291
292    // get ptr2
293        ptr2 = ptr1[ix1];
294        if( ptr2 == NULL ) return NULL;
295
296    // get ptr3
297        ptr3 = ptr2[ix2];
298        if( ptr3 == NULL ) return NULL;
299
300    // get value
301        void * value = ptr3[ix3];
302
303        return value;
304
305}  // end grdxt_lookup()
306
307////////////////////////////////////////////
308xptr_t grdxt_remote_lookup( xptr_t    rt_xp,
309                            uint32_t  key )
310{
311    // get cluster and local pointer on remote rt descriptor
312    grdxt_t       * rt_ptr = GET_PTR( rt_xp );
313    cxy_t           rt_cxy = GET_CXY( rt_xp );
314
315    // get widths
316    uint32_t        w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
317    uint32_t        w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
318    uint32_t        w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
319
320// Check key value
321assert( ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
322
323    // compute indexes
324    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
325        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
326        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
327
328    // get ptr1
329    void         ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
330
331    // get ptr2
332        void         ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
333        if( ptr2 == NULL ) return XPTR_NULL;
334
335    // get ptr3
336        void         ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
337        if( ptr3 == NULL ) return XPTR_NULL;
338
339    // get value
340        xptr_t      value = XPTR( rt_cxy , ptr3[ix3] );
341
342        return value;
343
344}  // end grdxt_remote_lookup()
345
346//////////////////////////////////////
347void * grdxt_get_first( grdxt_t  * rt,
348                        uint32_t   start_key,
349                        uint32_t * found_key )
350{
351    uint32_t        ix1;
352    uint32_t        ix2;
353    uint32_t        ix3;
354
355    uint32_t        w1 = rt->ix1_width;
356    uint32_t        w2 = rt->ix2_width;
357    uint32_t        w3 = rt->ix3_width;
358
359// Check key value
360assert( ((start_key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", start_key );
361
362    // compute max indexes
363    uint32_t        max1 = 1 << w1;
364    uint32_t        max2 = 1 << w2;
365    uint32_t        max3 = 1 << w3;
366
367    // compute min indexes
368    uint32_t        min1 = start_key >> (w2 + w3);           
369        uint32_t        min2 = (start_key >> w3) & ((1 << w2) -1);
370        uint32_t        min3 = start_key & ((1 << w3) - 1); 
371
372    void         ** ptr1 = rt->root;
373    void         ** ptr2;
374    void         ** ptr3;
375
376    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
377    {
378        ptr2 = ptr1[ix1];
379        if( ptr2 == NULL ) continue;
380
381        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
382        {
383            ptr3 = ptr2[ix2];
384            if( ptr3 == NULL ) continue;
385
386            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
387            {
388                if( ptr3[ix3] == NULL ) continue;
389                else                   
390                {
391                    *found_key = (ix1 << (w2+w3)) | (ix2 << w1) | ix3;
392                    return ptr3[ix3];
393                }
394            }
395        }
396    }
397
398    return NULL;
399
400}  // end grdxt_get_first()
Note: See TracBrowser for help on using the repository browser.