Ignore:
Timestamp:
Jun 18, 2017, 10:06:41 PM (7 years ago)
Author:
alain
Message:

Introduce syscalls.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/kernel/libk/htab.c

    r1 r23  
    22 * htable.c - Generic, embedded hash table implementation.
    33 *
    4  * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
    5  *            Mohamed Lamine Karaoui (2015)
    6  *            Alain Greiner (2016)
     4 * Author      Alain Greiner (2016,2017)
    75 *
    86 * Copyright (c) UPMC Sorbonne Universites
    … …  
    108 * This file is part of ALMOS-MKH.
    119 *
    12  * ALMOS-MKH.is free software; you can redistribute it and/or modify it
     10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
    1311 * under the terms of the GNU General Public License as published by
    1412 * the Free Software Foundation; version 2.0 of the License.
    1513 *
    16  * ALMOS-MKH.is distributed in the hope that it will be useful, but
     14 * ALMOS-MKH is distributed in the hope that it will be useful, but
    1715 * WITHOUT ANY WARRANTY; without even the implied warranty of
    1816 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    … …  
    2018 *
    2119 * You should have received a copy of the GNU General Public License
    22  * along with ALMOS-MKH.; if not, write to the Free Software Foundation,
     20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
    2321 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
    2422 */
    2523
    26 #include <htable.h>
    27 #include <kmem.h>
    28 #include <ppm.h>
    29 
    30 ///////////////////////////////////////////////
    31 error_t ht_header_init( ht_header_t  * header,
    32                         ht_hash_t    * hash,
    33                         ht_compare_t * compare )
     24#include <kernel_config.h>
     25#include <hal_types.h>
     26#include <hal_special.h>
     27#include <htab.h>
     28#include <rwlock.h>
     29#include <list.h>
     30#include <printk.h>
     31#include <vfs.h>
     32
     33///////////////////////////////////////////////////////////////////////////////////////////
     34//    Item type specific (static) functions (two functions for each item type).
     35// Example below if for <vhs_inode_t>, where the identifier is the inum field.
     36///////////////////////////////////////////////////////////////////////////////////////////
     37
     38///////////////////////////////////////////////////////////////////////////////////////////
     39// These static functions compute the hash index from the key.
     40///////////////////////////////////////////////////////////////////////////////////////////
     41// @ key      : local pointer on key.
     42// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
     43///////////////////////////////////////////////////////////////////////////////////////////
     44
     45static uint32_t htab_inode_index( void * key )
     46{
     47        uint32_t * inum = key;
     48        return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
     49}
     50
     51///////////////////////////////////////////////////////////////////////////////////////
     52// These static functions are used by htab_lookup(), htab_insert(), and htab_remove().
     53// They scan one sub-list identified by  <index> to find an item  identified by <key>.
     54// The sub-list is not modified, but the lock must have been taken by the caller.
     55///////////////////////////////////////////////////////////////////////////////////////
     56// @ htab    : pointer on hash table.
     57// @ index   : index of sub-list to be scanned.
     58// @ key     : pointer on item identifier.
     59// @ return pointer on item if found / return NULL if not found.
     60///////////////////////////////////////////////////////////////////////////////////////
     61
     62static void * htab_inode_scan( htab_t  * htab,
     63                               uint32_t  index,
     64                               void    * key )
     65{
     66    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
     67    vfs_inode_t  * inode;        // pointer on item
     68   
     69        LIST_FOREACH( &htab->roots[index] , list_entry )
     70        {
     71        inode = (vfs_inode_t *)LIST_ELEMENT( list_entry , vfs_inode_t , list );
     72        if( inode->inum == *(uint32_t *)key ) return inode;
     73    }
     74
     75    // no matching item found
     76        return NULL;
     77}
     78
     79////////////////////////////////////////////////////////////////////////////////////////
     80//         Generic access functions
     81////////////////////////////////////////////////////////////////////////////////////////
     82
     83////////////////////////////////////////
     84void htab_init( htab_t           * htab,
     85                htab_item_type_t   type )
    3486{
    3587        uint32_t     i;
    36         kmem_req_t   req;
    37         page_t     * page;
    38 
    39         req.type  = KMEM_PAGE;
    40         req.size  = 0;
    41         req.flags = AF_ZERO;
    42         page      = kmem_alloc( &req );
    43        
    44         if( page == NULL ) return ENOMEM;
    45 
    46         header->nb_buckets = CONFIG_PPM_PAGE_SIZE/sizeof( list_entry_t );
    47         header->buckets    = ppm_page2base( page );
    48         header->hash       = hash;
    49         header->compare    = compare;
    50 
    51         for( i=0 ; i < header->nb_buckets ; i++ )
    52         {
    53                 list_root_init( &header->buckets[i] );
    54         }
    55 
    56         return 0;
    57 }
    58 
    59 ////////////////////////////////////////
    60 error_t ht_node_init( ht_node_t * node )
    61 {
    62         node->index = (uint32_t) -1;
    63         list_entry_init( &node->list );
    64 
    65         return 0;
    66 }
    67 
    68 /////////////////////////////////////////////////
    69 static ht_node_t * __hfind( ht_header_t * header,
    70                             uint32_t      index,
    71                             void        * key)
    72 {
    73         ht_node_t    * node;
    74         list_entry_t * root,
    75     list_entry_t * iter;
    76 
    77         root = &header->buckets[index % header->nb_buckets];
    78 
    79         LIST_FOREACH( root , iter )
    80         {
    81                 node = LIST_ELEMENT( iter , ht_node_t , list );
    82                 if( node->index == index )
    83                 {
    84                         if( header->compare( node , key ) ) return node;
    85                 }
    86         }
    87 
    88         return NULL;
    89 }
    90 
    91 //////////////////////////////////////////
    92 ht_node_t * ht_find( ht_header_t * header,
    93                      void        * key )
    94 {
    95         uint32_t index = header->hash( key );
    96 
    97         return __ht_find( header , index , key );
    98 }
    99 
    100 ////////////////////////////////////////
    101 error_t ht_insert( ht_header_t * header,
    102                    ht_node_t   * node,
    103                    void        * key )
    104 {
    105         uint32_t index = header->hash( key );
    106 
    107         ht_node_t * node = __ht_find( header , index , key );
    108 
    109         if( node != NULL ) return EINVAL;
    110 
    111         list_entry_t * root = &header->buckets[index % header->nb_buckets];
    112 
    113         list_add_first( root , &node->list);
    114 
    115         node->index = index;
    116 
    117         return 0;
    118 }
    119 
    120 ////////////////////////////////////////
    121 error_t ht_remove( ht_header_t * header,
    122                    void        * key )
    123 {
    124         uint32_t index = header->hash( key );
    125 
    126         ht_node_t * node = __ht_find( header , index , key );
    127 
    128         if( node == NULL ) return EINVAL;
    129 
    130         list_unlink( &node->list );
    131 
    132         return 0;
    133 }
    134 
     88
     89    // initialize readlock
     90    rwlock_init( &htab->lock );
     91
     92    htab->items = 0;
     93
     94    if( type == HTAB_INODE_TYPE )
     95    {
     96        htab->scan    = &htab_inode_scan;
     97        htab->index   = &htab_inode_index;
     98    }
     99    else
     100    {
     101        printk("\n[PANIC] in %s : undefined item type\n", __FUNCTION__ );
     102        hal_core_sleep();
     103    }
     104
     105    // initialize partial lists
     106    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
     107    {
     108        list_root_init( &htab->roots[i] );
     109    }
     110}
     111
     112/////////////////////////////////////////
     113error_t htab_insert( htab_t       * htab,
     114                     void         * key,
     115                     list_entry_t * list_entry )
     116{
     117    // compute index from key
     118    uint32_t index = htab->index( key );
     119
     120    // take the lock in write mode
     121    rwlock_wr_lock( &htab->lock );
     122
     123    // scan sub-list to check if item exist
     124    void * item = htab->scan( htab , index , key );
     125
     126    if( item != NULL ) // item exist => return error
     127    {
     128        // release lock
     129        rwlock_wr_unlock( &htab->lock );
     130
     131        return -1;
     132    }
     133    else               // item doesn't exist => register
     134    {
     135        // register item in hash table
     136        list_add_last( &htab->roots[index] , list_entry );
     137
     138        // update items number
     139        htab->items++;
     140
     141        // release lock
     142        rwlock_wr_unlock( &htab->lock );
     143
     144        return 0;
     145    }
     146}
     147
     148/////////////////////////////////////////
     149error_t htab_remove( htab_t       * htab,
     150                     void         * key,
     151                     list_entry_t * list_entry )
     152{
     153    // compute index from key
     154    uint32_t index = htab->index( key );
     155
     156    // take the lock in write mode
     157    rwlock_wr_lock( &htab->lock );
     158
     159    // scan sub-list to chek if item exist
     160    void * item = htab->scan( htab , index , key );
     161
     162    if( item == NULL ) // item doesn't exist
     163    {
     164        // release lock
     165        rwlock_wr_unlock( &htab->lock );
     166
     167        return -1;
     168    }
     169    else               // item exist => remove it
     170    {
     171        // remove item from hash table
     172        list_unlink( list_entry );
     173
     174        // update items number
     175        htab->items--;
     176
     177        // release lock
     178        rwlock_wr_unlock( &htab->lock );
     179
     180        return 0;
     181    }
     182}
     183
     184//////////////////////////////////
     185void * htab_lookup( htab_t * htab,
     186                    void   * key )
     187{
     188    // compute index from key
     189    uint32_t index = htab->index( key );
     190
     191    // take the lock in read mode
     192    rwlock_rd_lock( &htab->lock );
     193
     194    // scan sub-list
     195    void * item = htab->scan( htab , index , key );
     196
     197    // release lock
     198    rwlock_rd_unlock( &htab->lock );
     199
     200        return item;
     201}
     202
     203
     204
Note: See TracChangeset for help on using the changeset viewer.