Changeset 188 for trunk/kernel/libk


Ignore:
Timestamp:
Jul 12, 2017, 8:12:41 PM (7 years ago)
Author:
alain
Message:

Redefine the PIC device API.

Location:
trunk/kernel/libk
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/kernel/libk/xhtab.c

    r50 r188  
    3535
    3636///////////////////////////////////////////////////////////////////////////////////////////
    37 // Item type specific (static) functions (two functions for each item type).
    38 // - for type <vfs_dentry_t>, identifier is the name field.
    39 ///////////////////////////////////////////////////////////////////////////////////////////
    40 
    41 ///////////////////////////////////////////////////////////////////////////////////////////
    42 // These static functions compute the hash index from the key.
    43 ///////////////////////////////////////////////////////////////////////////////////////////
    44 // @ key      : local pointer on key.
     37// Item type specific functions (three functions for each item type).
     38///////////////////////////////////////////////////////////////////////////////////////////
     39
     40///////////////////////////////////////////////////////////////////////////////////////////
     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.
     43///////////////////////////////////////////////////////////////////////////////////////////
     44// @ key      : local pointer on name.
    4545// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
    4646///////////////////////////////////////////////////////////////////////////////////////////
    47 
    48 /////////////////////////////////////////
    49 uint32_t xhtab_dentry_index( void * key )
     47static uint32_t xhtab_dentry_index_from_key( void * key )
    5048{
    5149        char     * name  = key;
    … …  
    5553        index = index + (*(name++) ^ index);
    5654    }
    57         return index % HASHTAB_SIZE;
     55        return index % XHASHTAB_SIZE;
    5856}
    5957
     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
    6070////////////////////////////////////////////////////////////////////////////////////////////
    61 // These static function are used by xhtab_lookup(), xhtab_insert(), xhtab_remove().
    62 // They scan one sub-list identified by  <index> to find an item  identified by <key>.
    63 // The sub-list is not modified, but the readlock must have been taken by the caller.
     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.
    6473////////////////////////////////////////////////////////////////////////////////////////////
    65 // @ xhtab_xp  : extended pointer on hash table.
    66 // @ index     : index of sub-list to be scanned.
    67 // @ key       : local pointer on item identifier.
    68 // return an extended pointer on item if found / return XPTR_NULL if not found.
     74// @ item_xp   : extended pointer on item.
     75// @ key       : pointer on searched item identifier.
     76// returns true if given name matches directory entry name.
    6977////////////////////////////////////////////////////////////////////////////////////////////
    70 
    71 ////////////////////////////////////////////////////
    72 static xptr_t xhtab_dentry_scan( xptr_t    xhtab_xp,
    73                                  uint32_t  index,
    74                                  void    * key )
     78static bool_t xhtab_dentry_item_match_key( xptr_t item_xp,
     79                                           void    * key )
     80{
     81    vfs_dentry_t * dentry_ptr;
     82    cxy_t          dentry_cxy;
     83
     84    char           name[CONFIG_VFS_MAX_NAME_LENGTH];
     85
     86    // get dentry cluster and local pointer
     87    dentry_cxy = GET_CXY( item_xp );
     88    dentry_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
     89
     90    // make a local copy of directory entry name
     91    hal_remote_strcpy( XPTR( local_cxy , name ) ,
     92                       XPTR( dentry_cxy , &dentry_ptr->name ) );
     93
     94    return( strcmp( name , (char*)key ) == 0 );
     95}
     96                       
     97////////////////////////////////////////////////////////////////////////////////////////
     98//         Generic access functions
     99////////////////////////////////////////////////////////////////////////////////////////
     100
     101//////////////////////////////////////////
     102void xhtab_init( xhtab_t          * xhtab,
     103                 xhtab_item_type_t  type )
     104{
     105        uint32_t i;
     106
     107    // initialize readlock
     108    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
     109
     110    xhtab->items  = 0;
     111
     112    if( type == XHTAB_DENTRY_TYPE )
     113    {
     114        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
     115        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
     116        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
     117    }
     118    else
     119    {
     120        printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ );
     121        hal_core_sleep();
     122    }
     123
     124        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
     125    {
     126                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
     127    } 
     128
     129}  // end xhtab_init()
     130
     131//////////////////////////////////////
     132xptr_t xhtab_scan( xptr_t    xhtab_xp,
     133                   uint32_t  index,
     134                   void    * key )
    75135{
    76136    xptr_t    xlist_xp;                                 // xlist_entry_t (iterator)
     137    xptr_t    item_xp;                                  // associated item
    77138    xhtab_t * xhtab_ptr;                                // hash table local pointer
    78139    cxy_t     xhtab_cxy;                                // hash table cluster
    79     char      local_name[CONFIG_VFS_MAX_NAME_LENGTH];   // local copy of dentry name
    80140
    81141    // get hash table cluster and local pointer
    … …  
    86146    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
    87147    {
    88         // get extended pointer on dentry containing the xlist_entry_t
    89             xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist );
    90 
    91         // get dentry cluster and local pointer
    92         cxy_t          dentry_cxy = GET_CXY( dentry_xp );
    93         vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( dentry_xp );
    94    
    95         // make a local copy of dentry name
    96         hal_remote_memcpy( XPTR( local_cxy  , local_name ) ,
    97                            XPTR( dentry_cxy , dentry_ptr->name ),
    98                            CONFIG_VFS_MAX_NAME_LENGTH  );
    99 
    100         // check matching
    101         if( strcmp( local_name , (char *)key ) == 0 ) return dentry_xp;
     148        // get extended pointer on item containing the xlist entry
     149            item_xp = xhtab_ptr->item_from_xlist( xlist_xp );
     150
     151        // check matching
     152        if( xhtab_ptr->item_match_key( item_xp , key ) ) return item_xp;
    102153    }
    103154
    104155    // No matching item found
    105156    return XPTR_NULL;
    106 }
    107 
    108 ////////////////////////////////////////////////////////////////////////////////////////
    109 //         Generic access functions
    110 ////////////////////////////////////////////////////////////////////////////////////////
    111 
    112 //////////////////////////////////////////
    113 void xhtab_init( xhtab_t          * xhtab,
    114                  xhtab_item_type_t  type )
    115 {
    116         uint32_t i;
    117 
    118     // initialize readlock
    119     remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
    120 
    121     xhtab->items  = 0;
    122 
    123     if( type == XHTAB_DENTRY_TYPE )
    124     {
    125         xhtab->scan  = &xhtab_dentry_scan;
    126         xhtab->index = &xhtab_dentry_index;
    127     }
    128     else
    129     {
    130         printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ );
    131         hal_core_sleep();
    132     }
    133 
    134         for( i=0 ; i < HASHTAB_SIZE ; i++ )
    135     {
    136                 xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
    137     } 
    138157}
    139158
    … …  
    148167
    149168    // compute index from key
    150         uint32_t index = xhtab_ptr->index( key );
     169        uint32_t index = xhtab_ptr->index_from_key( key );
    151170
    152171    // take the lock protecting hash table
    … …  
    154173
    155174    // search a matching item
    156     xptr_t item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
     175    xptr_t item_xp = xhtab_scan( xhtab_xp , index , key );
    157176
    158177    if( item_xp != XPTR_NULL )    // error if found
    … …  
    188207
    189208    // compute index from key
    190         uint32_t index = xhtab_ptr->index( key );
     209        uint32_t index = xhtab_ptr->index_from_key( key );
    191210
    192211    // take the lock protecting hash table
    … …  
    194213
    195214    // get extended pointer on item to remove
    196     xptr_t item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
     215    xptr_t item_xp = xhtab_scan( xhtab_xp , index , key );
    197216
    198217    if( item_xp == XPTR_NULL )    // error if not found
    … …  
    229248
    230249    // compute index from key
    231         uint32_t index = xhtab_ptr->index( key );
     250        uint32_t index = xhtab_ptr->index_from_key( key );
    232251
    233252    // take the lock protecting hash table
    … …  
    235254
    236255    // scan sub-list
    237     item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
     256    item_xp = xhtab_scan( xhtab_xp , index , key );
    238257
    239258    // release the lock protecting hash table
    … …  
    244263}  // end xhtab_lookup()
    245264
    246 
     265///////////////////////////////////////
     266void xhtab_read_lock( xptr_t xhtab_xp )
     267{
     268    // get xhtab cluster and local pointer
     269    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
     270    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
     271
     272    // take the lock protecting hash table
     273    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
     274}
     275
     276/////////////////////////////////////////
     277void xhtab_read_unlock( xptr_t xhtab_xp )
     278{
     279    // get xhtab cluster and local pointer
     280    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
     281    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
     282
     283    // release the lock protecting hash table
     284    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
     285}
     286
     287/////////////////////////////////////////
     288xptr_t xhtab_get_first( xptr_t xhtab_xp )
     289{
     290    uint32_t index;
     291    xptr_t   xlist_xp;
     292    xptr_t   item_xp;
     293    xptr_t   root_xp;
     294
     295    // get xhtab cluster and local pointer
     296    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
     297    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
     298
     299    //loop on subsets
     300    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
     301    {
     302        // get root of subset
     303        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
     304
     305        // get first item
     306        xlist_xp = xlist_next( root_xp , root_xp );
     307
     308        if( xlist_xp != XPTR_NULL )  // first item found
     309        {
     310            // get extended pointer on item containing the xlist entry
     311                item_xp = xhtab_ptr->item_from_xlist( xlist_xp );
     312
     313            // register item in hash table header
     314            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
     315            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
     316
     317            return item_xp;
     318        }
     319    }
     320           
     321    // item not found
     322    return XPTR_NULL;
     323
     324} // end xhtab_get_first()
     325   
     326////////////////////////////////////////
     327xptr_t xhtab_get_next( xptr_t xhtab_xp )
     328{
     329    uint32_t index;
     330    xptr_t   xlist_xp;
     331    xptr_t   item_xp;
     332    xptr_t   root_xp;
     333
     334    uint32_t current_index;
     335    xptr_t   current_xlist_xp;
     336
     337    // get xhtab cluster and local pointer
     338    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
     339    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
     340
     341    // get current item pointers
     342    current_index    = hal_remote_lw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) );
     343    current_xlist_xp = hal_remote_lwd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) );
     344
     345    //loop on subsets
     346    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
     347    {
     348        // get root of subset
     349        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
     350
     351        // get next item
     352        xlist_xp = xlist_next( root_xp , current_xlist_xp );
     353
     354        if( xlist_xp != XPTR_NULL )  // next item found
     355        {
     356            // get extended pointer on item containing the xlist entry
     357                item_xp = xhtab_ptr->item_from_xlist( xlist_xp );
     358
     359            // register item in hash table header
     360            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
     361            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
     362
     363            return item_xp;
     364        }
     365    }
     366           
     367    // item not found
     368    return XPTR_NULL;
     369
     370} // end xhtab_get_next()
     371
     372

  • trunk/kernel/libk/xhtab.h

    r23 r188  
    3838// The main goal is to speedup search by key for a large number of items of same type.
    3939// For this purpose the set of all registered items is split in several subsets.
    40 // Each subset is organised an embedded double linked lists.
    41 // - an item is uniquely identified by a <key>, that can be a single uint32_t,
    42 //   a name (character string), or a more complex structure.
    43 // - From the pointer on <key>, we use an item type specific xhtab_index() function,
     40// Each subset is organised as an embedded double linked lists.
     41// - an item is uniquely identified by a <key>, that is a single uint32_t value.
     42// - From the <key> value,the hash table uses an item type specific xhtab_index() function,
    4443//   to compute an <index> value, defining a subset of registered items.
    45 // - to discriminate between items that have the same <index>, the hash table uses another
    46 //   item type specific "xhtab_scan()" function for the associative search in subset.
     44// - to discriminate between items that have the same <index>, the hash table makes
     45//   an associative search in subset.
    4746// - Each registered item is a structure, that must contain an embedded xlist_entry,
    4847//   that is part of the xlist implementing the subset.
    4948//
    50 // Implementation Note: for each supported item type ***, you must define the two
    51 //                      xhtab_***_index() and xhtab_***_scan() functions, and
    52 //                      update the xhtab_init() function.
     49// A total order is defined for all registered items by the increasing index values,
     50// and for each index value by the position in the partial xlist.
     51// This order is used by the two functions xhtab_get_first() and xhtab_get_next(), that
     52// are used to scan all registered items. The two "current_index" and "current_xlist_xp"
     53// fields in the hash table header register the current item during a scan.
     54//
     55// Implementation Note:
     56// For each supported item type ***, you must define the three item-type-specific
     57// functions specified below, and you must update the xhtab_init() function
     58// and the xhtab_item_type_t.
    5359///////////////////////////////////////////////////////////////////////////////////////////
    5460
    55 #define HASHTAB_SIZE    64   // number of subsets
     61#define XHASHTAB_SIZE    64   // number of subsets
    5662
    5763/******************************************************************************************
    58  * These typedef define the two item type specific function prototypes.
     64 * This define the three item type specific function prototypes.
    5965 *****************************************************************************************/
    6066
    61 typedef  xptr_t    xhtab_scan_t( xptr_t xhtab_xp , uint32_t index , void * key );
    62 
    63 typedef  uint32_t  xhtab_index_t( void * key );
     67typedef  bool_t    xhtab_match_t ( xptr_t item_xp , void * key );
     68typedef  xptr_t    xhtab_item_t  ( xptr_t xlist_xp );
     69typedef  uint32_t  xhtab_index_t ( void * key );
    6470
    6571/******************************************************************************************
    … …  
    7985typedef struct xhtab_s
    8086{
    81         xlist_entry_t      roots[HASHTAB_SIZE];   /*! array of roots of xlist                */
    82     xhtab_index_t    * index;                 /*! item specific function                 */
    83     xhtab_scan_t     * scan;                  /*! item specific function                 */
     87        xlist_entry_t      roots[XHASHTAB_SIZE];  /*! array of roots of xlist                */
     88    xhtab_index_t    * index_from_key;        /*! item specific function                 */
     89    xhtab_match_t    * item_match_key;        /*! item specific function                 */
     90    xhtab_item_t     * item_from_xlist;       /*! item specific function                 */
    8491    uint32_t           items;                 /*! number of registered items             */
    8592    remote_rwlock_t    lock;                  /*! lock protecting hash table accesses    */
     93    uint32_t           current_index;         /*! current item subset index              */
     94    xptr_t           * current_xlist_xp;      /*! xptr on current item xlist entry       */
    8695}
    8796xhtab_t;
    … …  
    131140                      void    * key );
    132141
     142/******************************************************************************************
     143 * This blocking function takes the lock protecting exclusive access to the hash table.
     144 * It should be called before the xhtab_get_first() & xhtab_get_next() functions.
     145 ******************************************************************************************
     146 * @ xhtab_xp  : extended pointer on hash table.
     147 *****************************************************************************************/
     148void xhtab_read_lock( xptr_t xhtab_xp );
     149
     150/******************************************************************************************
     151 * This function releases the lock protecting exclusive access to the hash table.
     152 * It should be called after the xhtab_get_first() & xhtab_get_next() functions.
     153 ******************************************************************************************
     154 * @ xhtab_xp  : extended pointer on hash table.
     155 *****************************************************************************************/
     156void xhtab_read_unlock( xptr_t xhtab_xp );
     157
     158/******************************************************************************************
     159 * This function returns an extended pointer on the first item registered in hash table,
     160 * and register this pointer in the hash table header.
     161 * The lock protecting the hash table must have been previously taken by the caller.
     162 ******************************************************************************************
     163 * @ xhtab_xp  : extended pointer on hash table.
     164 * @ return extended pointer on item if success / XPTR_NULL if not found.
     165 *****************************************************************************************/
     166xptr_t xhtab_get_first( xptr_t xhtab_xp );
     167
     168/******************************************************************************************
     169 * This function returns an extended pointer on item following the currently pointed
     170 * item in the hash table header.
     171 * The lock protecting the hash table must have been previously taken by the caller.
     172 ******************************************************************************************
     173 * @ xhtab_xp  : extended pointer on hash table.
     174 * @ return extended pointer on item if success / XPTR_NULL if not found.
     175 *****************************************************************************************/
     176xptr_t xhtab_get_next( xptr_t xhtab_xp );
     177
     178
    133179
    134180#endif  /* _XHTAB_H_ */
Note: See TracChangeset for help on using the changeset viewer.