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

Last change on this file since 687 was 683, checked in by alain, 4 years ago

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