/* * xhtab.h - Remote access embedded hash table definition. * * Author Alain Greiner (2016,2017,2018,2019) * * 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 #include #include #include /////////////////////////////////////////////////////////////////////////////////////////// // 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 xlist. // - an item is uniquely identified by a , that is a item specific pointer, // that can be a - for example - a char* defining the item "name". // - From the value, the hash table uses an item type specific index_from_key() // function, to compute an value, defining a subset of registered items. // - to discriminate between items that have the same , the hash table makes // an associative search on the key in subset, using the item type specific // item_match_key() function. // - 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 xlist implementing a subset. // 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 128 // number of subsets /****************************************************************************************** * Here are 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 currently supported item types. * - The XHTAB_DENTRY_TYPE is used to implement the set of directory entries for a * directory inode : the "children" inode field is an embedded xhtab. *****************************************************************************************/ 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_busylock_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 item found / return false if item not found. *****************************************************************************************/ bool_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_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_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_ */