Changeset 0ca7286 in mainline for uspace/lib/block/libblock.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/lib/block/libblock.c (modified) (5 diffs)

uspace/lib/block/libblock.c

@@ -62 +62 @@
 static LIST_INITIALIZE(dcl);
 
-#define CACHE_BUCKETS_LOG2  10
-#define CACHE_BUCKETS       (1 << CACHE_BUCKETS_LOG2)
 
 typedef struct {
@@ -256 +254 @@
 }
 
-static hash_index_t cache_hash(unsigned long *key)
-{
-        return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1);
-}
-
-static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item)
+static size_t cache_key_hash(unsigned long *key)
+{
+        /* As recommended by Effective Java, 2nd Edition. */
+        size_t hash = 17;
+        hash = 31 * hash + key[1];
+        hash = 31 * hash + key[0];
+        return hash;
+}
+
+static size_t cache_hash(const link_t *item)
+{
+        block_t *b = hash_table_get_instance(item, block_t, hash_link);
+        unsigned long key[] = {
+                LOWER32(b->lba),
+                UPPER32(b->lba)
+        };
+        
+        return cache_key_hash(key);
+}
+
+static bool cache_match(unsigned long *key, size_t keys, const link_t *item)
 {
         block_t *b = hash_table_get_instance(item, block_t, hash_link);
@@ -267 +280 @@
 }
 
-static void cache_remove_callback(link_t *item)
-{
-}
-
-static hash_table_operations_t cache_ops = {
+
+static hash_table_ops_t cache_ops = {
         .hash = cache_hash,
-        .compare = cache_compare,
-        .remove_callback = cache_remove_callback
+        .key_hash = cache_key_hash,
+        .match = cache_match,
+        .equal = 0,
+        .remove_callback = 0
 };
 
@@ -305 +317 @@
         cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
 
-        if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2,
-            &cache_ops)) {
+        if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) {
                 free(cache);
                 return ENOMEM;
@@ -540 +551 @@
                 b->lba = ba;
                 b->pba = ba_ltop(devcon, b->lba);
-                hash_table_insert(&cache->block_hash, key, &b->hash_link);
+                hash_table_insert(&cache->block_hash, &b->hash_link);
 
                 /*