Index: trunk/kernel/libk/htab.h
===================================================================
--- trunk/kernel/libk/htab.h	(revision 690)
+++ trunk/kernel/libk/htab.h	(revision 1)
@@ -2,5 +2,7 @@
  * htab.h - Generic embedded hash table definition.
  * 
- * Authors  Alain Greiner (2016,2017,2018)
+ * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
+ *            Mohamed Lamine Karaoui (2015)
+ *            Alain Greiner (2016)
  *
  * Copyright (c) UPMC Sorbonne Universites
@@ -26,98 +28,89 @@
 #define _HTAB_H_
 
-#include <hal_kernel_types.h>
-#include <rwlock.h>
+#include <hal_types.h>
 #include <list.h>
 
-/////////////////////////////////////////////////////////////////////////////////////////
-// This file define a generic, embedded, local 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 
-//   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.
+ * This define the generic, user defined, function types.
  ***************************************************************************************/
 
-struct htab_s;
+struct ht_node_s;
 
-typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );
-
-typedef uint32_t   htab_index_t( void * key );
+typedef bool_t     ht_compare_t( struct ht_node_s * node , void * key );
+typedef uint32_t   ht_hash_t( void * key );
 
 /****************************************************************************************
- * This define the supported item types.
+ * This structure defines the hash table header.
  ***************************************************************************************/
 
-typedef enum
+typedef struct ht_header_s
 {
-    HTAB_BLOUP_TYPE = 1,                     /*! item is a bloup_t                     */
+	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      */
 }
-htab_item_type_t;
+ht_header_t;
 
 /****************************************************************************************
- * This structure defines the the root of a local hash table.
+ * This structure defines one hash table node.
  ***************************************************************************************/
 
-typedef struct htab_s
+typedef struct ht_node_s
 {
-	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             */
-    busylock_t        lock;                 /*! lock protecting hash table accesses    */
+	uint32_t     index;           /*! integer value computed from the key              */
+	list_entry_t list;	          /*! member of list of all nodes in same bucket       */
 }
-htab_t;
+ht_node_t;
 
 /****************************************************************************************
- * This function initialises an empty hash table (zero registered item).
+ * This function initialises one hash table node.
  ****************************************************************************************
- * @ htab       : pointer on hash table.
- * @ type       : item type.
+ccccc
  ***************************************************************************************/
-void htab_init( htab_t           * htab,
-                htab_item_type_t   type );
+void ht_node_init( ht_node_t * node );
 
 /****************************************************************************************
- * This function register a new item in the hash table.
+ * 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)
  ****************************************************************************************
- * @ 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.
+ * @ 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.
  ***************************************************************************************/
-error_t htab_insert( htab_t       * htab,
-                     void         * key,
-                     list_entry_t * list_entry );
+error_t ht_header_init( ht_header_t  * header,
+                        ht_hash_t    * ht_hash,
+                        ht_compare_t * ht_compare );
 
 /****************************************************************************************
- * This function remove an item from the hash table.
+ * This function register a new node in the hash table.
  ****************************************************************************************
- * @ header     : pointer on 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.
- * @ list_entry : pointer on list_entry_t embedded in item to be removed.
- * @ return 0 if success / return EINVAL if item not found.
+ * @ return 0 if success / return EINVAL if node already registered...
  ***************************************************************************************/
-error_t htab_remove( htab_t       * htab,
-                     void         * key,
-                     list_entry_t * list_entry );
+error_t ht_insert( ht_header_t * header,
+                   ht_node_t   * node,
+                   void        * key );
 
 /****************************************************************************************
@@ -125,11 +118,20 @@
  * identified by its key.
  ****************************************************************************************
- * @ htab      : pointer on the hash table.
- * @ key       : pointer on the item identifier.
- * @ return pointer on item if found / return NULL if not found.
+ * @ header     : pointer on the hash table header.
+ * @ key        : pointer on the item identifier.
+ * @ return pointer on node if found / return NULL if not found.
  ***************************************************************************************/
-void * htab_lookup( htab_t * htab,
-                    void   * key);
+ht_node_t * ht_find( ht_header_t * header,
+                     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 /* _HTAB_H_ */
+#endif /* _HTABLE_H_ */
