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

Last change on this file since 458 was 457, checked in by alain, 6 years ago

This version modifies the exec syscall and fixes a large number of small bugs.
The version number has been updated (0.1)

File size: 9.5 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 <errno.h>
27#include <printk.h>
28#include <vseg.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
57//////////////////////////////////
58void grdxt_destroy( grdxt_t * rt )
59{
60        kmem_req_t req;
61
62    uint32_t   w1 = rt->ix1_width;
63    uint32_t   w2 = rt->ix2_width;
64    uint32_t   w3 = rt->ix3_width;
65
66    void    ** ptr1 = rt->root;
67    void    ** ptr2;
68    void    ** ptr3;
69
70        uint32_t   ix1;
71        uint32_t   ix2;
72
73        req.type = KMEM_GENERIC;
74
75        for( ix1=0 ; ix1 < (1 << w1) ; ix1++ )
76        {
77        ptr2 = ptr1[ix1];
78
79                if( ptr2 == NULL ) continue;
80
81        for( ix2=0 ; ix2 < (1 << w2) ; ix2++ )
82        {
83            ptr3 = ptr2[ix2];
84
85                    if( ptr3 == NULL ) continue;
86
87            // release level 3 array
88                    req.ptr  = ptr3;
89            req.type = KMEM_GENERIC;
90            req.size = sizeof(void *) * (1 << w3);
91                    kmem_free( &req );
92        }
93
94        // release level 2 array
95                req.ptr  = ptr2;
96        req.type = KMEM_GENERIC;
97        req.size = sizeof(void *) * (1 << w2);
98                kmem_free( &req );
99    }
100
101    // release level 1 array
102        req.ptr  = ptr1;
103    req.type = KMEM_GENERIC;
104    req.size = sizeof(void *) * (1 << w1);
105        kmem_free( &req );
106
107}  // end grdxt_destroy()
108
109///////////////////////////////
110void grdxt_print( grdxt_t * rt,
111                  char    * name )
112{
113        uint32_t        ix1; 
114        uint32_t        ix2;
115        uint32_t        ix3;
116
117    uint32_t        w1 = rt->ix1_width;
118    uint32_t        w2 = rt->ix2_width;
119    uint32_t        w3 = rt->ix3_width;
120
121    void         ** ptr1 = rt->root;
122    void         ** ptr2;
123    void         ** ptr3;
124
125    intptr_t        key; 
126    intptr_t        value;
127
128        printk("\n***** Generic Radix tree %s : n1 = %d / n2 = %d / n3 = %d\n\n", 
129           name, 1<<w1 , 1<<w2 , 1<<w3 );
130
131        for( ix1=0 ; ix1 < (1<<w1) ; ix1++ )
132        {
133        ptr2 = ptr1[ix1];
134        if( ptr2 == NULL )  continue;
135   
136        for( ix2=0 ; ix2 < (1<<w2) ; ix2++ )
137        {
138            ptr3 = ptr2[ix2];
139            if( ptr3 == NULL ) continue;
140
141            for( ix3=0 ; ix3 < (1<<w3) ; ix3++ )
142            {
143                value = (intptr_t)ptr3[ix3];
144                if( value == 0 )  continue;
145
146                key = (ix1<<(w2+w3)) + (ix2<<w3) + ix3;
147                printk(" - key = %x / value = %x\n", key , value );
148            }
149        }
150        }
151} // end grdxt_print()
152
153////////////////////////////////////
154error_t grdxt_insert( grdxt_t  * rt,
155                      uint32_t   key,
156                      void     * value )
157{
158        kmem_req_t      req;
159
160    uint32_t        w1 = rt->ix1_width;
161    uint32_t        w2 = rt->ix2_width;
162    uint32_t        w3 = rt->ix3_width;
163
164    // Check key
165    if( (key >> (w1 + w2 + w3)) != 0 )
166    {
167        assert( false , __FUNCTION__ ,
168        "key value %x exceed (%d + %d + %d) bits", key , w1 , w2 , w3 );
169    }
170
171    // compute indexes
172    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
173        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
174        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
175
176    void         ** ptr1 = rt->root;                     // pointer on level 1 array
177        void         ** ptr2;                                // pointer on level 2 array
178        void         ** ptr3;                                // pointer on level 3 array
179
180    // If required, we must allocate memory for the selected level 2 array,
181    // and atomically update the level 1 array.
182        if( ptr1[ix1] == NULL )
183        {
184        // allocate memory for level 2 array
185        req.type = KMEM_GENERIC;
186        req.size = sizeof(void *) << w2;
187        req.flags = AF_KERNEL | AF_ZERO;
188        ptr2 = kmem_alloc( &req );
189        if( ptr2 == NULL) return ENOMEM;
190
191        // update level 1 array
192        ptr1[ix1] = ptr2;
193        }
194    else    // get pointer on selected level 2 array.
195    {
196            ptr2 = ptr1[ix1];
197    }
198
199    // If required, we must allocate memory for the selected level 3 array,
200    // and atomically update the level 2 array.
201        if( ptr2[ix2] == NULL )
202        {
203        // allocate memory for level 3 array
204        req.type = KMEM_GENERIC;
205        req.size = sizeof(void *) << w3;
206        req.flags = AF_KERNEL | AF_ZERO;
207        ptr3 = kmem_alloc( &req );
208        if( ptr3 == NULL) return ENOMEM;
209
210        //  update level 3 array
211                ptr2[ix2] = ptr3;
212        }
213    else    // get pointer on selected level 3 array.
214    {
215            ptr3 = ptr2[ix2];
216    }
217
218    // selected slot in level 3 array must be empty
219        if( ptr3[ix3] != NULL ) return EEXIST;
220
221    // register the value
222        ptr3[ix3] = value;
223        hal_fence();
224
225        return 0;
226}
227
228///////////////////////////////////
229void * grdxt_remove( grdxt_t  * rt,
230                     uint32_t   key )
231{
232    uint32_t        w1 = rt->ix1_width;
233    uint32_t        w2 = rt->ix2_width;
234    uint32_t        w3 = rt->ix3_width;
235
236    // Check key
237    if( (key >> (w1 + w2 + w3)) != 0 )
238    {
239        assert( false , __FUNCTION__ ,
240        "key value %x exceed (%d + %d + %d) bits", key , w1 , w2 , w3 );
241    }
242
243    // compute indexes
244    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
245        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
246        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
247
248    void         ** ptr1 = rt->root;                     // pointer on level 1 array
249        void         ** ptr2;                                // pointer on level 2 array
250        void         ** ptr3;                                // pointer on level 3 array
251
252    // get ptr2
253        ptr2 = ptr1[ix1];
254        if( ptr2 == NULL ) return NULL;
255
256    // get ptr3
257        ptr3 = ptr2[ix2];
258        if( ptr3 == NULL ) return NULL;
259
260    // get value
261        void * value = ptr3[ix3];
262
263    // reset selected slot
264        ptr3[ix3] = NULL;
265        hal_fence();
266
267        return value;
268}
269
270///////////////////////////////////
271void * grdxt_lookup( grdxt_t  * rt,
272                     uint32_t   key )
273{
274    uint32_t        w1 = rt->ix1_width;
275    uint32_t        w2 = rt->ix2_width;
276    uint32_t        w3 = rt->ix3_width;
277
278    // Check key
279    if( (key >> (w1 + w2 + w3)) != 0 )
280    {
281        assert( false , __FUNCTION__ ,
282        "key value %x exceed (%d + %d + %d) bits", key , w1 , w2 , w3 );
283    }
284
285    void         ** ptr1 = rt->root;
286    void         ** ptr2;
287    void         ** ptr3;
288
289    // compute indexes
290    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
291        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
292        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
293
294    // get ptr2
295        ptr2 = ptr1[ix1];
296        if( ptr2 == NULL ) return NULL;
297
298    // get ptr3
299        ptr3 = ptr2[ix2];
300        if( ptr3 == NULL ) return NULL;
301
302    // get value
303        void * value = ptr3[ix3];
304
305        return value;
306}
307
308//////////////////////////////////////
309void * grdxt_get_first( grdxt_t  * rt,
310                        uint32_t   start_key,
311                        uint32_t * found_key )
312{
313    uint32_t        ix1;
314    uint32_t        ix2;
315    uint32_t        ix3;
316
317    uint32_t        w1 = rt->ix1_width;
318    uint32_t        w2 = rt->ix2_width;
319    uint32_t        w3 = rt->ix3_width;
320
321    // Check start_key
322    if( (start_key >> (w1 + w2 + w3)) != 0 )
323    {
324        assert( false , __FUNCTION__ ,
325        "start_key value %x exceed (%d + %d + %d) bits", start_key , w1 , w2 , w3 );
326    }
327
328    // compute max indexes
329    uint32_t        max1 = 1 << w1;
330    uint32_t        max2 = 1 << w2;
331    uint32_t        max3 = 1 << w3;
332
333    // compute min indexes
334    uint32_t        min1 = start_key >> (w2 + w3);           
335        uint32_t        min2 = (start_key >> w3) & ((1 << w2) -1);
336        uint32_t        min3 = start_key & ((1 << w3) - 1); 
337
338    void         ** ptr1 = rt->root;
339    void         ** ptr2;
340    void         ** ptr3;
341
342    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
343    {
344        ptr2 = ptr1[ix1];
345        if( ptr2 == NULL ) continue;
346
347        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
348        {
349            ptr3 = ptr2[ix2];
350            if( ptr3 == NULL ) continue;
351
352            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
353            {
354                if( ptr3[ix3] == NULL ) continue;
355                else                   
356                {
357                    *found_key = (ix1 << (w2+w3)) | (ix2 << w1) | ix3;
358                    return ptr3[ix3];
359                }
360            }
361        }
362    }
363
364    return NULL;
365}
Note: See TracBrowser for help on using the repository browser.