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

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

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_special.h>
#include <htab.h>
#include <busylock.h>
#include <list.h>
#include <printk.h>
#include <vfs.h>


///////////////////////////////////////////////////////////////////////////////////////////
//    Item type specific (static) functions (two functions for each item type).
// Example below if for <bloup_t> type, where the identifier is an uint32_t field. 
///////////////////////////////////////////////////////////////////////////////////////////

typedef struct bloup_s
{
    uint32_t       key;
    list_entry_t   list;
}
bloup_t;

///////////////////////////////////////////////////////////////////////////////////////////
// This static function computes the hash index from the key.
///////////////////////////////////////////////////////////////////////////////////////////
// @ key      : local pointer on key.
// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
///////////////////////////////////////////////////////////////////////////////////////////
static uint32_t htab_bloup_index( void * key )
{
        return (*(uint32_t *)key) % HASHTAB_SIZE;
}

///////////////////////////////////////////////////////////////////////////////////////
// This static function is used by htab_lookup(), htab_insert(), and htab_remove().
// They scan one sub-list identified by  <index> to find an item  identified by <key>.
// The sub-list is not modified, but the lock must have been taken by the caller.
///////////////////////////////////////////////////////////////////////////////////////
// @ htab    : pointer on hash table.
// @ index   : index of sub-list to be scanned.
// @ key     : pointer on item identifier.
// @ return pointer on item if found / return NULL if not found.
///////////////////////////////////////////////////////////////////////////////////////
static void * htab_bloup_scan( htab_t  * htab,
                               uint32_t  index,
                               void    * key )
{
    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
    bloup_t      * bloup;        // pointer on item
    
        LIST_FOREACH( &htab->roots[index] , list_entry )
        {
        bloup = (bloup_t *)LIST_ELEMENT( list_entry , bloup_t , list );
        if( bloup->key == *(uint32_t *)key ) return bloup; 
    }

    // no matching item found
        return NULL;
}

////////////////////////////////////////////////////////////////////////////////////////
//         Generic access functions
////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////
void htab_init( htab_t           * htab,
                htab_item_type_t   type )
{
        uint32_t     i;

    // initialize readlock
    busylock_init( &htab->lock , LOCK_HTAB_STATE );

    htab->items = 0;

    if( type == HTAB_BLOUP_TYPE )
    {
        htab->scan    = &htab_bloup_scan;
        htab->index   = &htab_bloup_index;
    }
    else
    {
        assert( false , "undefined item type\n" );
    }

    // initialize partial lists
    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
    {
        list_root_init( &htab->roots[i] );
    }
}

/////////////////////////////////////////
error_t htab_insert( htab_t       * htab, 
                     void         * key,
                     list_entry_t * list_entry )
{
    // compute index from key
    uint32_t index = htab->index( key );

    // take the lock 
    busylock_acquire( &htab->lock );

    // scan sub-list to check if item exist
    void * item = htab->scan( htab , index , key );

    if( item != NULL ) // item exist => return error
    {
        // release lock
        busylock_release( &htab->lock );

        return 0xFFFFFFFF;
    }
    else               // item doesn't exist => register
    {
        // register item in hash table
        list_add_last( &htab->roots[index] , list_entry );

        // update items number
        htab->items++;

        // release lock
        busylock_release( &htab->lock );

        return 0;
    }
}

/////////////////////////////////////////
error_t htab_remove( htab_t       * htab, 
                     void         * key,
                     list_entry_t * list_entry )
{
    // compute index from key
    uint32_t index = htab->index( key );

    // take the lock 
    busylock_acquire( &htab->lock );

    // scan sub-list to chek if item exist
    void * item = htab->scan( htab , index , key );

    if( item == NULL ) // item doesn't exist
    {
        // release lock
        busylock_release( &htab->lock );

        return 0xFFFFFFFF;
    }
    else               // item exist => remove it 
    {
        // remove item from hash table
        list_unlink( list_entry );

        // update items number
        htab->items--;

        // release lock
        busylock_release( &htab->lock );

        return 0;
    }
}

//////////////////////////////////
void * htab_lookup( htab_t * htab, 
                    void   * key )
{
    // compute index from key
    uint32_t index = htab->index( key );

    // take the lock
    busylock_acquire( &htab->lock );

    // scan sub-list
    void * item = htab->scan( htab , index , key );

    // release lock 
    busylock_release( &htab->lock );

        return item;
}