source: trunk/kernel/libk/xhtab.c @ 437

Last change on this file since 437 was 423, checked in by alain, 7 years ago

cosmetic
File size: 17.0 KB
RevLine 
[1]1/*
2 * xhtab.c - Remote access embedded hash table implementation.
3 *
[23]4 * Author     Alain Greiner          (2016,2017)
[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
[14]24#include <kernel_config.h>
[1]25#include <hal_types.h>
26#include <hal_special.h>
27#include <hal_remote.h>
28#include <xlist.h>
29#include <remote_rwlock.h>
30#include <string.h>
31#include <printk.h>
32#include <xhtab.h>
33#include <vfs.h>
34
35
[23]36///////////////////////////////////////////////////////////////////////////////////////////
[188]37// Item type specific functions (three functions for each item type).
[23]38///////////////////////////////////////////////////////////////////////////////////////////
39
40///////////////////////////////////////////////////////////////////////////////////////////
[188]41// This functions compute the hash index from the key when item is a vfs_dentry_t.
42// The key is the directory entry name.
[23]43///////////////////////////////////////////////////////////////////////////////////////////
[188]44// @ key      : local pointer on name.
[23]45// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
46///////////////////////////////////////////////////////////////////////////////////////////
[188]47static uint32_t xhtab_dentry_index_from_key( void * key )
[23]48{
49        char     * name  = key;
50        uint32_t   index = 0;
51        while( *name )
52    {
53        index = index + (*(name++) ^ index);
54    }
[188]55        return index % XHASHTAB_SIZE;
[23]56} 
57
[188]58///////////////////////////////////////////////////////////////////////////////////////////
59// This functions returns the extended pointer on the item, from the extended pointer
60// on xlist contained in the item, when the item is a vfs_entry_t.
61///////////////////////////////////////////////////////////////////////////////////////////
62// @ xlist_xp      : extended pointer on embedded xlist entry.
63// @ return the extended pointer on the dentry containing this xlist entry.
64///////////////////////////////////////////////////////////////////////////////////////////
65static xptr_t xhtab_dentry_item_from_xlist( xptr_t xlist_xp )
66{
67    return XLIST_ELEMENT( xlist_xp , vfs_dentry_t , list );
68}
69
[23]70////////////////////////////////////////////////////////////////////////////////////////////
[188]71// This function compare the identifier of an item to a given <key>. For a vfs_entry_t,
72// it returns true when the directory name matches the name pointed by the <key> argument.
[23]73////////////////////////////////////////////////////////////////////////////////////////////
[188]74// @ item_xp   : extended pointer on item.
75// @ key       : pointer on searched item identifier.
76// returns true if given name matches directory entry name.
[23]77////////////////////////////////////////////////////////////////////////////////////////////
[204]78static bool_t xhtab_dentry_item_match_key( xptr_t    item_xp,
[188]79                                           void    * key )
[1]80{
[204]81    char name[CONFIG_VFS_MAX_NAME_LENGTH];
[23]82
[188]83    // get dentry cluster and local pointer
[204]84    cxy_t          dentry_cxy = GET_CXY( item_xp );
85    vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
[23]86
[188]87    // make a local copy of directory entry name
88    hal_remote_strcpy( XPTR( local_cxy , name ) ,
89                       XPTR( dentry_cxy , &dentry_ptr->name ) );
[23]90
[188]91    return( strcmp( name , (char*)key ) == 0 );
[1]92}
[204]93
94////////////////////////////////////////////////////////////////////////////////////////////
95// This function print the item key, that is the name for a vfs_entry_t,
96////////////////////////////////////////////////////////////////////////////////////////////
97// @ item_xp   : extended pointer on item.
98////////////////////////////////////////////////////////////////////////////////////////////
99static void xhtab_dentry_item_print_key( xptr_t item_xp )
100{
101    char name[CONFIG_VFS_MAX_NAME_LENGTH];
102
103    // get dentry cluster and local pointer
104    cxy_t          dentry_cxy = GET_CXY( item_xp );
105    vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
106   
107    // make a local copy of directory entry name
108    hal_remote_strcpy( XPTR( local_cxy , name ) ,
109                       XPTR( dentry_cxy , &dentry_ptr->name ) );
110
111    // print dentry name
112    printk("%s , ", name );
113}                       
114
[23]115////////////////////////////////////////////////////////////////////////////////////////
116//         Generic access functions
117////////////////////////////////////////////////////////////////////////////////////////
118
119//////////////////////////////////////////
120void xhtab_init( xhtab_t          * xhtab,
121                 xhtab_item_type_t  type )
[1]122{
123        uint32_t i;
124
125    // initialize readlock
126    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
127
[204]128    xhtab->items            = 0;
129    xhtab->current_index    = 0;
130    xhtab->current_xlist_xp = XPTR_NULL;
[1]131
132    if( type == XHTAB_DENTRY_TYPE )
133    {
[188]134        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
135        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
136        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
[204]137        xhtab->item_print_key  = &xhtab_dentry_item_print_key;
[1]138    }
139    else
140    {
[423]141        assert( false , __FUNCTION__ , "illegal item type\n" );
[1]142    }
143
[188]144        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
[1]145    {
146                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
147    } 
[188]148
149}  // end xhtab_init()
150
151//////////////////////////////////////
152xptr_t xhtab_scan( xptr_t    xhtab_xp,
153                   uint32_t  index,
154                   void    * key )
155{
[204]156    xptr_t              xlist_xp;           // xlist_entry_t (iterator)
157    xptr_t              item_xp;            // associated item
158    xhtab_t           * xhtab_ptr;          // hash table local pointer
159    cxy_t               xhtab_cxy;          // hash table cluster
160    item_from_xlist_t * item_from_xlist;    // function pointer
161    item_match_key_t  * item_match_key;     // function pointer
[188]162
163    // get hash table cluster and local pointer
164    xhtab_cxy = GET_CXY( xhtab_xp );
165    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
166
[204]167    // get pointer on "item_from_xlist" function
168    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
169                                                           &xhtab_ptr->item_from_xlist ) );
170    // get pointer on "item_match_key" function
171    item_match_key = (item_match_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
172                                                         &xhtab_ptr->item_match_key ) );
173
[188]174    // scan sub-list[index]
175    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
176    {
177        // get extended pointer on item containing the xlist entry
[204]178            item_xp = item_from_xlist( xlist_xp );
[188]179
180        // check matching
[204]181        if( item_match_key( item_xp , key ) ) return item_xp;
[188]182    }
183
184    // No matching item found
185    return XPTR_NULL;
[1]186
[204]187}  // end xhtab_scan()
188
[1]189///////////////////////////////////////
[23]190error_t xhtab_insert( xptr_t   xhtab_xp,
191                      void   * key,
192                      xptr_t   xlist_xp )
[1]193{
[204]194    xptr_t             item_xp;
195    uint32_t           index;
196    cxy_t              xhtab_cxy;
197    xhtab_t          * xhtab_ptr;
198    index_from_key_t * index_from_key;     // function pointer
199   
[1]200    // get xhtab cluster and local pointer
[204]201    xhtab_cxy = GET_CXY( xhtab_xp );
202    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
[1]203
[204]204    // get pointer on "index_from_key" function
205    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
206                                                         &xhtab_ptr->index_from_key ) );
[1]207    // compute index from key
[204]208        index = index_from_key( key );
[1]209
210    // take the lock protecting hash table
211    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
212
[23]213    // search a matching item
[204]214    item_xp = xhtab_scan( xhtab_xp , index , key );
[1]215
[23]216    if( item_xp != XPTR_NULL )    // error if found
217    {
218        // release the lock protecting hash table
219        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
[1]220
[23]221        return EINVAL;
222    }
223    else                          // insert item if not found
224    {
225        // register item in hash table
226            xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
[1]227
[23]228        // update number of registered items
229        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
230
231        // release the lock protecting hash table
232        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
233
234        return 0;
235    }
236}  // end xhtab_insert()
237
[1]238/////////////////////////////////////
[23]239error_t xhtab_remove( xptr_t   xhtab_xp,
240                      void   * key,
241                      xptr_t   xlist_entry_xp )
[1]242{
[204]243    xptr_t             item_xp;
244    uint32_t           index;
245    cxy_t              xhtab_cxy;
246    xhtab_t          * xhtab_ptr;
247    index_from_key_t * index_from_key;     // function pointer
248
[1]249    // get xhtab cluster and local pointer
[204]250    xhtab_cxy = GET_CXY( xhtab_xp );
251    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
[1]252
[204]253    // get pointer on "index_from_key" function
254    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
255                                                         &xhtab_ptr->index_from_key ) );
[23]256    // compute index from key
[204]257        index = index_from_key( key );
[23]258
[1]259    // take the lock protecting hash table
260    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
261
262    // get extended pointer on item to remove
[204]263    item_xp = xhtab_scan( xhtab_xp , index , key );
[1]264
[23]265    if( item_xp == XPTR_NULL )    // error if not found
[1]266    {
267        // release the lock protecting hash table
268        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
[23]269
270        return EINVAL;
[1]271    }
272    else                          // remove item if found
273    {
274        // remove item from hash table <=> unlink xlist_entry_t
[23]275        xlist_unlink( xlist_entry_xp );
[1]276
277        // update number of registered items
278        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
279
280        // release the lock protecting hash table
281        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
[23]282
283        return 0;
[1]284    }
[23]285}  // end xhtab_remove()
[1]286
287/////////////////////////////////////////
288xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
289                      void    * key )
290{
[204]291    xptr_t             item_xp;
292    uint32_t           index;
293    cxy_t              xhtab_cxy;
294    xhtab_t          * xhtab_ptr;
295    index_from_key_t * index_from_key;     // function pointer
[1]296
297    // get xhtab cluster and local pointer
[204]298    xhtab_cxy = GET_CXY( xhtab_xp );
299    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
[1]300
[204]301    // get pointer on "index_from_key" function
302    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
303                                                         &xhtab_ptr->index_from_key ) );
[1]304    // compute index from key
[204]305        index = index_from_key( key );
[1]306
307    // take the lock protecting hash table
308    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
309
310    // scan sub-list
[188]311    item_xp = xhtab_scan( xhtab_xp , index , key );
[1]312
313    // release the lock protecting hash table
314    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
315
316    return item_xp;
317
318}  // end xhtab_lookup()
319
[188]320///////////////////////////////////////
321void xhtab_read_lock( xptr_t xhtab_xp )
322{
323    // get xhtab cluster and local pointer
324    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
325    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
[1]326
[188]327    // take the lock protecting hash table
328    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
329}
330
331/////////////////////////////////////////
332void xhtab_read_unlock( xptr_t xhtab_xp )
333{
334    // get xhtab cluster and local pointer
335    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
336    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
337
338    // release the lock protecting hash table
339    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
340}
341
342/////////////////////////////////////////
343xptr_t xhtab_get_first( xptr_t xhtab_xp )
344{
[204]345    uint32_t            index;
346    cxy_t               xhtab_cxy;
347    xhtab_t           * xhtab_ptr;
348    xptr_t              xlist_xp;
349    xptr_t              item_xp;
350    xptr_t              root_xp;
351    item_from_xlist_t * item_from_xlist;   // function pointer
[188]352
353    // get xhtab cluster and local pointer
[204]354    xhtab_cxy = GET_CXY( xhtab_xp );
355    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
[188]356
[204]357    // get pointer on "item_from_xlist" function
358    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
359                                                           &xhtab_ptr->item_from_xlist ) );
[188]360    //loop on subsets
361    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
362    {
363        // get root of subset
364        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
365
366        // get first item
367        xlist_xp = xlist_next( root_xp , root_xp );
368
369        if( xlist_xp != XPTR_NULL )  // first item found
370        {
371            // get extended pointer on item containing the xlist entry
[204]372                item_xp = item_from_xlist( xlist_xp );
[188]373
374            // register item in hash table header
375            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
376            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
377
378            return item_xp;
379        }
380    }
381           
382    // item not found
383    return XPTR_NULL;
384
385} // end xhtab_get_first()
386   
387////////////////////////////////////////
388xptr_t xhtab_get_next( xptr_t xhtab_xp )
389{
[204]390    uint32_t            index;
391    cxy_t               xhtab_cxy;
392    xhtab_t           * xhtab_ptr;
393    xptr_t              xlist_xp;
394    xptr_t              item_xp;
395    xptr_t              root_xp;
396    item_from_xlist_t * item_from_xlist;   // function pointer
[188]397
398    uint32_t current_index;
399    xptr_t   current_xlist_xp;
400
401    // get xhtab cluster and local pointer
[204]402    xhtab_cxy = GET_CXY( xhtab_xp );
403    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
[188]404
405    // get current item pointers
406    current_index    = hal_remote_lw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) ); 
407    current_xlist_xp = hal_remote_lwd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) ); 
408
[204]409    // get pointer on "item_from_xlist" function
410    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
411                                                           &xhtab_ptr->item_from_xlist ) );
[188]412    //loop on subsets
413    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
414    {
415        // get root of subset
416        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
417
418        // get next item
[204]419        if( index == current_index ) xlist_xp = xlist_next( root_xp , current_xlist_xp );
420        else                         xlist_xp = xlist_next( root_xp , root_xp );
[188]421
422        if( xlist_xp != XPTR_NULL )  // next item found
423        {
424            // get extended pointer on item containing the xlist entry
[204]425                item_xp = item_from_xlist( xlist_xp );
[188]426
427            // register item in hash table header
428            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
429            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
430
431            return item_xp;
432        }
433    }
434           
435    // item not found
436    return XPTR_NULL;
437
438} // end xhtab_get_next()
439
[204]440/////////////////////////////////////
441void xhtab_display( xptr_t xhtab_xp )
442{
443    uint32_t            index;
444    cxy_t               xhtab_cxy;
445    xhtab_t           * xhtab_ptr;
446    xptr_t              root_xp;
447    xptr_t              iter_xp;
448    xptr_t              item_xp;
449    item_from_xlist_t * item_from_xlist;   // function pointer
450    item_print_key_t  * item_print_key;    // function pointer
[188]451
[204]452    // get xhtab cluster and local pointer
453    xhtab_cxy = GET_CXY( xhtab_xp );
454    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
455
456    // get pointer on "item_from_xlist" function
457    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
458                                                           &xhtab_ptr->item_from_xlist ) );
459    // get pointer on "item_print_key" function
460    item_print_key = (item_print_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
461                                                         &xhtab_ptr->item_print_key ) );
462    //loop on subsets
463    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
464    {
465        printk(" index = %d : ", index );
466
467        // get root of subset
468        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
469
470        // loop on xlist
471        XLIST_FOREACH( root_xp , iter_xp )
472        {
473            // get item from xlist
474            item_xp = item_from_xlist( iter_xp );
475           
476            // print item identifier
477            item_print_key( item_xp );
478        }
479
480        printk("\n");
481    }
482}  // end xhtab_display()
Note: See TracBrowser for help on using the repository browser.