source: trunk/kernel/libk/htab.c @ 15

/*
 * 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;
}