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

Last change on this file since 174 was 124, checked in by max@…, 7 years ago

rename hal_wbflush->hal_fence

File size: 9.7 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_types.h>
25#include <hal_special.h>
26#include <errno.h>
27#include <printk.h>
28#include <kmem.h>
29#include <grdxt.h>
30
31/////////////////////////////////
32error_t grdxt_init( grdxt_t * rt,
33                    uint32_t  ix1_width,
34                    uint32_t  ix2_width,
35                    uint32_t  ix3_width )
36{
37    void      ** root;
38        kmem_req_t   req;
39 
40        rt->ix1_width = ix1_width;
41        rt->ix2_width = ix2_width;
42        rt->ix3_width = ix3_width;
43
44    // allocates first level array
45        req.type  = KMEM_GENERIC;
46        req.size  = sizeof(void *) << ix1_width;
47        req.flags = AF_KERNEL | AF_ZERO;
48        root = kmem_alloc( &req );
49        if( root == NULL ) return ENOMEM;
50 
51        rt->root = root;
52
53        return 0;
54}
55
56//////////////////////////////////
57void grdxt_destroy( grdxt_t * rt )
58{
59        kmem_req_t req;
60
61    uint32_t   w1 = rt->ix1_width;
62    uint32_t   w2 = rt->ix2_width;
63    uint32_t   w3 = rt->ix3_width;
64
65    void    ** ptr1 = rt->root;
66    void    ** ptr2;
67    void    ** ptr3;
68
69        uint32_t   ix1;
70        uint32_t   ix2;
71
72        req.type = KMEM_GENERIC;
73
74        for( ix1=0 ; ix1 < (1 << w1) ; ix1++ )
75        {
76        ptr2 = ptr1[ix1];
77
78                if( ptr2 == NULL ) continue;
79
80        for( ix2=0 ; ix2 < (1 << w2) ; ix2++ )
81        {
82            ptr3 = ptr2[ix2];
83
84                    if( ptr3 == NULL ) continue;
85
86            // release level 3 array
87                    req.ptr  = ptr3;
88            req.type = KMEM_GENERIC;
89            req.size = sizeof(void *) * (1 << w3);
90                    kmem_free( &req );
91        }
92
93        // release level 2 array
94                req.ptr  = ptr2;
95        req.type = KMEM_GENERIC;
96        req.size = sizeof(void *) * (1 << w2);
97                kmem_free( &req );
98    }
99
100    // release level 1 array
101        req.ptr  = ptr1;
102    req.type = KMEM_GENERIC;
103    req.size = sizeof(void *) * (1 << w1);
104        kmem_free( &req );
105
106}  // end grdxt_destroy()
107
108///////////////////////////////
109void grdxt_print( grdxt_t * rt,
110                  char    * name )
111{
112        uint32_t        ix1; 
113        uint32_t        ix2;
114        uint32_t        ix3;
115
116    uint32_t        w1 = rt->ix1_width;
117    uint32_t        w2 = rt->ix2_width;
118    uint32_t        w3 = rt->ix3_width;
119
120    void         ** ptr1 = rt->root;
121    void         ** ptr2;
122    void         ** ptr3;
123
124    intptr_t        key; 
125    intptr_t        value;
126
127        printk("*** %s : n1 = %d / n2 = %d / n3 = %d\n", 
128           name, 1<<w1 , 1<<w2 , 1<<w3 );
129
130        for( ix1=0 ; ix1 < (1<<w1) ; ix1++ )
131        {
132        ptr2 = ptr1[ix1];
133        if( ptr2 == NULL )  continue;
134   
135        for( ix2=0 ; ix2 < (1<<w2) ; ix2++ )
136        {
137            ptr3 = ptr2[ix2];
138            if( ptr3 == NULL ) continue;
139
140            for( ix3=0 ; ix3 < (1<<w3) ; ix3++ )
141            {
142                value = (intptr_t)ptr3[ix3];
143                if( value == 0 )  continue;
144
145                key = (ix1<<(w2+w3)) + (ix2<<w3) + ix3;
146                printk(" - key = %x / value = %x\n", key , value );
147            }
148        }
149        }
150} // end grdxt_print()
151
152////////////////////////////////////
153error_t grdxt_insert( grdxt_t  * rt,
154                      uint32_t   key,
155                      void     * value )
156{
157        kmem_req_t      req;
158
159    uint32_t        w1 = rt->ix1_width;
160    uint32_t        w2 = rt->ix2_width;
161    uint32_t        w3 = rt->ix3_width;
162
163    // Check key
164    if( (key >> (w1 + w2 + w3)) != 0 )
165    {
166        printk("\n[PANIC] in %s : key value %x exceed (%d + %d + %d) bits\n",
167               __FUNCTION__ , key , w1 , w2 , w3 );
168        hal_core_sleep();
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        printk("\n[PANIC] in %s : key value %x exceed (%d + %d + %d) bits\n",
240               __FUNCTION__ , key , w1 , w2 , w3 );
241        hal_core_sleep();
242    }
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
271///////////////////////////////////
272void * grdxt_lookup( grdxt_t  * rt,
273                     uint32_t   key )
274{
275    uint32_t        w1 = rt->ix1_width;
276    uint32_t        w2 = rt->ix2_width;
277    uint32_t        w3 = rt->ix3_width;
278
279    // Check key
280    if( (key >> (w1 + w2 + w3)) != 0 )
281    {
282        printk("\n[PANIC] in %s : key value %x exceed (%d + %d + %d) bits\n",
283               __FUNCTION__ , key , w1 , w2 , w3 );
284        hal_core_sleep();
285    }
286
287    void         ** ptr1 = rt->root;
288    void         ** ptr2;
289    void         ** ptr3;
290
291    // compute indexes
292    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
293        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
294        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
295
296    // get ptr2
297        ptr2 = ptr1[ix1];
298        if( ptr2 == NULL ) return NULL;
299
300    // get ptr3
301        ptr3 = ptr2[ix2];
302        if( ptr3 == NULL ) return NULL;
303
304    // get value
305        void * value = ptr3[ix3];
306
307        return value;
308}
309
310//////////////////////////////////////
311void * grdxt_get_first( grdxt_t  * rt,
312                        uint32_t   start_key,
313                        uint32_t * found_key )
314{
315    uint32_t        ix1;
316    uint32_t        ix2;
317    uint32_t        ix3;
318
319    uint32_t        w1 = rt->ix1_width;
320    uint32_t        w2 = rt->ix2_width;
321    uint32_t        w3 = rt->ix3_width;
322
323    // Check start_key
324    if( (start_key >> (w1 + w2 + w3)) != 0 )
325    {
326        printk("\n[PANIC] in %s : start_key value %x exceed (%d + %d + %d) bits\n",
327               __FUNCTION__ , start_key , w1 , w2 , w3 );
328        hal_core_sleep();
329    }
330
331    // compute max indexes
332    uint32_t        max1 = 1 << w1;
333    uint32_t        max2 = 1 << w2;
334    uint32_t        max3 = 1 << w3;
335
336    // compute min indexes
337    uint32_t        min1 = start_key >> (w2 + w3);           
338        uint32_t        min2 = (start_key >> w3) & ((1 << w2) -1);
339        uint32_t        min3 = start_key & ((1 << w3) - 1); 
340
341    void         ** ptr1 = rt->root;
342    void         ** ptr2;
343    void         ** ptr3;
344
345    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
346    {
347        ptr2 = ptr1[ix1];
348        if( ptr2 == NULL ) continue;
349
350        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
351        {
352            ptr3 = ptr2[ix2];
353            if( ptr3 == NULL ) continue;
354
355            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
356            {
357                if( ptr3[ix3] == NULL ) continue;
358                else                   
359                {
360                    *found_key = (ix1 << (w2+w3)) | (ix2 << w1) | ix3;
361                    return ptr3[ix3];
362                }
363            }
364        }
365    }
366
367    return NULL;
368}
Note: See TracBrowser for help on using the repository browser.