Changeset 0ca7286 in mainline for uspace/srv/fs/tmpfs/tmpfs_ops.c

Timestamp:

2012-07-21T11:19:27Z (12 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/fs/tmpfs/tmpfs_ops.c (modified) (5 diffs)

uspace/srv/fs/tmpfs/tmpfs_ops.c

@@ -56 +56 @@
 #define max(a, b)               ((a) > (b) ? (a) : (b))
 
-#define NODES_BUCKETS   256
-
 /** All root nodes have index 0. */
 #define TMPFS_SOME_ROOT         0
@@ -146 +144 @@
 
 /* Implementation of hash table interface for the nodes hash table. */
-static hash_index_t nodes_hash(unsigned long key[])
-{
-        return key[NODES_KEY_INDEX] % NODES_BUCKETS;
-}
-
-static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static size_t nodes_key_hash(unsigned long key[])
+{
+        /* Based on Effective Java, 2nd Edition. */
+        size_t hash = 17;
+        hash = 37 * hash + key[NODES_KEY_DEV];
+        hash = 37 * hash + key[NODES_KEY_INDEX];
+        return hash;
+}
+
+static size_t nodes_hash(const link_t *item)
+{
+        tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, nh_link);
+        
+        unsigned long key[] = {
+                [NODES_KEY_DEV] = nodep->service_id,
+                [NODES_KEY_INDEX] = nodep->index
+        };
+        
+        return nodes_key_hash(key);
+}
+
+static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
 {
         tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
@@ -192 +206 @@
 
 /** TMPFS nodes hash table operations. */
-hash_table_operations_t nodes_ops = {
+hash_table_ops_t nodes_ops = {
         .hash = nodes_hash,
-        .compare = nodes_compare,
+        .key_hash = nodes_key_hash,
+        .match = nodes_match,
+        .equal = 0,
         .remove_callback = nodes_remove_callback
 };
@@ -220 +236 @@
 bool tmpfs_init(void)
 {
-        if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
+        if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
                 return false;
         
@@ -331 +347 @@
 
         /* Insert the new node into the nodes hash table. */
-        unsigned long key[] = {
-                [NODES_KEY_DEV] = nodep->service_id,
-                [NODES_KEY_INDEX] = nodep->index
-        };
-        hash_table_insert(&nodes, key, &nodep->nh_link);
+        hash_table_insert(&nodes, &nodep->nh_link);
         *rfn = FS_NODE(nodep);
         return EOK;