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

Last change on this file since 532 was 492, checked in by viala@…, 6 years ago

Refactoring assert calling to conform with new assert macro.

Made with this command for the general case.
find ./kernel/ hal/ -name "*.c" | xargs sed -i -e '/assert(/ s/,[ ]*FUNCTION[ ]*,/,/'

And some done by hand.

File size: 5.9 KB
RevLine 
[1]1/*
2 * htable.c - Generic, embedded hash table implementation.
3 *
[23]4 * Author      Alain Greiner (2016,2017)
[1]5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
[23]10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
[1]11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
[23]14 * ALMOS-MKH is distributed in the hope that it will be useful, but
[1]15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
[23]20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
[1]21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
[23]24#include <kernel_config.h>
[457]25#include <hal_kernel_types.h>
[23]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>
[1]32
[23]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 )
[1]46{
[23]47        uint32_t * inum = key;
48        return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
49}
[1]50
[23]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///////////////////////////////////////////////////////////////////////////////////////
[1]61
[23]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 )
[1]70        {
[23]71        inode = (vfs_inode_t *)LIST_ELEMENT( list_entry , vfs_inode_t , list );
72        if( inode->inum == *(uint32_t *)key ) return inode; 
73    }
[1]74
[23]75    // no matching item found
76        return NULL;
[1]77}
78
[23]79////////////////////////////////////////////////////////////////////////////////////////
80//         Generic access functions
81////////////////////////////////////////////////////////////////////////////////////////
82
[1]83////////////////////////////////////////
[23]84void htab_init( htab_t           * htab,
85                htab_item_type_t   type )
[1]86{
[23]87        uint32_t     i;
[1]88
[23]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    {
[492]101        assert( false , "undefined item type\n" );
[23]102    }
103
104    // initialize partial lists
105    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
106    {
107        list_root_init( &htab->roots[i] );
108    }
[1]109}
110
[23]111/////////////////////////////////////////
112error_t htab_insert( htab_t       * htab, 
113                     void         * key,
114                     list_entry_t * list_entry )
[1]115{
[23]116    // compute index from key
117    uint32_t index = htab->index( key );
[1]118
[23]119    // take the lock in write mode
120    rwlock_wr_lock( &htab->lock );
[1]121
[23]122    // scan sub-list to check if item exist
123    void * item = htab->scan( htab , index , key );
[1]124
[23]125    if( item != NULL ) // item exist => return error
126    {
127        // release lock
128        rwlock_wr_unlock( &htab->lock );
[1]129
[23]130        return -1;
131    }
132    else               // item doesn't exist => register
133    {
134        // register item in hash table
135        list_add_last( &htab->roots[index] , list_entry );
[1]136
[23]137        // update items number
138        htab->items++;
139
140        // release lock
141        rwlock_wr_unlock( &htab->lock );
142
143        return 0;
144    }
[1]145}
146
[23]147/////////////////////////////////////////
148error_t htab_remove( htab_t       * htab, 
149                     void         * key,
150                     list_entry_t * list_entry )
[1]151{
[23]152    // compute index from key
153    uint32_t index = htab->index( key );
[1]154
[23]155    // take the lock in write mode
156    rwlock_wr_lock( &htab->lock );
[1]157
[23]158    // scan sub-list to chek if item exist
159    void * item = htab->scan( htab , index , key );
[1]160
[23]161    if( item == NULL ) // item doesn't exist
162    {
163        // release lock
164        rwlock_wr_unlock( &htab->lock );
[1]165
[23]166        return -1;
167    }
168    else               // item exist => remove it
169    {
170        // remove item from hash table
171        list_unlink( list_entry );
[1]172
[23]173        // update items number
174        htab->items--;
[1]175
[23]176        // release lock
177        rwlock_wr_unlock( &htab->lock );
178
179        return 0;
180    }
[1]181}
182
[23]183//////////////////////////////////
184void * htab_lookup( htab_t * htab, 
185                    void   * key )
[1]186{
[23]187    // compute index from key
188    uint32_t index = htab->index( key );
[1]189
[23]190    // take the lock in read mode
191    rwlock_rd_lock( &htab->lock );
[1]192
[23]193    // scan sub-list
194    void * item = htab->scan( htab , index , key );
[1]195
[23]196    // release lock
197    rwlock_rd_unlock( &htab->lock );
[1]198
[23]199        return item;
[1]200}
201
[23]202
203
Note: See TracBrowser for help on using the repository browser.