/*
 * htab.h - Generic embedded hash table definition.
 * 
 * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
 *            Mohamed Lamine Karaoui (2015)
 *            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 _HTAB_H_
#define _HTAB_H_

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

/****************************************************************************************
 * This file define a generic, embedded, hash table.
 * The main goal is to provide fast retrieval for a large number of items of same type
 * in a given cluster. 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 the <key>, the hash table uses an user defined ht_hash() 
 *   function, to compute an <index> value, defining a subset of registered
 *   items, to restrict the associative search.
 * - As several items can have the same <index>, the hash table uses the user defined
 *   ht_compare() function for a final associative search on the subset.
 * - Each registered item is a structure, that must contain an embedded ht_node_t,
 *   This ht_node_t is part of a rooted double linked list, and contains the <index>.
 * - Finally, the hash table returns a pointer on the embedded ht_node_t, and the
 *   pointer on the searched item can be obtained by a simple offset.
 ***************************************************************************************/

/****************************************************************************************
 * This define the generic, user defined, function types.
 ***************************************************************************************/

struct ht_node_s;

typedef bool_t     ht_compare_t( struct ht_node_s * node , void * key );
typedef uint32_t   ht_hash_t( void * key );

/****************************************************************************************
 * This structure defines the hash table header.
 ***************************************************************************************/

typedef struct ht_header_s
{
	uint32_t        nb_buckets;   /*! number of subsets (one linked list per subset)   */
	ht_hash_t     * hash;         /*! user defined hash function                       */ 
	ht_compare_t  * compare;      /*! user defined compare function                    */
	list_entry_t  * buckets;      /*! array of root of partial lists of ht_node_t      */
}
ht_header_t;

/****************************************************************************************
 * This structure defines one hash table node.
 ***************************************************************************************/

typedef struct ht_node_s
{
	uint32_t     index;           /*! integer value computed from the key              */
	list_entry_t list;	          /*! member of list of all nodes in same bucket       */
}
ht_node_t;

/****************************************************************************************
 * This function initialises one hash table node.
 ****************************************************************************************
ccccc
 ***************************************************************************************/
void ht_node_init( ht_node_t * node );

/****************************************************************************************
 * This function allocates memory for the buckets array, and initializes the header.
 * The number of buckets (number of subsets) is PAGE_SIZE / sizeof(list_entry_t)
 ****************************************************************************************
 * @ header     : pointer on the hash table header.
 * @ ht_hash    : pointer on the user defined hash function.
 * @ ht_compare : pointer on the user defined compare function.
 * @ return 0 if success / return ENOMEM if error.
 ***************************************************************************************/
error_t ht_header_init( ht_header_t  * header,
                        ht_hash_t    * ht_hash,
                        ht_compare_t * ht_compare );

/****************************************************************************************
 * This function register a new node in the hash table.
 ****************************************************************************************
 * @ header     : pointer on the hash table header.
 * @ node       : pointer on the node to be registered (embedded in item).
 * @ key        : pointer on the item identifier.
 * @ return 0 if success / return EINVAL if node already registered...
 ***************************************************************************************/
error_t ht_insert( ht_header_t * header,
                   ht_node_t   * node,
                   void        * key );

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

/****************************************************************************************
 * This function remove an item from the hash table.
 ****************************************************************************************
 * @ header     : pointer on the hash table header.
 * @ key        : pointer on the item identifier.
 * @ return 0 if success / return EINVAL if not found.
 ***************************************************************************************/
error_t ht_remove( ht_header_t * header,
                   void        * key );

#endif /* _HTABLE_H_ */