Changeset 0ca7286 in mainline for uspace/lib/c/generic/async.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/c/generic/async.c (modified) (10 diffs)

uspace/lib/c/generic/async.c

@@ -115 +115 @@
 #include <macros.h>
 
-#define CLIENT_HASH_TABLE_BUCKETS  32
-#define CONN_HASH_TABLE_BUCKETS    32
 
 /** Session data */
@@ -392 +390 @@
 static LIST_INITIALIZE(timeout_list);
 
-static hash_index_t client_hash(unsigned long key[])
+static size_t client_key_hash(unsigned long key[])
 {
         assert(key);
-        
-        return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS);
-}
-
-static int client_compare(unsigned long key[], hash_count_t keys, link_t *item)
+        /* LOWER32(in_task_id) */
+        return key[0] >> 4;
+}
+
+static size_t client_hash(const link_t *item)
+{
+        client_t *client = hash_table_get_instance(item, client_t, link);
+        
+        unsigned long key[2] = {
+                LOWER32(client->in_task_id),
+                UPPER32(client->in_task_id),
+        };
+
+        return client_key_hash(key);
+}
+
+static bool client_match(unsigned long key[], size_t keys, const link_t *item)
 {
         assert(key);
@@ -410 +420 @@
 }
 
-static void client_remove(link_t *item)
-{
-}
 
 /** Operations for the client hash table. */
-static hash_table_operations_t client_hash_table_ops = {
+static hash_table_ops_t client_hash_table_ops = {
         .hash = client_hash,
-        .compare = client_compare,
-        .remove_callback = client_remove
+        .key_hash = client_key_hash,
+        .match = client_match,
+        .equal = 0,
+        .remove_callback = 0
 };
 
@@ -428 +437 @@
  *
  */
-static hash_index_t conn_hash(unsigned long key[])
+static size_t conn_key_hash(unsigned long key[])
 {
         assert(key);
-        
-        return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS);
+        return key[0] >> 4;
+}
+
+static size_t conn_hash(const link_t *item)
+{
+        connection_t *conn = hash_table_get_instance(item, connection_t, link);
+        unsigned long key = conn->in_phone_hash;
+        return conn_key_hash(&key);
 }
 
@@ -444 +459 @@
  *
  */
-static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool conn_match(unsigned long key[], size_t keys, const link_t *item)
 {
         assert(key);
@@ -453 +468 @@
 }
 
+static bool conn_equal(const link_t *item1, const link_t *item2)
+{
+        connection_t *c1 = hash_table_get_instance(item1, connection_t, link);
+        connection_t *c2 = hash_table_get_instance(item2, connection_t, link);
+        
+        return c1->in_phone_hash == c2->in_phone_hash;
+}
+
 static void conn_remove(link_t *item)
 {
@@ -458 +481 @@
 
 /** Operations for the connection hash table. */
-static hash_table_operations_t conn_hash_table_ops = {
+static hash_table_ops_t conn_hash_table_ops = {
         .hash = conn_hash,
-        .compare = conn_compare,
+        .key_hash = conn_key_hash,
+        .match = conn_match,
+        .equal = conn_equal,
         .remove_callback = conn_remove
 };
@@ -715 +740 @@
                 
                         atomic_set(&client->refcnt, 1);
-                        hash_table_insert(&client_hash_table, key, &client->link);
+                        hash_table_insert(&client_hash_table, &client->link);
                 }
         }
@@ -915 +940 @@
         
         /* Add connection to the connection hash table */
-        unsigned long key = conn->in_phone_hash;
         
         futex_down(&async_futex);
-        hash_table_insert(&conn_hash_table, &key, &conn->link);
+        hash_table_insert(&conn_hash_table, &conn->link);
         futex_up(&async_futex);
         
@@ -1110 +1134 @@
 void __async_init(void)
 {
-        if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS,
-            2, &client_hash_table_ops))
+        if (!hash_table_create(&client_hash_table, 0, 2, &client_hash_table_ops))
                 abort();
         
-        if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS,
-            1, &conn_hash_table_ops))
+        if (!hash_table_create(&conn_hash_table, 0, 1, &conn_hash_table_ops))
                 abort();