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

Last change on this file since 675 was 671, checked in by alain, 4 years ago

Cosmetic.

File size: 6.0 KB
Line 
1/*
2 * htable.c - Generic, embedded hash table implementation.
3 *
4 * Author      Alain Greiner (2016,2017)
5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
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 *
14 * ALMOS-MKH is distributed in the hope that it will be useful, but
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
20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#include <kernel_config.h>
25#include <hal_kernel_types.h>
26#include <hal_special.h>
27#include <htab.h>
28#include <busylock.h>
29#include <list.h>
30#include <printk.h>
31#include <vfs.h>
32
33
34///////////////////////////////////////////////////////////////////////////////////////////
35//    Item type specific (static) functions (two functions for each item type).
36// Example below if for <bloup_t> type, where the identifier is an uint32_t field.
37///////////////////////////////////////////////////////////////////////////////////////////
38
39typedef struct bloup_s
40{
41    uint32_t       key;
42    list_entry_t   list;
43}
44bloup_t;
45
46///////////////////////////////////////////////////////////////////////////////////////////
47// This static function computes the hash index from the key.
48///////////////////////////////////////////////////////////////////////////////////////////
49// @ key      : local pointer on key.
50// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
51///////////////////////////////////////////////////////////////////////////////////////////
52static uint32_t htab_bloup_index( void * key )
53{
54        return (*(uint32_t *)key) % HASHTAB_SIZE;
55}
56
57///////////////////////////////////////////////////////////////////////////////////////
58// This static function is used by htab_lookup(), htab_insert(), and htab_remove().
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///////////////////////////////////////////////////////////////////////////////////////
67static void * htab_bloup_scan( htab_t  * htab,
68                               uint32_t  index,
69                               void    * key )
70{
71    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
72    bloup_t      * bloup;        // pointer on item
73   
74        LIST_FOREACH( &htab->roots[index] , list_entry )
75        {
76        bloup = (bloup_t *)LIST_ELEMENT( list_entry , bloup_t , list );
77        if( bloup->key == *(uint32_t *)key ) return bloup; 
78    }
79
80    // no matching item found
81        return NULL;
82}
83
84////////////////////////////////////////////////////////////////////////////////////////
85//         Generic access functions
86////////////////////////////////////////////////////////////////////////////////////////
87
88////////////////////////////////////////
89void htab_init( htab_t           * htab,
90                htab_item_type_t   type )
91{
92        uint32_t     i;
93
94    // initialize readlock
95    busylock_init( &htab->lock , LOCK_HTAB_STATE );
96
97    htab->items = 0;
98
99    if( type == HTAB_BLOUP_TYPE )
100    {
101        htab->scan    = &htab_bloup_scan;
102        htab->index   = &htab_bloup_index;
103    }
104    else
105    {
106        assert( __FUNCTION__, false , "undefined item type\n" );
107    }
108
109    // initialize partial lists
110    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
111    {
112        list_root_init( &htab->roots[i] );
113    }
114}
115
116/////////////////////////////////////////
117error_t htab_insert( htab_t       * htab, 
118                     void         * key,
119                     list_entry_t * list_entry )
120{
121    // compute index from key
122    uint32_t index = htab->index( key );
123
124    // take the lock
125    busylock_acquire( &htab->lock );
126
127    // scan sub-list to check if item exist
128    void * item = htab->scan( htab , index , key );
129
130    if( item != NULL ) // item exist => return error
131    {
132        // release lock
133        busylock_release( &htab->lock );
134
135        return 0xFFFFFFFF;
136    }
137    else               // item doesn't exist => register
138    {
139        // register item in hash table
140        list_add_last( &htab->roots[index] , list_entry );
141
142        // update items number
143        htab->items++;
144
145        // release lock
146        busylock_release( &htab->lock );
147
148        return 0;
149    }
150}
151
152/////////////////////////////////////////
153error_t htab_remove( htab_t       * htab, 
154                     void         * key,
155                     list_entry_t * list_entry )
156{
157    // compute index from key
158    uint32_t index = htab->index( key );
159
160    // take the lock
161    busylock_acquire( &htab->lock );
162
163    // scan sub-list to chek if item exist
164    void * item = htab->scan( htab , index , key );
165
166    if( item == NULL ) // item doesn't exist
167    {
168        // release lock
169        busylock_release( &htab->lock );
170
171        return 0xFFFFFFFF;
172    }
173    else               // item exist => remove it
174    {
175        // remove item from hash table
176        list_unlink( list_entry );
177
178        // update items number
179        htab->items--;
180
181        // release lock
182        busylock_release( &htab->lock );
183
184        return 0;
185    }
186}
187
188//////////////////////////////////
189void * htab_lookup( htab_t * htab, 
190                    void   * key )
191{
192    // compute index from key
193    uint32_t index = htab->index( key );
194
195    // take the lock
196    busylock_acquire( &htab->lock );
197
198    // scan sub-list
199    void * item = htab->scan( htab , index , key );
200
201    // release lock
202    busylock_release( &htab->lock );
203
204        return item;
205}
206
207
208
Note: See TracBrowser for help on using the repository browser.