Ignore:
Timestamp:
Jun 18, 2017, 10:06:41 PM (6 years ago)
Author:
alain
Message:

Introduce syscalls.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/kernel/libk/xhtab.h

    r14 r23  
    22 * xhtab.h - Remote access embedded hash table definition.
    33 *
    4  * Author     Alain Greiner          (2016)
     4 * Author     Alain Greiner  (2016,2017)
    55 *
    66 * Copyright (c) UPMC Sorbonne Universites
    … …  
    3131
    3232
    33 /******************************************************************************************
    34  * This file define a generic, embedded, hash table that can be remotely accessed by
    35  * any thread running in any cluster.
    36  * The main goal is to speedup search by key in a set of items identified by their key.
    37  * For this purpose the set of all registered items is split in several subsets:
    38  * Each subset is organised an embedded double linked lists.
    39  * - an item is uniquely identified by a <key>, that can be a single uint32_t,
    40  *   a name (character string), or a more complex structure.
    41  * - From the <key>, the hash table uses an item type specific "xhtab_index()" function,
    42  *   to compute an <index> value, defining a subset of registered items.
    43  * - to discriminate between items that have the same <index>, the hash table uses another
    44  *   item type specific "xhtab_compare()" function for the associative search in subset.
    45  * - Each registered item is a structure, that must contain an embedded xlist_entry,
    46  *   that is part of the xlist implementing the subset.
    47  * - The xhtab header contains an array indexed by <index> and containing the roots
    48  *   of the various xlists implementing the subsets.
    49  *   pointer on the searched item can be obtained by a simple offset.
    50  * Implementation note:
    51  * to use this generic infrastructure for a new type of item, you must define a new
    52  * type in the xhtan_item_type_t" below, and to define the two  associated
    53  * "xhtab_compare() and xhtab_index().
    54  *****************************************************************************************/
     33///////////////////////////////////////////////////////////////////////////////////////////
     34// This file define a generic, embedded, remotely accessible hash table.
     35//
     36// It can be accessed by any thread, running in any cluster.
     37// It is generic as it can be used to register various types of items.
     38// The main goal is to speedup search by key for a large number of items of same type.
     39// 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,
     44//   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.
     47// - Each registered item is a structure, that must contain an embedded xlist_entry,
     48//   that is part of the xlist implementing the subset.
     49//
     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.
     53///////////////////////////////////////////////////////////////////////////////////////////
    5554
    5655#define HASHTAB_SIZE    64   // number of subsets
    5756
    5857/******************************************************************************************
    59  * These typedef define the generic xhtab_compare() and xhtab_index() function prototypes.
    60  * It must exist a specific couple of functions for each item type.
    61  * @ entry_xp : extended pointer on an xlist_entry_t in a partial xlist.
    62  * @ key      : local pointer on the searched item key.
    63  * @ item_xp  : buffer to store extended pointer on found item.
     58 * These typedef define the two item type specific function prototypes.
    6459 *****************************************************************************************/
    6560
    66 typedef  bool_t    xhtab_compare_t( xptr_t entry_xp , void * key , xptr_t * item_xp );
     61typedef  xptr_t    xhtab_scan_t( xptr_t xhtab_xp , uint32_t index , void * key );
     62
    6763typedef  uint32_t  xhtab_index_t( void * key );
    6864
    … …  
    7369typedef enum
    7470{
    75     XHTAB_DENTRY_TYPE = 1,                   /*! item is a vfs_dentry_t                  */
    76     XHTAB_INODE_TYPE  = 2,                   /*! item is a vfs_inode_t                   */
     71    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */
    7772}
    7873xhtab_item_type_t;
    7974
    8075/******************************************************************************************
    81  * This structure define the root of a generic, remote accessible, hash table.
     76 * This structure define the root of the remote accessible hash table.
    8277 *****************************************************************************************/
    8378
    … …  
    8580{
    8681        xlist_entry_t      roots[HASHTAB_SIZE];   /*! array of roots of xlist                */
    87     xhtab_compare_t  * compare;               /*! item specific index function           */
    88     xhtab_index_t    * index;                 /*! item specific compare function         */
     82    xhtab_index_t    * index;                 /*! item specific function                 */
     83    xhtab_scan_t     * scan;                  /*! item specific function                 */
    8984    uint32_t           items;                 /*! number of registered items             */
    90     remote_rwlock_t  lock;                  /*! lock protecting hash table modifs      */
     85    remote_rwlock_t    lock;                  /*! lock protecting hash table accesses    */
    9186}
    9287xhtab_t;
    9388
    9489/******************************************************************************************
    95  * This function initializes an empty hash table (zero children).
     90 * This function initializes an empty hash table (zero registered item).
    9691 * The initialisation must be done by a thread running in cluster containing the table.
    9792 ******************************************************************************************
    … …  
    9994 * @ type    : item type (see above).
    10095 *****************************************************************************************/
    101 void xhtab_init( xhtab_t * xhtab,
    102                  uint32_t  type );
     96void xhtab_init( xhtab_t           * xhtab,
     97                 xhtab_item_type_t   type );
    10398
    10499/******************************************************************************************
    … …  
    108103 * @ key        : local pointer on item identifier.
    109104 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
     105 * @ return 0 if success / return EINVAL if item already registered.
    110106 *****************************************************************************************/
    111 void xhtab_register( xptr_t   xhtab_xp,
    112                      void   * key,
    113                      xptr_t   xlist_xp );
     107error_t xhtab_insert( xptr_t   xhtab_xp,
     108                      void   * key,
     109                      xptr_t   xlist_xp );
    114110
    115111/******************************************************************************************
    116112 * This function safely remove an item from the hash table, using the lock protecting it.
    117113 ******************************************************************************************
    118  * @ xhtab_xp : extended pointer on hash table.
    119  * @ key      : local pointer on item identifier.
     114 * @ xhtab_xp       : extended pointer on hash table.
     115 * @ key            : local pointer on item identifier.
     116 * @ xlist_entry_xp : extended pointer on xlist_entry embedded in item to be removed.
     117 * @ return 0 if success / return EINVAL if item not found.
    120118 *****************************************************************************************/
    121 void xhtab_remove( xptr_t   xhtab_xp,
    122                    void   * key );
     119error_t xhtab_remove( xptr_t   xhtab_xp,
     120                      void   * key,
     121                      xptr_t   xlist_entry_xp );
    123122
    124123/******************************************************************************************
    … …  
    133132
    134133
    135 /************************  vfs_dentry_t specific functions  ******************************/
    136 
    137 /******************************************************************************************
    138  * This function compute the hash index from the key, when the item is a vhs_dentry_t.
    139  ******************************************************************************************
    140  * @ key      : local pointer on dentry name.
    141  * @ return the index value, from 0 to (HASHTAB_SIZE - 1)
    142  *****************************************************************************************/
    143 uint32_t xhtab_dentry_index( void * key );
    144 
    145 /******************************************************************************************
    146  * This function check the key value for a given item, when the item is a vhs_dentry_t.
    147  ******************************************************************************************
    148  * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t.
    149  * @ key      : local pointer on searched dentry name.
    150  * @ return true if the item name matches the searched name.
    151  *****************************************************************************************/
    152 bool_t xhtab_dentry_compare( xptr_t   xlist_xp,
    153                              void   * key,
    154                              xptr_t * item_xp );
    155 
    156 
    157 /************************  vfs_inode_t specific functions  *******************************/
    158 
    159 /******************************************************************************************
    160  * This function compute the hash index from the key, when the item is a vhs_inode_t.
    161  ******************************************************************************************
    162  * @ key      : local pointer on dentry name.
    163  * @ return the index value, from 0 to (HASHTAB_SIZE - 1)
    164  *****************************************************************************************/
    165 uint32_t xhtab_inode_index( void * key );
    166 
    167 /******************************************************************************************
    168  * This function check the key value for a given item, when the item is a vhs_inode_t.
    169  ******************************************************************************************
    170  * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t.
    171  * @ key      : local pointer on searched dentry name.
    172  * @ return true if the item name matches the searched name.
    173  *****************************************************************************************/
    174 bool_t xhtab_inode_compare( xptr_t   xlist_xp,
    175                             void   * key,
    176                             xptr_t * item_xp );
    177 
    178134#endif  /* _XHTAB_H_ */
Note: See TracChangeset for help on using the changeset viewer.