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

Last change on this file since 563 was 563, checked in by alain, 3 years ago

Complete restructuration of kernel spinlocks.

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>
[563]28#include <busylock.h>
[23]29#include <list.h>
30#include <printk.h>
31#include <vfs.h>
[1]32
[563]33
[23]34///////////////////////////////////////////////////////////////////////////////////////////
35//    Item type specific (static) functions (two functions for each item type).
36// Example below if for <vhs_inode_t>, where the identifier is the inum field.
37///////////////////////////////////////////////////////////////////////////////////////////
38
39///////////////////////////////////////////////////////////////////////////////////////////
40// These static functions compute the hash index from the key.
41///////////////////////////////////////////////////////////////////////////////////////////
42// @ key      : local pointer on key.
43// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
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///////////////////////////////////////////////////////////////////////////////////////
61static void * htab_inode_scan( htab_t  * htab,
62                               uint32_t  index,
63                               void    * key )
64{
65    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
66    vfs_inode_t  * inode;        // pointer on item
67   
68        LIST_FOREACH( &htab->roots[index] , list_entry )
[1]69        {
[23]70        inode = (vfs_inode_t *)LIST_ELEMENT( list_entry , vfs_inode_t , list );
71        if( inode->inum == *(uint32_t *)key ) return inode; 
72    }
[1]73
[23]74    // no matching item found
75        return NULL;
[1]76}
77
[23]78////////////////////////////////////////////////////////////////////////////////////////
79//         Generic access functions
80////////////////////////////////////////////////////////////////////////////////////////
81
[1]82////////////////////////////////////////
[23]83void htab_init( htab_t           * htab,
84                htab_item_type_t   type )
[1]85{
[23]86        uint32_t     i;
[1]87
[23]88    // initialize readlock
[563]89    busylock_init( &htab->lock , LOCK_HTAB_STATE );
[23]90
91    htab->items = 0;
92
93    if( type == HTAB_INODE_TYPE )
94    {
95        htab->scan    = &htab_inode_scan;
96        htab->index   = &htab_inode_index;
97    }
98    else
99    {
[492]100        assert( false , "undefined item type\n" );
[23]101    }
102
103    // initialize partial lists
104    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
105    {
106        list_root_init( &htab->roots[i] );
107    }
[1]108}
109
[23]110/////////////////////////////////////////
111error_t htab_insert( htab_t       * htab, 
112                     void         * key,
113                     list_entry_t * list_entry )
[1]114{
[23]115    // compute index from key
116    uint32_t index = htab->index( key );
[1]117
[563]118    // take the lock
119    busylock_acquire( &htab->lock );
[1]120
[23]121    // scan sub-list to check if item exist
122    void * item = htab->scan( htab , index , key );
[1]123
[23]124    if( item != NULL ) // item exist => return error
125    {
126        // release lock
[563]127        busylock_release( &htab->lock );
[1]128
[563]129        return 0xFFFFFFFF;
[23]130    }
131    else               // item doesn't exist => register
132    {
133        // register item in hash table
134        list_add_last( &htab->roots[index] , list_entry );
[1]135
[23]136        // update items number
137        htab->items++;
138
139        // release lock
[563]140        busylock_release( &htab->lock );
[23]141
142        return 0;
143    }
[1]144}
145
[23]146/////////////////////////////////////////
147error_t htab_remove( htab_t       * htab, 
148                     void         * key,
149                     list_entry_t * list_entry )
[1]150{
[23]151    // compute index from key
152    uint32_t index = htab->index( key );
[1]153
[563]154    // take the lock
155    busylock_acquire( &htab->lock );
[1]156
[23]157    // scan sub-list to chek if item exist
158    void * item = htab->scan( htab , index , key );
[1]159
[23]160    if( item == NULL ) // item doesn't exist
161    {
162        // release lock
[563]163        busylock_release( &htab->lock );
[1]164
[563]165        return 0xFFFFFFFF;
[23]166    }
167    else               // item exist => remove it
168    {
169        // remove item from hash table
170        list_unlink( list_entry );
[1]171
[23]172        // update items number
173        htab->items--;
[1]174
[23]175        // release lock
[563]176        busylock_release( &htab->lock );
[23]177
178        return 0;
179    }
[1]180}
181
[23]182//////////////////////////////////
183void * htab_lookup( htab_t * htab, 
184                    void   * key )
[1]185{
[23]186    // compute index from key
187    uint32_t index = htab->index( key );
[1]188
[563]189    // take the lock
190    busylock_acquire( &htab->lock );
[1]191
[23]192    // scan sub-list
193    void * item = htab->scan( htab , index , key );
[1]194
[23]195    // release lock
[563]196    busylock_release( &htab->lock );
[1]197
[23]198        return item;
[1]199}
200
[23]201
202
Note: See TracBrowser for help on using the repository browser.