/*
 * htable.c - Generic, embedded hash table implementation.
 * 
 * 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
 */

#include <htable.h>
#include <kmem.h>
#include <ppm.h>

///////////////////////////////////////////////
error_t ht_header_init( ht_header_t  * header,
                        ht_hash_t    * hash,
                        ht_compare_t * compare )
{
	uint32_t     i;
	kmem_req_t   req;
	page_t     * page;

	req.type  = KMEM_PAGE;
	req.size  = 0;
	req.flags = AF_ZERO;
	page      = kmem_alloc( &req );
	
	if( page == NULL ) return ENOMEM;

	header->nb_buckets = CONFIG_PPM_PAGE_SIZE/sizeof( list_entry_t );
	header->buckets    = ppm_page2base( page );
	header->hash       = hash;
	header->compare    = compare;

	for( i=0 ; i < header->nb_buckets ; i++ )
	{
		list_root_init( &header->buckets[i] );
	}

	return 0;
}

////////////////////////////////////////
error_t ht_node_init( ht_node_t * node )
{
	node->index = (uint32_t) -1;
	list_entry_init( &node->list );

	return 0;
}

/////////////////////////////////////////////////
static ht_node_t * __hfind( ht_header_t * header,
                            uint32_t      index,
                            void        * key)
{
	ht_node_t    * node;
	list_entry_t * root,
    list_entry_t * iter;

	root = &header->buckets[index % header->nb_buckets];

	LIST_FOREACH( root , iter )
	{
		node = LIST_ELEMENT( iter , ht_node_t , list );
		if( node->index == index )
		{
			if( header->compare( node , key ) ) return node;
		}
	}

	return NULL;
}

//////////////////////////////////////////
ht_node_t * ht_find( ht_header_t * header,
                     void        * key )
{
	uint32_t index = header->hash( key );

	return __ht_find( header , index , key );
}

////////////////////////////////////////
error_t ht_insert( ht_header_t * header,
                   ht_node_t   * node,
                   void        * key )
{
	uint32_t index = header->hash( key );

	ht_node_t * node = __ht_find( header , index , key );

	if( node != NULL ) return EINVAL;

	list_entry_t * root = &header->buckets[index % header->nb_buckets];

	list_add_first( root , &node->list);

	node->index = index;

	return 0;
}

////////////////////////////////////////
error_t ht_remove( ht_header_t * header,
                   void        * key )
{
	uint32_t index = header->hash( key );

	ht_node_t * node = __ht_find( header , index , key );

	if( node == NULL ) return EINVAL;

	list_unlink( &node->list );

	return 0;
}