source: trunk/kernel/libk/htab.h @ 185

/*
 * htab.h - Generic embedded hash table definition.
 * 
 * Authors  Alain Greiner (2016,2017)
 *
 * 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 _HTAB_H_
#define _HTAB_H_

#include <hal_types.h>
#include <rwlock.h>
#include <list.h>

/////////////////////////////////////////////////////////////////////////////////////////
// This file define a generic, embedded, hash table.
//
// It can only be accessed by threads running in the local cluster.
// It is generic as it can be used to register various types of items.
// The main goal is to provide fast retrieval for 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 a double linked lists.
// - an item is uniquely identified by a <key>, that can be a single uint32_t, 
//   a character string, or a more complex structure.
// - From the pointer on <key>, we use an item type specific htab_index() function,
//   to compute an <index> value, defining a subset of registered items.
// - As several items can have the same <index>, we use the item type specific defined
//   htab_scan() function for a final associative search on the subset.
// - Each registered item is a structure, that must contain an embedded list_entry_t,
//   that is part of a rooted double linked list.
//
// Implementation Note: for each supported item type ***, you must define the two
//                      htab_***_index() and htab_***_scan() functions, and
//                      update the htab_init() function.
/////////////////////////////////////////////////////////////////////////////////////////

#define HASHTAB_SIZE    64   // number of subsets

/****************************************************************************************
 * These typedef define the two item type specific function prototypes.
 ***************************************************************************************/

struct htab_s;

typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );

typedef uint32_t   htab_index_t( void * key );

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

typedef enum
{
    HTAB_INODE_TYPE = 1,                     /*! item is a vfs_inode_t                 */
}
htab_item_type_t;

/****************************************************************************************
 * This structure defines the the root of a local hash table.
 ***************************************************************************************/

typedef struct htab_s
{
        list_entry_t      roots[HASHTAB_SIZE];  /*! array of roots of partial lists        */
        htab_index_t    * index;                /*! item type  specific function           */
        htab_scan_t     * scan;                 /*! item type specific function            */
    uint32_t          items;                /*! number of registered items             */
    rwlock_t          lock;                 /*! lock protecting hash table accesses    */
}
htab_t;

/****************************************************************************************
 * This function initialises an empty hash table (zero registered item).
 ****************************************************************************************
 * @ htab       : pointer on hash table.
 * @ type       : item type.
 ***************************************************************************************/
void htab_init( htab_t           * htab,
                htab_item_type_t   type );

/****************************************************************************************
 * This function register a new item in the hash table.
 ****************************************************************************************
 * @ htab       : pointer on the hash table.
 * @ key        : pointer on the item identifier.
 * @ list_entry : pointer on list_entry_t embedded in item to be registered.
 * @ return 0 if success / return EINVAL if item already registered.
 ***************************************************************************************/
error_t htab_insert( htab_t       * htab,
                     void         * key,
                     list_entry_t * list_entry );

/****************************************************************************************
 * This function remove an item from the hash table.
 ****************************************************************************************
 * @ header     : pointer on the hash table.
 * @ key        : pointer on the item identifier.
 * @ list_entry : pointer on list_entry_t embedded in item to be removed.
 * @ return 0 if success / return EINVAL if item not found.
 ***************************************************************************************/
error_t htab_remove( htab_t       * htab,
                     void         * key,
                     list_entry_t * list_entry );

/****************************************************************************************
 * This function returns a pointer on the node embedded in the item 
 * identified by its key.
 ****************************************************************************************
 * @ htab      : pointer on the hash table.
 * @ key       : pointer on the item identifier.
 * @ return pointer on item if found / return NULL if not found.
 ***************************************************************************************/
void * htab_lookup( htab_t * htab,
                    void   * key);


#endif /* _HTAB_H_ */