Changeset 0ca7286 in mainline for uspace/srv/vfs/vfs_node.c

Timestamp:

2012-07-21T11:19:27Z (13 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

2732c94

Parents:

1c1da4b

Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

File:

• uspace/srv/vfs/vfs_node.c (modified) (7 diffs)

uspace/srv/vfs/vfs_node.c

@@ -58 +58 @@
 #define KEY_INDEX       2
 
-static hash_index_t nodes_hash(unsigned long []);
-static int nodes_compare(unsigned long [], hash_count_t, link_t *);
-static void nodes_remove_callback(link_t *);
+static size_t nodes_key_hash(unsigned long []);
+static size_t nodes_hash(const link_t *);
+static bool nodes_match(unsigned long [], size_t, const link_t *);
 
 /** VFS node hash table operations. */
-hash_table_operations_t nodes_ops = {
+hash_table_ops_t nodes_ops = {
         .hash = nodes_hash,
-        .compare = nodes_compare,
-        .remove_callback = nodes_remove_callback
+        .key_hash = nodes_key_hash,
+        .match = nodes_match,
+        .equal = 0,
+        .remove_callback = 0,
 };
 
@@ -75 +77 @@
 bool vfs_nodes_init(void)
 {
-        return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops);
+        return hash_table_create(&nodes, 0, 3, &nodes_ops);
 }
 
@@ -207 +209 @@
                 link_initialize(&node->nh_link);
                 fibril_rwlock_initialize(&node->contents_rwlock);
-                hash_table_insert(&nodes, key, &node->nh_link);
+                hash_table_insert(&nodes, &node->nh_link);
         } else {
                 node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
@@ -240 +242 @@
 }
 
-hash_index_t nodes_hash(unsigned long key[])
-{
-        hash_index_t a = key[KEY_FS_HANDLE] << (NODES_BUCKETS_LOG / 4);
-        hash_index_t b = (a | key[KEY_DEV_HANDLE]) << (NODES_BUCKETS_LOG / 2);
-        
-        return (b | key[KEY_INDEX]) & (NODES_BUCKETS - 1);
-}
-
-int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
+size_t nodes_key_hash(unsigned long key[])
+{
+        /* Combine into a hash like they do in Effective Java, 2nd edition. */
+        size_t hash = 17;
+        hash = 37 * hash + key[KEY_FS_HANDLE];
+        hash = 37 * hash + key[KEY_DEV_HANDLE];
+        hash = 37 * hash + key[KEY_INDEX];
+        return hash;
+}
+
+size_t nodes_hash(const link_t *item)
+{
+        vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
+        
+        unsigned long key[] = {
+                [KEY_FS_HANDLE] = node->fs_handle,
+                [KEY_DEV_HANDLE] = node->service_id,
+                [KEY_INDEX] = node->index
+        };
+        
+        return nodes_key_hash(key);
+}
+
+
+bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
 {
         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
@@ -256 +274 @@
 }
 
-void nodes_remove_callback(link_t *item)
-{
-}
 
 struct refcnt_data {
@@ -267 +282 @@
 };
 
-static void refcnt_visitor(link_t *item, void *arg)
+static bool refcnt_visitor(link_t *item, void *arg)
 {
         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
@@ -275 +290 @@
             (node->service_id == rd->service_id))
                 rd->refcnt += node->refcnt;
+        
+        return true;
 }