Index: trunk/kernel/libk/htab.c
===================================================================
--- trunk/kernel/libk/htab.c	(revision 1)
+++ trunk/kernel/libk/htab.c	(revision 23)
@@ -2,7 +2,5 @@
  * htable.c - Generic, embedded hash table implementation.
  * 
- * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
- *            Mohamed Lamine Karaoui (2015)
- *            Alain Greiner (2016)
+ * Author      Alain Greiner (2016,2017)
  *
  * Copyright (c) UPMC Sorbonne Universites
@@ -10,9 +8,9 @@
  * This file is part of ALMOS-MKH.
  *
- * ALMOS-MKH.is free software; you can redistribute it and/or modify it
+ * ALMOS-MKH is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by
  * the Free Software Foundation; version 2.0 of the License.
  *
- * ALMOS-MKH.is distributed in the hope that it will be useful, but
+ * ALMOS-MKH is distributed in the hope that it will be useful, but
  * WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -20,115 +18,187 @@
  *
  * You should have received a copy of the GNU General Public License
- * along with ALMOS-MKH.; if not, write to the Free Software Foundation,
+ * along with ALMOS-MKH; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  */
 
-#include <htable.h>
-#include <kmem.h>
-#include <ppm.h>
-
-///////////////////////////////////////////////
-error_t ht_header_init( ht_header_t  * header,
-                        ht_hash_t    * hash,
-                        ht_compare_t * compare )
+#include <kernel_config.h>
+#include <hal_types.h>
+#include <hal_special.h>
+#include <htab.h>
+#include <rwlock.h>
+#include <list.h>
+#include <printk.h>
+#include <vfs.h>
+
+///////////////////////////////////////////////////////////////////////////////////////////
+//    Item type specific (static) functions (two functions for each item type).
+// Example below if for <vhs_inode_t>, where the identifier is the inum field. 
+///////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////
+// These static functions compute the hash index from the key.
+///////////////////////////////////////////////////////////////////////////////////////////
+// @ key      : local pointer on key.
+// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
+///////////////////////////////////////////////////////////////////////////////////////////
+
+static uint32_t htab_inode_index( void * key )
+{
+	uint32_t * inum = key;
+	return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////
+// These static functions are used by htab_lookup(), htab_insert(), and htab_remove().
+// They scan one sub-list identified by  <index> to find an item  identified by <key>.
+// The sub-list is not modified, but the lock must have been taken by the caller.
+///////////////////////////////////////////////////////////////////////////////////////
+// @ htab    : pointer on hash table.
+// @ index   : index of sub-list to be scanned.
+// @ key     : pointer on item identifier.
+// @ return pointer on item if found / return NULL if not found.
+///////////////////////////////////////////////////////////////////////////////////////
+
+static void * htab_inode_scan( htab_t  * htab,
+                               uint32_t  index,
+                               void    * key )
+{
+    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
+    vfs_inode_t  * inode;        // pointer on item
+    
+	LIST_FOREACH( &htab->roots[index] , list_entry )
+	{
+        inode = (vfs_inode_t *)LIST_ELEMENT( list_entry , vfs_inode_t , list );
+        if( inode->inum == *(uint32_t *)key ) return inode; 
+    }
+
+    // no matching item found
+	return NULL;
+}
+
+////////////////////////////////////////////////////////////////////////////////////////
+//         Generic access functions
+////////////////////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////
+void htab_init( htab_t           * htab,
+                htab_item_type_t   type )
 {
 	uint32_t     i;
-	kmem_req_t   req;
-	page_t     * page;
-
-	req.type  = KMEM_PAGE;
-	req.size  = 0;
-	req.flags = AF_ZERO;
-	page      = kmem_alloc( &req );
-	
-	if( page == NULL ) return ENOMEM;
-
-	header->nb_buckets = CONFIG_PPM_PAGE_SIZE/sizeof( list_entry_t );
-	header->buckets    = ppm_page2base( page );
-	header->hash       = hash;
-	header->compare    = compare;
-
-	for( i=0 ; i < header->nb_buckets ; i++ )
-	{
-		list_root_init( &header->buckets[i] );
-	}
-
-	return 0;
-}
-
-////////////////////////////////////////
-error_t ht_node_init( ht_node_t * node )
-{
-	node->index = (uint32_t) -1;
-	list_entry_init( &node->list );
-
-	return 0;
-}
-
-/////////////////////////////////////////////////
-static ht_node_t * __hfind( ht_header_t * header,
-                            uint32_t      index,
-                            void        * key)
-{
-	ht_node_t    * node;
-	list_entry_t * root,
-    list_entry_t * iter;
-
-	root = &header->buckets[index % header->nb_buckets];
-
-	LIST_FOREACH( root , iter )
-	{
-		node = LIST_ELEMENT( iter , ht_node_t , list );
-		if( node->index == index )
-		{
-			if( header->compare( node , key ) ) return node;
-		}
-	}
-
-	return NULL;
-}
-
-//////////////////////////////////////////
-ht_node_t * ht_find( ht_header_t * header,
-                     void        * key )
-{
-	uint32_t index = header->hash( key );
-
-	return __ht_find( header , index , key );
-}
-
-////////////////////////////////////////
-error_t ht_insert( ht_header_t * header,
-                   ht_node_t   * node,
-                   void        * key )
-{
-	uint32_t index = header->hash( key );
-
-	ht_node_t * node = __ht_find( header , index , key );
-
-	if( node != NULL ) return EINVAL;
-
-	list_entry_t * root = &header->buckets[index % header->nb_buckets];
-
-	list_add_first( root , &node->list);
-
-	node->index = index;
-
-	return 0;
-}
-
-////////////////////////////////////////
-error_t ht_remove( ht_header_t * header,
-                   void        * key )
-{
-	uint32_t index = header->hash( key );
-
-	ht_node_t * node = __ht_find( header , index , key );
-
-	if( node == NULL ) return EINVAL;
-
-	list_unlink( &node->list );
-
-	return 0;
-}
-
+
+    // initialize readlock
+    rwlock_init( &htab->lock );
+
+    htab->items = 0;
+
+    if( type == HTAB_INODE_TYPE )
+    {
+        htab->scan    = &htab_inode_scan;
+        htab->index   = &htab_inode_index;
+    }
+    else
+    {
+        printk("\n[PANIC] in %s : undefined item type\n", __FUNCTION__ );
+        hal_core_sleep();
+    }
+
+    // initialize partial lists
+    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
+    {
+        list_root_init( &htab->roots[i] );
+    }
+}
+
+/////////////////////////////////////////
+error_t htab_insert( htab_t       * htab, 
+                     void         * key,
+                     list_entry_t * list_entry )
+{
+    // compute index from key
+    uint32_t index = htab->index( key );
+
+    // take the lock in write mode
+    rwlock_wr_lock( &htab->lock );
+
+    // scan sub-list to check if item exist
+    void * item = htab->scan( htab , index , key );
+
+    if( item != NULL ) // item exist => return error
+    {
+        // release lock
+        rwlock_wr_unlock( &htab->lock );
+
+        return -1;
+    }
+    else               // item doesn't exist => register
+    {
+        // register item in hash table
+        list_add_last( &htab->roots[index] , list_entry );
+
+        // update items number
+        htab->items++;
+
+        // release lock
+        rwlock_wr_unlock( &htab->lock );
+
+        return 0;
+    }
+}
+
+/////////////////////////////////////////
+error_t htab_remove( htab_t       * htab, 
+                     void         * key,
+                     list_entry_t * list_entry )
+{
+    // compute index from key
+    uint32_t index = htab->index( key );
+
+    // take the lock in write mode
+    rwlock_wr_lock( &htab->lock );
+
+    // scan sub-list to chek if item exist
+    void * item = htab->scan( htab , index , key );
+
+    if( item == NULL ) // item doesn't exist
+    {
+        // release lock
+        rwlock_wr_unlock( &htab->lock );
+
+        return -1;
+    }
+    else               // item exist => remove it 
+    {
+        // remove item from hash table
+        list_unlink( list_entry );
+
+        // update items number
+        htab->items--;
+
+        // release lock
+        rwlock_wr_unlock( &htab->lock );
+
+        return 0;
+    }
+}
+
+//////////////////////////////////
+void * htab_lookup( htab_t * htab, 
+                    void   * key )
+{
+    // compute index from key
+    uint32_t index = htab->index( key );
+
+    // take the lock in read mode
+    rwlock_rd_lock( &htab->lock );
+
+    // scan sub-list
+    void * item = htab->scan( htab , index , key );
+
+    // release lock 
+    rwlock_rd_unlock( &htab->lock );
+
+	return item;
+}
+
+
+
