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/htab.h

    r1 r23  
    22 * htab.h - Generic embedded hash table definition.
    33 *
    4  * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
    5  *            Mohamed Lamine Karaoui (2015)
    6  *            Alain Greiner (2016)
     4 * Authors  Alain Greiner (2016,2017)
    75 *
    86 * Copyright (c) UPMC Sorbonne Universites
    … …  
    2927
    3028#include <hal_types.h>
     29#include <rwlock.h>
    3130#include <list.h>
    3231
     32/////////////////////////////////////////////////////////////////////////////////////////
     33// This file define a generic, embedded, hash table.
     34//
     35// It can only be accessed by threads running in the local cluster.
     36// It is generic as it can be used to register various types of items.
     37// The main goal is to provide fast retrieval for a large number of items of same type.
     38// For this purpose the set of all registered items is split in several subsets.
     39// Each subset is organised as a double linked lists.
     40// - an item is uniquely identified by a <key>, that can be a single uint32_t,
     41//   a character string, or a more complex structure.
     42// - From the pointer on <key>, we use an item type specific htab_index() function,
     43//   to compute an <index> value, defining a subset of registered items.
     44// - As several items can have the same <index>, we use the item type specific defined
     45//   htab_scan() function for a final associative search on the subset.
     46// - Each registered item is a structure, that must contain an embedded list_entry_t,
     47//   that is part of a rooted double linked list.
     48//
     49// Implementation Note: for each supported item type ***, you must define the two
     50//                      htab_***_index() and htab_***_scan() functions, and
     51//                      update the htab_init() function.
     52/////////////////////////////////////////////////////////////////////////////////////////
     53
     54#define HASHTAB_SIZE    64   // number of subsets
     55
    3356/****************************************************************************************
    34  * This file define a generic, embedded, hash table.
    35  * The main goal is to provide fast retrieval for a large number of items of same type
    36  * in a given cluster. For this purpose the set of all registered items is split
    37  * in several subsets. Each subset is organised as a double linked lists.
    38  * - an item is uniquely identified by a <key>, that can be a single uint32_t,
    39  *   a character string, or a more complex structure.
    40  * - From the pointer on the <key>, the hash table uses an user defined ht_hash()
    41  *   function, to compute an <index> value, defining a subset of registered
    42  *   items, to restrict the associative search.
    43  * - As several items can have the same <index>, the hash table uses the user defined
    44  *   ht_compare() function for a final associative search on the subset.
    45  * - Each registered item is a structure, that must contain an embedded ht_node_t,
    46  *   This ht_node_t is part of a rooted double linked list, and contains the <index>.
    47  * - Finally, the hash table returns a pointer on the embedded ht_node_t, and the
    48  *   pointer on the searched item can be obtained by a simple offset.
     57 * These typedef define the two item type specific function prototypes.
    4958 ***************************************************************************************/
    5059
     60struct htab_s;
     61
     62typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );
     63
     64typedef uint32_t   htab_index_t( void * key );
     65
    5166/****************************************************************************************
    52  * This define the generic, user defined, function types.
     67 * This define the supported item types.
    5368 ***************************************************************************************/
    5469
    55 struct ht_node_s;
    56 
    57 typedef bool_t     ht_compare_t( struct ht_node_s * node , void * key );
    58 typedef uint32_t   ht_hash_t( void * key );
     70typedef enum
     71{
     72    HTAB_INODE_TYPE = 1,                     /*! item is a vfs_inode_t                 */
     73}
     74htab_item_type_t;
    5975
    6076/****************************************************************************************
    61  * This structure defines the hash table header.
     77 * This structure defines the the root of a local hash table.
    6278 ***************************************************************************************/
    6379
    64 typedef struct ht_header_s
     80typedef struct htab_s
    6581{
    66         uint32_t        nb_buckets;   /*! number of subsets (one linked list per subset)   */
    67         ht_hash_t     * hash;         /*! user defined hash function                       */
    68         ht_compare_t  * compare;      /*! user defined compare function                    */
    69         list_entry_t  * buckets;      /*! array of root of partial lists of ht_node_t      */
     82        list_entry_t      roots[HASHTAB_SIZE];  /*! array of roots of partial lists        */
     83        htab_index_t    * index;                /*! item type  specific function           */
     84        htab_scan_t     * scan;                 /*! item type specific function            */
     85    uint32_t          items;                /*! number of registered items             */
     86    rwlock_t          lock;                 /*! lock protecting hash table accesses    */
    7087}
    71 ht_header_t;
     88htab_t;
    7289
    7390/****************************************************************************************
    74  * This structure defines one hash table node.
     91 * This function initialises an empty hash table (zero registered item).
     92 ****************************************************************************************
     93 * @ htab       : pointer on hash table.
     94 * @ type       : item type.
    7595 ***************************************************************************************/
    76 
    77 typedef struct ht_node_s
    78 {
    79         uint32_t     index;           /*! integer value computed from the key              */
    80         list_entry_t list;                /*! member of list of all nodes in same bucket       */
    81 }
    82 ht_node_t;
     96void htab_init( htab_t           * htab,
     97                htab_item_type_t   type );
    8398
    8499/****************************************************************************************
    85  * This function initialises one hash table node.
     100 * This function register a new item in the hash table.
    86101 ****************************************************************************************
    87 ccccc
     102 * @ htab       : pointer on the hash table.
     103 * @ key        : pointer on the item identifier.
     104 * @ list_entry : pointer on list_entry_t embedded in item to be registered.
     105 * @ return 0 if success / return EINVAL if item already registered.
    88106 ***************************************************************************************/
    89 void ht_node_init( ht_node_t * node );
     107error_t htab_insert( htab_t       * htab,
     108                     void         * key,
     109                     list_entry_t * list_entry );
    90110
    91111/****************************************************************************************
    92  * This function allocates memory for the buckets array, and initializes the header.
    93  * The number of buckets (number of subsets) is PAGE_SIZE / sizeof(list_entry_t)
     112 * This function remove an item from the hash table.
    94113 ****************************************************************************************
    95  * @ header     : pointer on the hash table header.
    96  * @ ht_hash    : pointer on the user defined hash function.
    97  * @ ht_compare : pointer on the user defined compare function.
    98  * @ return 0 if success / return ENOMEM if error.
     114 * @ header     : pointer on the hash table.
     115 * @ key        : pointer on the item identifier.
     116 * @ list_entry : pointer on list_entry_t embedded in item to be removed.
     117 * @ return 0 if success / return EINVAL if item not found.
    99118 ***************************************************************************************/
    100 error_t ht_header_init( ht_header_t  * header,
    101                         ht_hash_t    * ht_hash,
    102                         ht_compare_t * ht_compare );
    103 
    104 /****************************************************************************************
    105  * This function register a new node in the hash table.
    106  ****************************************************************************************
    107  * @ header     : pointer on the hash table header.
    108  * @ node       : pointer on the node to be registered (embedded in item).
    109  * @ key        : pointer on the item identifier.
    110  * @ return 0 if success / return EINVAL if node already registered...
    111  ***************************************************************************************/
    112 error_t ht_insert( ht_header_t * header,
    113                    ht_node_t   * node,
    114                    void        * key );
     119error_t htab_remove( htab_t       * htab,
     120                     void         * key,
     121                     list_entry_t * list_entry );
    115122
    116123/****************************************************************************************
    … …  
    118125 * identified by its key.
    119126 ****************************************************************************************
    120  * @ header     : pointer on the hash table header.
    121  * @ key        : pointer on the item identifier.
    122  * @ return pointer on node if found / return NULL if not found.
     127 * @ htab      : pointer on the hash table.
     128 * @ key       : pointer on the item identifier.
     129 * @ return pointer on item if found / return NULL if not found.
    123130 ***************************************************************************************/
    124 ht_node_t * ht_find( ht_header_t * header,
    125                      void        * key);
     131void * htab_lookup( htab_t * htab,
     132                    void   * key);
    126133
    127 /****************************************************************************************
    128  * This function remove an item from the hash table.
    129  ****************************************************************************************
    130  * @ header     : pointer on the hash table header.
    131  * @ key        : pointer on the item identifier.
    132  * @ return 0 if success / return EINVAL if not found.
    133  ***************************************************************************************/
    134 error_t ht_remove( ht_header_t * header,
    135                    void        * key );
    136134
    137 #endif /* _HTABLE_H_ */
     135#endif /* _HTAB_H_ */
Note: See TracChangeset for help on using the changeset viewer.