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

Redefine the PIC device API.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.