/* * xhtab.h - Remote access embedded hash table definition. * * Author Alain Greiner (2016) * * 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, hash table that can be remotely accessed by * any thread running in any cluster. * The main goal is to speedup search by key in a set of items identified by their key. * For this purpose the set of all registered items is split in several subsets: * Each subset is organised an embedded double linked lists. * - an item is uniquely identified by a , that can be a single uint32_t, * a name (character string), or a more complex structure. * - From the , the hash table uses an item type specific "xhtab_index()" function, * to compute an value, defining a subset of registered items. * - to discriminate between items that have the same , the hash table uses another * item type specific "xhtab_compare()" function for the associative search in subset. * - Each registered item is a structure, that must contain an embedded xlist_entry, * that is part of the xlist implementing the subset. * - The xhtab header contains an array indexed by and containing the roots * of the various xlists implementing the subsets. * pointer on the searched item can be obtained by a simple offset. * Implementation note: * to use this generic infrastructure for a new type of item, you must define a new * type in the xhtan_item_type_t" below, and to define the two associated * "xhtab_compare() and xhtab_index(). *****************************************************************************************/ #define HASHTAB_SIZE 64 // number of subsets /****************************************************************************************** * These typedef define the generic xhtab_compare() and xhtab_index() function prototypes. * It must exist a specific couple of functions for each item type. * @ entry_xp : extended pointer on an xlist_entry_t in a partial xlist. * @ key : local pointer on the searched item key. * @ item_xp : buffer to store extended pointer on found item. *****************************************************************************************/ typedef bool_t xhtab_compare_t( xptr_t entry_xp , void * key , xptr_t * item_xp ); typedef uint32_t xhtab_index_t( void * key ); /****************************************************************************************** * This define the supported item types. *****************************************************************************************/ typedef enum { XHTAB_DENTRY_TYPE = 1, /*! item is a vfs_dentry_t */ XHTAB_INODE_TYPE = 2, /*! item is a vfs_inode_t */ } xhtab_item_type_t; /****************************************************************************************** * This structure define the root of a generic, remote accessible, hash table. *****************************************************************************************/ typedef struct xhtab_s { xlist_entry_t roots[HASHTAB_SIZE]; /*! array of roots of xlist */ xhtab_compare_t * compare; /*! item specific index function */ xhtab_index_t * index; /*! item specific compare function */ uint32_t items; /*! number of registered items */ remote_rwlock_t lock; /*! lock protecting hash table modifs */ } xhtab_t; /****************************************************************************************** * This function initializes an empty hash table (zero children). * 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, uint32_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. *****************************************************************************************/ void xhtab_register( 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. *****************************************************************************************/ void xhtab_remove( xptr_t xhtab_xp, void * key ); /****************************************************************************************** * 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 ); /************************ vfs_dentry_t specific functions ******************************/ /****************************************************************************************** * This function compute the hash index from the key, when the item is a vhs_dentry_t. ****************************************************************************************** * @ key : local pointer on dentry name. * @ return the index value, from 0 to (HASHTAB_SIZE - 1) *****************************************************************************************/ uint32_t xhtab_dentry_index( void * key ); /****************************************************************************************** * This function check the key value for a given item, when the item is a vhs_dentry_t. ****************************************************************************************** * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t. * @ key : local pointer on searched dentry name. * @ return true if the item name matches the searched name. *****************************************************************************************/ bool_t xhtab_dentry_compare( xptr_t xlist_xp, void * key, xptr_t * item_xp ); /************************ vfs_inode_t specific functions *******************************/ /****************************************************************************************** * This function compute the hash index from the key, when the item is a vhs_inode_t. ****************************************************************************************** * @ key : local pointer on dentry name. * @ return the index value, from 0 to (HASHTAB_SIZE - 1) *****************************************************************************************/ uint32_t xhtab_inode_index( void * key ); /****************************************************************************************** * This function check the key value for a given item, when the item is a vhs_inode_t. ****************************************************************************************** * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t. * @ key : local pointer on searched dentry name. * @ return true if the item name matches the searched name. *****************************************************************************************/ bool_t xhtab_inode_compare( xptr_t xlist_xp, void * key, xptr_t * item_xp ); #endif /* _XHTAB_H_ */