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

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

Cosmetic.
File size: 21.9 KB
RevLine 
[1]1/*
[626]2 * grdxt.c - Three-levels Generic Radix-tree implementation.
[1]3 *
[626]4 * authors  Alain Greiner (2016,2017,2018,2019))
[1]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
[457]24#include <hal_kernel_types.h>
[1]25#include <hal_special.h>
[603]26#include <hal_remote.h>
[1]27#include <errno.h>
28#include <printk.h>
29#include <kmem.h>
30#include <grdxt.h>
31
[635]32////////////////////////////////////////////////////////////////////////////////////////
33//               Local access functions
34////////////////////////////////////////////////////////////////////////////////////////
35
[1]36/////////////////////////////////
37error_t grdxt_init( grdxt_t * rt,
38                    uint32_t  ix1_width,
39                    uint32_t  ix2_width,
40                    uint32_t  ix3_width )
41{
42    void      ** root;
43        kmem_req_t   req;
44 
45        rt->ix1_width = ix1_width;
46        rt->ix2_width = ix2_width;
47        rt->ix3_width = ix3_width;
48
49    // allocates first level array
[635]50        req.type  = KMEM_KCM;
51        req.order = ix1_width + ( (sizeof(void*) == 4) ? 2 : 3 );
[1]52        req.flags = AF_KERNEL | AF_ZERO;
53        root = kmem_alloc( &req );
[635]54
55        if( root == NULL )
56    {
57        printk("\n[ERROR] in %s : cannot allocate first level array\n", __FUNCTION__);
58        return -1;
59    }
[1]60 
61        rt->root = root;
62
63        return 0;
64
[603]65}  // end grdxt_init()
66
[1]67//////////////////////////////////
68void grdxt_destroy( grdxt_t * rt )
69{
70        kmem_req_t req;
71
72    uint32_t   w1 = rt->ix1_width;
73    uint32_t   w2 = rt->ix2_width;
74    uint32_t   w3 = rt->ix3_width;
75
76    void    ** ptr1 = rt->root;
77    void    ** ptr2;
78    void    ** ptr3;
79
80        uint32_t   ix1;
81        uint32_t   ix2;
[635]82        uint32_t   ix3;
[1]83
[671]84assert( __FUNCTION__, (rt != NULL) , "pointer on radix tree is NULL\n" );
[603]85
[473]86        for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ )
[1]87        {
88        ptr2 = ptr1[ix1];
89
90                if( ptr2 == NULL ) continue;
91
[473]92        for( ix2=0 ; ix2 < (uint32_t)(1 << w2) ; ix2++ )
[1]93        {
94            ptr3 = ptr2[ix2];
95
96                    if( ptr3 == NULL ) continue;
97
[635]98            for( ix3=0 ; ix3 < (uint32_t)(1 << w3) ; ix3++ )
99            {
100                 if( ptr3[ix3] != NULL )
101                 {
102                     printk("\n[WARNING] in %s : ptr3[%d][%d][%d] non empty\n",
103                     __FUNCTION__, ix1, ix2, ix3 );
104                 }
105            }
106
[1]107            // release level 3 array
[635]108            req.type = KMEM_KCM;
[1]109                    req.ptr  = ptr3;
110                    kmem_free( &req );
111        }
112
113        // release level 2 array
[635]114        req.type = KMEM_KCM;
[1]115                req.ptr  = ptr2;
116                kmem_free( &req );
117    }
118
119    // release level 1 array
[635]120    req.type = KMEM_KCM;
[1]121        req.ptr  = ptr1;
122        kmem_free( &req );
123
124}  // end grdxt_destroy()
125
[603]126////////////////////////////////////
[1]127error_t grdxt_insert( grdxt_t  * rt,
128                      uint32_t   key,
129                      void     * value )
130{
131        kmem_req_t      req;
132
133    uint32_t        w1 = rt->ix1_width;
134    uint32_t        w2 = rt->ix2_width;
135    uint32_t        w3 = rt->ix3_width;
136
[603]137// Check key value
[671]138assert( __FUNCTION__, ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
[1]139
140    // compute indexes
141    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
142        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
143        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
144
[635]145    // get ptr1
146    void ** ptr1 = rt->root;
[1]147
[635]148    if( ptr1 == NULL ) return -1;
149
150    // get ptr2
151        void ** ptr2 = ptr1[ix1];
152
153    // If required, allocate memory for the missing level 2 array
154        if( ptr2 == NULL )
[1]155        {
156        // allocate memory for level 2 array
[635]157        req.type  = KMEM_KCM;
158        req.order = w2 + ( (sizeof(void*) == 4) ? 2 : 3 );
[1]159        req.flags = AF_KERNEL | AF_ZERO;
160        ptr2 = kmem_alloc( &req );
161
[635]162        if( ptr2 == NULL) return -1;
163
[1]164        // update level 1 array
165        ptr1[ix1] = ptr2;
166        }
167
[635]168    // get ptr3
169        void ** ptr3 = ptr2[ix2];
170
171    // If required, allocate memory for the missing level 3 array
172        if( ptr3 == NULL )
[1]173        {
174        // allocate memory for level 3 array
[635]175        req.type = KMEM_KCM;
176        req.order = w3 + ( (sizeof(void*) == 4) ? 2 : 3 );
[1]177        req.flags = AF_KERNEL | AF_ZERO;
178        ptr3 = kmem_alloc( &req );
179
[635]180        if( ptr3 == NULL) return -1;
181
[1]182        //  update level 3 array
183                ptr2[ix2] = ptr3;
184        }
185
186    // register the value
187        ptr3[ix3] = value;
[635]188
[124]189        hal_fence();
[1]190
191        return 0;
192
[603]193}  // end grdxt_insert()
194
[1]195///////////////////////////////////
196void * grdxt_remove( grdxt_t  * rt,
197                     uint32_t   key )
198{
199    uint32_t        w1 = rt->ix1_width;
200    uint32_t        w2 = rt->ix2_width;
201    uint32_t        w3 = rt->ix3_width;
202
[603]203// Check key value
[671]204assert( __FUNCTION__, ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
[1]205
206    // compute indexes
207    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
208        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
209        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
210
[635]211    // get ptr1
212    void ** ptr1 = rt->root;
[1]213
[635]214    if( ptr1 == NULL ) return NULL;
215
[1]216    // get ptr2
[635]217        void ** ptr2 = ptr1[ix1];
218
[1]219        if( ptr2 == NULL ) return NULL;
220
221    // get ptr3
[635]222        void ** ptr3 = ptr2[ix2];
223
[1]224        if( ptr3 == NULL ) return NULL;
225
226    // get value
227        void * value = ptr3[ix3];
228
229    // reset selected slot
230        ptr3[ix3] = NULL;
[124]231        hal_fence();
[1]232
233        return value;
234
[603]235}  // end grdxt_remove()
236
[1]237///////////////////////////////////
238void * grdxt_lookup( grdxt_t  * rt,
239                     uint32_t   key )
240{
241    uint32_t        w1 = rt->ix1_width;
242    uint32_t        w2 = rt->ix2_width;
243    uint32_t        w3 = rt->ix3_width;
244
[603]245// Check key value
[671]246assert( __FUNCTION__, ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
[1]247
248    void         ** ptr1 = rt->root;
249    void         ** ptr2;
250    void         ** ptr3;
251
252    // compute indexes
253    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
254        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
255        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
256
257    // get ptr2
258        ptr2 = ptr1[ix1];
259        if( ptr2 == NULL ) return NULL;
260
261    // get ptr3
262        ptr3 = ptr2[ix2];
263        if( ptr3 == NULL ) return NULL;
264
265    // get value
266        void * value = ptr3[ix3];
267
268        return value;
269
[603]270}  // end grdxt_lookup()
271
[635]272//////////////////////////////////////
273void * grdxt_get_first( grdxt_t  * rt,
274                        uint32_t   start_key,
275                        uint32_t * found_key )
276{
277    uint32_t        ix1;
278    uint32_t        ix2;
279    uint32_t        ix3;
280
281    uint32_t        w1 = rt->ix1_width;
282    uint32_t        w2 = rt->ix2_width;
283    uint32_t        w3 = rt->ix3_width;
284
285// Check key value
[671]286assert( __FUNCTION__, ((start_key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", start_key );
[635]287
288    // compute max indexes
289    uint32_t        max1 = 1 << w1;
290    uint32_t        max2 = 1 << w2;
291    uint32_t        max3 = 1 << w3;
292
293    // compute min indexes
294    uint32_t        min1 = start_key >> (w2 + w3);           
295        uint32_t        min2 = (start_key >> w3) & ((1 << w2) -1);
296        uint32_t        min3 = start_key & ((1 << w3) - 1); 
297
298    void         ** ptr1 = rt->root;
299    void         ** ptr2;
300    void         ** ptr3;
301
302    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
303    {
304        ptr2 = ptr1[ix1];
305        if( ptr2 == NULL ) continue;
306
307        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
308        {
309            ptr3 = ptr2[ix2];
310            if( ptr3 == NULL ) continue;
311
312            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
313            {
314                if( ptr3[ix3] == NULL ) continue;
315                else                   
316                {
[656]317                    *found_key = (ix1 << (w2+w3)) | (ix2 << w3) | ix3;
[635]318                    return ptr3[ix3];
319                }
320            }
321        }
322    }
323
324    return NULL;
325
326}  // end grdxt_get_first()
327
328
329
330////////////////////////////////////////////////////////////////////////////////////////
331//               Remote access functions
332////////////////////////////////////////////////////////////////////////////////////////
333
[657]334////////////////////////////////////////////
335error_t grdxt_remote_init( xptr_t     rt_xp,
336                           uint32_t   ix1_width,
337                           uint32_t   ix2_width,
338                           uint32_t   ix3_width )
339{
340    void      ** root;
341        kmem_req_t   req;
342
343    // get cluster and local pointer
344    cxy_t     rt_cxy = GET_CXY( rt_xp );
345    grdxt_t * rt_ptr = GET_PTR( rt_xp );
346 
347    // initialize widths
348    hal_remote_s32( XPTR( rt_cxy , &rt_ptr->ix1_width ) , ix1_width );
349    hal_remote_s32( XPTR( rt_cxy , &rt_ptr->ix2_width ) , ix2_width );
350    hal_remote_s32( XPTR( rt_cxy , &rt_ptr->ix3_width ) , ix3_width );
351
352    // allocates first level array
353        req.type  = KMEM_KCM;
354        req.order = ix1_width + ( (sizeof(void*) == 4) ? 2 : 3 );
355        req.flags = AF_KERNEL | AF_ZERO;
356        root      = kmem_remote_alloc( rt_cxy , &req );
357
358        if( root == NULL )
359    {
360        printk("\n[ERROR] in %s : cannot allocate first level array\n", __FUNCTION__);
361        return -1;
362    }
363 
364    // register first level array in rt descriptor
365    hal_remote_spt( XPTR( rt_cxy , &rt_ptr->root ) , root );
366 
367        return 0;
368
369}  // end grdxt_remote_init()
370
371//////////////////////////////////////////
372void grdxt_remote_destroy( xptr_t  rt_xp )
373{
374        kmem_req_t req;
375
376    uint32_t   w1;
377    uint32_t   w2;
378    uint32_t   w3;
379
380        uint32_t   ix1;
381        uint32_t   ix2;
382        uint32_t   ix3;
383
384    void    ** ptr1;
385    void    ** ptr2;
386    void    ** ptr3;
387
388    // get cluster and local pointer
389    cxy_t     rt_cxy = GET_CXY( rt_xp );
390    grdxt_t * rt_ptr = GET_PTR( rt_xp );
391
392    // get widths
393    w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
394    w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
395    w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
396
397    // get ptr1
398    ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
399
400        for( ix1=0 ; ix1 < (uint32_t)(1 << w1) ; ix1++ )
401        {
402        // get ptr2
403        ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
404
405                if( ptr2 == NULL ) continue;
406
407        for( ix2=0 ; ix2 < (uint32_t)(1 << w2) ; ix2++ )
408        {
[671]409            // get ptr3
[657]410            ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
411
412                    if( ptr3 == NULL ) continue;
413
414            for( ix3=0 ; ix3 < (uint32_t)(1 << w3) ; ix3++ )
415            {
416                 if( ptr3[ix3] != NULL )
417                 {
418                     printk("\n[WARNING] in %s : ptr3[%d][%d][%d] non empty\n",
419                     __FUNCTION__, ix1, ix2, ix3 );
420                 }
421            }
422
423            // release level 3 array
424            req.type = KMEM_KCM;
425                    req.ptr  = ptr3;
426                    kmem_remote_free( rt_cxy , &req );
427        }
428
429        // release level 2 array
430        req.type = KMEM_KCM;
431                req.ptr  = ptr2;
432            kmem_remote_free( rt_cxy , &req );
433    }
434
435    // release level 1 array
436    req.type = KMEM_KCM;
437        req.ptr  = ptr1;
438    kmem_remote_free( rt_cxy , &req );
439
440}  // end grdxt_remote_destroy()
441
[635]442//////////////////////////////////////////////
443error_t grdxt_remote_insert( xptr_t     rt_xp,
444                             uint32_t   key,
445                             void     * value )
446{
447    kmem_req_t  req;
448
449    // get cluster and local pointer on remote rt descriptor
450        cxy_t     rt_cxy = GET_CXY( rt_xp );
451    grdxt_t * rt_ptr = GET_PTR( rt_xp );
452
[656]453#if DEBUG_GRDXT_INSERT
454uint32_t cycle = (uint32_t)hal_get_cycles();
455if(DEBUG_GRDXT_INSERT < cycle)
456printk("\n[%s] enter / rt_xp (%x,%x) / key %x / value %x\n",
457__FUNCTION__, rt_cxy, rt_ptr, key, (intptr_t)value ); 
458#endif
459
[635]460    // get widths
461    uint32_t        w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
462    uint32_t        w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
463    uint32_t        w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
464
[656]465#if DEBUG_GRDXT_INSERT
466if(DEBUG_GRDXT_INSERT < cycle)
467printk("\n[%s] get widths : w1 %d / w2 %d / w3 %d\n",
468__FUNCTION__, w1, w2, w3 ); 
469#endif
470
[635]471// Check key value
[671]472assert( __FUNCTION__, ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
[635]473
474    // compute indexes
475    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
476        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
477        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
478
[656]479#if DEBUG_GRDXT_INSERT
480if(DEBUG_GRDXT_INSERT < cycle)
481printk("\n[%s] compute indexes : ix1 %d / ix2 %d / ix3 %d\n",
482__FUNCTION__, ix1, ix2, ix3 ); 
483#endif
484
[635]485    // get ptr1
486    void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
487
488    if( ptr1 == NULL ) return -1;
489
[656]490#if DEBUG_GRDXT_INSERT
491if(DEBUG_GRDXT_INSERT < cycle)
492printk("\n[%s] compute ptr1 = %x\n",
493__FUNCTION__, (intptr_t)ptr1 ); 
494#endif
495
[635]496    // get ptr2
497    void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
498
[656]499#if DEBUG_GRDXT_INSERT
500if(DEBUG_GRDXT_INSERT < cycle)
501printk("\n[%s] get current ptr2 = %x\n",
502__FUNCTION__, (intptr_t)ptr2 ); 
503#endif
504
[635]505    // allocate memory for the missing level_2 array if required
506    if( ptr2 == NULL )
507    {
508        // allocate memory in remote cluster
509        req.type  = KMEM_KCM;
510        req.order = w2 + ((sizeof(void*) == 4) ? 2 : 3 );
511        req.flags = AF_ZERO | AF_KERNEL;
512        ptr2 = kmem_remote_alloc( rt_cxy , &req );
513
514        if( ptr2 == NULL ) return -1;
[656]515       
[635]516        // update level_1 entry
517        hal_remote_spt( XPTR( rt_cxy , &ptr1[ix1] ) , ptr2 );
[656]518
519#if DEBUG_GRDXT_INSERT
520if(DEBUG_GRDXT_INSERT < cycle)
521printk("\n[%s] update ptr1[%d] : &ptr1[%d] = %x / ptr2 = %x\n",
522__FUNCTION__, ix1, ix1, &ptr1[ix1], ptr2 );
523#endif
524
[635]525    }
526
527    // get ptr3
528    void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
529
[656]530#if DEBUG_GRDXT_INSERT
531if(DEBUG_GRDXT_INSERT < cycle)
532printk("\n[%s] get current ptr3 = %x\n",
533__FUNCTION__, (intptr_t)ptr3 ); 
534#endif
535
[635]536    // allocate memory for the missing level_3 array if required
537    if( ptr3 == NULL )
538    {
539        // allocate memory in remote cluster
540        req.type  = KMEM_KCM;
541        req.order = w3 + ((sizeof(void*) == 4) ? 2 : 3 );
542        req.flags = AF_ZERO | AF_KERNEL;
543        ptr3 = kmem_remote_alloc( rt_cxy , &req );
544
545        if( ptr3 == NULL ) return -1;
546
547        // update level_2 entry
548        hal_remote_spt( XPTR( rt_cxy , &ptr2[ix2] ) , ptr3 );
[656]549
550#if DEBUG_GRDXT_INSERT
551if(DEBUG_GRDXT_INSERT < cycle)
552printk("\n[%s] update  ptr2[%d] : &ptr2[%d] %x / ptr3 %x\n",
553__FUNCTION__, ix2, ix2, &ptr2[ix2], ptr3 );
554#endif
555
[635]556    }
557
558    // register value in level_3 array
559    hal_remote_spt( XPTR( rt_cxy , &ptr3[ix3] ) , value );
560
[656]561#if DEBUG_GRDXT_INSERT
562if(DEBUG_GRDXT_INSERT < cycle)
563printk("\n[%s] update  ptr3[%d] : &ptr3[%d] %x / value %x\n",
564__FUNCTION__, ix3, ix3, &ptr3[ix3], value );
565#endif
566
[635]567    hal_fence();
568
569        return 0;
570
571}  // end grdxt_remote_insert()
572
[603]573////////////////////////////////////////////
[657]574xptr_t grdxt_remote_remove( xptr_t    rt_xp,
[635]575                            uint32_t  key )
576{
577    // get cluster and local pointer on remote rt descriptor
578        cxy_t     rt_cxy = GET_CXY( rt_xp );
579    grdxt_t * rt_ptr = GET_PTR( rt_xp );
580
581    // get widths
582    uint32_t        w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
583    uint32_t        w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
584    uint32_t        w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
585
586// Check key value
[671]587assert( __FUNCTION__, ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
[635]588
589    // compute indexes
590    uint32_t        ix1 = key >> (w2 + w3);              // index in level 1 array
591        uint32_t        ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
592        uint32_t        ix3 = key & ((1 << w3) - 1);         // index in level 3 array
593
594    // get ptr1
595    void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
596
597    // get ptr2
598        void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
[657]599        if( ptr2 == NULL ) return XPTR_NULL;
[635]600
601    // get ptr3
602        void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
[657]603        if( ptr3 == NULL ) return XPTR_NULL;
[635]604
605    // get value
606        void * value = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );
607
608    // reset selected slot
609        hal_remote_spt( XPTR( rt_cxy, &ptr3[ix3] ) , NULL );
610        hal_fence();
611
[657]612        return XPTR( rt_cxy , value );
[635]613
614}  // end grdxt_remote_remove()
615
616////////////////////////////////////////////
[603]617xptr_t grdxt_remote_lookup( xptr_t    rt_xp,
618                            uint32_t  key )
619{
620    // get cluster and local pointer on remote rt descriptor
621    grdxt_t       * rt_ptr = GET_PTR( rt_xp );
622    cxy_t           rt_cxy = GET_CXY( rt_xp );
623
624    // get widths
625    uint32_t        w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
626    uint32_t        w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
627    uint32_t        w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
628
629// Check key value
[671]630assert( __FUNCTION__, ((key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", key );
[603]631
632    // compute indexes
[657]633    uint32_t       ix1 = key >> (w2 + w3);              // index in level 1 array
634        uint32_t       ix2 = (key >> w3) & ((1 << w2) -1);  // index in level 2 array
635        uint32_t       ix3 = key & ((1 << w3) - 1);         // index in level 3 array
[603]636
637    // get ptr1
[610]638    void ** ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
[603]639
640    // get ptr2
[610]641        void ** ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
[603]642        if( ptr2 == NULL ) return XPTR_NULL;
643
644    // get ptr3
[610]645        void ** ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
[603]646        if( ptr3 == NULL ) return XPTR_NULL;
647
[610]648    // get pointer on registered item
649    void  * item_ptr = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );
[603]650
[610]651    // return extended pointer on registered item
652    if ( item_ptr == NULL )  return XPTR_NULL;
653        else                     return XPTR( rt_cxy , item_ptr );
[603]654
655}  // end grdxt_remote_lookup()
656
[657]657////////////////////////////////////////////////
658xptr_t grdxt_remote_get_first( xptr_t     rt_xp,
659                               uint32_t   start_key,
660                               uint32_t * found_key )
661{
662    uint32_t        ix1;
663    uint32_t        ix2;
664    uint32_t        ix3;
665
666    void        ** ptr1;       // local base address of remote first level array
667    void        ** ptr2;       // local base address of remote second level array
668    void        ** ptr3;       // local base address of remote third level array
669
670    // get cluster and local pointer on remote rt descriptor
671    grdxt_t       * rt_ptr = GET_PTR( rt_xp );
672    cxy_t           rt_cxy = GET_CXY( rt_xp );
673
674    // get widths
675    uint32_t        w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
676    uint32_t        w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
677    uint32_t        w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
678
679// Check key value
[671]680assert( __FUNCTION__, ((start_key >> (w1 + w2 + w3)) == 0 ), "illegal key value %x\n", start_key );
[657]681
682    // compute min indexes
683    uint32_t       min1 = start_key >> (w2 + w3);           
684        uint32_t       min2 = (start_key >> w3) & ((1 << w2) -1);
685        uint32_t       min3 = start_key & ((1 << w3) - 1); 
686
687    // compute max indexes
688    uint32_t       max1 = 1 << w1;
689    uint32_t       max2 = 1 << w2;
690    uint32_t       max3 = 1 << w3;
691
692    // get ptr1
693    ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
694
695    for( ix1 = min1 ; ix1 < max1 ; ix1++ )
696    {
697        ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
698        if( ptr2 == NULL ) continue;
699
700        for( ix2 = min2 ; ix2 < max2 ; ix2++ )
701        {
702            ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
703            if( ptr3 == NULL ) continue;
704
705            for( ix3 = min3 ; ix3 < max3 ; ix3++ )
706            {
707                void * item = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );
708
709                if( item == NULL ) continue;
710                else                   
711                {
712                    *found_key = (ix1 << (w2+w3)) | (ix2 << w3) | ix3;
713                    return XPTR( rt_cxy , item );
714                }
715            }
716        }
717    }
718
719    return XPTR_NULL;
720
721}  // end grdxt_remote_get_first()
722
[635]723/////////////////////////i/////////////////
724void grdxt_remote_display( xptr_t    rt_xp,
725                           char    * name )
[1]726{
[635]727        uint32_t       ix1; 
728        uint32_t       ix2;
729        uint32_t       ix3;
[1]730
[656]731    void        ** ptr1;
732    void        ** ptr2;
733    void        ** ptr3;
734
[635]735// check rt_xp
[671]736assert( __FUNCTION__, (rt_xp != XPTR_NULL) , "pointer on radix tree is NULL\n" );
[1]737
[635]738    // get cluster and local pointer on remote rt descriptor
739    grdxt_t      * rt_ptr = GET_PTR( rt_xp );
740    cxy_t          rt_cxy = GET_CXY( rt_xp );
[1]741
[635]742    // get widths
743    uint32_t       w1 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix1_width ) );
744    uint32_t       w2 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix2_width ) );
745    uint32_t       w3 = hal_remote_l32( XPTR( rt_cxy , &rt_ptr->ix3_width ) );
[1]746
[656]747    ptr1 = hal_remote_lpt( XPTR( rt_cxy , &rt_ptr->root ) );
[1]748
[635]749        printk("\n***** Generic Radix Tree for <%s>\n", name );
[1]750
[635]751        for( ix1=0 ; ix1 < (uint32_t)(1<<w1) ; ix1++ )
752        {
[656]753            ptr2 = hal_remote_lpt( XPTR( rt_cxy , &ptr1[ix1] ) );
[635]754        if( ptr2 == NULL )  continue;
755   
756        for( ix2=0 ; ix2 < (uint32_t)(1<<w2) ; ix2++ )
[1]757        {
[656]758                ptr3 = hal_remote_lpt( XPTR( rt_cxy , &ptr2[ix2] ) );
[1]759            if( ptr3 == NULL ) continue;
760
[635]761            for( ix3=0 ; ix3 < (uint32_t)(1<<w3) ; ix3++ )
[1]762            {
[635]763                void * value = hal_remote_lpt( XPTR( rt_cxy , &ptr3[ix3] ) );
764                if( value == NULL )  continue;
765
766                uint32_t key = (ix1<<(w2+w3)) + (ix2<<w3) + ix3;
[656]767                printk(" - key = %x / value = %x / ptr1 = %x / ptr2 = %x / ptr3 = %x\n",
768                key, (intptr_t)value, (intptr_t)ptr1, (intptr_t)ptr2, (intptr_t)ptr3 );
[1]769            }
770        }
[635]771        }
[1]772
[635]773} // end grdxt_remote_display()
[603]774
[635]775
Note: See TracBrowser for help on using the repository browser.