source: trunk/kernel/libk/xhtab.c @ 198

Last change on this file since 198 was 188, checked in by alain, 7 years ago

Redefine the PIC device API.

File size: 12.2 KB
Line 
1/*
2 * xhtab.c - Remote access 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_types.h>
26#include <hal_special.h>
27#include <hal_remote.h>
28#include <xlist.h>
29#include <remote_rwlock.h>
30#include <string.h>
31#include <printk.h>
32#include <xhtab.h>
33#include <vfs.h>
34
35
36///////////////////////////////////////////////////////////////////////////////////////////
37// Item type specific functions (three functions for each item type).
38///////////////////////////////////////////////////////////////////////////////////////////
39
40///////////////////////////////////////////////////////////////////////////////////////////
41// This functions compute the hash index from the key when item is a vfs_dentry_t.
42// The key is the directory entry name.
43///////////////////////////////////////////////////////////////////////////////////////////
44// @ key      : local pointer on name.
45// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
46///////////////////////////////////////////////////////////////////////////////////////////
47static uint32_t xhtab_dentry_index_from_key( void * key )
48{
49        char     * name  = key;
50        uint32_t   index = 0;
51        while( *name )
52    {
53        index = index + (*(name++) ^ index);
54    }
55        return index % XHASHTAB_SIZE;
56} 
57
58///////////////////////////////////////////////////////////////////////////////////////////
59// This functions returns the extended pointer on the item, from the extended pointer
60// on xlist contained in the item, when the item is a vfs_entry_t.
61///////////////////////////////////////////////////////////////////////////////////////////
62// @ xlist_xp      : extended pointer on embedded xlist entry.
63// @ return the extended pointer on the dentry containing this xlist entry.
64///////////////////////////////////////////////////////////////////////////////////////////
65static xptr_t xhtab_dentry_item_from_xlist( xptr_t xlist_xp )
66{
67    return XLIST_ELEMENT( xlist_xp , vfs_dentry_t , list );
68}
69
70////////////////////////////////////////////////////////////////////////////////////////////
71// This function compare the identifier of an item to a given <key>. For a vfs_entry_t,
72// it returns true when the directory name matches the name pointed by the <key> argument.
73////////////////////////////////////////////////////////////////////////////////////////////
74// @ item_xp   : extended pointer on item.
75// @ key       : pointer on searched item identifier.
76// returns true if given name matches directory entry name.
77////////////////////////////////////////////////////////////////////////////////////////////
78static bool_t xhtab_dentry_item_match_key( xptr_t item_xp,
79                                           void    * key )
80{
81    vfs_dentry_t * dentry_ptr;
82    cxy_t          dentry_cxy;
83
84    char           name[CONFIG_VFS_MAX_NAME_LENGTH];
85
86    // get dentry cluster and local pointer
87    dentry_cxy = GET_CXY( item_xp );
88    dentry_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
89
90    // make a local copy of directory entry name
91    hal_remote_strcpy( XPTR( local_cxy , name ) ,
92                       XPTR( dentry_cxy , &dentry_ptr->name ) );
93
94    return( strcmp( name , (char*)key ) == 0 );
95}
96                       
97////////////////////////////////////////////////////////////////////////////////////////
98//         Generic access functions
99////////////////////////////////////////////////////////////////////////////////////////
100
101//////////////////////////////////////////
102void xhtab_init( xhtab_t          * xhtab,
103                 xhtab_item_type_t  type )
104{
105        uint32_t i;
106
107    // initialize readlock
108    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
109
110    xhtab->items  = 0;
111
112    if( type == XHTAB_DENTRY_TYPE )
113    {
114        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
115        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
116        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
117    }
118    else
119    {
120        printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ );
121        hal_core_sleep();
122    }
123
124        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
125    {
126                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
127    } 
128
129}  // end xhtab_init()
130
131//////////////////////////////////////
132xptr_t xhtab_scan( xptr_t    xhtab_xp,
133                   uint32_t  index,
134                   void    * key )
135{
136    xptr_t    xlist_xp;                                 // xlist_entry_t (iterator)
137    xptr_t    item_xp;                                  // associated item
138    xhtab_t * xhtab_ptr;                                // hash table local pointer
139    cxy_t     xhtab_cxy;                                // hash table cluster
140
141    // get hash table cluster and local pointer
142    xhtab_cxy = GET_CXY( xhtab_xp );
143    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
144
145    // scan sub-list[index]
146    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
147    {
148        // get extended pointer on item containing the xlist entry
149            item_xp = xhtab_ptr->item_from_xlist( xlist_xp );
150
151        // check matching
152        if( xhtab_ptr->item_match_key( item_xp , key ) ) return item_xp;
153    }
154
155    // No matching item found
156    return XPTR_NULL;
157}
158
159///////////////////////////////////////
160error_t xhtab_insert( xptr_t   xhtab_xp,
161                      void   * key,
162                      xptr_t   xlist_xp )
163{
164    // get xhtab cluster and local pointer
165    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
166    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
167
168    // compute index from key
169        uint32_t index = xhtab_ptr->index_from_key( key );
170
171    // take the lock protecting hash table
172    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
173
174    // search a matching item
175    xptr_t item_xp = xhtab_scan( xhtab_xp , index , key );
176
177    if( item_xp != XPTR_NULL )    // error if found
178    {
179        // release the lock protecting hash table
180        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
181
182        return EINVAL;
183    }
184    else                          // insert item if not found
185    {
186        // register item in hash table
187            xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
188
189        // update number of registered items
190        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
191
192        // release the lock protecting hash table
193        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
194
195        return 0;
196    }
197}  // end xhtab_insert()
198
199/////////////////////////////////////
200error_t xhtab_remove( xptr_t   xhtab_xp,
201                      void   * key,
202                      xptr_t   xlist_entry_xp )
203{
204    // get xhtab cluster and local pointer
205    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
206    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
207
208    // compute index from key
209        uint32_t index = xhtab_ptr->index_from_key( key );
210
211    // take the lock protecting hash table
212    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
213
214    // get extended pointer on item to remove
215    xptr_t item_xp = xhtab_scan( xhtab_xp , index , key );
216
217    if( item_xp == XPTR_NULL )    // error if not found
218    {
219        // release the lock protecting hash table
220        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
221
222        return EINVAL;
223    }
224    else                          // remove item if found
225    {
226        // remove item from hash table <=> unlink xlist_entry_t
227        xlist_unlink( xlist_entry_xp );
228
229        // update number of registered items
230        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
231
232        // release the lock protecting hash table
233        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
234
235        return 0;
236    }
237}  // end xhtab_remove()
238
239/////////////////////////////////////////
240xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
241                      void    * key )
242{
243    xptr_t  item_xp;
244
245    // get xhtab cluster and local pointer
246    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
247    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
248
249    // compute index from key
250        uint32_t index = xhtab_ptr->index_from_key( key );
251
252    // take the lock protecting hash table
253    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
254
255    // scan sub-list
256    item_xp = xhtab_scan( xhtab_xp , index , key );
257
258    // release the lock protecting hash table
259    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
260
261    return item_xp;
262
263}  // end xhtab_lookup()
264
265///////////////////////////////////////
266void xhtab_read_lock( xptr_t xhtab_xp )
267{
268    // get xhtab cluster and local pointer
269    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
270    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
271
272    // take the lock protecting hash table
273    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
274}
275
276/////////////////////////////////////////
277void xhtab_read_unlock( xptr_t xhtab_xp )
278{
279    // get xhtab cluster and local pointer
280    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
281    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
282
283    // release the lock protecting hash table
284    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
285}
286
287/////////////////////////////////////////
288xptr_t xhtab_get_first( xptr_t xhtab_xp )
289{
290    uint32_t index;
291    xptr_t   xlist_xp;
292    xptr_t   item_xp;
293    xptr_t   root_xp;
294
295    // get xhtab cluster and local pointer
296    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
297    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
298
299    //loop on subsets
300    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
301    {
302        // get root of subset
303        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
304
305        // get first item
306        xlist_xp = xlist_next( root_xp , root_xp );
307
308        if( xlist_xp != XPTR_NULL )  // first item found
309        {
310            // get extended pointer on item containing the xlist entry
311                item_xp = xhtab_ptr->item_from_xlist( xlist_xp );
312
313            // register item in hash table header
314            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
315            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
316
317            return item_xp;
318        }
319    }
320           
321    // item not found
322    return XPTR_NULL;
323
324} // end xhtab_get_first()
325   
326////////////////////////////////////////
327xptr_t xhtab_get_next( xptr_t xhtab_xp )
328{
329    uint32_t index;
330    xptr_t   xlist_xp;
331    xptr_t   item_xp;
332    xptr_t   root_xp;
333
334    uint32_t current_index;
335    xptr_t   current_xlist_xp;
336
337    // get xhtab cluster and local pointer
338    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
339    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
340
341    // get current item pointers
342    current_index    = hal_remote_lw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) ); 
343    current_xlist_xp = hal_remote_lwd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) ); 
344
345    //loop on subsets
346    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
347    {
348        // get root of subset
349        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
350
351        // get next item
352        xlist_xp = xlist_next( root_xp , current_xlist_xp );
353
354        if( xlist_xp != XPTR_NULL )  // next item found
355        {
356            // get extended pointer on item containing the xlist entry
357                item_xp = xhtab_ptr->item_from_xlist( xlist_xp );
358
359            // register item in hash table header
360            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
361            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
362
363            return item_xp;
364        }
365    }
366           
367    // item not found
368    return XPTR_NULL;
369
370} // end xhtab_get_next()
371
372
Note: See TracBrowser for help on using the repository browser.