Index: trunk/kernel/libk/htab.h
===================================================================
--- trunk/kernel/libk/htab.h	(revision 1)
+++ trunk/kernel/libk/htab.h	(revision 23)
@@ -2,7 +2,5 @@
  * htab.h - Generic embedded hash table definition.
  * 
- * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
- *            Mohamed Lamine Karaoui (2015)
- *            Alain Greiner (2016)
+ * Authors  Alain Greiner (2016,2017)
  *
  * Copyright (c) UPMC Sorbonne Universites
@@ -29,88 +27,97 @@
 
 #include <hal_types.h>
+#include <rwlock.h>
 #include <list.h>
 
+/////////////////////////////////////////////////////////////////////////////////////////
+// This file define a generic, embedded, hash table.
+//
+// It can only be accessed by threads running in the local cluster.
+// It is generic as it can be used to register various types of items.
+// The main goal is to provide fast retrieval for a large number of items of same type.
+// For this purpose the set of all registered items is split in several subsets. 
+// Each subset is organised as a double linked lists.
+// - an item is uniquely identified by a <key>, that can be a single uint32_t, 
+//   a character string, or a more complex structure.
+// - From the pointer on <key>, we use an item type specific htab_index() function,
+//   to compute an <index> value, defining a subset of registered items.
+// - As several items can have the same <index>, we use the item type specific defined
+//   htab_scan() function for a final associative search on the subset.
+// - Each registered item is a structure, that must contain an embedded list_entry_t,
+//   that is part of a rooted double linked list.
+//
+// Implementation Note: for each supported item type ***, you must define the two
+//                      htab_***_index() and htab_***_scan() functions, and
+//                      update the htab_init() function.
+/////////////////////////////////////////////////////////////////////////////////////////
+
+#define HASHTAB_SIZE    64   // number of subsets
+
 /****************************************************************************************
- * This file define a generic, embedded, hash table.
- * The main goal is to provide fast retrieval for a large number of items of same type
- * in a given cluster. For this purpose the set of all registered items is split
- * in several subsets. Each subset is organised as a double linked lists.
- * - an item is uniquely identified by a <key>, that can be a single uint32_t, 
- *   a character string, or a more complex structure.
- * - From the pointer on the <key>, the hash table uses an user defined ht_hash() 
- *   function, to compute an <index> value, defining a subset of registered
- *   items, to restrict the associative search.
- * - As several items can have the same <index>, the hash table uses the user defined
- *   ht_compare() function for a final associative search on the subset.
- * - Each registered item is a structure, that must contain an embedded ht_node_t,
- *   This ht_node_t is part of a rooted double linked list, and contains the <index>.
- * - Finally, the hash table returns a pointer on the embedded ht_node_t, and the
- *   pointer on the searched item can be obtained by a simple offset.
+ * These typedef define the two item type specific function prototypes.
  ***************************************************************************************/
 
+struct htab_s;
+
+typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );
+
+typedef uint32_t   htab_index_t( void * key );
+
 /****************************************************************************************
- * This define the generic, user defined, function types.
+ * This define the supported item types.
  ***************************************************************************************/
 
-struct ht_node_s;
-
-typedef bool_t     ht_compare_t( struct ht_node_s * node , void * key );
-typedef uint32_t   ht_hash_t( void * key );
+typedef enum
+{
+    HTAB_INODE_TYPE = 1,                     /*! item is a vfs_inode_t                 */
+}
+htab_item_type_t;
 
 /****************************************************************************************
- * This structure defines the hash table header.
+ * This structure defines the the root of a local hash table.
  ***************************************************************************************/
 
-typedef struct ht_header_s
+typedef struct htab_s
 {
-	uint32_t        nb_buckets;   /*! number of subsets (one linked list per subset)   */
-	ht_hash_t     * hash;         /*! user defined hash function                       */ 
-	ht_compare_t  * compare;      /*! user defined compare function                    */
-	list_entry_t  * buckets;      /*! array of root of partial lists of ht_node_t      */
+	list_entry_t      roots[HASHTAB_SIZE];  /*! array of roots of partial lists        */
+	htab_index_t    * index;                /*! item type  specific function           */
+	htab_scan_t     * scan;                 /*! item type specific function            */
+    uint32_t          items;                /*! number of registered items             */
+    rwlock_t          lock;                 /*! lock protecting hash table accesses    */
 }
-ht_header_t;
+htab_t;
 
 /****************************************************************************************
- * This structure defines one hash table node.
+ * This function initialises an empty hash table (zero registered item).
+ ****************************************************************************************
+ * @ htab       : pointer on hash table.
+ * @ type       : item type.
  ***************************************************************************************/
-
-typedef struct ht_node_s
-{
-	uint32_t     index;           /*! integer value computed from the key              */
-	list_entry_t list;	          /*! member of list of all nodes in same bucket       */
-}
-ht_node_t;
+void htab_init( htab_t           * htab,
+                htab_item_type_t   type );
 
 /****************************************************************************************
- * This function initialises one hash table node.
+ * This function register a new item in the hash table.
  ****************************************************************************************
-ccccc
+ * @ htab       : pointer on the hash table.
+ * @ key        : pointer on the item identifier.
+ * @ list_entry : pointer on list_entry_t embedded in item to be registered.
+ * @ return 0 if success / return EINVAL if item already registered.
  ***************************************************************************************/
-void ht_node_init( ht_node_t * node );
+error_t htab_insert( htab_t       * htab,
+                     void         * key,
+                     list_entry_t * list_entry );
 
 /****************************************************************************************
- * This function allocates memory for the buckets array, and initializes the header.
- * The number of buckets (number of subsets) is PAGE_SIZE / sizeof(list_entry_t)
+ * This function remove an item from the hash table.
  ****************************************************************************************
- * @ header     : pointer on the hash table header.
- * @ ht_hash    : pointer on the user defined hash function.
- * @ ht_compare : pointer on the user defined compare function.
- * @ return 0 if success / return ENOMEM if error.
+ * @ header     : pointer on the hash table.
+ * @ key        : pointer on the item identifier.
+ * @ list_entry : pointer on list_entry_t embedded in item to be removed.
+ * @ return 0 if success / return EINVAL if item not found.
  ***************************************************************************************/
-error_t ht_header_init( ht_header_t  * header,
-                        ht_hash_t    * ht_hash,
-                        ht_compare_t * ht_compare );
-
-/****************************************************************************************
- * This function register a new node in the hash table.
- ****************************************************************************************
- * @ header     : pointer on the hash table header.
- * @ node       : pointer on the node to be registered (embedded in item).
- * @ key        : pointer on the item identifier.
- * @ return 0 if success / return EINVAL if node already registered...
- ***************************************************************************************/
-error_t ht_insert( ht_header_t * header,
-                   ht_node_t   * node,
-                   void        * key );
+error_t htab_remove( htab_t       * htab,
+                     void         * key,
+                     list_entry_t * list_entry );
 
 /****************************************************************************************
@@ -118,20 +125,11 @@
  * identified by its key.
  ****************************************************************************************
- * @ header     : pointer on the hash table header.
- * @ key        : pointer on the item identifier.
- * @ return pointer on node if found / return NULL if not found.
+ * @ htab      : pointer on the hash table.
+ * @ key       : pointer on the item identifier.
+ * @ return pointer on item if found / return NULL if not found.
  ***************************************************************************************/
-ht_node_t * ht_find( ht_header_t * header,
-                     void        * key);
+void * htab_lookup( htab_t * htab,
+                    void   * key);
 
-/****************************************************************************************
- * This function remove an item from the hash table.
- ****************************************************************************************
- * @ header     : pointer on the hash table header.
- * @ key        : pointer on the item identifier.
- * @ return 0 if success / return EINVAL if not found.
- ***************************************************************************************/
-error_t ht_remove( ht_header_t * header,
-                   void        * key );
 
-#endif /* _HTABLE_H_ */
+#endif /* _HTAB_H_ */
