Changeset 0ca7286 in mainline for uspace/srv/fs/ext2fs/ext2fs_ops.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/fs/ext2fs/ext2fs_ops.c (modified) (5 diffs)

uspace/srv/fs/ext2fs/ext2fs_ops.c

@@ -65 +65 @@
 #define OPEN_NODES_DEV_HANDLE_KEY 0
 #define OPEN_NODES_INODE_KEY 1
-#define OPEN_NODES_BUCKETS 256
 
 typedef struct ext2fs_instance {
@@ -123 +122 @@
 
 /* Hash table interface for open nodes hash table */
-static hash_index_t open_nodes_hash(unsigned long key[])
-{
-        /* TODO: This is very simple and probably can be improved */
-        return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
-}
-
-static int open_nodes_compare(unsigned long key[], hash_count_t keys, 
-    link_t *item)
+static size_t open_nodes_key_hash(unsigned long key[])
+{
+        /* Hash construction recommended in Effective Java, 2nd Edition. */
+        size_t hash = 17;
+        hash = 31 * hash + key[OPEN_NODES_DEV_HANDLE_KEY];
+        hash = 31 * hash + key[OPEN_NODES_INODE_KEY];
+        return hash;
+}
+
+static size_t open_nodes_hash(const link_t *item)
+{
+        ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
+
+        assert(enode->instance);
+        assert(enode->inode_ref);
+        
+        unsigned long key[] = {
+                [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
+                [OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
+        };
+        
+        return open_nodes_key_hash(key);
+}
+
+static bool open_nodes_match(unsigned long key[], size_t keys, 
+    const link_t *item)
 {
         ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
@@ -145 +162 @@
 }
 
-static void open_nodes_remove_cb(link_t *link)
-{
-        /* We don't use remove callback for this hash table */
-}
-
-static hash_table_operations_t open_nodes_ops = {
+static hash_table_ops_t open_nodes_ops = {
         .hash = open_nodes_hash,
-        .compare = open_nodes_compare,
-        .remove_callback = open_nodes_remove_cb,
+        .key_hash = open_nodes_key_hash,
+        .match = open_nodes_match,
+        .equal = 0,
+        .remove_callback = 0,
 };
 
@@ -161 +175 @@
 int ext2fs_global_init(void)
 {
-        if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
-            OPEN_NODES_KEYS, &open_nodes_ops)) {
+        if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
                 return ENOMEM;
         }
@@ -362 +375 @@
         *rfn = node;
         
-        hash_table_insert(&open_nodes, key, &enode->link);
+        hash_table_insert(&open_nodes, &enode->link);
         inst->open_nodes_count++;