source: trunk/kernel/libk/xhtab.h @ 517

/*
 * xhtab.h - Remote access embedded hash table definition.
 * 
 * Author     Alain Greiner  (2016,2017,2018)
 *
 * Copyright (c) UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH.
 *
 * ALMOS-MKH is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2.0 of the License.
 *
 * ALMOS-MKH is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _XHTAB_H_
#define _XHTAB_H_

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <remote_rwlock.h>
#include <xlist.h>


///////////////////////////////////////////////////////////////////////////////////////////
// This file define a generic, embedded, remotely accessible hash table.
//
// It can be accessed by any thread, running in any cluster.
// It is generic as it can be used to register various types of items.
// The main goal is to speedup search by key in a large number of items of same type.
// For this purpose the set of all registered items is split in several subsets.
// Each subset is organised as an embedded double linked lists.
// - an item is uniquely identified by a <key>, that is a single uint32_t value. 
// - From the <key> value, the hash table uses an item type specific xhtab_index() 
//   function, to compute an <index> value, defining a subset of registered items.
// - to discriminate between items that have the same <index>, the hash table makes
//   an associative search on the key in subset.
// - Each registered item is a structure, that must contain an embedded xlist_entry,
//   that is part of the xlist implementing the subset. 
//
// For all registered items, a total order is defined by the increasing index values, 
// and for each index value, by the position in the partial xlist. 
// This order is used by the two functions xhtab_get_first() and xhtab_get_next(), that
// are used to scan all registered items. The two "current_index" and "current_xlist_xp"
// fields in the hash table header register the current item during a scan.
//
// Implementation Note:
// To inroduce a new item type, you must define the four item-type-specific
// functions specified below, and you must update the xhtab_init() function
// and the xhtab_item_type_t.
///////////////////////////////////////////////////////////////////////////////////////////

#define XHASHTAB_SIZE    8   // number of subsets

/******************************************************************************************
 * This define the four item_type_specific function prototypes that must be defined
 * for each item type.
 *****************************************************************************************/

typedef  bool_t    (item_match_key_t)   ( xptr_t item_xp , void * key );
typedef  xptr_t    (item_from_xlist_t)  ( xptr_t xlist_xp );
typedef  uint32_t  (index_from_key_t)   ( void * key );
typedef  void      (item_print_key_t)   ( xptr_t item_xp );

/******************************************************************************************
 * This define the supported item types.
 *****************************************************************************************/

typedef enum
{
    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */ 
}
xhtab_item_type_t;

/******************************************************************************************
 * This structure define the root of the remotely accessible hash table. 
 *****************************************************************************************/

typedef struct xhtab_s
{
        xlist_entry_t       roots[XHASHTAB_SIZE];  /*! array of roots of xlist               */
    index_from_key_t  * index_from_key;        /*! item specific function pointer        */
    item_match_key_t  * item_match_key;        /*! item specific function pointer        */
    item_from_xlist_t * item_from_xlist;       /*! item specific function pointer        */
    item_print_key_t  * item_print_key;        /*! item specific function pointer        */
    uint32_t            items;                 /*! number of registered items            */
    remote_rwlock_t     lock;                  /*! lock protecting hash table accesses   */
    uint32_t            current_index;         /*! current item subset index             */
    xptr_t              current_xlist_xp;      /*! xptr on current item xlist entry      */
}
xhtab_t;

/******************************************************************************************
 * This function initializes an empty hash table (zero registered item).
 * The initialisation must be done by a thread running in cluster containing the table.
 ******************************************************************************************
 * @ xhtab    : local pointer on local xhtab to be initialized.
 * @ type     : item type (see above).
 *****************************************************************************************/
void xhtab_init( xhtab_t           * xhtab,
                 xhtab_item_type_t   type );

/******************************************************************************************
 * This function safely register an item in the hash table, using the lock protecting it.
 ******************************************************************************************
 * @ xhtab_xp   : extended pointer on hash table.
 * @ key        : local pointer on item identifier.
 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
 * @ return 0 if success / return EINVAL if item already registered.
 *****************************************************************************************/
error_t xhtab_insert( xptr_t   xhtab_xp,
                      void   * key,
                      xptr_t   xlist_xp );

/******************************************************************************************
 * This function safely remove an item from the hash table, using the lock protecting it.
 ******************************************************************************************
 * @ xhtab_xp   : extended pointer on hash table.
 * @ key        : local pointer on item identifier.
 * @ xlist_xp   : extended pointer on xlist_entry embedded in item to be removed.
 * @ return 0 if success / return EINVAL if item not found.
 *****************************************************************************************/
error_t xhtab_remove( xptr_t   xhtab_xp,
                      void   * key,
                      xptr_t   xlist_entry_xp );

/******************************************************************************************
 * This function search an item by its key in hash table, using the lock protecting it.
 ******************************************************************************************
 * @ xhtab_xp  : extended pointer on hash table.
 * @ key       : local pointer on searched item identifier.
 * @ return extended pointer on the searched item if found / XPTR_NULL if not found.
 *****************************************************************************************/
xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
                      void    * key );

/******************************************************************************************
 * This blocking function takes the lock protecting exclusive access to the hash table. 
 * It should be called before the xhtab_get_first() & xhtab_get_next() functions.
 ******************************************************************************************
 * @ xhtab_xp  : extended pointer on hash table.
 *****************************************************************************************/
void xhtab_read_lock( xptr_t xhtab_xp );

/******************************************************************************************
 * This function releases the lock protecting exclusive access to the hash table. 
 * It should be called after the xhtab_get_first() & xhtab_get_next() functions.
 ******************************************************************************************
 * @ xhtab_xp  : extended pointer on hash table.
 *****************************************************************************************/
void xhtab_read_unlock( xptr_t xhtab_xp );

/******************************************************************************************
 * This function returns an extended pointer on the first item registered in hash table,
 * and register this pointer in the hash table header.
 * The lock protecting the hash table must have been previously taken by the caller.
 ******************************************************************************************
 * @ xhtab_xp  : extended pointer on hash table.
 * @ return extended pointer on item if success / XPTR_NULL if not found.
 *****************************************************************************************/
xptr_t xhtab_get_first( xptr_t xhtab_xp );

/******************************************************************************************
 * This function returns an extended pointer on item following the currently pointed
 * item in the hash table header.
 * The lock protecting the hash table must have been previously taken by the caller.
 ******************************************************************************************
 * @ xhtab_xp  : extended pointer on hash table.
 * @ return extended pointer on item if success / XPTR_NULL if not found.
 *****************************************************************************************/
xptr_t xhtab_get_next( xptr_t xhtab_xp );

/******************************************************************************************
 * This function displays the full content of an xhtab.
 ******************************************************************************************
 * @ xhtab_xp  : extended pointer on hash table.
 *****************************************************************************************/
void xhtab_display( xptr_t  xhtab_xp );

#endif  /* _XHTAB_H_ */