source: trunk/kernel/libk/xhtab.c@ 14

/*
 * xhtab.c - Remote access embedded hash table implementation.
 * 
 * Author     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 <kernel_config.h>
#include <hal_types.h>
#include <hal_special.h>
#include <hal_remote.h>
#include <xlist.h>
#include <remote_rwlock.h>
#include <string.h>
#include <printk.h>
#include <xhtab.h>
#include <vfs.h>


///////////////////////////////////////////////////////////////////////////////////////
// This static function s called by the xhtab_lookup() and xhtab_register() functions.
// It scan one sub-list identified by  <index> to find an item  identified by <key>.
// The hash table is identified by <cxy> and local pointer <xhtab>.
// The sub-list is not modified, but the readlock must have been taken by the caller.
///////////////////////////////////////////////////////////////////////////////////////
// @ cxy       : hash table cluster.
// @ xhtab_xp  : hash table local pointer.
// @ index     : index of sub-list to be scanned.
// @ key       : local pointer on item identifier.
///////////////////////////////////////////////////////////////////////////////////////
static xptr_t xhtab_scan( cxy_t     cxy,
                          xhtab_t * xhtab,
                          uint32_t  index,
                          void    * key )
{
    xptr_t   xlist_xp;    // extended pointer on xlist_entry_t (iterator)
    xptr_t   item_xp;     // extended pointer on found item (return value)
    
    // scan the sub-list[index]
        XLIST_FOREACH( XPTR( cxy , &xhtab->roots[index] ) , xlist_xp )
        {
        if ( xhtab->compare( xlist_xp , key , &item_xp ) ) return item_xp;
    }

    // no matching item found
        return XPTR_NULL;
}

/////////////////////////////////
void xhtab_init( xhtab_t * xhtab,
                 uint32_t  type )
{
        uint32_t i;

    // initialize readlock
    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );

    xhtab->items  = 0;

    if( type == XHTAB_DENTRY_TYPE )
    {
        hal_remote_spt( XPTR( local_cxy , &xhtab->compare ) , &xhtab_dentry_compare );
        hal_remote_spt( XPTR( local_cxy , &xhtab->index   ) , &xhtab_dentry_index   );
    }
    else
    {
        printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ );
        hal_core_sleep();
    }

        for( i=0 ; i < HASHTAB_SIZE ; i++ )
    {
                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
    }  
}

///////////////////////////////////////
void xhtab_register( xptr_t   xhtab_xp,
                     void   * key,
                     xptr_t   xlist_xp )
{
    // get xhtab cluster and local pointer 
    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );

    // compute index from key
        uint32_t index = xhtab_ptr->index( key );

    // take the lock protecting hash table
    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

    // register item in hash table
        xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );

    // update number of registered items
    hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );

    // release the lock protecting hash table
    remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

}  // end xhtab_register()

/////////////////////////////////////
void xhtab_remove( xptr_t   xhtab_xp,
                   void   * key )
{
    // get xhtab cluster and local pointer 
    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );

    // take the lock protecting hash table
    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

    // compute index from key
        uint32_t index = xhtab_ptr->index( key );

    // get extended pointer on item to remove
    xptr_t item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key );

    if( item_xp == XPTR_NULL )    // do nothing if not found
    {
        // release the lock protecting hash table
        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    }
    else                          // remove item if found
    {
        // get item cluster and local pointer 
        cxy_t          item_cxy = GET_CXY( item_xp );
        vfs_dentry_t * item_ptr = (vfs_dentry_t *)GET_PTR( item_xp );

        // remove item from hash table <=> unlink xlist_entry_t
        xlist_unlink( XPTR( item_cxy , &item_ptr->xlist ) );

        // update number of registered items
        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );

        // release the lock protecting hash table
        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    }
}  // end xhtab_unregister()

/////////////////////////////////////////
xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
                      void    * key )
{
    xptr_t  item_xp;

    // get xhtab cluster and local pointer 
    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );

    // compute index from key
        uint32_t index = xhtab_ptr->index( key );

    // take the lock protecting hash table
    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

    // scan sub-list
    item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key );

    // release the lock protecting hash table
    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

    return item_xp;

}  // end xhtab_lookup()



/////////////////////////////////////////
uint32_t xhtab_dentry_index( void * key )
{
        char    * str   = key;
        uint32_t  index = 0;
  
        while( *str ) index = index + (*(str++) ^ index);

        return index % HASHTAB_SIZE;
} 

///////////////////////////////////////////////
bool_t xhtab_dentry_compare( xptr_t   xlist_xp,
                             void   * key,
                             xptr_t * item_xp )
{
    char   tested_name[256];      // local copy of name stored in remote hash table

    char * searched_name = key;   // local pointer on searched name 

    // compute name length
    uint32_t length = strlen( searched_name );

    // get extended pointer on dentry containing the xlist_entry_t
        xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist );

    // get dentry cluster and local pointer 
    cxy_t          dentry_cxy = GET_CXY( dentry_xp );
    vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( dentry_xp );
    
    // make a local copy of remote dentry name
    hal_remote_memcpy( XPTR( local_cxy  , tested_name ) ,
                       XPTR( dentry_cxy , dentry_ptr->name ) , length );

    // check matching / return if match
    if( strcmp( tested_name , searched_name ) == 0 )
    {
        return true;
        *item_xp = dentry_xp;
    }
    else
    {
        return false;
    }
}


 
////////////////////////////////////////
uint32_t xhtab_inode_index( void * key )
{
        uint32_t * inum = key;

        return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
} 

///////////////////////////////////////////////
bool_t xhtab_inode_compare( xptr_t   xlist_xp,
                            void   * key,
                            xptr_t * item_xp )
{
    uint32_t * searched_inum = key;
    uint32_t   tested_inum;   

    // get extended pointer on inode containing the xlist_entry_t
        xptr_t inode_xp = XLIST_ELEMENT( xlist_xp , vfs_inode_t , xlist );

    // get inode cluster and local pointer 
    cxy_t         inode_cxy = GET_CXY( inode_xp );
    vfs_inode_t * inode_ptr = (vfs_inode_t *)GET_PTR( inode_xp );
    
    // get tested inode inum
    tested_inum = hal_remote_lw( XPTR( inode_cxy , &inode_ptr->inum ) );

    // check matching / return if match
    if( tested_inum == *searched_inum )
    {
        return true;
        *item_xp = inode_xp;
    }
    else
    {
        return false;
    }
}