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

Last change on this file since 440 was 423, checked in by alain, 7 years ago

cosmetic
File size: 17.0 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    char name[CONFIG_VFS_MAX_NAME_LENGTH];
82
83    // get dentry cluster and local pointer
84    cxy_t          dentry_cxy = GET_CXY( item_xp );
85    vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
86
87    // make a local copy of directory entry name
88    hal_remote_strcpy( XPTR( local_cxy , name ) ,
89                       XPTR( dentry_cxy , &dentry_ptr->name ) );
90
91    return( strcmp( name , (char*)key ) == 0 );
92}
93
94////////////////////////////////////////////////////////////////////////////////////////////
95// This function print the item key, that is the name for a vfs_entry_t,
96////////////////////////////////////////////////////////////////////////////////////////////
97// @ item_xp   : extended pointer on item.
98////////////////////////////////////////////////////////////////////////////////////////////
99static void xhtab_dentry_item_print_key( xptr_t item_xp )
100{
101    char name[CONFIG_VFS_MAX_NAME_LENGTH];
102
103    // get dentry cluster and local pointer
104    cxy_t          dentry_cxy = GET_CXY( item_xp );
105    vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
106   
107    // make a local copy of directory entry name
108    hal_remote_strcpy( XPTR( local_cxy , name ) ,
109                       XPTR( dentry_cxy , &dentry_ptr->name ) );
110
111    // print dentry name
112    printk("%s , ", name );
113}                       
114
115////////////////////////////////////////////////////////////////////////////////////////
116//         Generic access functions
117////////////////////////////////////////////////////////////////////////////////////////
118
119//////////////////////////////////////////
120void xhtab_init( xhtab_t          * xhtab,
121                 xhtab_item_type_t  type )
122{
123        uint32_t i;
124
125    // initialize readlock
126    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
127
128    xhtab->items            = 0;
129    xhtab->current_index    = 0;
130    xhtab->current_xlist_xp = XPTR_NULL;
131
132    if( type == XHTAB_DENTRY_TYPE )
133    {
134        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
135        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
136        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
137        xhtab->item_print_key  = &xhtab_dentry_item_print_key;
138    }
139    else
140    {
141        assert( false , __FUNCTION__ , "illegal item type\n" );
142    }
143
144        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
145    {
146                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
147    } 
148
149}  // end xhtab_init()
150
151//////////////////////////////////////
152xptr_t xhtab_scan( xptr_t    xhtab_xp,
153                   uint32_t  index,
154                   void    * key )
155{
156    xptr_t              xlist_xp;           // xlist_entry_t (iterator)
157    xptr_t              item_xp;            // associated item
158    xhtab_t           * xhtab_ptr;          // hash table local pointer
159    cxy_t               xhtab_cxy;          // hash table cluster
160    item_from_xlist_t * item_from_xlist;    // function pointer
161    item_match_key_t  * item_match_key;     // function pointer
162
163    // get hash table cluster and local pointer
164    xhtab_cxy = GET_CXY( xhtab_xp );
165    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
166
167    // get pointer on "item_from_xlist" function
168    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
169                                                           &xhtab_ptr->item_from_xlist ) );
170    // get pointer on "item_match_key" function
171    item_match_key = (item_match_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
172                                                         &xhtab_ptr->item_match_key ) );
173
174    // scan sub-list[index]
175    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
176    {
177        // get extended pointer on item containing the xlist entry
178            item_xp = item_from_xlist( xlist_xp );
179
180        // check matching
181        if( item_match_key( item_xp , key ) ) return item_xp;
182    }
183
184    // No matching item found
185    return XPTR_NULL;
186
187}  // end xhtab_scan()
188
189///////////////////////////////////////
190error_t xhtab_insert( xptr_t   xhtab_xp,
191                      void   * key,
192                      xptr_t   xlist_xp )
193{
194    xptr_t             item_xp;
195    uint32_t           index;
196    cxy_t              xhtab_cxy;
197    xhtab_t          * xhtab_ptr;
198    index_from_key_t * index_from_key;     // function pointer
199   
200    // get xhtab cluster and local pointer
201    xhtab_cxy = GET_CXY( xhtab_xp );
202    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
203
204    // get pointer on "index_from_key" function
205    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
206                                                         &xhtab_ptr->index_from_key ) );
207    // compute index from key
208        index = index_from_key( key );
209
210    // take the lock protecting hash table
211    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
212
213    // search a matching item
214    item_xp = xhtab_scan( xhtab_xp , index , key );
215
216    if( item_xp != XPTR_NULL )    // error if found
217    {
218        // release the lock protecting hash table
219        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
220
221        return EINVAL;
222    }
223    else                          // insert item if not found
224    {
225        // register item in hash table
226            xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
227
228        // update number of registered items
229        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
230
231        // release the lock protecting hash table
232        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
233
234        return 0;
235    }
236}  // end xhtab_insert()
237
238/////////////////////////////////////
239error_t xhtab_remove( xptr_t   xhtab_xp,
240                      void   * key,
241                      xptr_t   xlist_entry_xp )
242{
243    xptr_t             item_xp;
244    uint32_t           index;
245    cxy_t              xhtab_cxy;
246    xhtab_t          * xhtab_ptr;
247    index_from_key_t * index_from_key;     // function pointer
248
249    // get xhtab cluster and local pointer
250    xhtab_cxy = GET_CXY( xhtab_xp );
251    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
252
253    // get pointer on "index_from_key" function
254    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
255                                                         &xhtab_ptr->index_from_key ) );
256    // compute index from key
257        index = index_from_key( key );
258
259    // take the lock protecting hash table
260    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
261
262    // get extended pointer on item to remove
263    item_xp = xhtab_scan( xhtab_xp , index , key );
264
265    if( item_xp == XPTR_NULL )    // error if not found
266    {
267        // release the lock protecting hash table
268        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
269
270        return EINVAL;
271    }
272    else                          // remove item if found
273    {
274        // remove item from hash table <=> unlink xlist_entry_t
275        xlist_unlink( xlist_entry_xp );
276
277        // update number of registered items
278        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
279
280        // release the lock protecting hash table
281        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
282
283        return 0;
284    }
285}  // end xhtab_remove()
286
287/////////////////////////////////////////
288xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
289                      void    * key )
290{
291    xptr_t             item_xp;
292    uint32_t           index;
293    cxy_t              xhtab_cxy;
294    xhtab_t          * xhtab_ptr;
295    index_from_key_t * index_from_key;     // function pointer
296
297    // get xhtab cluster and local pointer
298    xhtab_cxy = GET_CXY( xhtab_xp );
299    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
300
301    // get pointer on "index_from_key" function
302    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
303                                                         &xhtab_ptr->index_from_key ) );
304    // compute index from key
305        index = index_from_key( key );
306
307    // take the lock protecting hash table
308    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
309
310    // scan sub-list
311    item_xp = xhtab_scan( xhtab_xp , index , key );
312
313    // release the lock protecting hash table
314    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
315
316    return item_xp;
317
318}  // end xhtab_lookup()
319
320///////////////////////////////////////
321void xhtab_read_lock( xptr_t xhtab_xp )
322{
323    // get xhtab cluster and local pointer
324    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
325    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
326
327    // take the lock protecting hash table
328    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
329}
330
331/////////////////////////////////////////
332void xhtab_read_unlock( xptr_t xhtab_xp )
333{
334    // get xhtab cluster and local pointer
335    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
336    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
337
338    // release the lock protecting hash table
339    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
340}
341
342/////////////////////////////////////////
343xptr_t xhtab_get_first( xptr_t xhtab_xp )
344{
345    uint32_t            index;
346    cxy_t               xhtab_cxy;
347    xhtab_t           * xhtab_ptr;
348    xptr_t              xlist_xp;
349    xptr_t              item_xp;
350    xptr_t              root_xp;
351    item_from_xlist_t * item_from_xlist;   // function pointer
352
353    // get xhtab cluster and local pointer
354    xhtab_cxy = GET_CXY( xhtab_xp );
355    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
356
357    // get pointer on "item_from_xlist" function
358    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
359                                                           &xhtab_ptr->item_from_xlist ) );
360    //loop on subsets
361    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
362    {
363        // get root of subset
364        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
365
366        // get first item
367        xlist_xp = xlist_next( root_xp , root_xp );
368
369        if( xlist_xp != XPTR_NULL )  // first item found
370        {
371            // get extended pointer on item containing the xlist entry
372                item_xp = item_from_xlist( xlist_xp );
373
374            // register item in hash table header
375            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
376            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
377
378            return item_xp;
379        }
380    }
381           
382    // item not found
383    return XPTR_NULL;
384
385} // end xhtab_get_first()
386   
387////////////////////////////////////////
388xptr_t xhtab_get_next( xptr_t xhtab_xp )
389{
390    uint32_t            index;
391    cxy_t               xhtab_cxy;
392    xhtab_t           * xhtab_ptr;
393    xptr_t              xlist_xp;
394    xptr_t              item_xp;
395    xptr_t              root_xp;
396    item_from_xlist_t * item_from_xlist;   // function pointer
397
398    uint32_t current_index;
399    xptr_t   current_xlist_xp;
400
401    // get xhtab cluster and local pointer
402    xhtab_cxy = GET_CXY( xhtab_xp );
403    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
404
405    // get current item pointers
406    current_index    = hal_remote_lw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) ); 
407    current_xlist_xp = hal_remote_lwd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) ); 
408
409    // get pointer on "item_from_xlist" function
410    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
411                                                           &xhtab_ptr->item_from_xlist ) );
412    //loop on subsets
413    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
414    {
415        // get root of subset
416        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
417
418        // get next item
419        if( index == current_index ) xlist_xp = xlist_next( root_xp , current_xlist_xp );
420        else                         xlist_xp = xlist_next( root_xp , root_xp );
421
422        if( xlist_xp != XPTR_NULL )  // next item found
423        {
424            // get extended pointer on item containing the xlist entry
425                item_xp = item_from_xlist( xlist_xp );
426
427            // register item in hash table header
428            hal_remote_sw ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
429            hal_remote_swd( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
430
431            return item_xp;
432        }
433    }
434           
435    // item not found
436    return XPTR_NULL;
437
438} // end xhtab_get_next()
439
440/////////////////////////////////////
441void xhtab_display( xptr_t xhtab_xp )
442{
443    uint32_t            index;
444    cxy_t               xhtab_cxy;
445    xhtab_t           * xhtab_ptr;
446    xptr_t              root_xp;
447    xptr_t              iter_xp;
448    xptr_t              item_xp;
449    item_from_xlist_t * item_from_xlist;   // function pointer
450    item_print_key_t  * item_print_key;    // function pointer
451
452    // get xhtab cluster and local pointer
453    xhtab_cxy = GET_CXY( xhtab_xp );
454    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
455
456    // get pointer on "item_from_xlist" function
457    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
458                                                           &xhtab_ptr->item_from_xlist ) );
459    // get pointer on "item_print_key" function
460    item_print_key = (item_print_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
461                                                         &xhtab_ptr->item_print_key ) );
462    //loop on subsets
463    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
464    {
465        printk(" index = %d : ", index );
466
467        // get root of subset
468        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
469
470        // loop on xlist
471        XLIST_FOREACH( root_xp , iter_xp )
472        {
473            // get item from xlist
474            item_xp = item_from_xlist( iter_xp );
475           
476            // print item identifier
477            item_print_key( item_xp );
478        }
479
480        printk("\n");
481    }
482}  // end xhtab_display()
Note: See TracBrowser for help on using the repository browser.