source: trunk/kernel/libk/htab.c

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

Cosmetic.

File size: 6.0 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).
[610]36// Example below if for <bloup_t> type, where the identifier is an uint32_t field.
[23]37///////////////////////////////////////////////////////////////////////////////////////////
38
[610]39typedef struct bloup_s
40{
41    uint32_t       key;
42    list_entry_t   list;
43}
44bloup_t;
45
[23]46///////////////////////////////////////////////////////////////////////////////////////////
[610]47// This static function computes the hash index from the key.
[23]48///////////////////////////////////////////////////////////////////////////////////////////
49// @ key      : local pointer on key.
50// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
51///////////////////////////////////////////////////////////////////////////////////////////
[610]52static uint32_t htab_bloup_index( void * key )
[1]53{
[610]54        return (*(uint32_t *)key) % HASHTAB_SIZE;
[23]55}
[1]56
[23]57///////////////////////////////////////////////////////////////////////////////////////
[610]58// This static function is used by htab_lookup(), htab_insert(), and htab_remove().
[23]59// They scan one sub-list identified by  <index> to find an item  identified by <key>.
60// The sub-list is not modified, but the lock must have been taken by the caller.
61///////////////////////////////////////////////////////////////////////////////////////
62// @ htab    : pointer on hash table.
63// @ index   : index of sub-list to be scanned.
64// @ key     : pointer on item identifier.
65// @ return pointer on item if found / return NULL if not found.
66///////////////////////////////////////////////////////////////////////////////////////
[610]67static void * htab_bloup_scan( htab_t  * htab,
[23]68                               uint32_t  index,
69                               void    * key )
70{
71    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
[610]72    bloup_t      * bloup;        // pointer on item
[23]73   
74        LIST_FOREACH( &htab->roots[index] , list_entry )
[1]75        {
[610]76        bloup = (bloup_t *)LIST_ELEMENT( list_entry , bloup_t , list );
77        if( bloup->key == *(uint32_t *)key ) return bloup; 
[23]78    }
[1]79
[23]80    // no matching item found
81        return NULL;
[1]82}
83
[23]84////////////////////////////////////////////////////////////////////////////////////////
85//         Generic access functions
86////////////////////////////////////////////////////////////////////////////////////////
87
[1]88////////////////////////////////////////
[23]89void htab_init( htab_t           * htab,
90                htab_item_type_t   type )
[1]91{
[23]92        uint32_t     i;
[1]93
[23]94    // initialize readlock
[563]95    busylock_init( &htab->lock , LOCK_HTAB_STATE );
[23]96
97    htab->items = 0;
98
[610]99    if( type == HTAB_BLOUP_TYPE )
[23]100    {
[610]101        htab->scan    = &htab_bloup_scan;
102        htab->index   = &htab_bloup_index;
[23]103    }
104    else
105    {
[671]106        assert( __FUNCTION__, false , "undefined item type\n" );
[23]107    }
108
109    // initialize partial lists
110    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
111    {
112        list_root_init( &htab->roots[i] );
113    }
[1]114}
115
[23]116/////////////////////////////////////////
117error_t htab_insert( htab_t       * htab, 
118                     void         * key,
119                     list_entry_t * list_entry )
[1]120{
[23]121    // compute index from key
122    uint32_t index = htab->index( key );
[1]123
[563]124    // take the lock
125    busylock_acquire( &htab->lock );
[1]126
[23]127    // scan sub-list to check if item exist
128    void * item = htab->scan( htab , index , key );
[1]129
[23]130    if( item != NULL ) // item exist => return error
131    {
132        // release lock
[563]133        busylock_release( &htab->lock );
[1]134
[563]135        return 0xFFFFFFFF;
[23]136    }
137    else               // item doesn't exist => register
138    {
139        // register item in hash table
140        list_add_last( &htab->roots[index] , list_entry );
[1]141
[23]142        // update items number
143        htab->items++;
144
145        // release lock
[563]146        busylock_release( &htab->lock );
[23]147
148        return 0;
149    }
[1]150}
151
[23]152/////////////////////////////////////////
153error_t htab_remove( htab_t       * htab, 
154                     void         * key,
155                     list_entry_t * list_entry )
[1]156{
[23]157    // compute index from key
158    uint32_t index = htab->index( key );
[1]159
[563]160    // take the lock
161    busylock_acquire( &htab->lock );
[1]162
[23]163    // scan sub-list to chek if item exist
164    void * item = htab->scan( htab , index , key );
[1]165
[23]166    if( item == NULL ) // item doesn't exist
167    {
168        // release lock
[563]169        busylock_release( &htab->lock );
[1]170
[563]171        return 0xFFFFFFFF;
[23]172    }
173    else               // item exist => remove it
174    {
175        // remove item from hash table
176        list_unlink( list_entry );
[1]177
[23]178        // update items number
179        htab->items--;
[1]180
[23]181        // release lock
[563]182        busylock_release( &htab->lock );
[23]183
184        return 0;
185    }
[1]186}
187
[23]188//////////////////////////////////
189void * htab_lookup( htab_t * htab, 
190                    void   * key )
[1]191{
[23]192    // compute index from key
193    uint32_t index = htab->index( key );
[1]194
[563]195    // take the lock
196    busylock_acquire( &htab->lock );
[1]197
[23]198    // scan sub-list
199    void * item = htab->scan( htab , index , key );
[1]200
[23]201    // release lock
[563]202    busylock_release( &htab->lock );
[1]203
[23]204        return item;
[1]205}
206
[23]207
208
Note: See TracBrowser for help on using the repository browser.